一种求解作业车间调度问题的异步元胞遗传算法*

陆曈曈，胡方军，张 屹

(三峡大学a.经济与管理学院;b.水电机械设备设计与维护湖北省重点实验室，湖北 宜昌 443002)

0 引言

作业车间调度问题(Job-shop Scheduling Problem，JSP)是一类在一定的任务配置和约束要求前提下，合理安排生产资源和加工顺序的问题。JSP 属于典型的NP-hard 问题，也是最困难的组合优化问题之一［1］，一直是国内外学者研究的热点与难点之一。为企业生产过程制定合理的调度计划，能有效提高企业的资源利用率和生产效率，提高经济效益。因此，找到一种快速、高效地求解JSP 的算法，不仅具有重要的理论研究价值，而且能带来巨大的经济效益。

近些年来，学者们对于求解JSP 的算法研究已取得不少研究成果，如运用模糊逻辑、模拟退火、神经网络、免疫算法、禁忌搜索和遗传算法等智能优化算法，为求解JSP 问题提供了一些可行的方法［2］。在遗传算法求解JSP 问题方面，Davis L［3］最早将遗传算法应用于JSP 问题的求解。张长水等［4］提出一种改进的遗传算法并应用于JSP 问题求解。刘民等［5］提出运用遗传算法求解并行多机调度问题。王万良等［2］提出一种双倍体遗传算法，并应用于作业车间调度问题求解。蔡良伟等［6］提出一种多种群遗传算法用于解决作业车间调度问题。张守胜［7］对交叉和变异算子作了改进，提出了一种求解JSP 问题的改进遗传算法。张超勇［8］等提出一种新的调度类型，并采用改进的遗传算法求解作业车间调度问题。研究表明，传统遗传算法具有较强全局搜索能力，在求解规模较大的JSP 时往往容易陷入局部收敛而不能得到最优解。元胞遗传算法(Cellular Genetic Algorithm，cGA)是将遗传算法与元胞自动机理论结合提出的一种新算法，自提出以来，不断受到国内外学者的关注，并相继出现了很多研究成果。近些年来，元胞遗传算法已成功地应用于非常复杂的组合优化问题，如VRP 与SAT 问题［9］，成为解决这些问题的新方法。元胞遗传算法还应用于其他如逻辑、信息、调度问题［10］等领域。基于此，本文提出了一种异步元胞遗传算法(asynchronous Cellular Genetic Algorithm，acGA)，建立作业车间调度模型，针对JSP设计合理的编码解码方案和交叉变异算子，将该算法、同步元胞遗传算法(scGA)以及传统遗传算法(sGA)应用于作业车间调度问题实例求解，将算法优化结果进行比较验证本文提出的异步元胞遗传算法求解JSP的有效性。

1 作业车间调度问题描述

JSP 可描述为:n个工件要在m台加工机器上加工，设J ={J1，J2，…，Jn}和M ={M1，M2，…，Mm}分别表示由n个工件和m台加工机器组成的集合。工件集合J中的工件Ji(1 ≤i≤n)在各机器上按照其预先确定的工序顺序Oi ={Oi1，Oi2，…，Oip}(p表示工件Ji的工序数)进行加工，各工件之间无先后顺序。约束要求:同一机器在同一时刻最多只能加工一个零件的一道工序;某个工件同时只能被一台机器加工。且假设机器不发生故障，若以tijk和Cijk分别表示工件Ji的第j(1 ≤j≤p)道工序在机器Mk(1 ≤k≤m)上的加工时间和完成加工时间，以Cmax表示最后一个工件在最后一台机器上完成加工的时间。优化目标是在满足各项约束的条件下，进行合理调度，确定各工件在各台机器上的开工时间stijk，使得最大完工时间Cmax最小。JSP 数学模型如下:

2 异步元胞遗传算法

元胞遗传算法(cGA)将种群个体分布在一个环形联通的网状空间拓扑结构中，种群个体的遗传操作仅限制在与其相邻的个体(邻居)之间进行。cGA 不仅继承了传统遗传算法全局搜索能力强的优势，而且结合元胞自动机的优点，使局部寻优能力得到增强，且易于并行化，算法收敛速度加快，搜索能力得到提高。

