。814 北京科技大学学报 第32卷 m-k+1台机器上加工；和P粉别为工件在第1 和逆序情况下的调度甘特图.由图可以看出，正序 个和第2个JSSP的第台机器上的加工时间.令m 调度方案与逆序调度方案的关键路径均由同一批工 表示第1个SSP的设备所加工的工件数，则该设 序的加工时间所决定，因此makespan值不会发生变 备所加工的工件有序集可记为元k={πk(1)πk 化（这两个调度图均为13. (2),,元k()}.如果第2个SSP的设备m-k+ 表13×3作业车间调度问题描述 1所加工的工件有序集为πm-1={πk(),, Table Descrption of a3x3 pb shop schedu ling pobkm πk(2,元k(1),那么对应的最优调度方案分别称 工件号 工序编号 机器顺序 加工时间 为正序调度方案和逆序调度方案，而对应的调度问 0,99s M.M.M 343 题分别称为原问题和逆向问题(reverse problem. 021,932933 MM.M 332 例如，一个三个工件、三台设备的作业车间调度 0,9320 M,M.M 351 方案，加工时间数据如表1所示.图1给出了正序 (a) 正序调度甘特图(C=13 (b) 逆序调度甘特图(C=3) 32 2.2 2.3 3.3 1.1 21 1.2 3.2 2.1 M,… 3.1 13 22 2.2 3.1 6 10 12 14 6 10 12 时间 时间 图1正(，逆（序调度甘特图 Fg 1 Gantt charts of prward a and backwadd scheduling(b 2.3求解策略 基于活动调度思想，文献[4提出了一种GT算 标准遗传算法是针对一个宏观的种群进行选 法与GA相结合的求解算法（记为GIGA),该文将 择、交叉和变异三种操作，类似于人类进化过程，一 搜索空间限制为活动调度空间，通过空间缩减来提 群人随着时间的推移而不断地进化，具备越来越多 高算法的搜索效率.虽然算法GTGA可以遍历整个 的优良品质.然而，由于他们的生长、演化、环境和 活动调度空间，但是该算法并没有利用调度问题固 原始祖先的局限性，经过相当长时间后，将逐渐进化 有的特征信息来加速收敛.考虑到SSP调度问题 到某些特征相对优势的状态，当一个种群进化到这 的加工可逆性，通过定义1可知，正、逆序调度方案 种状态，称为平衡态，这个种群的特性就不会再有很 之间是一一对应关系且具有相同的mak espan值，因 大的变化. 此‖Gm可以转化为求解其逆向问题.文献[5- 双种群遗传算法是一种并行遗传算法，它使用 6已经证明对于某些难于求解的调度问题，以正序 多种群同时进化，并交换种群之间优秀个体所携带 JSSP为基准按照逆序方式来生成染色体可能更具 的遗传信息，以打破种群内的平衡态达到更高的平 优势，可以较大程度地提高算法的求解效率，并在一 衡态，跳出局部最优.在操作时，首先建立两个遗传 定的程度上提高求解质量.因此，本文提出了一种 算法群体，即种群A和种群B分别独立地进行选 正逆序调度方法与GTGA相结合的双种群遗传算法 择、交叉和变异操作，且交叉概率、变异概率不同. (简记为FBGIGA),该算法以正逆序调度方法和活 当每一代运行结束以后，产生一个随机数u円分别 动调度技术为基础来设计相应的子种群初始化策 从AB中选出最优染色体和nm个染色体进行杂 略、交叉和变异操作，试图通过正逆序策略和空间缩 交，以打破平衡态，互相进入对方种群形成最优 减来提高算法的性能.其中种群A采用正序调度遗 解g 传算法，种群B采用逆序调度遗传算法.北 京 科 技 大 学 学 报 第 32卷 m-k+1台机器上加工;pij和 p → ij分别为工件 i在第 1 个和第 2个 JSSP的第 j台机器上的加工时间.令 nm 表示第 1个 JSSP的设备 k所加工的工件数, 则该设 备所加工的工件有序集可记为 πk ={πk ( 1 ), πk ( 2), …, πk(nm) }.如果第 2个 JSSP的设备 m-k+ 1所加工的工件有序集为 π → m-k+1 ={πk( nm ), …, πk( 2), πk( 1) }, 那么对应的最优调度方案分别称 为正序调度方案和逆序调度方案, 而对应的调度问 题分别称为原问题和逆向问题 ( reverseproblem) . 例如, 一个三个工件、三台设备的作业车间调度 方案, 加工时间数据如表 1 所示.图 1 给出了正序 和逆序情况下的调度甘特图.由图可以看出, 正序 调度方案与逆序调度方案的关键路径均由同一批工 序的加工时间所决定, 因此 makespan值不会发生变 化 (这两个调度图均为 13). 表 1 3×3作业车间调度问题描述 Table1 Descriptionofa3 ×3 jobshopschedulingproblem 工件号 工序编号 机器顺序 加工时间 J1 O11 , O12 , O13 M1 , M2 , M3 3, 4, 3 J2 O21 , O22 , O23 M2 , M1 , M3 3, 3, 2 J3 O31 , O32 , O33 M3 , M1 , M2 3, 5, 1 图 1 正 ( a) 、逆 ( b)序调度甘特图 Fig.1 Ganttchartsofforward( a) andbackwardscheduling(b) 2.3 求解策略 标准遗传算法是针对一个宏观的种群进行选 择 、交叉和变异三种操作, 类似于人类进化过程, 一 群人随着时间的推移而不断地进化, 具备越来越多 的优良品质 .然而, 由于他们的生长 、演化 、环境和 原始祖先的局限性, 经过相当长时间后, 将逐渐进化 到某些特征相对优势的状态, 当一个种群进化到这 种状态, 称为平衡态, 这个种群的特性就不会再有很 大的变化. 双种群遗传算法是一种并行遗传算法, 它使用 多种群同时进化, 并交换种群之间优秀个体所携带 的遗传信息, 以打破种群内的平衡态达到更高的平 衡态, 跳出局部最优.在操作时, 首先建立两个遗传 算法群体, 即种群 A和种群 B, 分别独立地进行选 择 、交叉和变异操作, 且交叉概率 、变异概率不同 . 当每一代运行结束以后, 产生一个随机数 num, 分别 从 A、B中选出最优染色体和 num个染色体进行杂 交, 以打破平衡态, 互相进入对方种群形成最优 解 [ 9] . 基于活动调度思想, 文献 [ 4]提出了一种 GT算 法与 GA相结合的求解算法 (记为 GTGA), 该文将 搜索空间限制为活动调度空间, 通过空间缩减来提 高算法的搜索效率 .虽然算法 GTGA可以遍历整个 活动调度空间, 但是该算法并没有利用调度问题固 有的特征信息来加速收敛.考虑到 JSSP调度问题 的加工可逆性, 通过定义 1可知, 正 、逆序调度方案 之间是一一对应关系且具有相同的 makespan值, 因 此 Jm‖ Cmax可以转化为求解其逆向问题 .文献 [ 5-- 6]已经证明对于某些难于求解的调度问题, 以正序 JSSP为基准按照逆序方式来生成染色体可能更具 优势, 可以较大程度地提高算法的求解效率, 并在一 定的程度上提高求解质量 .因此, 本文提出了一种 正逆序调度方法与 GTGA相结合的双种群遗传算法 (简记为 FBGTGA), 该算法以正逆序调度方法和活 动调度技术为基础来设计相应的子种群初始化策 略、交叉和变异操作, 试图通过正逆序策略和空间缩 减来提高算法的性能.其中种群 A采用正序调度遗 传算法, 种群 B采用逆序调度遗传算法. · 814·