混合流水车间调度的自适应遗传算法求解
⇨⇦
【摘 要】针对以最小化总流程时间为目标的混合流水车间调度问题，考虑到工业生产中并行机的异构或新旧程度等使得同一工序在不同工位的加工时间的不同，假设每个生产阶段的并行机为不相关并行机，结合遗传参数自适应动态调整机制，提出了一种自适应遗传算法。基于不同规模问题的仿真实验说明了所提出算法的有效性。
【关键词】混合流水车间;不相关并行机;总流程时间;自适应遗传算法
1.引言
混合流水车间调度问题（hybrid flow shop scheduling problem， HFSSP）在流程工业较为常见，如钢铁业、化工业等。按并行机的特点，可将HFSSP分为同构并行机、均匀并行机、不相关并行机调度问题[1]。由于两阶段HFSSP即使只有一个阶段有多台机器也是NP-hard的，因此求解HFSSP的方法多为近似算法。
在相同并行机环境下，关于HFSSP的近似算法多追求最小化最大完工时间，如韩忠华等[2]提出了改进帝国竞争算法;任彩乐等[3]设计了基于两阶段解码方法的候鸟优化算法;吴秀丽和崔琪[4]考虑可再生能源提出集成低碳调度策略的快速非支配遗传算法以同时最小化最大完工时间和碳排放量。
在不相关并行机环境下，吴楚格等[5]提出了解决并行机调度的基于信息熵的自适应分布估计算法，目标是最小化最大完工时间。针对HFSSP，为最小化最大完工时间，孟磊磊等[1]考虑了阻塞限制，提出了一种改进的回溯搜索算法;宋存利[6]提出了改进贪婪遗传算法;王芳等[7]结合自适应调整模型设计了高效分布估算算法求解大规模调度问题;杜利珍等[8]提出了果蠅优化算法。
从上述研究现状可发现，对于含不相关并行机的HFSSP的研究多为最大完工时间问题，缺乏对其它目标问题的探讨。因此，为减少在制品库存，本文以总流程时间为目标函数，设计结合遗传参数自适应动态调整机制的遗传算法，以有效求解该问题。
2.问题描述
本文所研究的混合流水车间调度问题可描述如下：J个工件经O道工序进行加工，每道工序i可由UPi台不相关并行工位的任一个来完成，工件j在工序i中不同工位上的加工时间不同。
令bji、pji、fji分别表示工件j在工序i的开工时间、加工时间和完工时间;令Xjik为0-1变量，当工件j在工序i选择工位k（k=1，2，...，UPi）加工时，其值为1，否则为0。则工件开工和完工时间之间有：fji=bji+∑kXjikpjik。为减少在制品库存，所研究的HFSSP旨在追求总流程时间最小化，即确定工件在每道工序的工位分配以及同一工位上工件的加工序列以使所有工件的完工时间之和最小。因此，HFSSP的调度目标可表示为：
需满足的约束条件有：
（1）所有工件在零时刻均可用于加工。
（2）工件j在工序i可选择任一台工位进行加工。选择的工位不同，则它的加工时间也会不同。
（3）每个工位一次至多加工一个工件，而每个工件一次只能在一台工位进行加工。
（4）同一时刻正在加工的工件数不能超过该工序的工位数。
（5）相邻工位间的运输时间忽略不计。
（6）相邻工序间有无限缓冲区。
3.自适应遗传算法设计
遗传算法（genetic algorithm， GA）利用染色体进化实现种群的迭代，最终找到所求问题的近优解。为改进遗传算法解，本文在执行GA的过程中设计了随迭代进程而变化的计遗传参数算公式，具体求解步骤如下：
（1）参数初始化。对种群规模、最大迭代数MG、当前迭代cg等进行初始化。
（2）初始种群生成。利用二维矩阵编码机制随机生成染色体矩阵，矩阵的每一行对应于一个工件在各工位的分配，即每个元素代表了对应工件在一道工序所分配的工位号，每一列则为各工件在同一工序的工位号。进而，计算每个个体的适应度值。
（3）选择操作。应用轮盘赌规则从当前种群筛选出进入交叉和变异的染色体。适应度值越大的染色体被选中的概率越大。
（4）自适应遗传参数设计。当个体适应度值Fz超过平均适应度值Favg时，计算当前最大适应度值Fmax与Favg的差值△F，交叉概率PC通过PC=PCmax-（PCmax-PCmin）/（cg/MG+Fz/△F）来获取，变异概率PM通过PM= PMmin-（PMmax-PMmin）/（cg/MG+Fz/△F）计算得到。否则，令PC=PCmax，PM= PMmin。
（5）交叉操作。设计基于工件和基于工位的两种单点倒置交叉方式。前者操作中，随机选择两个父代染色体A和B，将A（B）的前a行和B（A）的后J-a行基因进行交叉组合生成子代染色体。后者操作中，随机选择一个工位号c，将染色体A（B）的前c列基因与染色体B（A）的后O-c列基因组合，从而形成新的染色体。根据交叉概率选择上述交叉方式，得到新染色体。
（6）变异操作。应用单点变异方式，随机选择一个基因，将其重新产生，从而产生新个体。
（7）终止条件检验。当算法达到最大迭代数或运行时间达到限制时，程序停止。
4.仿真实验
为了验证算法的有效性，对于不同规模的问题，利用自适应遗传算法进行仿真实验。所有实验均在处理器为AMD A8-4500M，1.9GHz，内存为4.00G的计算机上运行。J、O、UPi分别取值为{30， 40， 60， 70}，{3， 4， 5}，{4， 5}，假设每个阶段并行机数相同，J、O、UPi的不同取值共产生了4×3×2=24种组合。考虑到时间成本，将最大运行时间设置为1200s，最大迭代次数设置为100。通过不同的实验测试，将交叉概率和变异概率分别取为0.6和0.3。
利用上述数据运行所提算法，得到实验结果如表1所示。從表1可知，对于不同规模问题，自适应遗传算法在平均923.734秒内得到的平均目标值为5172，即所设计算法可在合理的计算时间内得到满意的近优解。随着问题规模的增加，执行算法所需时间也会有所增长。图1表示四种规模问题下（O=4，UPi=5）的目标值变化趋势，由此可知随着问题规模的增大，算法的收敛效果越好，优势越明显。
5.结论
本文研究了不相关并行机环境下的混合流水车间调度问题，以总流程时间为目标函数提出了自适应遗传算法进行求解。通过对不同规模实例进行仿真实验，结果说明了所提出的算法能够在可接受的计算时间内得到满意的近优解。进一步的研究可探索运输问题与上述调度的协同问题。
【参考文献】
[1]孟磊磊， 张超勇， 任彩乐， 李振国， 任亚平. 求解带有阻塞限制的HFSP的MILP模型与改进回溯搜索算法[J]. 2018， 29（22）： 2647-2658.
[2]韩忠华，孙越，史海波，林硕. 改进帝国竞争算法求解柔性流水车间排产问题[J].控制工程，2017， 24（8）： 1649-1655.
[3]任彩乐， 张超勇， 孟磊磊， 余俊， 洪辉. 基于改进候鸟优化算法的混合流水车间调度问题[J]. 计算机集成制造系统， 2019， 25（3）： 643-653.
[4]吴秀丽， 崔琪. 考虑可再生能源的多目标柔性流水车间调度问题[J]. 计算机集成制造系统， 2018， 24（11）： 2792-2807.
[5]吴楚格， 王凌， 郑晓龙. 求解不相关并行机调度的一种自适应分布估计算法[J]. 控制与决策， 2016， 31（12）： 2177-2182.
[6]宋存利. 求解混合流水车间调度的改进贪婪遗传算法[J]. 系统工程与电子技术， 2019， 41（5）： 1079-1086.
[7]王芳， 唐秋华， 饶运清， 张超勇， 张利平. 求解柔性流水车间调度问题的高效分布估算算法[J]. 自动化学报， 2017， 43（2）： 280-293.
[8]杜利珍， 王震， 柯善富， 熊子雪， 李新宇. 混合流水车间调度问题的果蝇优化算法求解[J]. 中国机械工程， 2019， 30（12）： 1480-1485.