改进遗传算法求解作业车间提前/拖期调度问题

葛安华，周晏明，李权章

(东北林业大学工程技术学院，哈尔滨 150040)

作业车间调度问题，是一类满足任务配置和顺序约束要求的资源分配问题，其目的是对作业进行有效排序，是最难解决的组合优化问题之一［1］。在实际的制造企业加工车间中所面临的问题大多为作业车间调度，如车间生产自动化水平相对较低，凭计划员经验调度，频繁调整生产计划，设备利用率不均衡，生产周期加长以及人员与设备的浪费［2］。对作业车间调度问题的研究有助于提高生产车间自动化水平，改善设备利用的均衡性，具有重要理论意义和工程价值。

随着近年来智能优化技术的发展，许多求解作业车间调度问题的启发式方法被提出，如禁忌搜索算法、模拟退火算法、遗传算法等，国内外的专家学者在相关方面也做了大量的研究工作［3－5］。文献［3］研究了一种基于禁忌搜索技术解决作业车间调度最短完工时间的算法。禁忌搜索算法偏向于局部搜索，对初始解的依赖性较强，不好的初始解会造成计算时间过长。文献 ［4］阐述了模拟退火算法在作业车间调度问题上的应用。虽然理论上模拟退火算法可以在足够长的时间后跳出局部最优，但在实际应用中往往会陷入到优化效果与计算时间的矛盾中。遗传算法，因其通用性强，全局搜索性能较好，在求解过程中可同时保留多个方案而得到广泛的应用。但因其固有特征，在求解作业车间调度问题时仍具有局部寻优能力差，搜索效率不高等现象。文献 ［5］通过改进遗传算法的编码方式、交叉、变异策略等方法提高了算法求解总加工时间最短的作业调度问题的能力。

在实际的车间调度问题中，企业的生产调度多以产品的订单交货期为主要依据［6］，故本文将最小化产品的提前/拖期惩罚作为目标函数，以提高遗传算法在作业车间调度问题中的求解质量和收敛速度为目标，提出一种带有记忆功能的改进遗传算法，并利用爬山算法提高其局部搜索能力，通过与其他算法计算结果的对比分析验证其优越性。

1 问题描述

作业车间提前/拖期调度问题可以描述为:

(1)在m台机器上生产n个相互独立的产品，产品集合表示为N={1，2，……，n}，机器集合表示为M={1，2，……，m}，每个产品需经过若干道工序才能完成，且每道工序在特定的机器上加工;

(2)sijk和tijk分别表示第i个产品的第j道工序在机器k上的开始加工时间和加工时数，产品i的最后一道工序的开始加工时间和所需加工时数分别是siek和tiek，则产品i的完工时间ci=siek+tiek;

(3)产品i的交货时间窗口为 ［ei，di］，产品i单位时间的提前惩罚为ωi，拖期惩罚为αi，若产品在时间窗口之内完成生产，则不受惩罚，否则对产品i进行惩罚;

目标函数为最小化产品的总惩罚，表示为:

公式 (1)表示的是目标函数，即最小化所有产品的提前/拖期惩罚。公式 (2)表示工艺约束条件决定的各产品的各道工序的先后加工顺序以及各道工序在相应机器上的加工顺序。其中，若机器h先于机器k加工产品i，则aihk为1否则为0，若产品i先于工件j在机器k上加工，则bijk为1否则为0;sik和tik分别表示产品i在机器k上的开始加工时间和加工时数;G是一个足够大的正数。

2 遗传算法的设计

为提高遗传算法的收敛速度，采用一种可以保留较高适应度个体的记忆功能，并利用爬山算法对记忆种群进行局部搜索，从而增强算法的局部搜索能力。改进遗传算法的具体步骤如下:

(1)设置种群尺寸为PS，记忆库尺寸为MS。

(2)产生初始种群P(t)，从初始种群中选取MS个较优个体保存在记忆库M(t)中。

(3)分别以交叉概率Pc和变异概率Pm对个体进行交叉和变异操作，将得到的子代个体保存到种群O(t)中。

(4)以记忆库M(t)中的染色体为初始解，利用爬山算法进行局部搜索，得到更新后的记忆库M’(t)。

