基于进化算法的多目标生产排序研究进展

摘要/Abstract

摘要：利用多目标进化算法求解复杂生产排序问题是近10 a来发展迅速的研究方向.首先调查了国内外采用进化算法求解多目标生产作业排序的研究现状，分别对3类不同策略的多目标进化算法设计思想进行分析，在总结各类方法优劣的基础上，给出了进一步研究的趋势展望.

关键词： 多目标进化算法, 生产排序, 交互式策略

Abstract: Researches that employ multi-objective evolutionary algorithm to solve complex production scheduling problems have boomed during the past decade.A comprehensive investigation on evolutionary algorithm based multi-objective production scheduling techniques,which includes three kind of optimization frameworks,has been taken in this paper.Future research trends have been proposed after the merits and drawbacks of each generic of the algorithm being compared with others.

Key words: multi-objective evolutionary algorithm, production scheduling, interactive strategy

师瑞峰. 基于进化算法的多目标生产排序研究进展[J]. journal6, 2008, 29(6): 42-46.

SHI Rui-Feng. Current Progress in Evolutionary Algorithm Based Multi-Objective Production Scheduling[J]. journal6, 2008, 29(6): 42-46.

参考文献

[1] SMITH W E.Various Optimizers for Single Stage Production [J].Naval Research Logistics Quarterly,1956,3(1):59-66.

[2] MORTON T E,PENTICO D W.Heuristic Scheduling Systems [M].New York:John Wiley \& Sons,1993.

[3] EMMONS H.One Machine Sequencing to Minimize Mean Flowtime with Minimum Number Tardy [J].Naval Research Logistics Quarterly,1975,22:585-592.

[4] SEN T,GUPTA S K.A Branch and Bound to Solve a Bicriterion Scheduling Problem [J].IIE Transactions,1983,15:84-88.

[5] WASSENHOVE VAN L N,GELDERS F.Solving a Bicriterion Scheduling Problem [J].European Journal of Operational Research,1980,4:42-48.

[6] KAO E P C.A Multiple Objective Decision Theoretic Approach to One Machine Scheduling Problems [J].Computers and Operations Research,1980,7(4):251-259.

[7] HEADY R B,ZHU Z.Minimizing the Sum of Job Earliness and Tardiness in a Multimachine System [J].International Journal of Production Research,1998,36(6):1619-1632.

[8] SIVRIKAYA-SERIFOGLU F,ULUSOY G.Parallel Machine Scheduling with Earliness and Tardiness Penalties [J].Computers and Operations Research,1999,26:773-787.

[9] SAYIN S,KARABATI S.A Bicriteria Approach to the Two-Machine Flow Shop Scheduling Problem [J].European Journal of Operational Research,1999,113:435-449.

[10] ITOH K,HUANG D,ENKAWA T.Twofold Look-Ahead Search for Multi-Criterion Job Shop Scheduling [J].International Journal of Production Research,1993,31:2 215-2 234.

[11] LIANG S J,LEWIS J M.Job Shop Scheduling Using Multiple Criteria [M]//ACAR M,MAKRA J.Mechatronics:The Basis for New Industrial Development.Boston:Computational Mechanics Publications,1994:77-82.

[12] WANG L,WANG M.A Hybrid Algorithm for Earliness-Tardiness Scheduling Problem with Sequence Dependent Setup Time [C]//MICHEL A.Proceedings of 36th IEEE Conference on Decision and Control.San Diego,California:IEEE Press,1997:1 219-1 222.

[13] ISHIBUCHI H,MURATA T.A Multi-Objective Genetic Local Search Algorithm and Its Application to Flowshop Scheduling [J].IEEE Transactions on Systems,Man,and Cybernetics-Part C:Applications and Reviews,1998,28(3):392-403.

[14] BAGCHI T P.Multiobjective Scheduling by Genetic Algorithms [M].Boston:Kluwer Academic Publisher,1999.

[15] BRIZUELA C,SANNOMIYA N,ZHAO Y.Multi-Objective Flow-Shop:Preliminary Results [C]//ZITZLER E,DEB K,THIELE L,et al.Proceedings of 1st International Conference on Evolutionary Multi-Criteria Optimization (EMO2001).Switzerland,Zurich:Springer,2001:443-457.

