基于离散布谷鸟搜索算法的带阻塞有差速混合流水车间调度

发布时间：2019-11-14 16:53

【摘要】：基于以最小完工时间为目标的带阻塞有差速混合流水车间调度问题,提出了一种改进的离散布谷鸟搜索算法。在基本布谷鸟搜索算法的莱维飞行和巢寄生性的基础结构上,提出了一种基于交叉策略的莱维飞行机制,以便算法能够解决离散问题;同时,通过非余弦递减策略的动态发现概率去发现劣质鸟巢,并利用排列差分进化算法的变异思想将劣质鸟巢重建;在搜索过程中设定全局最优极值保持代数为阈值去重新发现劣质鸟巢,以防止算法陷入局部最优;最后利用邻域搜索方法进一步提高算法的搜索精度。通过仿真实验验证了该算法在求解混合流水车间调度类离散问题上的有效性与优越性。
【图文】：

最大完工时间,存储策略,水车,工序流

合流水车间调度问题，仿真实验验证了改进ＤＣＳ算法求解ＢＵＨＦＳＰ问题的有效性。１问题描述一般的流水车间调度都会假设工序间缓冲区无限大，而本文研究的带阻塞混合流水车间调度问题则假设工序之间不存在缓冲区，即若某工件的某一工序完成该工序操作后，下一工序机器仍处于被占用状态，，则该工件会在该机器上等待，并且阻塞该工序以后工件的加工直至下一个工序机器被释放。针对一般流水调度车间模型，假设某车间要加工６件不同的工件，每个工件要经历３道工序，则不同的工序间存储策略的对比如图１所示。图１不同存储策略的３道工序流水车间最大完工时间的对比Ｆｉｇ．１Ｃｏｍｐａｒｉｓｏｎｏｆｔｈｅｍａｋｅ－ｓｐａｎｏｆ３ｐｒｏｃｅｄｕｒｅｓｗｉｔｈｄｉｆｆｅｒｅｎｔｓｔｏｒａｇｅｓｔｒａｔｅｇｉｅｓ一般对带阻塞有差速混合流水车间调度生产过程作如下假设：（１）所有工件加工工序相同；（２）有并行机存在的工序，工件可以选择任意空闲机器进行加工；４２６

混合流水车间,调度模型,带阻,工序

各工序、各机器上的加工时间已知，并且各工序的并行机加工同一工件的时间可能不同；（７）原料不限，完工工件存储空间不限。根据以上假设，带阻塞有差速的混合流水车间可以描述为：ｎ个待加工的工件要依次经过Ｓ道工序的加工，每道工序至少有一台加工设备并且至少有一道工序存在并行加工设备（设第ｊ道工序的设备数为ｍｊ，ｊ＝１，２，…，Ｓ），要求确定所有工件的加工顺序及其在并行机上的分配情况，以使得最大完工时间（ｍａｋｅｓｐａｎ）最校有差速混合流水车间调度模型如图２所示，其中ｍｉ表示不同工序并行机的数量，矩形的大小表示工件在该机器上加工时间。图２带阻塞有差速混合流水车间调度模型Ｆｉｇ．２ＭｏｄｅｌｏｆＢＵＨＦＳＰ假设工件数为ｎ，机器数为ｍ，工序数为λ，第ｋ道工序的并行机数量为πｋ（ｋ＝１，２，…，λ），Ｔｉ，ｊ表示工件Ｊｉ（ｉ＝１，２，…，ｎ）在机器Ｍｊ（ｊ＝１，２，…，ｍ）上的加工时间，Ｓｉ，ｋ表示工件Ｊｉ在工序ｋ上的开始加工时间，Ｃｉ，ｋ表示工件Ｊｉ在工序ｋ上的完工时间，ｃｍａｘ为最大完工时间，Ｒｊ表示Ｍｊ被释放的时间，可以得出ＢＵＨＦＳＰ的数学模型为ｍｉｎＣｍａｘ（１）ｓ．ｔ．∑πｋ－１ｊ＝１ｘｉ，ｊ，ｋ＝１ｉ＝１，２，…，ｎ；ｋ＝１，２，…，λｘｉ，ｊ，ｋ＝１，Ｊｉ在第ｋ道工序使用第ｊ个机器加工０，｛否则（２）０≤∑ｎ－１ｉ＝１ｙｉ，ｊ，ｔ≤１

【参考文献】