2.1 种群空间结构和个体邻居

在元胞遗传算法中，种群中的个体通常分布于二维网状结构中，在这种网状结构中同行或同列的边界个体进行首尾相连，如图1 所示。在元胞模型中，在网格中的每个个体拥有一个邻居结构，且与其邻近个体的邻居相互重叠，种群中所有个体的邻居结构有相同的尺寸和形状。如图2 为元胞遗传算法中六种常用的邻居结构形状，其定义如下:Ln(线型)表示个体的邻居是由其在东、南、西、北方向的n个最近的个体组成;而Cn(紧凑型)通常指个体的邻居由其在水平、垂直和对角线方向的n -1 个邻近个体组成。在这六种结构中，最常用的两种邻居结构为:①L5 型，也称为冯·诺依曼(Von Neumann)型或NEWS 邻居结构;②C9型，也称为Moore 型［11］。本文提出的acGA 就是采用Moore 型邻居结构。

图1 种群空间结构

图2 典型元胞邻居结构

2.2 异步元胞遗传算法过程

本文所提出的acGA 在传统元胞遗传算法的基础上引入异步更新策略，即在算法迭代过程中，以一个特定的顺序逐个产生并更新子代个体，本文采用的的异步更新策略是固定线性扫描方法［12］:以逐行逐个个体扫描的方式相继地更新元胞个体。其种群个体更新过程如图3 所示。

图3 acGA 的个体更新示意图

为了更详细描述算法过程，下面给出异步元胞遗传算法伪代码，如下表1 所示:

表1 acGA 伪代码

2.3 编码与解码

编码表示个体的遗传基因，合理的编码方式是实现高效率遗传操作的前提，也是算法成功应用于实际问题关键之一。本文对JSP 问题采用基于工序的编码方式，对于n个工件在m台机器上加工的调度问题，其染色体由n × m个基因组成，是所有工件工序的一个排列，每个工件的工序都用其工件号表示。

本文采用基于工序的解码方式，该方法具有在置换染色体总能得到可行调度方案、避免死锁的优点。对于n个工件在m台机器上加工的调度问题的编码，每个工件号在染色体中出现m次，染色体中出现第k次(k≤m)的工件号表示该工件的第k道工序。以下表2 中的3 个工件在3 台机器上加工的JSP 调度问题为例:

表2 一个3 个工件3 台机器的JSP 实例

图4 基于工序编码的解码方式

如图4 所示，若表2 实例中的一条染色体为［2 3 1 3 1 1 2 2 3］，染色体中1，2，3 分别表示工件J1、J2、J3。染色体中的3 个1 从前到后依次为工件J1的工序1、工序2、工序3，同理可得染色体中的2 和3 意义。该染色体对应的机器序列为［3 2 1 3 2 3 1 2 1］，对应的加工时间序列为［2 2 3 2 2 3 3 4 3］。按照该解码方式将染色体上的工件工序依次安排在对应的机器上，即为该染色体对应的调度方案。

2.4 遗传操作

2.4.1 选择操作

选择操作的作用是根据一定规则从种群中选择进行遗传操作的父代个体，合理的选择操作能有效提高算法收敛的效率。针对JSP 问题，本文算法采用二元锦标制选择算子。

2.4.2 交叉操作

交叉操作是遗传算法中获得子代个体的重要遗传操作，它决定了算法的性能的优劣。对于JSP 问题，在进行交叉算子设计时需考虑到交叉所得个体的合法性。设两个父代个体染色体分别为P1、P2，交叉后产生的子代个体染色体分别为S1、S2，本文设计的交叉算子具体步骤如下:

步骤1:随机产生两个不相同的随机数n1、n2(n1、n2小于染色体长度，不妨设n1＜n2);

步骤2:初步交叉。将父代个体P1中第n1到第n2位的基因复制到子代S‘1对应位置，将父代个体P2中第n1到第n2为的基因复制到子代S’2的对应位置;

