基于正逆序策略求解Job Shop的遗传调度算法

D010.13374斤.issn10153x.200.06.024 第32卷第6期 北京科技大学学报 Vol32 No 6 2010年6月 Journal ofUniversity of Science and Technobgy Bejjing Jun 2010 基于正逆序策略求解Job Shor的遗传调度算法 王伟玲李铁克苏志雄 北京科技大学经济管理学院。北京100083 摘要针对标准遗传算法在求解车间作业调度问题中易陷入局部极值点的缺点，提出了一种基于领域知识的动态双种群 遗传算法.由于最优调度必定是活动调度，算法利用活动调度技术来进行空间缩减：两个子种群分别采用正、逆序调度策略来 提高种群的多样性。算法采用一种新的染色体编码来表示活动调度方案，并给出了相应子种群的初始化策略、遗传操作，以及 子种群之间的交叉方式.Bencmarki算例的仿真实验与分析表明，该算法在计算时间和求解质量上均具有较好的效果. 关键词车间作业调度：遗传算法：双种群，优化 分类号TP278 G enetic a lgoritlm with forward backward scheduling for job-shop problems WANGWeilng LITeke g Zhi-xiong Schpol of Econon ics and Mamgment University of Sc ience and Technopgy Beijng Beijing 100083 China ABSTRACT When he sandard genetic algritm s app lied np job shop schedu lng prob ms it has he common defects of earl convergence and easiy falling inp localmninization A dynam ic double popu ation genetic agoritm based on domain knowledge is applied into pb shop scheduling pr kms Snce the op tmal schedue is active the active scheduling technplue is used o reduce he search space Moreover the orward and backward schedu lng strategies are adop ted in prove the popu lation diversity by the two sub populatons respectivey A new chrmosome encod ing is used p represent the active schedul W ith this codng scheme he nitial ization strategy the genetic operations of every subpopu ation and the crossoveroperator beween he two subpopulatons are proposed Experinen al results of the Bendmark instances taken from literatures indicae hat it outperpms current approaches n con putational tie and quality of he sou tions KEY WORDS pb-sho schedulig genetic agorithm doble popu lation optmization 作业车间调度问题(b shop scheduling piob agorit四GA作为一种常用的元启发式算法，是 四SS是一类典型的生产调度问题，具有很 一种基于“优胜劣汰、适者生存”的高度并行、随机 强的工程背景，许多实际工程问题均可与之相转化. 和自适应优化算法，具有通用性、鲁棒性和隐含并行 近年来随着先进制造技术的发展，作业车间调度问 性等特点，适用于求解组合优化问题，因此标准遗传 题的含义有所拓展，增加了随机性、动态性、不确定 算法是被研究用来求解调度问题最多的算法之一. 性、约束性和多目标等，与实际生产更为接近. 但是，标准遗传算法容易陷入局部极值解，出现“早 目前，作业车间调度问题的研究方法主要包括 熟收敛”现象. 精确算法（如分支定界法、Lagrang松弛法，启发 文献[4]提出一种生成活动调度的遗传算法 式规则和元启发式算法（如模拟退火、遗传算法、 (Giffler Thompson genetie algoritm GIGA,它本质 禁忌搜索和蚁群算法！).其中精确算法只适合求 上是一种基于枚举的树搜索算法，所生成的活动调 解较小规模的问题：启发式规则求解快速然而其求 度中至少包含调度问题的一个最优解，数据实验证 解质量还有较大的改进空间：而遗传算法(genetic 明其对于大规模作业车间调度问题具有较好的求解 收稿日期.2009-07-31 基金项目：国家自然科学基金资助项目(NQ70371057.70771008) 作者简介：王伟玲(1976-)，女，博士研究生：李铁克(1958)，男，教授，博士生导师，Ema1e@163m

第 32卷 第 6期 2010年 6月 北 京 科 技 大 学 学 报 JournalofUniversityofScienceandTechnologyBeijing Vol.32 No.6 Jun.2010 基于正逆序策略求解 JobShop的遗传调度算法 王伟玲 李铁克 苏志雄 北京科技大学经济管理学院, 北京 100083 摘 要 针对标准遗传算法在求解车间作业调度问题中易陷入局部极值点的缺点, 提出了一种基于领域知识的动态双种群 遗传算法.由于最优调度必定是活动调度, 算法利用活动调度技术来进行空间缩减;两个子种群分别采用正、逆序调度策略来 提高种群的多样性.算法采用一种新的染色体编码来表示活动调度方案, 并给出了相应子种群的初始化策略、遗传操作, 以及 子种群之间的交叉方式.Benchmark算例的仿真实验与分析表明, 该算法在计算时间和求解质量上均具有较好的效果. 关键词 车间作业调度;遗传算法;双种群;优化 分类号 TP278 Geneticalgorithm withforward-backwardschedulingforjob-shopproblems WANGWei-ling, LITie-ke, SUZhi-xiong SchoolofEconomicsandManagement, UniversityofScienceandTechnologyBeijing, Beijing100083, China ABSTRACT Whenthestandardgeneticalgorithmisappliedintojob-shopschedulingproblems, ithasthecommondefectsofearly convergenceandeasilyfallingintolocalminimization.Adynamicdouble-populationgeneticalgorithmbasedondomainknowledgeis appliedintojob-shopschedulingproblems.Sincetheoptimalscheduleisactive, theactiveschedulingtechniqueisusedtoreducethe searchspace.Moreover, theforwardandbackwardschedulingstrategiesareadoptedtoimprovethepopulationdiversitybythetwosub￾populations, respectively.Anewchromosomeencodingisusedtorepresenttheactiveschedule.Withthiscodingscheme, theinitial￾izationstrategy, thegeneticoperationsofeverysubpopulationandthecrossoveroperatorbetweenthetwosubpopulationsareproposed. ExperimentalresultsoftheBenchmarkinstancestakenfromliteraturesindicatethatitoutperformscurrentapproachesincomputational timeandqualityofthesolutions. KEYWORDS job-shopscheduling;geneticalgorithm;double-population;optimization 收稿日期:2009--07--31 基金项目:国家自然科学基金资助项目 ( No.70371057, 70771008) 作者简介:王伟玲 ( 1976— ), 女, 博士研究生;李铁克 ( 1958— ), 男, 教授, 博士生导师, E-mail:tiekeli@163.com 作业车间调度问题 ( job-shopschedulingprob￾lem, JSSP) 是一类典型的生产调度问题 [ 1] , 具有很 强的工程背景, 许多实际工程问题均可与之相转化 . 近年来随着先进制造技术的发展, 作业车间调度问 题的含义有所拓展, 增加了随机性、动态性、不确定 性 、约束性和多目标等, 与实际生产更为接近. 目前, 作业车间调度问题的研究方法主要包括 精确算法 (如分支定界法 、Lagrangian松弛法 ), 启发 式规则 [ 2] 和元启发式算法 (如模拟退火、遗传算法 、 禁忌搜索和蚁群算法 ) [ 3] .其中精确算法只适合求 解较小规模的问题;启发式规则求解快速然而其求 解质量还有较大的改进空间;而遗传算法 ( genetic algorithm, GA) 作为一种常用的元启发式算法, 是 一种基于 “优胜劣汰 、适者生存 ”的高度并行 、随机 和自适应优化算法, 具有通用性、鲁棒性和隐含并行 性等特点, 适用于求解组合优化问题, 因此标准遗传 算法是被研究用来求解调度问题最多的算法之一. 但是, 标准遗传算法容易陷入局部极值解, 出现“早 熟收敛”现象. 文献 [ 4] 提出一种生成活动调度的遗传算法 ( Giffler-Thompsongeneticalgorithm, GTGA), 它本质 上是一种基于枚举的树搜索算法, 所生成的活动调 度中至少包含调度问题的一个最优解, 数据实验证 明其对于大规模作业车间调度问题具有较好的求解 DOI :10 .13374 /j .issn1001 -053x .2010 .06 .024

第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·

。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·

第6期 王伟玲等：基于正逆序策略求解Job Shop的遗传调度算法 815 因为在双种群遗传算法中，每一种群都是按照 其选择概率（本文中，优先规则为最早完工时间优 标准算法进行操作的，所以下面关于适应度、选择、 先(earliest completion tie EC)与随机规则(ram 交叉和变异的介绍，都是针对一个种群描述的. don nule RR,选择概率分别为0.2和0.8)，然后 3算法设计 执行GT算法的Stp1到SeP2 Stp2按概率选择优先规则，然后执行GT算 3.1设计子种群A 法的Sep3到Step4 子种群A采用正序调度遗传算法，问题的求解 Sp3若Q:为非空，则令仁中↓并确定第 按照原问题的顺序约束进行各个操作，详细设计如 道工序集合S的优先规则及其选择概率（本文中， 下所述 优先规则为ECT RR与最早开工时间优先(earlijest 3.1.1染色体编码 starting ti,eEST,选择概率分别为0.3.0.5和 编码问题是设计遗传算法求解调度问题的首要 0.2,然后转到GT算法的Sp2 和关键问题，在群体中每条染色体表示问题的一个 Sp4重复Sep1到Stp4直到生成初始种 解，需要考虑染色体的合法性、可行性、有效性以及 群为止 对问题解空间表征的完全性四.SP调度常用的 3.1.3GT咬叉操作 编码方式有基于操作的编码、基于工件的编码、基于 交叉算子用于随机交换种群中的两个父代个体 先后表的编码、基于工件对关系的编码、基于优先规 的某些基因，在解空间中进行有效搜索，从而组合出 则的编码以及随机键编码等.在本文中，染色体编 新的子代个体，它是遗传算法的最重要操作，决定遗 码用矩阵X来表示一条染色体，则可以将其分成三 传算法的全局搜索能力.正序调度算法的交叉操作 部分X、苓和茎其中是由m个小段组成，每个 可以描述如下， 小段M(主l2,m叫对应哈机器上的个工件 St1令双亲中较好的父辈的选择概率为 的完工时间，苓对应解的makepan值，苓则对应编 0.7另外一个父辈的选择概率为0.3 码的生成方式（正序取值为Q逆序为1），因此它的 Stp2执行GT算法的Step1到SteP2 长度为mX叶1如图2所示. Stp3令Gm为S需要机器m进行加工的 染色体X 操作 SP4在两个父辈个体中选择一个个体B并 在冲突集合G的所有操作找到在个体P中以最 ①①..C Direction 早可能开工的工序，在后代个体中以最早可能 …图 开工时间中o:=maY:,5:)将此工件安排到设 图2染色体编码 备m上加工. F 2 Chrmosome coding Step5执行GT算法的Step4到Step5 3.1.4GT变异操作 当算法收敛以后，对于每台设备M(≠12 变异有利于遗传算法跳离搜索空间的一个固定 ,m)需要根据最优染色体的完工时间与生成方式 区域，搜索更广阔的解空间，以改善算法的局部搜索 信息来生成完整的正序调度方案.其生成过程可以 能力，维持群体的多样性，防止算法出现早熟收敛的 描述如下：根据direction信息来选择问题的相关数 据，如果directia=L还需要将完工时间“调整”为 作用.正序调度算法的变异操作过程可以描述 如下： 正序情况下的相对数值；最后，根据最早完工时间优 先的规则，以GT算法为基础来生成完整的调度 Step1执行GT算法的Sep1到SteP2 方案. Sp2令Gm为S需要机器m进行加工的 3.12初始种群 操作. 本文利用G算法按照正序方式来产生初始种 S即3产生一个随机数e∈[01)，并与变异 群，进而保证初始种群具有较高的质量，且不失初 概率Pm∈[01)比较大小（本文取Pm=0.6).如果 始种群的多样性.正序调度算法的种群初始化方法 <P则从冲突集.中随机挑选一道工序C, 可以描述如下， 否则从冲突集G·里面找出一个在父辈里最早被加 SeP1确定第1道工序集合S的优先规则及 工的工序O,然后，以最早可能开工时间o:=

第 6期 王伟玲等:基于正逆序策略求解 JobShop的遗传调度算法 因为在双种群遗传算法中, 每一种群都是按照 标准算法进行操作的, 所以下面关于适应度 、选择 、 交叉和变异的介绍, 都是针对一个种群描述的 . 3 算法设计 3.1 设计子种群 A 子种群 A采用正序调度遗传算法, 问题的求解 按照原问题的顺序约束进行各个操作, 详细设计如 下所述 . 3.1.1 染色体编码 编码问题是设计遗传算法求解调度问题的首要 和关键问题, 在群体中每条染色体表示问题的一个 解, 需要考虑染色体的合法性、可行性、有效性以及 对问题解空间表征的完全性 [ 10] .JSSP调度常用的 编码方式有基于操作的编码、基于工件的编码 、基于 先后表的编码、基于工件对关系的编码、基于优先规 则的编码以及随机键编码等 .在本文中, 染色体编 码用矩阵 X来表示一条染色体, 则可以将其分成三 部分 x1 、x2 和 x3, 其中 x1 是由 m个小段组成, 每个 小段 Mj(j=1, 2, …, m)对应 m台机器上的 n个工件 的完工时间, x2 对应解的 makespan值, x3 则对应编 码的生成方式 (正序取值为 0, 逆序为 1) , 因此它的 长度为 m×n+1, 如图 2所示. 图 2 染色体编码 Fig.2 Chromosomecoding 当算法收敛以后, 对于每台设备 Mj( j=1, 2, …, m)需要根据最优染色体的完工时间与生成方式 信息来生成完整的正序调度方案.其生成过程可以 描述如下:根据 direction信息来选择问题的相关数 据, 如果 direction=1, 还需要将完工时间 “调整 ”为 正序情况下的相对数值;最后, 根据最早完工时间优 先的规则, 以 GT算法为基础来生成完整的调度 方案. 3.1.2 初始种群 本文利用 GT算法按照正序方式来产生初始种 群, 进而保证初始种群具有较高的质量, 且不失初 始种群的多样性 .正序调度算法的种群初始化方法 可以描述如下. Step1 确定第 1道工序集合 S1 的优先规则及 其选择概率 (本文中, 优先规则为最早完工时间优 先 (earliestcompletiontime, ECT) 与随机规则 (ran￾domrule, RR), 选择概率分别为 0.2和 0.8), 然后 执行 GT算法的 Step1到 Step2. Step2 按概率选择优先规则, 然后执行 GT算 法的 Step3到 Step4. Step3 若 Qt+1为非空, 则令 t=t+1, 并确定第 t道工序集合 St的优先规则及其选择概率 (本文中, 优先规则为 ECT, RR与最早开工时间优先 ( earliest startingtime, EST), 选择概率分别为 0.3、 0.5 和 0.2), 然后转到 GT算法的 Step2. Step4 重复 Step1到 Step4, 直到生成初始种 群为止. 3.1.3 GT交叉操作 交叉算子用于随机交换种群中的两个父代个体 的某些基因, 在解空间中进行有效搜索, 从而组合出 新的子代个体, 它是遗传算法的最重要操作, 决定遗 传算法的全局搜索能力 .正序调度算法的交叉操作 可以描述如下 . Step1 令双亲中较好的父辈的选择概率为 0.7, 另外一个父辈的选择概率为 0.3. Step2 执行 GT算法的 Step1到 Step2. Step3 令 Gm＊为 St需要机器 m ＊ t 进行加工的 操作 . Step4 在两个父辈个体中选择一个个体 ps, 并 在冲突集合 Gm＊的所有操作找到在个体 ps中以最 早可能开工的工序 O ＊ ij, 在后代个体中以最早可能 开工时间 O＊ij =max( Tm＊t , rO＊ij )将此工件安排到设 备 m ＊ t 上加工 . Step5 执行 GT算法的 Step4到 Step5. 3.1.4 GT变异操作 变异有利于遗传算法跳离搜索空间的一个固定 区域, 搜索更广阔的解空间, 以改善算法的局部搜索 能力, 维持群体的多样性, 防止算法出现早熟收敛的 作用 .正序调度算法的变异操作过程可以描述 如下 : Step1 执行 GT算法的 Step1到 Step2. Step2 令 Gm＊为 St需要机器 m ＊ t 进行加工的 操作 . Step3 产生一个随机数 ε∈ [ 0, 1), 并与变异 概率 Pm∈ [ 0, 1)比较大小 (本文取 Pm =0.6).如果 ε<Pm, 则从冲突集 Gm＊中随机挑选一道工序 O ＊ ij, 否则从冲突集 Gm＊里面找出一个在父辈里最早被加 工的工序 O ＊ ij, 然后, 以最早可能开工时间 O＊ij = · 815·

。816 北京科技大学学报 第32卷 mYT,)将此工件安排到设备m上加工. 「34 3 Step4执行GI算法的Sep4到Step5 矩阵 T-= 3 2, 将和T分别上下翻转而后 3.2设计子种群B L35 子种群B采用逆序调度算法具体步骤如下 左右翻转得到： (1)首先，根据约束条件(1)和(2)对原问题的 9 83 相关数据进行变换即转换为逆向问题的数据，具体 地讲就是将加工时间矩阵和机器顺序矩阵分别进行 13113, 1073 上下翻转而后左右翻转进行转换，如表1所示的车 间作业调度问题的机器顺序矩阵为= 「153 123 「343 T=233, 21 对应的时间矩阵T=334,则其逆 L343 31 L351 则代入求解式(1)~(3得到： 「213「153 问题的数据即为k31王，T23 X=多-文+T= L321L343 「9 83「153 「51013 (2)然后，根据正序调度算法的步骤执行逆序 13- 13 113十233= 2 5 13, 调度算法.也就是说，正、逆序调度算法染色体编码 10 7 3L343 L61013 用的步骤是相同的，但是输入的数据不同. 等=多=13 3.3种群交叉 y=↓ 将两个子种群和B中的最优解取出，再在每 个种群中随机选取num个染色体将这nunm个染色 则逆序染色体即为所求 体经过相互转换后进行互换，进入对方种群. 同理，可以通过逆序调度方案的染色体x求得 假设正序染色体为￥逆序染色体为子则正逆 正序调度方案的染色体X 序染色体之间转换的具体过程如下. 4计算实验 对于染色体的第1部分来讲，首先将矩阵丫及 其对应的加工时间矩阵T上下翻转而后左右翻转 4.1测试数据与参数 得到X和T接着用调度方案的最大完工时间减 本文采用Mab编程语言，在CHU主频 去将会得到其对应逆问题的工序开工时间矩阵， 253GHz2GRAM的PC机上进行算法实现. 算例的所有数据均来自OR-lba的Job Shop 最后加上与逆问题所对应的加工时间矩阵则得到 排序的T和LA系列问题.算法选用的基本参数 其逆序染色体的第一部分，如下式所示： 为：子种群的规模均为PopS ize-40交叉概率P.= X=-X十T (3) 0.6子种群交叉的染色体个数num=5算法的终止 对于染色体的第2部分来讲，染色体对应的适 条件为：最大运行代数为10000最大运行时间为 应度值不论正序还是逆序保持不变，如下式所示： 1600,S适应度值达到当前最优值OP.t如果算法没 $=y (4) 有找到最优解，则将目前找到的“最好解”作为最终 对于染色体的第3部分来讲，如果=0则 调度解其对应的M akespan为m在本文的研究 =上反之亦然.如下式所示： 中，通过计算Cmax与当前最优值OP的相对误差来 1￥=0 0等=1 5) 判断算法的有效性，如下式所示： 由、和组成逆向染色体￥ Cs-OPt de OPt一X100% (6) 以上面图2所示的正逆序调度方案为例，进一 步说明正逆序染色体和之间的关系. 42实验结果与分析 通过正序调度甘特图可以知道正序染色体为 针对43个不同规模T和LA系列基准算例， 「3710 表2列出了算法FBGIGA各运行10次后的实验结 X=31113,￥=13等=0对应的加工时间 果以及蚁群算法MFBA的、混合遗传算法 L389 HGA、两层粒子群算法PT-SPPS)的实验结