(5)评价种群P(t)，O(t)和M’(t)，从中选择出种群P(t+1)。

(6)进行记忆库的第二次更新，从种群P(t+1)中选取其中较优的MS个个体更新记忆库。

(7)如果满足终止条件 (达到最大迭代次数N)则结束计算，否则转向 (3)。

2.1 编码设计

遗传算法在进行编码时，必须要考虑染色体的合法性、有效性、冗余性以及表征解空间的完全性［7］。编码设计的优劣对算法的各子阶段都有重大影响。好的编码设计可以保证在交叉、变异后依然保持染色体的有效性和完全性。目前已提出的编码方法有，基于优先规则的表达法、基于工序的表达法、基于优先表的表达法、基于工件的表达法、基于工件对关系的表达法、基于机器的表达法等［8］。

将基于工序表达法与机器表达法的实数编码方法相结合，形成一种新的双染色体矩阵编码方式。对于m台机器生产n种产品的问题，基于工序表达的实数编码，染色体有n×m个基因，每个代表产品的十进制数都在基因中重复出现m次，工序调度的顺序由染色体基因的顺序决定;同样基于机器表达的实数编码，其染色体也有n×m个基因，每个染色体基因分别表示相应产品的各道加工工序所在的机器编号。

2.2 种群的初始化及适应度函数的确定

依据上述编码方式的种群初始化很简便，首先建立一个随机分配个体基因的循环，生成个体的第一行基因，再利用产品的工序顺序约束生成个体的第二行基因。如此重复进行，直至达到设定的种群规模。

根据目标函数定义的适应度函数如下所示:

式中:F为适应度函数，F取值越大，总惩罚越小，其对应调度方案的适应度越高。

2.3 遗传算子

2.3.1 复制

2.3.2 交叉

考虑到基于双染色体矩阵编码交叉后子代的调度可行性，基于部分映射杂交 (PMX)和染色体分离的思想提出一种部分映射交叉重排算子［9－10］。这种交叉方法的具体过程如下:

(1)分别在两个父代染色体上选择两个步数相同的交叉点。

(2)两个父代交换彼此交叉点之间的子串。

(3)确定被交换的子串间基因的映射关系。

(4)消除掉染色体中多余的基因，以相应的缺失基因补充。

(5)根据产品相应工序所需加工机器的约束，重新排列染色体中的第二行基因。举例说明部分映射交叉重排算子，如图1所示，A、B为两个父代染色体，经交叉后得到两个子代个体A’、B’。

2.3.3 变异

为保证变异后的个体仍为可行解，基于前面交叉算子的设计思想，采用互反变异重排方法进行个体的变异操作。首先在染色体上随机选择两个位置，然后交换这两处的基因，再根据产品各工序所需加工机器的约束重排第二行的染色体基因［11］。

图1 交叉算子Fig.1 Crossover operator

2.4 爬山操作

爬山算法，又称局部搜索算法，是一种基于邻域搜索技术的、沿着可能改进解的质量的方向进行单方向搜索 (爬山)的搜索方法，其局部搜索能力很强，是一种常用的寻找局部最优解的方法［12］。它在解的空间内，以当前节点为中心和其邻域的节点值相比较，若其邻域节点更优，则用其替换当前节点继续搜索;反之则返回当前节点继续搜索。如此循环直至到达终止条件。

为弥补传统遗传算法局部搜索能力较弱的不足，采用基因逆转算子来实现爬山操作，更新种群记忆库。具体步骤如下:

(1)对于记忆库中的每个个体，随机选择个体上的两个点，再将两点之间的元素逆序插回到原来的位置中。

(2)判断逆转后的个体适应值是否增加，若增加则以逆转后的个体替换原个体，否则仍保留原个体。

(3)重复 (1)、(2)的操作，直至达到设定的迭代次数为止。

3 仿真实验

本节的仿真实验在Genuine Intel(R)T2130 1.87GHz处理器，2.0GB RAM，MATLAB R2011a环境下进行。

3.1 仿真分析

为验证文中改进遗传算法的优越性，将本文算法与文献［2］中的遗传算法 (IGA)进行比较。取种群规模100，记忆库规模20，交叉概率0.5，变异概率0.05，在不同规模 (n×m)下进行实验对比。实验中生产机器的集合，各工序所需加工时间随机产生，且满足平均分布。由于篇幅有限在此仅列出6组实验结果，见表1，每种规模仿真实验20次，其中最优值为所有运算结果中目标函数最小的值，平均值为每次运行所得最优值的平均值。

