基于遗传算法的路径柔性作业车间调度优化

谢 皓，应保胜，袁 波

（武汉科技大学机械自动化学院，湖北武汉，430081）

传统的作业车间调度问题中，工件的加工工序是确定的，某道工序的加工机器及加工时间也是确定的，而路径柔性作业车间调度则存在加工工艺路线中机器可变的情况，即工件的同一工序可以选择不同的机器进行加工，并且在不同机器上的加工时间也可能不同［1］。因此，路径柔性作业车间调度优化问题更为复杂。

工件的每道工序可以选择所有的加工机器来完成的调度称为完全路径柔性作业车间调度；每道工序只能在部分机器上进行加工的调度称为部分路径柔性作业车间调度［2］。在一般的加工工厂中，机器的数量和功能都有一定的限制，所以部分路径柔性车间调度问题能更真实地反映实际情况。本文即以部分路径柔性作业车间调度为研究对象，以最长完工时间最短化为优化目标建立调度模型，采用遗传算法进行模型求解，针对传统遗传算法中编码方法单一的问题，提出一种基于工序与机器编码相融合的编码方法，并通过算例对算法的有效性进行分析。

1 调度模型的建立

路径柔性作业车间调度问题可描述为：在一个加工车间中，有m台加工机床和n个待加工的工件，每个工件须经过一道或者多道工序，其加工顺序是确定的，同时每一道工序又可以在一台或多台不同的机器上进行加工，每道工序的加工时间随加工机器的不同而改变。调度目标是为每个工件的每道工序安排加工机器以及确定不同加工工件之间的顺序，以得到最优的完工时间。

建立这类车间调度问题的数学模型之前，先定义变量如下：i为工件序号，i＝1，2，…，n；k为机器序号，k＝1，2，…，m；j为工件的工序号；hi为工件i总的加工工序数；tijk为在机床k上加工工件i的第j道工序所花的时间；sij为工件i的第j道工序起始时间；eij为工件i的第j道工序结束时间；mij为工件i的第j道工序可选的机器数；ci为工件i最后一道工序完成的时间；R为一个无穷大的正整数；

模型的约束条件有两类：

（1）加工顺序约束，即工件i的第j道工序必须满足自身的加工时间约束（见式（1）），且工件i的第j＋1道工序必须在第j道工序完成后才能开始（见式（2））。

（2）资源约束，即在一个确定的时刻，同一台机床只能加工一个工件的一道工序，在该工序完工后才能开始加工下一个（见式（3）），并且同一道工序只能在一台机床上加工（见式（4））。

以最长完工时间最短化为调度优化目标，其目标函数为：

2 遗传算法设计

2.1 编码设计

用遗传算法求解作业车间调度问题可以采用基于工序顺序的编码方法［3］，但这种方法要求工件每道工序的加工机器是固定的，而在路径柔性作业车间调度中，机器是可以选择的，因此本文设计了一种基于工序和机器编码相融合的编码方法。

表1 路径柔性作业车间调度原始数据Table 1 Data of the path flexible job－shop scheduling

从表1中可以看出，工件1的第一道工序可在M1或M2上加工，第二道工序可在M3或M4上加工，第三道工序只能选择M4进行加工，其余以此类推。随机选择一个加工序列（即染色体）（1，2，5，4，1，1，2，3，2，4，3，5，4，3，5），染色体中的1～5为工件号，每个序号在染色体中出现的次数与其加工工序数相等，第一次出现某个序号，表示该序号对应工件的第一道加工工序，第二次出现则对应该工件的第二道工序，以此类推，一个可行的工序序列可以通过这样一个数字串来表示。

将工序编码和机器编码得到的染色体基因相同的位置一一对应起来，形成一个二维矩阵，矩阵的第一行为工序编码，第二行为机器编码，从而得到一个融合工序和机器编码的完整染色体［4］。需要特别说明的是，在产生第二行染色体时按照下面的表述来进行：对应第一行的某道工序Er，如果该工序加工时可以选用的机器数EM＞1，就用0～（EM－1）之间的一个数来表示Er的加工机器号，0表示Er由其可选用的第一台机器加工，1表示Er由其可选用的第二台机器加工，等等。如果工序Er可以选用的机器是惟一的，则用符号“－”来表示。通过矩阵两行之间的对应，就可以找到每道工序的加工机器。

例如，对于一个染色体：

