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