基于改进遗传算法的作业车间调度

王 明，蔡劲草，王 雷

（ 安徽工程大学 机械与汽车工程学院，安徽 芜湖 241000）

0．引言

作业车间调度(Job shop scheduling problem,JSP)是车间调度中最常见的调度类型，是最难的组合优化问题之一，对其研究具有重大的现实意义[1]。科学有效的生产调度不但可以提高生产加工过程中工人、设备资源的高效利用，还可缩短生产周期，降低生产成本[2]。随着遗传算法在组合优化问题的广泛应用，许多人开始对遗传算法进行深度研究。已有研究结果[3-6]表明，遗传算法对求解作业车间调度问题具有较好的效果。然而，由于传统遗传算法存在运行时间过长、易早熟收敛的缺点，许多学者在缩短运行时间、避免早熟收敛、保持种群多样性方面对遗传算法进行了改进研究，且都取得了较好的成果[7]。文献 [8]为了解决柔性作业车间调度问题中权重难以确定导致调度效率低的缺点，提出了一种改进的动态随机搜索遗传算法；张超勇等[9]人利用基于改进非支配排序遗传算法求解多目标柔性作业车间调度问题；文献[10]利用混合遗传禁忌搜索算法对柔性作业车间调度进行了研究。

本文试图利用改进遗传算法解决作业车间调度问题，并以完工时间为目标函数，通过实验结果验证了其有效性和可行性。

1．作业车间调度模型

JSP可简述为有n个工件需要在m台设备上进行加工，每个工件包含m个工序。工件在其被加工过程中需满足：（1）任一时刻的设备只能加工一个工件的某道工序，且每个工件同一时刻只能被一台设备加工；（2）一旦开始加工，工序中途不能被打断；（3）每个工件在同一台设备上最多加工一次；（4）每个工件必须遵守给定的工艺路线约束进行加工；（5）不考虑工件的运输、装夹等辅助时间。

本文以工件的最短完工时间为目标，建立目标函数（1）为：

式(1)中，Cik表示工件i在机器k上的完工时间。

2．改进遗传算法求解作业车间调度问题

2．1．编码与解码

作业车间调度编码的方法很多，但由于基于工序的编码具有编码和解码方案简单、柔性高、容易实现等特点[11]，所以在此选用基于工序的编码与解码。该问题的加工时间和工艺约束如表1所示。

工件J1、J2和J3分别用数字1、2和3表示，假设它的一个染色体表示为[213123312]，其中染色体中的数字即表示工件也表示工序，其中从左到右第n次出现的该数字的次数表示该工件的第n道工序，如数字1在染色体中从左到右出现三次，则第一个数字1表示工件J1的第1道工序，第二个数字1表示工件J1的第2道工序，第三个数字1表示工件J1的第3道工序，其它含义相同。图1所示的是编码及其对应的解码过程。最后得到加工甘特图，如图2所示，总完工时间C=12。

表1 加工时间和工艺约束Tab.1 Processing time and process constraints

图1 基于工序编码的解码方式Fig.1 method of decoding operation-basedcoding

2．2．遗传操作设计

2．2．1．选择

复制的作用是将父代个体的信息传递给子代，而这种传递是有选择的，父代中的每一个染色体，根据其适应度的大小决定它能够被选择复制到子代的几率。通过选择，使得群体中的优秀个体数目逐渐得到增加，整个优化过程朝着更好的方向进化，反映了优胜劣汰的基本原则[12]。根据适应度函数决定第i个父代个体被复制到子代个体数量为：

式（2）中，N是种群的规模；gi是父代中第i个体的适应度值(在此取式(1)的倒数为适应度函数)。所以，个体的适应度值如果越大的话，其被进化到下一代的数目也就会更多。

在选择的过程中，为了使得最优的个体能够顺利地进化到下一代，将每一代中最优前10%的精英个体直接进化到下一代。

图2 解码获得的调度结果Fig.2 Scheduling results obtained by decoding

2．2．2．交叉

为了进一步扩大算法的搜索空间，同时使子代获得比父代更好的解，需要进行交叉操作，产生新的染色体。鉴于本文所采用的基于工序编码方法的特点，使用顺序交叉和单点交叉相结合的方式，其算法步骤如下[13]：

（1）在两个父代个体染色体P1和P2中，随机选择一个基因位i，将1～i之间的基因片段作为交叉区域，并把交叉区域内的基因编码串分别记录到A和B中；

（2）在父代个体P1中，从左向右依次查找B中的所有基因值，将P1中出现在对应位置的基因位删除。同样，在父代个体P2中从左向右依次查找A中的所有基因值，将P2中对应位置的基因位删除；

（3）在两个父代个体P1、P2中，剩下的基因位右移并保持相对位置不变。