表1 方法比较Tab.1 Method comparison

从表1中可以看出，本文算法所求得的最优值和平均值均优于IGA，而且随着规模的不断扩大，效果更加明显，体现了本文算法的优越性。

3.2 实例应用

以某加工制造企业为例，验证本文算法在实际应用中的可行性和有效性，设提前惩罚为0.8，拖期惩罚设为1.4，产品各生产工序所需的加工时间、加工机器以及各产品的交货时间窗口见表2。

表2 加工数据Tab.2 Machining data

设定遗传算法的参数为:交叉概率Pc=0.4，变异概率Pm=0.02，种群尺寸PS=100，记忆库尺寸MS=20，最大迭代次数N=100，爬山算法的最大迭代次数N’=5。分别采用不带记忆功能的普通遗传算法和文中的改进算法，进行20次仿真实验，两种算法的实验结果见表3，图2为两种算法的收敛情况比较。

表3 实验结果Tab.3 Experimental results

图2 两种算法收敛情况Fig.2 Convergence situation of the two algorithms

从表3中可以看出，本文算法求解出了问题的最优解0，在20次仿真中搜索到最优解的次数为18次，而且搜索到最优值的平均迭代次数和平均计算时间都要优于普通遗传算法，说明改进遗传算法的运算性能稳定，搜索能力强。通过图2的比较则可以进一步看出，在整个搜索过程中，本文算法的收敛速度较快，在41代左右达到全局最优解0，而普通遗传算法的收敛速度明显较慢，且在43代左右以后逐步陷入局部最优。综上所述可知，无论是在求解质量还是收敛速度上，文中的改进遗传算法都优于不带记忆功能的普通遗传算法。

仿真结果表明，通过本文算法可以求解出惩罚值为0的最佳调度方案，即所有产品均可在交货窗口内按时完成生产。求解出的最优个体如下:

4 结论

为求解作业车间提前/拖期调度问题，文中提出一种基于双染色体矩阵编码的改进遗传算法，并利用记忆库和爬山算法提升算法的寻优能力和搜索速度。改进遗传算法的编码简洁、直观，收敛性能好，并能较好地解决相关的车间调度问题，满足大规模此类调度问题的需要。下一步将继续研究结合其他启发式方法的改进遗传算法在多目标作业车间调度问题中的应用，并进一步提高算法的性能。

【参 考 文 献】

［1］王万良，吴启迪．生产调度智能算法及其应用［M］．北京:科学出版社，2007．

［2］苏 莹，李 杰，阴慧辉，等．改进遗传算法求解作业车间调度问题［J］．制造技术与机床，2010，10:104 －108．

［3］黄 志，黄文奇．一种基于禁忌搜索的作业车间调度算法［J］．计算机工程与应用，2006，03:12 －14．

［4］赵良辉，邓飞其．用于作业车间调度的模拟退火算法［J］．制造业自动化，2006，28(3):10 －23．

［5］苏 春，王大侠．基于改进遗传算法的偏柔性作业车间调度［J］．工业工程，2010，13(6):61 －65．

［6］陈 杰，张力菠．供应链环境中交货期问题的研究［J］．中国制造业信息化，2005，34(4):105 －107．

［7］潘全科，朱剑英．多工艺路线的作业车间模糊调度优化［J］．中国机械工程，2004，15(24):2199 －2202．

［8］吕文阁，刘志勇，成思源，等．基于竞选算法的生产调度问题的研究［J］．机床与液压，2009，37(10):33 －36．

［9］玄光男，程润伟．遗传算法与工程优化［M］．北京:清华大学出版社，2004．

［10］韩冰源，肖生苓．配送中心线路优化方法的探讨［J］．森林工程，2005，21(2):67 －68．

［11］郎茂祥．配送车辆优化调度模型与算法［M］．北京:电子工业出版社，2009．

［12］郎茂祥，胡思继．用混合遗传算法求解物流配送优化问题的研究［J］．中国管理科学，2002，10(5):51 －56．