步骤3:调整。将P1中其它位上的基因按其在P1中的顺序依次插入S’2中的剩余位置，然后从左至右检查如果某基因出现次数多于合法数目，则按其先后顺序删掉除了第n1到第n2位的基因之外多余数目的该基因;若某基因出现次数少于合法数目，则按顺序在删除多余基因的位置插入短缺数目的该基因。以此种方式进行调整直到子代染色体中所有基因数目合法化，得到可行的子代S2;同理可得可行的子代S1。

以表2 中的3 个工件在3 台机器上加工的JSP 调度问题的某两条染色体为例，其交叉过程如图5 所示。

图5 交叉操作

如图5 所示的交叉操作过程，对于父代个体染色体P1、P2，随机选择的交叉基因位n1、n2为3、6，经过交叉后，得到的子代染色体体中存在有基因数目不合法情况，因此需要调整。对于S‘1，基因1 的数目多出2 个，基因2 的数目少了2 个，故将S‘1中除了第3 到第6 位基因之外的多余基因1 按顺序删掉2 个，即删除位于第7 和第9 位上的基因1，再在第7 和第9 位上分别插入基因2，得到合法染色体S1;同理可得合法染色体S2。可以看出，经过交叉后，子代S1、S2分别保留了P1、P2第3 到第6 位的基因及其顺序，既保留了父代的优良特征，又得到了可行的子代个体。

2.4.3 变异操作

变异操作在遗传算法中用于对染色体进行较小变动以获得新的个体，能增强种群多样性，有效防止算法陷入局部收敛。针对JSP 问题，本文采用交换变异算子。以表2 中的JSP 调度问题的某条染色体为例，其变异过程如下图6 所示:

图6 交换变异操作

如图6 所示变异过程，染色体P经过交换变异操作，第2 和第5 位上的染色体进行互换，得到新的染色体O。

3 实例计算及结果分析

为验证提出的异步元胞遗传算法(acGA)求解作业车间调度问题的性能，以最快完工时间最少为优化目标，采用acGA、一种采用同步更新策略的传统元胞遗传算法(scGA)、以及传统遗传算法(sGA)对JSP 问题的两个标准测试实例FT06(6 个工件6 台机器)和LA01(10 个工件5 台机器)进行求解，并进行结果对比。算法的参数设置:初始种群大小设为100;交叉概率为Pc =0.9 ;变异概率为Pm =0.2 ;算法在FT06 问题上迭代代数为100 代，在LA01 问题上为500 代。FT06 和LA01 两个JSP 实例的已知最优解分别为55和666。acGA 和sGA 在两个实例上运行的收敛曲线如下图7、图8 所示。

图7 acGA 和sGA 的收敛曲线(FT06)

图8 acGA 和sGA 的收敛曲线(LA01)

由图7、图8 可以看出，在相同的条件参数下，ac-GA、scGA 与sGA 最终都能收敛到最优解，但acGA 与scGA 两种元胞遗传算法与sGA 相比具有明显的优势，搜索效率更高，能够更快地收敛到最优解，特别是当算法运行到接近最优解时，acGA 和scGA 比sGA 更快地搜索到最优解，sGA 则容易陷入局部最优而不容易得到最优解，说明采用元胞结构的遗传算法局部搜索能力更强。而acGA 与scGA 相比，acGA 能更快收敛到最优解，说明本文采取的异步更新策略提高了算法的搜索效率，使得算法的全局和局部搜索能力增强。并且对于规模更大的LA01 实例，acGA 的搜索效率与收敛效果的优势更明显。对于FT06 和LA01 两个实例，acGA 计算所得到的调度方案的甘特图如图9、图10 所示:

图9 FT06 实例甘特图

图10 LA01 实例甘特图

为了进一步验证所提出的acGA 求解JSP 问题的稳定性以及计算精度，在相同的硬件条件下分别采用acGA、scGA 和sGA 分别对FT06 和LA01 两个JSP 实例独立计算10 次，每次运行均采用上述同样的参数设置。对计算结果进行统计分析，对比结果如表3 所示。