[16] BRIZUELA C,ACEVES R.Experimental Genetic Operators Analysis for the Multi-Objective Permutation Flowshop [C]//FONSECA C M,FLEMING P J,ZITZLER E,et al.Proceedings of 2nd International Conference on Evolutionary Multi-Criteria Optimization(EMO2003).Faro,Portugal:Springer,2003:578-592.

[17] 师瑞峰,周泓,上官春霞.混合递进多目标进化算法及其在Flow Shop排序中的应用 [J].系统工程理论与实践,2006,26(8):101-108.

[18] 师瑞峰,周泓.一种求解双目标 Flow Shop排序的递进进化算法 [J].管理科学学报,2007,10(5):11-20.

[19] 杨建国,丁慧敏,李蓓智.解决多目标 Flow Shop问题的生物免疫调度算法 [J].机械设计与研究,2002,18(4):28-30.

[20] SAAD I,HAMMADI S,BORNE P,et al.Aggregative Approach for the Multiobjective Optimization Flexible Job-Shop Scheduling Problems:Proceedings of 2006 International Conference on Service Systems and Service Management [C].France:Université de Technologie de Troyes,2006.

[21] 师瑞峰,周一民,周泓.一种求解双目标Job Shop问题的混合进化算法 [J].控制与决策,2007,22(11):1 228-1 234.

[22] 周泓,王建,上官春霞,等.一种求解 Job Shop问题的合作型协同进化算法 [J].中国机械工程,2007,18(20):2 449-2 455.

[23] VIA A，DE SOUSA J P.Using Metaheuristics in Multiobjective Resource Constrained Project Scheduling [J].European Journal

of Operational Research,2000,120:359-374.

[24] 师瑞峰,周一民,周泓,等.一类多层生产排序问题的建模与求解 [J].计算机集成制造系统-CIMS,2007,13(12):2 395-2 405.

[25] 蓝艇,刘士荣,顾幸生.基于进化算法的多目标优化方法 [J].控制与决策,2006,21(6):605-610.

[26] HORN J,NAFPLOITIS N，GOLDBERG D E.A Niched Pareto Genetic Algorithm for Multiobjective Optimization [C]//Proceedings of the 1st IEEE Conference on Evolutionary Computation.Piscataway,New Jersey:IEEE Service Center,1994:82-87.

[27] FONSECA C M，FLEMING P J.Genetic Algorithms for Multiobjective Optimization:Proceedings of the 5th International Conference on Genetic Algorithms [C].San Mateo,California,1993.

[28] MURATS T,ISHIBUCHI H，TANAKA H.Multi-Objective Genetic Algorithm and Its Application to Flowshop Scheduling [J].Computers Industry and Engineering,1996,30(4):957-968.

[29] ZITZLER E,THIELE L.Multiobjective Evolutionary Algorithms:A Comparative Case Study and the Strength Pareto Approach [J].IEEE Transaction on Evolutionary Computation,1999,3:257-271.

[30] DEB K,PRATAP A,AGARWAL S,et al.A Fast and Elitist Multiobjective Genetic Algorithm:NSGA-II [J].IEEE Transaction on Evolutionary Computation,2002,6(2):182-197.

[31] KNOWLES J D，CORNE D W.The Pareto Archived Evolutionary Strategy:A New Baseline Algorithm for Pareto

Multiobjective Optimization [C]//Proceedings of Congress on Evolutionary Computation.Washington D.C.:IEEE Service Center,1999:98-105.

[32] COELLO C A C,PULIDO G T，LECHUGA M S.Handling Multiple Objectives with Particle Swarm Optimization [J].IEEE Transactions on Evolutionary Computation,2004,8(3):256-279.

[33] DANIELS L.Incorporating Preference Information into Multi-Objective Scheduling [J].European Journal of Operational Resaerch,1994,77:272-286.

[34] SHAW K J，FLEMING P J.Including Real-Life Problem Preferences in Genetic Algorithms to Improve Optimization of

Production Schedules [C]//Proceedings of GALESIA.Glasgow,Scotland,1997:239-244.

