基于正逆序策略求解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·

第6期 王伟玲等：基于正逆序策略求解Job Shop的遗传调度算法 817 果，其中MFBAn的运行环境为2.4GH1GRAM 指出的是，加粗数值表示对应算例己达到目前已知 P℃HGA的运行环境为L.33 GHz AMD Thundebird 的最优值，且文献[6并没有给出算例L31~LA35 PCPT-JSP-PSO的运行环境为16O0MHzC值得 的实验结果，在此用VA示意 表2 FBGTGA算法Benchmarks实测结果 Table2 Results of FBGIGA a Forithm on Bendmak Probkms 规模 CGA算法测试结果 MFBAnta HGAI PT-JSP-PSO 2 算例 OPt m %dev时间/sCam %dew时间/sCmm dev 时间/ 。C %dew时间/s F106 6X6 5 55000046 55000 时 000 3 55 000 107 FTio 10×10 930 930 000 43 930 000 6 930 000 292 930 000 406 F20 20X5 1165 1165 000 5.5 1165 000 235 1166 000 204 1165 000 449 L01 10X5 666 666 000 1.4 666 000 6 66 000 37 666 000 168 LA02 10X5 655 655 000 3.7 655 000 655 000 51 655 000 168 LA03 10X5 59 597 000 68 597 000 37 597 000 39 597 000 168 L04 10X5 5 000 9.4 590 000 38 000 590 000 168 LA05 10X5 9 92 000 45 593 000 36 59g 000 593 000 168 L06 15X5 000 32 926 000 926 000 926 000 304 L07 15X5 g90 000 13.9 890 000 102 890 000 890 000 304 LA08 15X5 000 5.7 0 00 000 863 000 L09 15X5 951 时 000 5.1 os 0 物 000 951 000 吃 LAIO 15X5 000 32 0 000 9 958 000 LAL 20X5 1229 1222 000 51 1222 % 122 000 19 1222 000 450 LAI2 20X5 1039 1039 000 45 1039 000 235 1039 000 201 1039 000 450 LAI3 20x5 1150 1150 000 5.6 1150 00 235 1150 000 189 1150 000 450 LA14 20x5 1292 1292 000 1292 0 238 1292 000 187 1292 000 450 LAI5 20X5 1207 1207 000 1207 000 236 120m 000 187 1207 000 450 1A16 10X10 945 945 000 947 021 161 945 000 232 945 000 412 IAIZ 10X10 784 心 000 保 000 160 浅 000 216 784 000 412 1A18 10×10 848 848 000 848 000 000 219 848 000 412 LA1910X10 842 842 000 848 071 162 000 235 842 000 412 LA20 10X10 902 902 000 12.7 907 0 161 055 235 907 055 412 IA21 15X10 1046 1051 048 56 1063 63 902 1046 000 602 1060 134 763 LA22 15X10 927 938 119 63 944 1 83 900 935 086 629 935 086 763 LA23 15X10 1032 1032 000 13 1032 898 1032 000 1032 000 763 1A24 15X×10 935 948 139 62 940 053 193 578 944 096 763 LA25 15X10 97 072 58 989 123 904 98%6 092 609 984 072 763 LA26 20X10 1216 1218 016 3 1220 033 8763 016 1388 1218 016 1165 LA27 20×10 1235 1238 024 1240 040 8558 1256 170 1251 1258 186 1165 LA28 20×10 1216 1218 016 87 1247 255 8559 1232 132 1267 1218 016 1165 LA29 20×10 1152 1185 286 9%6 1162 087 8560 1196 1350 1184 278 1165 LA30 20X10 1355 1355 000 1365 074 8560 135$ 000 1260 1355 000 1165 LA31 30X10 1784 1784 000 478 N/A N/A N/ 1784 000 3745 1784 000 2353 L32 30X10 1850 1850 000 463 NA N/A N/A 18s0 000 3741 1850 000 2353 LA33 30X10 1719 1719 000 485 N/A N/A N/A 1719 0 00 3637 1719 000 2353 1A34 30×10 1721 1721 000 496 N/A N/A N/A 1721 000 3615 1721 000 2353 LA3530X10 1888 1888 000 583 NA N/A N/A 1888 000 3716 1888 Q00 2353 LA36 15X15 1268 1270 016 385 1300 252 12618 1279 087 1826 1278 079 1401 LA37 15X15 1397 1404 050 274 1439 301 12614 1408 079 1860 1410 093 1401 LA38 15X15 1196 1198 017 286 1224 234 12620 1219 192 1859 1221 209 1401 LA39 15X15 1233 1245 097 293 1262 235 12619 1246 105 1869 1251 1.46 1401 IA40 15X15 1222 1228 049 386 1250 229 126位4 1241 155 2185 1229 057 1401 平均值 024123 060 2832 044 1009 038 877

第 6期 王伟玲等:基于正逆序策略求解 JobShop的遗传调度算法 果, 其中 MFBAnt的运行环境为 2.4 GHz/1 GRAM PC, HGA的运行环境为 1.33 GHzAMDThunderbird PC, PT-JSP-PSO的运行环境为 1 600 MHzPC.值得 指出的是, 加粗数值表示对应算例已达到目前已知 的最优值, 且文献 [ 6] 并没有给出算例 LA31 ～ LA35 的实验结果, 在此用 N/A示意 . 表 2 FBGTGA算法 Benchmark实测结果 Table2 ResultsofFBGTGAalgorithmonBenchmarkproblems 算例 规模 n×m Opt. CGA算法测试结果 MFBAnt[ 6] HGA[ 11] PT-JSP-PSO[ 12] C＊ max %dev 时间 /s C＊ max %dev 时间 /s C＊ max %dev 时间 /s C＊ max %dev 时间/s FT06 6×6 55 55 0.00 0.46 55 0.00 34 55 0.00 13 55 0.00 107 FT10 10×10 930 930 0.00 4.3 930 0.00 162 930 0.00 292 930 0.00 406 FT20 20×5 1 165 1 165 0.00 5.5 1 165 0.00 235 1 165 0.00 204 1 165 0.00 449 LA01 10×5 666 666 0.00 1.4 666 0.00 36 666 0.00 37 666 0.00 168 LA02 10×5 655 655 0.00 3.7 655 0.00 36 655 0.00 51 655 0.00 168 LA03 10×5 597 597 0.00 6.8 597 0.00 37 597 0.00 39 597 0.00 168 LA04 10×5 590 590 0.00 9.4 590 0.00 38 590 0.00 42 590 0.00 168 LA05 10×5 593 593 0.00 4.5 593 0.00 36 593 0.00 32 593 0.00 168 LA06 15×5 926 926 0.00 3.2 926 0.00 101 926 0.00 99 926 0.00 304 LA07 15×5 890 890 0.00 13.9 890 0.00 102 890 0.00 86 890 0.00 304 LA08 15×5 863 863 0.00 5.7 863 0.00 101 863 0.00 99 863 0.00 304 LA09 15×5 951 951 0.00 5.1 951 0.00 103 951 0.00 94 951 0.00 304 LA10 15×5 958 958 0.00 3.2 958 0.00 102 958 0.00 91 958 0.00 304 LA11 20×5 1 222 1 222 0.00 5.1 1 222 0.00 236 1 222 0.00 197 1 222 0.00 450 LA12 20×5 1 039 1 039 0.00 4.5 1 039 0.00 235 1 039 0.00 201 1 039 0.00 450 LA13 20×5 1 150 1 150 0.00 5.6 1 150 0.00 235 1 150 0.00 189 1 150 0.00 450 LA14 20×5 1 292 1 292 0.00 8.3 1 292 0.00 238 1 292 0.00 187 1 292 0.00 450 LA15 20×5 1 207 1 207 0.00 5.3 1 207 0.00 236 1 207 0.00 187 1 207 0.00 450 LA16 10×10 945 945 0.00 5.4 947 0.21 161 945 0.00 232 945 0.00 412 LA17 10×10 784 784 0.00 6.8 784 0.00 160 784 0.00 216 784 0.00 412 LA18 10×10 848 848 0.00 7.2 848 0.00 162 848 0.00 219 848 0.00 412 LA19 10×10 842 842 0.00 4.6 848 0.71 162 842 0.00 235 842 0.00 412 LA20 10×10 902 902 0.00 12.7 907 0.55 161 907 0.55 235 907 0.55 412 LA21 15×10 1 046 1 051 0.48 56 1 063 1.63 902 1 046 0.00 602 1 060 1.34 763 LA22 15×10 927 938 1.19 63 944 1.83 900 935 0.86 629 935 0.86 763 LA23 15×10 1 032 1 032 0.00 13 1 032 0.00 898 1 032 0.00 594 1 032 0.00 763 LA24 15×10 935 948 1.39 62 940 0.53 905 953 1.93 578 944 0.96 763 LA25 15×10 977 984 0.72 58 989 1.23 904 986 0.92 609 984 0.72 763 LA26 20×10 1 216 1 218 0.16 73 1 220 0.33 8 763 1 218 0.16 1 388 1 218 0.16 1 165 LA27 20×10 1 235 1 238 0.24 79 1 240 0.40 8 558 1 256 1.70 1 251 1 258 1.86 1 165 LA28 20×10 1 216 1 218 0.16 87 1 247 2.55 8 559 1 232 1.32 1 267 1 218 0.16 1 165 LA29 20×10 1 152 1 185 2.86 96 1 162 0.87 8 560 1 196 3.82 1 350 1 184 2.78 1 165 LA30 20×10 1 355 1 355 0.00 95 1 365 0.74 8 560 1 355 0.00 1 260 1 355 0.00 1 165 LA31 30×10 1 784 1 784 0.00 478 N/A N/A N/A 1 784 0.00 3 745 1 784 0.00 2 353 LA32 30×10 1 850 1 850 0.00 463 N/A N/A N/A 1 850 0.00 3 741 1 850 0.00 2 353 LA33 30×10 1 719 1 719 0.00 485 N/A N/A N/A 1 719 0.00 3 637 1 719 0.00 2353 LA34 30×10 1 721 1 721 0.00 496 N/A N/A N/A 1 721 0.00 3 615 1 721 0.00 2 353 LA35 30×10 1 888 1 888 0.00 583 N/A N/A N/A 1 888 0.00 3716 1 888 0.00 2 353 LA36 15×15 1 268 1 270 0.16 385 1 300 2.52 12 618 1 279 0.87 1 826 1 278 0.79 1 401 LA37 15×15 1 397 1 404 0.50 274 1 439 3.01 12 614 1 408 0.79 1 860 1 410 0.93 1 401 LA38 15×15 1 196 1 198 0.17 286 1 224 2.34 12 620 1 219 1.92 1 859 1 221 2.09 1 401 LA39 15×15 1 233 1 245 0.97 293 1 262 2.35 12 619 1 246 1.05 1 869 1251 1.46 1 401 LA40 15×15 1 222 1 228 0.49 386 1 250 2.29 12 624 1 241 1.55 2 185 1 229 0.57 1 401 平均值 0.24 123 0.60 2 832 0.44 1 009 0.38 877 · 817·

。818 北京科技大学学报 第32卷 在求解质量方面，72%的问题算法FBGIGA都 pb-shop scheduling Math Oper Res 1976 1(2):117 取得了最优解，除了LA22LA24和L29以外，其他 I2 Parwa kar S Iskander W.A survey of scheduling mes Oper 问题相对其他算法而言也有了一些改进.从统计数 R5197725(1):45 据来看，算法BGGA、MFBAnt HGA以及PT [3 W ang I,Zheng D Z Metheuristic a poritlms a rev ew Cantrol Dec200015(3):257 JSP-PS0的平均相对误差分别为0.23%、0.60%、 (王凌，郑大钟.Meheuristic算法研究进展.控制与决策， 0.44%和0.38%.总体而言，算法CGA的求解效果 200015(3):257 还是很明显的. [4 Yamada T NakanoB A gene tic algoritm applicable o hge sca le 从计算时间上看，算法FBGIGA、 MFBAnt pb-hop pob kms/P roceed ings of the Secand In tema tioma l Con fer HGA以及PT-SP-PSO的平均计算时间分别是123 ence an Parallel Probkm Solving fiom Nature North-Holland 2832.1009和877§显然，相对其他智能算法来讲， Elsevier Science Publishers 1992 281 算法FBGIGA的求解时间也有很大的提高. Udomsakdgool A Kachitv ichyanukul V Twaway scheduling 总之，无论在求解质量还是计算效率上，算法 approach in ant a gorithm for soving pb shop Prob lems Ind Eng FBGTGA都具有一定的改善，从而验证了将正、逆序 Manage Syst20065(2片68 Udomsakd goolA Kachinv ichyanukul V Multip lecobny ant alg 调度与活动调度相结合的双种群遗传算法的有 rim wih forwardbadkward scheduling appoac for jshop 效性. schedu ling Problem//Advanoes n hdustral Engineering andOper 5结论 a tions Resea rcb Sprnger 2008 39 17 JainA S Meeran S Detem nistic jdh shop scheduling past Pres 本文分析了SSP调度问题的特点提出了一种 ent and futre Eur J OPer Res 1998 113(2):390 活动调度技术、正逆序调度方法与双种群遗传算法 [8 Pinedo M Schedulng Theory Agoritms and Systms Nev 相结合的调度算法.该算法利用染色体编码来表示 Jersey Prentice Hall 2002 159 活动调度解，并以G算法为基础按照正、逆序方式 [9 Zhao YW.Wu B Jiang I.et al Double popultions genetic alg 来生成染色体，进而将搜索空间限制为活动调度空 ritm for vehicle roting problem Comput nwegr Manuf Syst 间，通过空间缩减、正逆序策略和双种群并行进化策 200410(3):303 (赵燕伟，吴斌蒋丽，等.车辆路径问题的双种群遗传算法求 略来提高算法的搜索效率.通过正逆序调度方法的 解方法.计算机集成制造系统，200410(3)：303) 结合在一定程度上提高了种群的多样性，以避免早 [10 WagI,Shop Scheduling with Genetic Agoritm Beijng Tsing 熟收敛现象，进而在较大程度上提高了算法的求解 hua Unive rsity Press 2003 68 效率和求解质量.基于Benchmak算例的计算实验 (王凌.车间调度及其遗传算法.北京：清华大学出版社 结果，证明了算法FBGIGA的有效性，这也说明了 2003.68) 问题特征在调度算法设计中的重要性，利用特定领 [11]Gog ahves JF Mendes J JM Reserde MG CA hybrid gene tic 域的固有知识来指导寻优过程，可能在一定程度上 algorithm for he pb shop scheduling poblms Eur J Oper Res 提高算法的性能， 2005167(1):77 [12 Pongchaie ks P KachitvichyanikulV A wa kevel pan icle swam 参考文献 optmization algritm on pb-shop scheduling Poblems Int J 【刂Garey E↓JomnsonD SethiB The conplexit of fow shop and OPeR52009.4(4:390

北 京 科 技 大 学 学 报 第 32卷 在求解质量方面, 72%的问题算法 FBGTGA都 取得了最优解, 除了 LA22、LA24和 LA29以外, 其他 问题相对其他算法而言也有了一些改进.从统计数 据来看, 算法 FBGTGA﹑ MFBAnt、HGA以及 PT￾JSP-PSO的平均相对误差分别为 0.23%、 0.60%、 0.44%和 0.38%.总体而言, 算法 CGA的求解效果 还是很明显的. 从计算时间上看, 算法 FBGTGA﹑ MFBAnt、 HGA以及 PT-JSP-PSO的平均计算时间分别是 123、 2 832、1009和 877 s.显然, 相对其他智能算法来讲, 算法 FBGTGA的求解时间也有很大的提高. 总之, 无论在求解质量还是计算效率上, 算法 FBGTGA都具有一定的改善, 从而验证了将正、逆序 调度与活动调度相结合的双种群遗传算法的有 效性. 5 结论 本文分析了 JSSP调度问题的特点, 提出了一种 活动调度技术、正逆序调度方法与双种群遗传算法 相结合的调度算法.该算法利用染色体编码来表示 活动调度解, 并以 GT算法为基础按照正 、逆序方式 来生成染色体, 进而将搜索空间限制为活动调度空 间, 通过空间缩减 、正逆序策略和双种群并行进化策 略来提高算法的搜索效率 .通过正逆序调度方法的 结合在一定程度上提高了种群的多样性, 以避免早 熟收敛现象, 进而在较大程度上提高了算法的求解 效率和求解质量 .基于 Benchmark算例的计算实验 结果, 证明了算法 FBGTGA的有效性, 这也说明了 问题特征在调度算法设计中的重要性, 利用特定领 域的固有知识来指导寻优过程, 可能在一定程度上 提高算法的性能 . 参 考 文 献 [ 1] GareyEL, JohnsonDS, SethiR.Thecomplexityofflowshopand job-shopscheduling.MathOperRes, 1976, 1 ( 2) :117 [ 2] PanwalkarSS, IskanderW.Asurveyofschedulingrules.Oper Res, 1977, 25 ( 1) :45 [ 3] WangL, ZhengDZ.Meta-heuristicalgorithms:areview.Control Decis, 2000, 15( 3 ) :257 (王凌, 郑大钟.Meta-heuristic算法研究进展.控制与决策, 2000, 15( 3) :257) [ 4] YamadaT, NakanoR.Ageneticalgorithmapplicabletolarge-scale job-shopproblems∥ProceedingsoftheSecondInternationalConfer￾enceonParallelProblem Solvingfrom Nature.North-Holland: ElsevierSciencePublishers, 1992:281 [ 5] UdomsakdigoolA, KachitvichyanukulV.Two-way scheduling approachinantalgorithmforsolvingjobshopproblems.IndEng ManageSyst, 2006, 5 ( 2 ):68 [ 6] UdomsakdigoolA, KachitvichyanukulV.Multiple-colonyantalgo￾rithm withforward-backwardschedulingapproach forjob-shop schedulingproblem∥AdvancesinIndustrialEngineeringandOper￾ationsResearch.Springer, 2008:39 [ 7] JainAS, MeeranS.Deterministicjob-shopscheduling:past, pres￾entandfuture.EurJOperRes, 1998, 113 ( 2) :390 [ 8] PinedoM.Scheduling Theory, Algorithms, and Systems.New Jersey:PrenticeHall, 2002:159 [ 9] ZhaoYW, WuB, JiangL, etal.Doublepopulationsgeneticalgo￾rithmforvehicleroutingproblem.ComputIntegrManufSyst, 2004, 10( 3) :303 (赵燕伟, 吴斌, 蒋丽, 等.车辆路径问题的双种群遗传算法求 解方法.计算机集成制造系统, 2004, 10 ( 3) :303) [ 10] WangL.ShopSchedulingwithGeneticAlgorithm.Beijing:Tsing￾huaUniversityPress, 2003:68 (王凌.车间调度及其遗传算法.北京:清华大学出版社, 2003:68) [ 11] Gon alvesJF, MendesJJM, ResendeMGC.Ahybridgenetic algorithmforthejobshopschedulingproblems.EurJOperRes, 2005, 167 ( 1) :77 [ 12] PongchairerksP, KachitvichyanukulV.Atwo-levelparticleswarm optimizationalgorithm onjob-shopschedulingproblems.IntJ OperRes, 2009, 4 ( 4) :390 · 818·