求解并行JSP 作业车间调度问题的一种混合遗传算法

方 霞， 俞宏图， 熊 齐

（湖南文理学院， 国家Linux 技术培训与推广中心， 湖南 常德 415000）

0 引言

企业制造核心JSP 问题 （Job-Shop Scheduling Problem 作业车间调度）需要人员、物料、设备等多种资源优化整合，涉及到各类生产要素，具有数据量大、种类繁多的特点，同时加工任务也具备多品种、多批量、多工序、多任务等特征， 如何有效提高资源的利用率， 缩短加工周期、合理规划工件各工序的加工流程一直是研究的热点。

JSP 问题是NP 难问题，为了改进调度性能，一些学者进行了研究，提出了很多解决方案，得到了很多有意义的结论： 程八一采用作业分类策略产生候选表和轮换法对信息素更新提高算法效率[1]。 宋存利提出采用基于工序的随机键编码的一种混合微粒群算法HPSO 有效改进大多数经典调度问题[2]。 蒋南云等建立了双层生产计划与调度集成优化随机期望值模型[3]。 徐本柱设计了同工件同批工序间、不同工序间的并行调度算法，使分批具有方向性和预测搜索空间[4]。 Xiao-long Zheng，Ling Wang 提出了基于知识的果蝇优化算法KGFOA[5]，对于并行调度JSP 问题都有一定积极改进意义。

本文针对并行任务JSP 问题进行了更深一步的探究，结合JSP 问题的实际应用多样性和复合型，设计优化的底层染色体结构，嵌入可行解检测判断，生成动态生产调度表，混合遗传算法求解，得到更高效的并行调度JSP 问题求解方案。

1 作业车间调度数学模型

（同一台机器上，Oij在Opq之前加工）

约束条件（1）和（2）分别表达对应满足条件，其中基本符号说明：Cik—工序Oij在第K 台机器上加工完成时间；Sij—工序Oij的开始加工时间；Tij—工序Oij的加工时间（假定加工时间已经融合了存储、装卸、搬运和等待加工等准备环节， 不再另外标注相关等待时间）；Ji—工件i（i=1，2，…，n）；Mi—机器i（i=1，2，…，m）；Oij—工件i 的第j 道工序。

2 求解并行JSP 问题的混合遗传算法

2.1 染色体编码

为了方便表达调度及其甘特图采用工序顺序码。 工序总编号：统一对所有工序从小到大依次进行顺序编号。染色体基本信息表中每一条记录由五项基本信息构成：工序总编号/工件号/工序号/机器号/加工时间，如3/2/1/5/6 基因信息，分别表示总工序号为3，第2 个工件第1 道工序在机器5 上需加工时间为6（单位）。

2.2 生成初始可行解

JSP 问题求解是NP 难问题， 找到全局最优解不容易，求解时需要防止收敛速度过快而陷入局部最优解，初始要尽量使得染色体具备多样性。 采用蚁群算法随机性好、初始解均匀分布的特点，生成多种初始种群，具体实施步骤如下：

算法1：生成初始可行解

步骤1：设置种群数量N。 步骤2：对于染色体i，随机抛洒蚂蚁于总工序号编码位置，得到一组随机调度，这时还不能保证解的可行性。 步骤3：依次在染色体基本信息组成表中查询和染色体i 的总工序号对应的工件号，得到该染色体的工件编码，填入工件号j。 步骤4：根据染色体i 的工件号j，启动可行解检测子程序（算法2），调整得到具备可行解特征的染色体。 步骤5：根据染色体i 的工件号j 及其工序号，查找染色体基本信息表，得到相应的机器和加工信息。步骤6：重复步骤2～5，直到N 条染色体全部信息设置完成。

2.3 可行解检测

JSP 问题中如何保证可行解工序编码是调度任务完成的首要任务，本文中的可行解检测调整算法具体步骤如下：

算法2：可行解检测

步骤1：对生成的动态调度信息表，将工件i 的所有工序顺序编码，从1 开始依次填入其所有工序号j。 步骤2：筛选动态调度表的工件i 的所有工序j 信息，比对染色体基本信息表， 根据基本信息表的安排重置动态调度表的总工序号，使之成为可行解。 步骤3：根据总工序号，对动态调度表的机器编码、加工时间等信息进行匹配，保持数的一致性。 步骤4：对所有工件执行上述步骤，使动态调度信息生成为可行解。

2.4 选择算子

适应值函数：根据最小最大完工时间数学模型，对当前调度方案中每一条染色体分别进行操作， 根据当前工件的工序号， 查找对应选中机器的最早可以加工时间和当前工序的最早可以加工时间， 两者的最大值便是当前工序的最早开始加工时间。 调度方案中所有工序中最大的加工完成时间即为该调度方案的适应值结果。

每一次迭代适应值函数计算得到最小最大完工时间值，为当前各个调度方案的最好解，保留。 对所有种群的每一条染色体计算适应值函数值，采用锦标赛机制，两两比较，适应值优越的染色体保留下来。

2.5 交叉算子

采用随机选中工件实现交叉操作： 对动态生成的调度表，在执行可行性检测调整之前，首先在种群中任选两个染色体为父代，随机挑选生成交叉操作的工件号。具体交叉操作如图1 所示： 父代1 的该工件所有工序保持不动， 其余的工件顺序和父代2 的对应工序进行交叉依次填入，得到子代1；父代2 的操作反之亦然，得到新的子代2。 然后将交换更新的子代进行可行解检测调整，匹配每一个工件对应的工序号、机器编号及加工时间，得到新的子代可行解。算子中采用随机设置工件固定，以及顺序交叉邻域搜索策略，使得解的多样性性均得到充分保证。

图1 交叉操作

3 改进的混合遗传算法

针对并行JSP 作业车间调度问题，综合上述的选择、交叉、变异算子的各项描述，总体的混合遗传算法描述如下：

算法3：改进的混合蚁群算法求解JSP

步骤1： 根据工件加工工序的先后建立相应的AOE工序排序析取图；步骤2：根据初始数据，生成工序总编号，以及染色体基本信息表；步骤3：采用蚁群算法生成N条染色体初始种群（算法1），得到动调度信息；步骤4：对每一条染色体进行可行解检测调整（算法2），得到可行调度方案；步骤5：计算适应值函数，得到当前迭代生成调度的最优适应值，并保留；步骤6：选择适应值优越的染色体保留；步骤7：进行交叉操作，得到新的子代种群；步骤8：以一定概率进行变异操作，得到新的子代。

重复执行步骤5～8， 直至满足迭代次数要求，或者迭代超过20 次结束迭代。

4 实验仿真

实验环境仿真平台采用MATLAB 编程实现，针对国际通用数据ft06 问题检测，其相关收敛特性如图2 所示，能够快速找到目前已知最优解。

图2 Ft06 问题实验调度信息及收敛效果

5 结束语

对于并行JSP 作业车间调度问题，设计了高效的染色体基本结构，较好避免产生非可行解的可能性；同时选择蚁群算法， 加大解的搜索空间， 构造好的初始解种群。 然后通过融合遗传算法的选择、交叉、变异等操作，较好实现了JSP 作业车间调度的优化，从而提高找到全局最优解的效率。 通过国际通用数据实验证明，改进混合遗传算法能够有效提高并行JSP 作业车间调度问题的求解。