[35] 徐泽水.一种交互式多目标决策新方法 [J].系统工程理论与实践,2002,22(2):104-108.

[36] 黄洪钟,姚新胜,周仲荣.满意度原理研究与用的现状与展望 [J].控制与决策,2003,18(6):641-645,650.

[37] 周熠.倾向型心态的表示和推理 [D].博士学位论文.合肥:中国科学技术大学,2006.

[38] COELLO C A C.Handling Preferences in Evolutionary Multiobjective Optimization:A Survey [C]//Proceedings of the 2000 Congress on Evolutionary Computation.Piscataway,New Jersey:IEEE Service Center,2000:30-37.

[39] GREENWOOD G W,HU X S，AMBROSIO J G D.Fitness Functions for Multiple Objective Optimization Problems:Combining Preferences with Pareto Rankings [M]//BELEW R K，VOSE M D.Foundations of Genetic Algorithms.Morgan Kaufmann,San Mateo,California,1997:437-455.

[40] 崔逊学,林闯.一种基于偏好的多目标调和遗传算法 [J].软件学报,2005,16(5):761-770.

[41] 李艳君,吴铁军.一种并行多目标遗传算法及其在流程工业生产调度中的应用   [C]//第3届国际智能控制与自动化会议论文(WCICA2000).合肥:中国科学技术大学出版社，2000:525-528.

[42] 周泓,张惠民.求解多目标作业排序问题的遗传算法 [J].系统工程理论与实践,2001,21(8):1-8.

[43] TAKESHI UNO,KOSUKE KATO，HIDEKI KATAGIRI.An Application of Interactive Fuzzy Satisficing Approach with Particle Swarm Optimization for Multiobjective Emergency Facility Location Problem with A-Distance [C]//Proceedings of the 2007 IEEE Symposium on Computational Intelligence in Multicriteria Decision Making(MCDM2007).Honolulu,Hawaii:IEEE Press,2007:368-373.

[44] 孙福权,崔建江,汪定伟.模糊作业时间的并行多机调度问题与算法研究   [J].系统工程学报,2001,16(2):17-21.

[45] 高坚,刘其成.基于模糊评判的单机多目标作业排序问题的优化方法 [J].系统工程,2002,20(2):43-45.

[46] 黎群.单台机器多目标作业排序问题的探讨 [J].系统工程理论方法应用,2001,21(2):156-157.

[47] BRAR Y S,DHILLON J S，KOTHARI D P.Multiobjective Load Dispatch by Fuzzy Logic Based Searching Weightage Pattern [J].Electric Power Systems Research,2002,63:149-160.

[48] 关志华,寇纪淞,李敏强.基于模糊偏好的多目标进化优化算法   [J].天津大学学报：自然科学版,2002,35(3):275-280.

[49] KACEM I,HAMMADI S，BORNE P.Pareto-Optimality Approach for Flexible Job-Shop Scheduling Problems:Hybridization of Evolutionary Algorithms and Fuzzy Logic [J].Mathematics and Computers in Simulation,2002,60:245-276.

[50] PARMEE I C,CVETKOVIC D,WATSON A H,et al.Multi-Objective Satisfaction Within an Interactive Evolutionary Design Environment [J].Evolutionary Computation,2000(8):197-222.

[51] BRINTRUP A,RAMSDEN J，TIWARI A.Integrated Qualitativeness in Design by Multi-Objective Optimization and Interactive Evolutionary Computation [C]//Proceedings of the IEEE Conference on Evolutionary Computation(CEC2005).Edinburgh:IEEE Service Center,2005:2 154-2 160.

[52] TAMURA S,KAWAMURA N,LKKAI Y,et al.An Interactive High Speed Scheduling Method by Tabu Search for A Large-Scale Job Shop Problem with Group Constraints [C]//Proceedings of 10th IEEE Conference on Emerging Technologies and Factory Automation(ETFA2005).Catania,Italy:IEEE Press,2005:821-826.

[53] LEUNG M T.Multiobjective Models for Business Decision Making:Applications to Production Planning and Investment Analysis [D].PhD Thesis.Bloomington:Indiana University,1999.