表3 计算结果对比

从表3 可看出，对于FT06 和LA01 两个JSP 实例，acGA、scGA 和sGA 均能搜索到最优解。在10 次独立计算中，对于FT06 实例，sGA 得到最优解得次数为7次，少于scGA 的8 次和acGA 的10 次;sGA 和scGA得到的最差解为58，acGA 最差解55;sGA 的10 次计算平均解为55.7，scGA 的平均解55.5，而acGA 每次都收敛到最优解55，平均解为55。对于LA01 实例，sGA 的最优解得次数仅为5 次，scGA 的最优解次数为7 次，acGA 达到最优解次数最多，为9 次;sGA 得到的最差解为690，scGA 得到最差解为696，而acGA 最差解667;sGA 的10 次计算平均解为673.2，scGA 的平均解为671.5，都差于acGA 的平均解666.1。可看出，在求解JSP 问题时，本文提出的acGA 比scGA 和sGA 具有更强的搜索能力和更高的搜索效率，算法的收敛精度更高，算法稳定性更好，acGA 在求解JSP 问题时具有明显的优势。

4 结论

元胞遗传算法不仅能继承遗传算法的全局搜索优势，而且结合了元胞自动机的优点，提高了算法的局部搜索能力，能有效避免遗传算法陷入局部收敛。本文提出的异步元胞遗传算法(acGA)引入了一种异步更新策略，针对JSP 问题设计了适合JSP 问题的交叉算子，并采用二元锦标赛选择算子和交换变异算子，进一步避免了算法陷入早熟收敛，提高了算法的搜索能力和收敛效率。分别采用acGA、scGA 和sGA 对JSP 问题的两个标准测试实例FT06 和LA01 进行求解，结果对比表明在求解JSP 问题时，acGA 比scGA、sGA 的搜索效率更高，收敛速度更快，算法的稳定性也更好，表明acGA 是一种能快速、高效地求解JSP 问题的算法。

［1］张国辉，高亮，李培根.基于遗传规划的作业车间调度算法研究［J］.控制与决策，2008，23(8):924 -928.

［2］王万良，宋毅，吴启迪.求解作业车间调度问题的双倍体遗传算法与软件实现［J］.计算机集成制造系统，2004，10(1):65 -69.

［3］Davis L. Job-shop Scheduling with genetic algorithms［C］.

Proc. of International Conference on Genetic Algorithms and Their Applications，1985，136 -149.

［4］张长水，沈刚，阎平凡. 解Job-shop 调度问题的遗传算法［J］.电子学报，1995，23(7):1 -5.

［5］刘民，吴澄，蒋新松.用遗传算法解决并行多机调度问题［J］.系统工程理论与实践，1998，18(1)1:14 -17.

［6］蔡良伟，张基宏，李霞.作业车间调度的多种群遗传算法［J］.电子学报.2005，33(6):991 -994.

［7］张守胜.求解作业车间调度问题的改进的遗传算法［J］.计算机与现代化.2007，32(11):32 -35.

［8］张超勇，管在林，刘琼，等.一种新调度类型及其在作业车间调度中的应用［J］.机械工程学报，2008，44(10):24 -31.

［9］E. Alba，B. Dorronsoro，and H. Alfonso. Advanced models of cellular genetic algorithms evaluated on SAT，in Genetic and Evolutionary Computation Conference (GECCO)，Washington，D.C. USA，2005(6):1123 -1130.

［10］E. Alba，B. Dorronsoro，F. Luna，et al.A cellular multiobjective genetic algorithm for optimal broadcasting strategy in metropolitan manets［J］. Computer Communications，2006.

［11］SARMA J.，JONG K. DE. An analysis of the effects of neighbourhood size and shape on local selection algorithms［C］. Proceedings of the International Conference on Parallel Problem Solving from Nature (PPSN IV)，1996:236 -224.

［12］SCH NFISCH BIRGITT，DE ROOS ANDR Synchronous and asynchronous updating in cellular automata［J］. BioSystems，1999，51(3):123.