第6期 王伟玲等：基于正逆序策略求解Job Shop的遗传调度算法 ·813° 效果，但该算法并没有利用调度问题固有的特征信 Q={O|≠12,9≠12，m为当前所 息来加速算法收敛.文献[5-6]提出一种基于正逆 有待加工工序的集合： 序调度策略的蚁群算法及其改进算法，大量的数据 S为当前迭代中所有可调度的工序集合； 实验证明对有的问题而言，逆问题比原问题更容易 伪工序O对应的工件到达机器的时间且 求解，且如果算法将正逆序调度相结合，则在不增加 等于上一工序O的完工时间，即= 额外求解时间的前提下可以极大地提高问题的求解 F1(V,iY)在初始时刻=0V,iV方 质量，但这种算法并没有利用可以缩减搜索空间的 T为当前迭代中机器的最早可用时间，与机 活动调度算法， 器止排在工件之前的工件的完工时间相等 针对上述问题，本文进一步分析了作业车间调 即T=(H,iH在初始时刻T=0(Hj: 度问题的加工可逆性，提出一种基于正、逆序策略和 中o为集合S中工序O的最早可完工时间： 活动调度的双种群并行进化遗传算法，第1个子种 Gm为当前迭代中竞争机器m的工序集合. 群采用正序调度遗传算法，第2个子种群采用逆序 [GT算法] 调度遗传算法.两个子种群通过在活动调度的不同 S迎1令上1S为所有待加工工件的第1道 区域分别进行搜索来扩展解的搜索空间，可以提高 工序集合. 个体的多样性：通过定期进行信息交换协同求解，可 Sp2确定集合S中最早可完工的工序 以提高算法的全局搜索能力，从而加速算法收敛速 度，避免出现早熟而陷于局部最优解.通过基于 :=o,=may万动+}以及加工 B enchmak算例的对比实验，验证了该算法的有 中：的机器m,接着确定机器m上的冲突集 效性. Cm={O长SlK中：). S迎3根据启发式规则，从冲突集Cm里面挑 1问题描述 选一道工序并记作O,以最早可能开工时间中；= 作业车间调度问题可以简单地描述如下”.有 ma平T,b将此工件安排到设备m上加工. 个待加工的工件J={12；需要在m怡不同 StP4更新所有待加工工序集合Q和所有 的机器M={12m上加工，并满足以下基本假 可调度工序集合S+·由Q,中删除工序 定：①开始调度时，机器与工件均处于可用状态：② Q41=Q/AO片：由S中删除操作，并添加工件 在任意时刻每台机器最多只能加工一个工件：③每 的下道工序到来生成集合S,即S1=SU 个工件在某一时刻最多只能被一台设备加工：④每 {G#1}/八0. 个工件在每台机器上加工一次且仅一次并分别按 Stp5若Q1为非空，则令=什l并转到 指定的工艺路线通过所有的机器；⑤工件在某台机 Stp2否则，结束算法. 器上一旦开始加工后，就不允许中断：⑥工件在每台 2.2加工可逆性 机器的加工时间已知：⑦设备调整时间和工件传送 Pmeo在其专著中证明了流水车间调度问题 时间忽略不计.作业车间调度问题具有P-ha特 的加工可逆性，这种性质对于本文所考虑的作业车 性，个工件m台机器的作业车间调度问题的解空 间包括(n)个不同的排列.按照aIB|Y三参数 间调度问题也成立，且可以描述如下：对于作业车间 法[，目标函数为最小化时间跨度(make)的经 调度问题的任意一个工件加工顺序方案，如果工件 按照相反的排列次序来安排生产，那么对应的最优 典作业车间调度问题可以归结为‖Gmx 调度方案具有相同的makespan值，也就是说逆序调 2模型的求解思路 度不改变m akespan值.对于此种性质，可以给出以 2.1活动调度技术 下定义. 对于‖Gm问题，由于最优调度必定是活动 定义1如果两个具有个工件的JSSP满足 调度(active schedu月，如果调度算法只搜索活动调 以下条件： 度空间，可在很大程度上提高算法的搜索效率.文 M =Mm,V.iVk (1) 献[4给出了一种可以产生所有可能活动调度的 B=B-i V,i Vj (2) Giffer-Thonpson(G算法，该算法可以描述如下. 式中，M"和M为任意工件在第1个SSP中是 符号说明： 在第k始机器上加工，则在第2个SSP中就是在第第 6期 王伟玲等:基于正逆序策略求解 JobShop的遗传调度算法 效果, 但该算法并没有利用调度问题固有的特征信 息来加速算法收敛.文献 [ 5--6]提出一种基于正逆 序调度策略的蚁群算法及其改进算法, 大量的数据 实验证明对有的问题而言, 逆问题比原问题更容易 求解, 且如果算法将正逆序调度相结合, 则在不增加 额外求解时间的前提下可以极大地提高问题的求解 质量, 但这种算法并没有利用可以缩减搜索空间的 活动调度算法. 针对上述问题, 本文进一步分析了作业车间调 度问题的加工可逆性, 提出一种基于正、逆序策略和 活动调度的双种群并行进化遗传算法, 第 1 个子种 群采用正序调度遗传算法, 第 2个子种群采用逆序 调度遗传算法.两个子种群通过在活动调度的不同 区域分别进行搜索来扩展解的搜索空间, 可以提高 个体的多样性;通过定期进行信息交换协同求解, 可 以提高算法的全局搜索能力, 从而加速算法收敛速 度, 避免出现早熟而陷于局部最优解.通过基于 Benchmark算例的对比实验, 验证了该算法的有 效性. 1 问题描述 作业车间调度问题可以简单地描述如下 [ 7] .有 n个待加工的工件 J={1, 2, …, n}需要在 m台不同 的机器 M={1, 2, …, m}上加工, 并满足以下基本假 定 :①开始调度时, 机器与工件均处于可用状态 ;② 在任意时刻每台机器最多只能加工一个工件 ;③每 个工件在某一时刻最多只能被一台设备加工 ;④每 个工件在每台机器上加工一次且仅一次, 并分别按 指定的工艺路线通过所有的机器;⑤工件在某台机 器上一旦开始加工后, 就不允许中断 ;⑥工件在每台 机器的加工时间已知;⑦设备调整时间和工件传送 时间忽略不计.作业车间调度问题具有 NP-hard特 性, n个工件 m台机器的作业车间调度问题的解空 间包括 ( n!) m 个不同的排列.按照 α β γ三参数 法 [ 8] , 目标函数为最小化时间跨度 ( makespan) 的经 典作业车间调度问题可以归结为 Jm‖ Cmax. 2 模型的求解思路 2.1 活动调度技术 对于 Jm‖ Cmax问题, 由于最优调度必定是活动 调度 ( activeschedule), 如果调度算法只搜索活动调 度空间, 可在很大程度上提高算法的搜索效率.文 献 [ 4] 给出了一种可以产生所有可能活动调度的 Giffler--Thompson( GT)算法, 该算法可以描述如下. 符号说明: Qt={Oij i=1, 2, …, n;j=1, 2, …, m}为当前所 有待加工工序的集合; St为当前迭代 t中所有可调度的工序集合 ; rij为工序 Oij对应的工件 i到达机器 j的时间且 等于上 一工序 Oi( j-1) 的 完工 时间 t E i, j-1, 即 rij= t E i, j-1 ( i, j), 在初始时刻 rij=0( i, j); Tj为当前迭代 t中机器 j的最早可用时间, 与机 器 j上排在工件 i之前的工件 k的完工时间 t E kj相等, 即 Tj=t E kj( i, j), 在初始时刻 Tj=0( j) ; Oij为集合 St中工序 Oij的最早可完工时间 ; Cm＊为当前迭代 t中竞争机器 m ＊ t 的工序集合 . [ GT算法] Step1 令 t=1, St为所有待加工工件的第 1道 工序集合 . Step2 确定集合 St中最早可完工的工序 ＊ t =Ominij∈ St { Oij}=Ominij∈ St {max( Tj, rij) +pij}以及加工 ＊ t 的机器 m ＊ t, 接着确定机器 m ＊ t 上的冲突集 Cm＊ ={Oij∈ St rij< ＊ t }. Step3 根据启发式规则, 从冲突集 Cm＊里面挑 选一道工序并记作 O ＊ ij, 以最早可能开工时间 O＊ij = max( Tm＊t , rO＊ij )将此工件安排到设备 m ＊ t 上加工. Step4 更新所有待加工工序集合 Qt+1和所有 可调度工序集合 St+1 .由 Qt+1中删除工序 O ＊ ij, Qt+1 =Qt/{O ＊ ij };由 St中删除操作 O ＊ ij, 并添加工件 的下道 工序到 来生成集 合 St+1, 即 St+1 =St∪ {O ＊ i, j+1}/{O ＊ ij}. Step5 若 Qt+1为非空, 则令 t=t+1, 并转到 Step2;否则, 结束算法 . 2.2 加工可逆性 Pinedo在其专著 [ 8] 中证明了流水车间调度问题 的加工可逆性, 这种性质对于本文所考虑的作业车 间调度问题也成立, 且可以描述如下:对于作业车间 调度问题的任意一个工件加工顺序方案, 如果工件 按照相反的排列次序来安排生产, 那么对应的最优 调度方案具有相同的 makespan值, 也就是说逆序调 度不改变 makespan值.对于此种性质, 可以给出以 下定义. 定义 1 如果两个具有 n个工件的 JSSP满足 以下条件 : M ( k) =M → ( m-k+1) , i, k ( 1) pij=p → m+1 -i, j, i, j ( 2) 式中, M ( k)和 M → ( k)为任意工件 i在第 1个 JSSP中是 在第 k台机器上加工, 则在第 2个 JSSP中就是在第 · 813·