（4）将P1交叉区域的内容替换为B的内容，将P2交叉区域的内容替换为A的内容。至此，将分别得到两个子代个体C1和C2。具体的交叉过程如图3所示。

图3 交叉过程Fig 3 Crossprocess

2．2．3．变异

变异方法选择不当则有可能产生无意义的方案。本文利用单个染色体基因段倒置的方式进行变异，这种变异方法也较为简单。首先在一个染色体上任取A、B两点，将这两点之间的基因实施倒位即可得到新的染色体。变异操作具体实施的过程如图4所示。

为了加快收敛速度和增加个体多样性，利用文献[14]提出一种自适应交叉和变异概率，具体计算如下：

在式（3）、（4）中，gmax是每代群体中个体的最大适应度值；gavg是每代群体的平均适应度值；g'是被选择交叉的两个个体中较大的适应度值；g是被选择变异个体的适应度值。只要设定 k1, k2, k3, k4取(0,1)区间的值，就可自适应调整交叉和变异概率。

2．2．4．遗传终止

重复以上步骤，直到满足收敛条件或达到最大搜索步数为止，方可结束寻优搜索。

图4 变异过程Fig 4 Mutation process

3．调度实例

鉴于JSP的重要性和代表性，本文利用MT06基准案例来对本文使用的改进自适应遗传算法进行验证，其中MT06的加工工序和加工时间如表2所示。

算法参数选择为：k1=1.0，k2=1.0，k3=0.5，k4=0.5，种群规模N=100，代数T=100。运用 matlab编程求解，很快就可收敛于调度问题的最优解，如图5所示。本文改进算法与基本遗传算法的对比进化曲线如图6所示。可知，利用本文改进的自适应遗传算法只需3代就可得到问题的最优值，而利用基本遗传算法需要50代才能得到问题的最优值，从而说明该改进遗传算法的有效性和可行性。

图5 调度结果Fig.5 Scheduling result

表2 加工工艺及约束关系Tab.2 Processing time and process constraints

图6 进化曲线Fig.6 Evolutionary curve

4．结论

针对作业车间调度问题，利用一种改进的自适应遗传算法进行求解。建立了以完工时间为目标的作业车间调度模型，通过设置编码、解码方案，以及确定选择、交叉、变异等遗传算子，并利用精英个体保留策略及改进的自适应交叉和变异概率解决作业车间调度问题。通过对基准案例实验，得到优化调度方案和进化曲线，结果验证了该方法的有效性和可行性。

参考文献：

[1]王凌．车间调度及其遗传算法[M]．北京：清华大学出版社，2002：1-9．

[2]陶泽，张海涛．基于遗传算法的Job-Shop调度问题研究[J]．沈阳理工大学学报，2016，35（2）：60-64．

[3]蒋丽雯．基于遗传算法车间作业调度问题研究[D]．上海：上海交通大学，2007：17-20．

[4]GEN M,LIN L.Multiobjective Genetic Algorithm for Scheduling Problems in Manufacturing Systems[J].Industrial Engineering&Management Systems,2012,11(11):310-330.

[5]KURDI M.An effective new island model genetic algorithm for job shop scheduling problem[J].Computers&Operations Research,2016,67:132-142.

[6]ASADZADEH L.A local search genetic algorithm for the job shop scheduling problem with intelligent agents[J].Computers&Industrial Engineering,2015,85:376-383.

[7]彭忆炎，孔建寿，陈轩，等．面向智能制造的作业车间调度算法研究[J]．南京理工大学学报：自然科学版，2017，41（3）：322-329．

[8]赵小强，何浩．一种求解柔性作业车间调度问题的改进DRSGA[J]．南京理工大学学报：自然科学版，2016，40（3）：297-302．

[9]张超勇，董星，王晓娟，等．基于改进非支配排序遗传算法的多目标柔性作业车间调度[J]．机械工程学报，2010，46（11）：156-164．

[10]LI X,GAO L.An effective hybrid genetic algorithm and tabu search for flexible job shop scheduling problem[J].International Journal of Production Economics,2016,174:93-110.

[11]王雷．类生物化制造系统协调机制及关键技术研究[D]．南京：南京航空航天大学，2010：37-39．

[12]万敏，唐敦兵，王雷，等．求解车间调度问题的改进型自适应遗传算法[J]．机械科学与技术，2011，30（1）：39-42．

[12]谢胜利，黄强，董金祥．求解JSP的遗传算法中不可行调度的方案[J]．计算机集成制造系统，2002，8（11）：902-906．

[13]SRINIVAS M,PATNAIK L M.Adaptive probabilities of crossover and mutation in genetic algorithm [J].IEEE Transactions on Systems,Man,and Cybernetics,1994,24(4):656-667.