矩阵的第一列表示工件1的第一道工序在其可选用的第一台机床上加工，根据表1可知该机床为M1；矩阵的第三列表示工件5的第一道工序只能在惟一的一台机床上加工，根据表1可知该机床为M3；矩阵的第五列表示工件1的第二道工序在其可选用的第二台机床上加工，根据表1可知该机床为M4。通过类似的解码，得到一个可行的调度方案为（E111，E214，E513，E415，E124，E134，E222，E311，E233，E422，E325，E522，E431，E333，E534），其中Eijk表示工件i的第j道工序在机床k上加工。

2.2 选择算子

选择操作是为了避免有效基因的损失，因此适应度高的个体更容易生存下来。适应度函数一般由目标函数转换而来，本文的优化目标是最长加工时间最短化，可将目标函数值C的倒数作为个体的适应度f。

采用轮盘赌选择方法，个体p的选择概率为：

式中：M为种群大小。

2.3 交叉和变异算子

在进行交叉操作前，通过一种附加的方法产生新个体，以达到扩大搜索范围的目的。具体方法是：对于某些可以由多台机器进行加工的工序，随机变化染色体第二行的值。例如，对于个体矩阵第二行中带有下划线的数字被随机选择出来，然后将数字在可行范围内随机进行变换，就可以得到如下个体：

从而使某些工序的加工机器发生了变化。

交叉操作采用交换串的方法进行，即随机选择染色体中的两个位置，然后对这两点之间的串信息进行交换。进行交换后有些工件的工序会多出来，有些工件的工序会缺少一部分。找出遗失的工序，用多出来的工序进行替换。例如，有两个染色体：

染色体中箭头所示为交叉位置。在交叉过程中，先保留第二行的加工机器信息，只对矩阵的第一行进行操作，得到：

交叉后需要对染色体进行合法性检测。从产生的第一个子代offp1中可以看到，工件4的序号只在染色体中出现了一次，而工件1和工件2的序号在染色体中都出现了4次，这样的染色体不是合法的解，需要删掉多余信息，同时补全遗失的基因。在染色体中可以随机选择一个1和2，然后将其换成工号4。在第二个子代offp2中也出现了这种情况，需要进行类似变换。

经过合法性检测之后，将第二行的机器信息补充上去，同时加工信息在交叉前后必须保持不变，得到：

常用的变异方式有互换、逆序和插入等，本文采用插入方式，即随机选定一个基因位置，然后将其插入随机选定的另外一个位置中，其他基因序列不变。需要重点注意的是，在变异前后一定要保证加工机器不能改变。例如，个体

随机选择第一行中的13号基因位，然后随机选择5号基因位为需要插入的位置。在插入前，先保留第二行的机器信息，插入完成后，再将机器信息填上去。经过变异操作后得到以下个体：

3 算例分析

对一个8×8的路径柔性作业车间调度问题进行计算，其原始加工数据来源于文献［5］。优化目标为加工时间最短，初始种群随机产生，种群个体数为50，迭代次数为300，交叉概率为0.8，变异率为0.04。通过连续10次运行，得到最优调度如图1所示，图中方框内数字为工件序号。

图1 最优调度方案Fig.1 Optimal scheduling solution

图2为本文遗传算法和文献［5］中算法的收敛曲线比较。由图2可见，本文算法得出的最优解为14，文献［5］得出的最优解为15。同时，本文算法在150代左右就开始收敛，而文献［5］中算法在200代以后才达到了最优值，因此相比于文献［5］的算法，本文算法收敛更迅速，所得调度方案更优。

图2 收敛曲线Fig.2 Convergence curves

4 结语

本文采用遗传算法求解部分路径柔性作业车间调度问题。有别于传统基于工序的染色体编码方法，本文将工序编码和机器编码相结合，提出一种二维矩阵编码方法，设计出相应的遗传算子，并通过算例验证了本文所给算法的可行性与有效性。

［1］ 张国辉，高亮，李培根.改进遗传算法求解柔性作业车间调度问题［J］.机械工程学报，2009，45（7）：145－148.

［2］ 张超勇，李培根.柔性作业车间调度问题的两级遗传算法［J］.机械工程学报，2007，43（4）：119－124.

［3］ 谷峰，陈华平.病毒遗传算法在柔性工作车间调度中的应用［J］.系统工程与电子技术，2006，27（11）：139－142.

［4］ 王小平，曹立明.遗传算法——理论应用与软件实现［M］.西安：西安交通大学出版社，2002：28－35.

［5］ Hillier F S，Lieberman G J.Introduction to operations research［M］.Peking：Mechanical Industry Press，2008：129－150.