北 京 科 技 大 学 学 报 第 32卷 max(Tm＊t , rO＊ij )将此工件安排到设备 m ＊ t 上加工 . Step4 执行 GT算法的 Step4到 Step5. 3.2 设计子种群 B 子种群 B采用逆序调度算法, 具体步骤如下. ( 1) 首先, 根据约束条件 ( 1)和 ( 2)对原问题的 相关数据进行变换即转换为逆向问题的数据, 具体 地讲就是将加工时间矩阵和机器顺序矩阵分别进行 上下翻转而后左右翻转进行转换, 如表 1所示的车 间作 业 调 度 问 题 的 机 器 顺 序 矩 阵 为 JM = 1 2 3 2 1 3 3 1 2 , 对应的时间矩阵 T= 3 4 3 3 3 2 3 5 1 , 则其逆 问题的数据即为 J → M = 2 1 3 3 1 2 3 2 1 , T → = 1 5 3 2 3 3 3 4 3 . ( 2) 然后, 根据正序调度算法的步骤执行逆序 调度算法.也就是说, 正 、逆序调度算法染色体编码 用的步骤是相同的, 但是输入的数据不同 . 3.3 种群交叉 将两个子种群 A和 B中的最优解取出, 再在每 个种群中随机选取 num个染色体, 将这 num个染色 体经过相互转换后进行互换, 进入对方种群. 假设正序染色体为 x, 逆序染色体为 x → , 则正逆 序染色体之间转换的具体过程如下. 对于染色体的第 1部分来讲, 首先将矩阵 x1 及 其对应的加工时间矩阵 T上下翻转而后左右翻转 得到 x 1和 T → , 接着用调度方案的最大完工时间 x2 减 去 x → 1将会得到其对应逆问题的工序开工时间矩阵, 最后加上与逆问题所对应的加工时间矩阵 T → 则得到 其逆序染色体的第一部分 x → 1, 如下式所示: x → 1 =x2 -x 1 +T → ( 3) 对于染色体的第 2部分来讲, 染色体对应的适 应度值不论正序还是逆序保持不变, 如下式所示: x2 =x → 2 ( 4) 对于染色体的第 3 部分来讲, 如果 x3 =0, 则 x → 3 =1;反之亦然.如下式所示: x → 3 = 1, x3 =0 0, x3 =1 ( 5) 由 x → 1 、x → 2和 x → 3组成逆向染色体 x →. 以上面图 2所示的正逆序调度方案为例, 进一 步说明正逆序染色体 x和 x →之间的关系. 通过正序调度甘特图可以知道正序染色体 x为 x1 = 3 7 10 3 11 13 3 8 9 , x2 =13, x3 =0, 对应的加工时间 矩阵 T= 3 4 3 3 3 2 3 5 1 , 将 x1 和 T分别上下翻转而后 左右翻转得到 : x 1 = 9 8 3 13 11 3 10 7 3 , T → = 1 5 3 2 3 3 3 4 3 , 则代入求解式 ( 1) ～ ( 3)得到: x → 1 =x2 -x 1 +T → = 13 - 9 8 3 13 11 3 10 7 3 + 1 5 3 2 3 3 3 4 3 = 5 10 13 2 5 13 6 10 13 , x → 2 =x2 =13, x → 3 =1, 则逆序染色体 x → 即为所求 . 同理, 可以通过逆序调度方案的染色体 x → 求得 正序调度方案的染色体 x. 4 计算实验 4.1 测试数据与参数 本文 采 用 Matlab编 程 语言, 在 CPU主 频 2.53 GHz, 2GRAM的 PC机上进行算法实现 . 算例的所有数据均来自 OR-library的 JobShop 排序的 FT和 LA系列问题 .算法选用的基本参数 为:子种群的规模均为 PopSize=40;交叉概率 Pc = 0.6;子种群交叉的染色体个数 num=5;算法的终止 条件为:最大运行代数为 10 000, 最大运行时间为 1 600 s, 适应度值达到当前最优值 Opt.如果算法没 有找到最优解, 则将目前找到的 “最好解 ”作为最终 调度解, 其对应的 Μakespan为 C ＊ max.在本文的研究 中, 通过计算 C ＊ max与当前最优值 Opt的相对误差来 判断算法的有效性, 如下式所示: %dev= C ＊ max -Opt Opt ×100% ( 6) 4.2 实验结果与分析 针对 43个不同规模 FT和 LA系列基准算例, 表 2列出了算法 FBGTGA各运行 10 次后的实验结 果, 以 及 蚁 群 算 法 MFBAnt [ 6] 、 混 合 遗 传 算 法 HGA [ 11] 、两层粒子群算法 PT-JSP-PSO [ 12] 的实验结 · 816·