基于混合粒子群优化的置换流水车调度方法研究
|
摘要
制造业中的调度就是对加工过程进行计划,有效的调度方案可以减少加工时间,减小库存,保证交货期,增加企业的效益等。随着全球市场竞争的激烈和客户需求日益的个性化和多样化,调度问题越来越受到人们的重视。置换流水车间调度问题(Permutation Flow Shop Scheduling Problem, PFSP)是实际生产制造车间中十分常见且重要的一类排产方式,也是车间调度的一个热点。本文基于粒子群优化(Particle Swarm Optimization,PSO)算法,在解决单目标PFSP的基础上,深入系统的研究了多目标PFSP(Multi-objective PFSP,MPFSP)。
首先,阐述了研究的目的和意义,对流水车间单目标、多目标调度问题的算法和研究概况进行了综述。分析了该问题研究存在的不足及未来发展趋势。
其次,针对最小化最大完工时间为目标的PFSP,提出一种混合PSO,记为NE-HPSO。该算法采用NEH产生部分初始解,提高算法初始解的质量,采用基于随机键表示法的最小位置实数排序规则(Smallest Position Value,SPV)进行编码。为增强算法的局部搜索能力,设计了基于变邻域搜索算法(Variable neighborhood search, VNS)的局部搜索,邻域结构基于关键路径进行搭建。为了验证该算法的有效性,采取Taillard基准测试集进行测试,测试的到的结果与在该问题取得较好结果的算法进行比较,验证算法的有效性。
随后,在单目标PFSP问题研究的基础上,对多目标PFSP问题进行研究。考虑到MPFSP的各个目标的特点,采用四种启发式算法NEH,SPT,EDD及CDS产生四个高质量的初始解,提高初始解的质量。建立外部精英归档集储存Pareto解,并采用聚类的方式维持外部精英归档集的规模。设计一种基于距离的保持解分散性的方法,保证种群的多样性。对于外部精英归档集中的Pareto解进行局部搜索,局部搜索基于改进VNS,邻域结构采用交换,插入,逆序和Or-opt操作。为验证算法的有效性,测试实例仍采用Taillard基准测试集。该算法与解决多目标问题效果较优的改进强度Pareto进化算法(Strength Pareto Evolutionary Algorithm2,SPEA2)进行比较,得到了相当或者更优的结果,证明了算法的优良性能。
最后,在上述理论研究的基础上,开发了基于单目标和多目标的置换流水车间调度问题原型系统。对全文进行总结,并对PSO算法以及置换流水车间调度的今后研究工作进行了展望。
Scheduling in manufacturing industry plays the role of planning in production process. Proper and effective flowshop scheduling can help the enterprise to save time, decrease storage, guarantee due date and improve the production efficiency. With fierce competition in global markets and the increasing customer demand for personalized and diversified, scheduling attracts more and more attention. Permutation flowshop scheduling problem (PFSP) is one common and important scheduling problem. A hybrid particle swarm optimization (PSO) was proposed in this paper to solve single objective PFSP. Meantime, based on solving PFSP, deep research about handling multi-objective PFSP (MPFSP) was developed.
Firstly, the aim and significance of this research work are given. Then, A comprehensive review of both former and the state-of-the-art approaches on PFSP and MPFSP was introduced. Meantime, future research trends and challenges in this field were analyzed.
Secondly, a hybrid PSO, named NE-HPSO, was proposed to solve PFSP with minimization of makespan. NEH algorithm was taken to produce high quality initial solutions. An improved solution representation rule, smallest position value (SPV), is used to present solutions. Variable neighborhood search (VNS) algorithm is combined with PSO to enhance the local search ability. Two effective neighborhood structures concerned with characteristics of PFSP have been adopted to enhance the performance of VNS. Computational experiments have been conducted on benchmarks (Taillard’s instances) and comparison results with other existing algorithms show the efficiency of the proposed algorithm.
Thirdly, research on MPFSP was based on the research of PFSP. Considering the characters of three objectives solved, four constructed methods, NEH,SPT,EDD and CDS was used to improve the quality of inintial solutions. Meantime, a method based on distance was used to keep the diversity of solutions. To improve the performance of PSO, Pareto solutions were stored in a special elite set. What’s more, a vibrate procedure was adopted to enhance the search exploitation of searching optimal solutions for MPFSP. Then comparison of performance between Strength Pareto Evolutionary Algorithm2 (SPEA2) and this proposed was given based on Taillard’s tests.
Finally, a software prototype system for solving PFSP and MPFSP was developed with MFC in Visual C++ language based on the previous chapters. Conclusions of the paper as well as the future perspectives of PSO for PFSP were discussed.
首先,阐述了研究的目的和意义,对流水车间单目标、多目标调度问题的算法和研究概况进行了综述。分析了该问题研究存在的不足及未来发展趋势。
其次,针对最小化最大完工时间为目标的PFSP,提出一种混合PSO,记为NE-HPSO。该算法采用NEH产生部分初始解,提高算法初始解的质量,采用基于随机键表示法的最小位置实数排序规则(Smallest Position Value,SPV)进行编码。为增强算法的局部搜索能力,设计了基于变邻域搜索算法(Variable neighborhood search, VNS)的局部搜索,邻域结构基于关键路径进行搭建。为了验证该算法的有效性,采取Taillard基准测试集进行测试,测试的到的结果与在该问题取得较好结果的算法进行比较,验证算法的有效性。
随后,在单目标PFSP问题研究的基础上,对多目标PFSP问题进行研究。考虑到MPFSP的各个目标的特点,采用四种启发式算法NEH,SPT,EDD及CDS产生四个高质量的初始解,提高初始解的质量。建立外部精英归档集储存Pareto解,并采用聚类的方式维持外部精英归档集的规模。设计一种基于距离的保持解分散性的方法,保证种群的多样性。对于外部精英归档集中的Pareto解进行局部搜索,局部搜索基于改进VNS,邻域结构采用交换,插入,逆序和Or-opt操作。为验证算法的有效性,测试实例仍采用Taillard基准测试集。该算法与解决多目标问题效果较优的改进强度Pareto进化算法(Strength Pareto Evolutionary Algorithm2,SPEA2)进行比较,得到了相当或者更优的结果,证明了算法的优良性能。
最后,在上述理论研究的基础上,开发了基于单目标和多目标的置换流水车间调度问题原型系统。对全文进行总结,并对PSO算法以及置换流水车间调度的今后研究工作进行了展望。
Scheduling in manufacturing industry plays the role of planning in production process. Proper and effective flowshop scheduling can help the enterprise to save time, decrease storage, guarantee due date and improve the production efficiency. With fierce competition in global markets and the increasing customer demand for personalized and diversified, scheduling attracts more and more attention. Permutation flowshop scheduling problem (PFSP) is one common and important scheduling problem. A hybrid particle swarm optimization (PSO) was proposed in this paper to solve single objective PFSP. Meantime, based on solving PFSP, deep research about handling multi-objective PFSP (MPFSP) was developed.
Firstly, the aim and significance of this research work are given. Then, A comprehensive review of both former and the state-of-the-art approaches on PFSP and MPFSP was introduced. Meantime, future research trends and challenges in this field were analyzed.
Secondly, a hybrid PSO, named NE-HPSO, was proposed to solve PFSP with minimization of makespan. NEH algorithm was taken to produce high quality initial solutions. An improved solution representation rule, smallest position value (SPV), is used to present solutions. Variable neighborhood search (VNS) algorithm is combined with PSO to enhance the local search ability. Two effective neighborhood structures concerned with characteristics of PFSP have been adopted to enhance the performance of VNS. Computational experiments have been conducted on benchmarks (Taillard’s instances) and comparison results with other existing algorithms show the efficiency of the proposed algorithm.
Thirdly, research on MPFSP was based on the research of PFSP. Considering the characters of three objectives solved, four constructed methods, NEH,SPT,EDD and CDS was used to improve the quality of inintial solutions. Meantime, a method based on distance was used to keep the diversity of solutions. To improve the performance of PSO, Pareto solutions were stored in a special elite set. What’s more, a vibrate procedure was adopted to enhance the search exploitation of searching optimal solutions for MPFSP. Then comparison of performance between Strength Pareto Evolutionary Algorithm2 (SPEA2) and this proposed was given based on Taillard’s tests.
Finally, a software prototype system for solving PFSP and MPFSP was developed with MFC in Visual C++ language based on the previous chapters. Conclusions of the paper as well as the future perspectives of PSO for PFSP were discussed.
引文
[1]师瑞峰.基于进化算法的多目标生产排序研究进展.吉首大学学报(自然科学版),2008,29(6):42-46
[2] Johnson S M. Optimal Two and Three-stage Production Scheduling with Set-up Times Included. Naval Research Logistics Quarterly, 1954, 1: 64-68
[3] Manne A S.On the job-shop scheduling problem. Operations Research,1960,8:219~223
[4] Selen W J, Hott D D. A mixed-integer goal-programming formulation of the standard flowshop scheduling problem.Journal of the Operations Research Society of Japan, 1986, 37 1121–1128.
[5] Wilson, J M. Alternative formulations of a flowshop scheduling problem. Journal of the Operations Research Society of Japan,1989,40: 395–399
[6] French S. Sequencing and scheduling-an introduction to the mathematics of the job-shop. Ellis Horwood, John-Wiley &Sons, New York,1982
[7] Luh P B ,Hoitomt F J , Max E. Scheduling Generation and Con2figuration for Parallel Machines . IEEE Trans Robotics and Automation . 1990 , 6(6) :687– 696
[8] Lageweg B J, Lenstra J K, Kan A. A General Bounding Scheme for the Permutation Flow-Shop Problem. Operations Research, 1978, 26(1): 53-67.
[9] Carlier J, Rebai I. Two Branch and Bound Algorithms for the Permutation Flowshop Problem. European Journal of Operational Research, 1996, 90: 238-251.
[10] Haouari M, Ladhari T. A Branch-and-Bound-Based Local Search Method for the Flow Shop Problem. Journal of the Operational Research Society, 2003, 54(10): 1076-1084.
[11] Nawaz M, Enscore E, Ham I. A Heuristic Algorithm for the m Machine, n Job Flow Shop. OMEGA: The International Journal of Management Sciences,1983, 11(1): 91-95.
[12] Taillard E. Some Efficient Heuristic Methods for the Flow Shop Sequencing Problem. European Journal of Operational Research, 1990, 47(1): 65-74.
[13] Ruiz R, Maroto C. A Comprehensive Review and Evaluation of Permutation Flowshop Heuristics. European Journal of Operational Research, 2005, 165: 479-494.
[14] Osman I H, Potts C N. Simulated Annealing for Permutation Flow-Shop Scheduling. Omega(Oxford), 1989, 17(6): 551-557.
[15] Zegordi S H, Itoh K, Enkawa T. Minimizing Makespan for Flow Shop Scheduling by Combining Simulated Annealing with Sequencing Knowledge. European Journal of Operational Research, 1995, 85(3): 515-531.
[16] Ben-Daya M, Al-Fawzan M. A Tabu Search Approach for the Flow Shop Scheduling Problem. European Journal of Operational Research, 1998, 109(1): 88-95
[17] Chen C L, Vempati V S, Aljaber N. An Application of Genetic Algorithms for FlowShop Problems. European Journal of Operational Research, 1995, 80:389–396
[18]宁正元,林大辉,李丽珊等.置换流水车间调度问题的离散粒子群优化算法.集美大学学报(自然科学版,2008,13(2): 97-101.
[19]刘延风,刘三阳.置换流水车间调度的蚁群优化算法.计算机应用,2008,28(2):302-304.
[20] Wang L, Zheng D Z. An Effective Hybrid Heuristic for Flow Shop Scheduling. International Journal of Advanced Manufacturing Technology, 2003, 21(1): 38-44.
[21] Kai S, Genke Y. An Effective Hybrid Optimization Algorithm for the Flow Shop Scheduling Problem. Information Acquisition, 2006 IEEE International Conference on. 2006. 1234-1238.
[22] Sun Y, Liu M, Zhang C Y, et al. New High Performing Hybrid Particle Swarm Optimization for PermutationFlow Shop Scheduling Problem with Minimization of Makespan. The 2010 IEEE International Conference on Industrial Engineering and Engineering Management(on line)
[23] T’kindt V, Biliant J . Multicriteria scheduling: theory model s and algorithms . 2nd ed. Berlin , Germany Springer, 2005
[24] Carlos Coello, Gary Lamont,David Veldhuizen. Evolutionary Algorithms for Solving Multi-objective Problems, 2nd ed,vol. 2. Springer US, 2007: 5-60
[25] Fourman M P. Compaction of Symbolic Layout Using Genetic Algorithms. In Grefenstette JJ (editor). Genetic and Algorithms and Their Applications: Proceedings of the Frist International Conference on Genetic Algorithms. Lawrence Erlbaum, Hillsdale, New Jersey,1985:141-153
[26] T’kindt V, Gupta J N D, Billaut J C. Two-machine flowshop scheduling with a secondary criterion. Computers & Operations Research, 2003 (30): 505–526
[27] Gupta J N D, Neppalli V R, Werner F. Minimizing total flow time in a two-machine flowshop problem with minimum makespan. International Journal of Production Economics, 2001, 69: 323–338
[28] Lemesre J, Dhaenens C, Talbi E G. An exact parallel method for a biobjective permutation flowshop problem. European Journal of Operational Research,2007, 177: 1641–1655
[29] Naderi B, Zandieh M, Balagh A K G et al. An improved simulated annealing for hybrid flowshops with sequence-dependent setup and transportation times to minimize total completion time and total tardiness. Expert Systems with Applications, 2009,(36): 9625-9633
[30] Eren T, Güner E. A bi-criteria flowshop scheduling problem with setup time. Applied Mathematics and Computation, 2006,183: 1292–1300
[31] T’kindt V, Monmarche N, Tercinet F et al. An ant colony optimization algorithm to solve a 2-machine bi-criteria flowshop scheduling problem. European Journal of Operational Research , 2002, 142: 250–257
[32] Tseng C T, Liao C J. A discrete particle swarm optimization for lot-streaming flowshop scheduling problem. European Journal of Operational Research, 2008, 191:360–373
[33] Ravindran D, Haq A N, Selvakuar S J et al. Flow shop scheduling with multiple objective of minimizing makespan and total flow time. International Journal of Advanced Manufacturing Technology, 2005, 25: 1007–1012
[34] Murata T, Ishibuchi H, Tanaka H. Multiobjective genetic algorithm and its applications to flowshop scheduling. Computers & Industrial Engineering,1996b, 30: 957–968
[35] Nagar A, Heragu S S, Haddock J. A branch-and-bound approach for a two-machine flowshop scheduling problem. Journal of the Operational Research Society, 1995, 46: 721–734
[36] Ishibuchi H, Murata T. A multiobjective genetic local search algorithm and its application to flowshop scheduling. IEEE Transactions on Systems Man and Cybernetics Part C-Applications and Reviews, 1998, 28(3):392–403
[37] Qian B, Wang L, Huang D X et al. Multi-objective flow shop scheduling using differential evolution. Lecture Notes in Control and Information Sciences, 2006, 345: 1125-1136
[38] Tavakkoli-Moghaddam R, Rahimi-Vahed A, Mirzaei A H. A hybrid multi-objective immune algorithm for a flow shop scheduling problem with bi-objectives: weighted mean completion time and weighted mean tardiness. Information Sciences, 2007, 177: 5072–5090
[39] Brintrup AM, Ramsden J, Tiwari A. An interactive genetic algorithm-based framework for handling qualitative criteria in design optimization. Computers In Industry, 2007, 58: 279–291
[40] Tantar E, Dhaenens C, Figueira J R et al. A priori landscape analysis in guiding interactive multi-objective metaheuristics, CEC , (IEEE World Congress on Computational Intelligence), 2008. 4104– 4111
[41] Kuo C C. Capacitor placement and scheduling using interactive bi-objective programming with valuable trade off approach. Energy Conversion and Management, 2009, 50: 995–1003
[42] Land AH, Doig A G. An automatic method for solving discrete programming problems. Econometrica, 1960, 28:497-520
[43] Nagar A, Heragu S S, Haddock J. A branch-and-bound approach for a two-machine flowshop scheduling problem. Journal of the Operational Research Society, 1995, 46: 721–734
[44] Liao C J, Yu W C, Joe C B. Bicriterion scheduling in the two-machine flowshop. Journal of the Operations Research Society of Japan, 1997, 48: 929–935
[45] Say?n S, Karabat? S. A bicriteria approach to the two machine flow shop schedulingproblem. European Journal of Operational Research, 1999, 113: 435–449
[46] Sivrikaya-Serifo?lu F, Ulusoy G. A bicriteria two-machine permutation flowshop problem. European Journal of Operational Research, 1998, 107:414–430
[47] Yeh W C. A new branch-and-bound approach for the n/2/flowshop/αF +βCmax flowshop scheduling problem. Computers & Operations Research, 1999, 26:1293–1310
[48] Yeh W C. An efficient branch-and-bound algorithm for the two-machine bi-criteria flowshop scheduling problem. Journal of Manufacturing Systems, 2001, 20: 113–123
[49] Lee W C, Wu C C. Minimizing the total flow time and the tardiness in a two-machine flow shop. International Journal of Systems Science, 2001, 32: 365–373
[50] Lin B M T, Wu J M. Bi-criteria scheduling in a two-machine permutation flowshop. International Journal of Production Research, 2006, 44: 2299–2312
[51] Lemesre J, Dhaenens C, Talbi E G. An exact parallel method for a biobjective permutation flowshop problem. European Journal of Operational Research, 2007, 177: 1641–1655
[52] Metropolis N, Rosenblatt A N, Rosenblatt M N, et al. Equation of State Calculation by Fast Computing Machines. The Journal of Chemical Physics, 1953, 21(6):1087-1092.
[53] Kirkpatrick S ,Gelatt C ,Vecchi P. Optimization by Simulated Annealing. Science , 1983, (220) :671– 679.
[54] Suresh R K, Mohanasundaram K M. Pareto archived simulated annealing for permutation flow shop scheduling with multiple objectives. Proceedings of IEEE Conference on Cybernetics and Intelligent Systems, Singapore, December 1-3, 2004(2). 712-717
[55] Loukil T, Teghem J, Tuyttens D. Solving multiobjective production scheduling problems using metaheuristics. European Journal of Operational Research, 2005, 161: 42–61
[56] Varadharajan T K, Rajendran C. A multiobjective simulated annealing algorithm for scheduling in flowshops to minimize the makespan and total flow time of jobs. European Journal of Operational Research, 2005, 167: 772–795
[57] Hatami S, Ebrahimnejad S, Tavakkoli-Moghaddam R, Maboudian Y. Two meta-heuristics for three-stage assembly flowshop scheduling with sequence- dependent setup times. International Journal of Advanced Manufacturing Technology, 2010, 50:1153–1164
[58] Glover F. Future Paths for Integer programming and Links to Artificial Intelligence. Computer Operations, 1986 ,13(5) :533- 549.
[59] Armentano V A, Arroyo J E C. An application of a multiobjective tabu search algorithm to a bi-criteria flowshop problem. Journal of Heuristics, 2004, 10: 463–481
[60] Eren T, Güner E. A bi-criteria flowshop scheduling with a learning effect. Applied Mathematics and Computation, 2008a, 32(9): 1719–1733
[61] Eren T, Güner E. The triceiteria flowshop scheduling problem. International Journal of Advanced Manufacturing Technology, 2008b, 36: 1210–1220
[62] Loukil T, Teghem J, Fortemps P. Solving multiobjective production scheduling problems with tabu search. Control Cybernetics, 2000, 29(3): 819–828
[63] Holland J H. Adaptation in Natural and Artificial Systems. Ann Arbor, The University of Michigan Press, 1975
[64] Koza J R. Genetic Programming: on the Programming of Computers by Means of Natural Selection and Genetics. MIT Press, Cambridge MA, 1992.
[65] Verela R, Vela C R, Puente J, et al. A Knowledge-based Evolutionary Strategy for Scheduling Problems with Bottlenecks. European Journal of Operational Research, 2003, 145: 57-71
[66] Fogel L J, Owens A J, Walsh M J. Artificial Intelligence Through Simulated Evolution. New York: John Wiley and Sons, 1966.
[67]卫忠,徐晓飞,邓胜春.基于演化多目标算法的混合流水作业调度优化.南京理工大学学报,2006,30(3): 327-331
[68] Figueira J R, Liefooghe A, Talbi E G, et al. A parallel multiple reference point approach for multi-objective optimization. European Journal of Operational Research, 2010, 205:390–400
[69] Neppalli V R, Chen C L, Gupta J N D. Genetic algorithms for the two-stage bi-criteria flowshop problem. European Journal of Operational Research, 1996, 95: 356–373
[70] Murata T, Ishibuchi H, Gen M. Specification of genetic search directions in cellular multiobjective genetic algorithms. In: Zitzler E, Deb K, Thiele L, et al, editors, First International Conference on Evolutionary Multi-Criterion Optimization, Lecture Notes in Computer Science, 2001. 82–95
[71] Karimi, N, Zandieh M, Karamooz H R. Bi-objective group scheduling in hybridflexible flowshop: A multi-phase approach. Expert Systems with Applications, 2010, 37: 4024–4032
[72] Bagchi T P .Pareto-optimal solutions for multiobjective production scheduling problems. International Conference on Evolutionary Multi-Criterion Optimization, Lecture Notes in Computer Science,2001(1993)458-471
[73] Chang P C, Hsieh J C, Lin S G. The development of gradual-priority weighting approach for the multiobjective flowshop scheduling problem. International Journal of Production Economics, 2002, 79:171–183
[74] Dugardin F, Yalaoui F, Amodeo L. New multi-objective method to solve reentrant hybrid flow shop scheduling problem. European Journal of Operational Research, 2010, 203: 22–31
[75] Yeh W C. A memetic algorithm for the n/2/flowshop/αF +βCmax scheduling problem. International Journal of Advanced Manufacturing Technology, 2002, 20:464–473
[76] Ishibuchi H, Yoshida T, Murata T. Balance between genetic search and local search in memetic algorithms for multiobjective permutation flowshop scheduling. IEEE Transactions on Evolutionary Computation, 2003, 7: 204–223
[77] Arroyo J E C, Armentano, V. A. Genetic local search for multiobjective flowshop scheduling problems. European Journal of Operational Research1, 2005, 67:717–738
[78] Sridhar J, Rajendran C. Scheduling in flowshop and cellular manufacturing systems with multiple objectives: A genetic algorithmic approach. Production Planning Control, 1996, 7: 374–382
[79] Cavalieri S, Gaiardelli P. Hybrid genetic algorithms for a multiple-objective scheduling problem. Journal of Intelligent Manufacturing, 1998, 9:361–367
[80] Ponnambalam S G, Jagannathan H, Kataria M, et al. A TSP-GA multiobjective algorithm for flow-shop scheduling. International Journal of Advanced Manufacturing Technology, 2004, 23: 909–915
[81] Pasupathy T, Rajendran C, Suresh R K. A multiobjective genetic algorithm for scheduling in flow shops to minimize the makespan and total flow time of jobs. International Journal of Advanced Manufacturing Technology, 2006, 27: 804–815
[82] Melab N, Mezmaz M, Talbi E G. Parallel cooperative meta-heuristics on the computational grid. A case study: The biobjective flow-shop problem. Parallel Computing, 2006, 32:643–659
[83] Li B B, Wang L. A hybrid quantum-inspired genetic algorithm for multi-objective flow shop scheduling. IEEE Transactions on Systems, Man, and Cybernetics- Part B: Cybernetics, 2007, 37:576–591
[84] Chang P C, Chen S H, Liu C H. Sub-population genetic algorithm with mining genestructures for multi-objective flow shop scheduling problems. Expert Systems with Applications, 2007, 33: 762–771
[85] Dorigo M. Optimization, Learning and Natural Algorithms (in Italian). PhD Thesis. Milano, Italy: Dipartimento di Elettronica, Politecnico di Milano, 1992.
[86] Dorigo M, Maniezzo V, Colorni A. The ant system: Optimization by a colony of cooperating agents. IEEE Transactions on Systems, Man and Cybernetics—Part B, 1996, 26: 29–41.
[87] Rajendran C, Ziegler H. Ant-colony algorithms for permutation flow shop scheduling to minimize makespan/total flow time of jobs. European Journal of Operational Research, 2004, 155:426–438
[88] Marimuthu S, Ponnambalamb S G, Jawahar N. Threshold accepting and Ant-colony optimization algorithms for scheduling m-machine flow shops with lot streaming. Journal of Materials Processing Technology, 2009, 209: 1026–1041
[89] Pasia J M, Hartl R F, Doerner K F (2006) Solving a bi-objective flowshop scheduling problem by Pareto-ant colony optimization. Lecture notes in computer science, Ant colony optimization and swarm intelligence,2006 ( 4150). 294–305
[90] Yagmahan B, Yenisey M M. Ant colony optimization for multi-objective flow shop scheduling problem. Computers & Industrial Engineering, 2006, 54: 411– 420
[91] Yagmahan B, Yenisey M M. A multi-objective ant colony system algorithm for flow shop scheduling problem. Expert Systems with Applications, 2010, 37: 1361–1368
[92] Huang R H, Yang C L. Solving a multi-objective overlapping flow-shop scheduling. International Journal of Advanced Manufacturing Technology, 2009, 42:955–962
[93] Kennedy J, Eberhart RC. Particle swarm optimization. Process IEEE International Conference on Neural Networks,1 995:1942–1948
[94]王凌.微粒群算法及其应用.北京:清华大学出版社, 2008
[95]高亮,高海兵,周驰.基于粒子群优化的开放式车间调度.机械工程学报, 2006,42(2): 129-134.
[96]彭传勇,高亮,邵新宇,周驰.求解作业车间调度问题的广义粒子群优化算法.计算机集成制造系统, 2006, 12(6): 911-917.
[97] Guo W Z, Chen G L, Huang M, et al. A discrete particle swarm optimization algorithm for the multi-objective permutation flow shop sequencing problem. Proceeding of International Conference on Fuzzy Information and Engineering, 2007:323–331
[98] Li B B, Wang L, Liu B. An effective PSO-based hybrid algorithm for multiobjective permutation flow shop scheduling. IEEE Transactions on Systems, Man, and Cybernetics-Part A: Systems and Humans, 2008, 38 (4): 818-831
[99] Liao C J, Tseng C T, Luarn P. A discrete version of particle swarm optimization for flowshop scheduling problems. Computers & Operations Research, 2007, 34:3099–3111
[100] Sha D Y, Lin H H. A particle swarm optimization for multi-objective flowshop scheduling. International Journal of Advanced Manufacturing Technology, 2009, 45:749–758
[101] Rahimi-Vahed A R, Mirghorbani S M. A multiobjective particle swarm for a flow shop scheduling problem. Journal of Combinatorial Optimization, 2007, 13:79–102
[102] Storn R, Price K. Differential evolution—a simple and efficient adaptive scheme for global optimization over continuous spaces. Journal of Global Optimization 1997, 11:341–59.
[103] Qian B, Wang L, Huang D X,et al. Multi-objective flow shop scheduling using differential evolution. Lecture Notes in Control and Information Sciences, 2006, 345: 1125-1136
[104] Qian B, Wang L, Huang D X, et al. Mutli-objective no-wait flow-shop scheduling with a memetic algorithm based on differential evolution. Soft Computing, 2009a, 13: 847–869
[105] Qian B, Wang L, Huang D X, et al.An effective hybrid DE-based algorithm for multi-objective flow shop scheduling with limited buffers. Computers & Operations Research, 2009b, 36: 209– 233
[106] Pan Q K, Wang L, Qian B. A novel differential evolution algorithm for bi-criteria no-wait flow shop scheduling problems. Computers & Operations Research, 2009, 36:2498-251
[107] Zheng T M, Yamashiro M. Solving flow shop scheduling problems by quantum differential evolutionary algorithm. International Journal of Advanced Manufacturing Technology, 2010, 49:643–662
[108] Forrest S,Javornik B,Smith R, et al.Using Genetic Algorithms to Explore Pattern Recognition in the Immune System. Evolutionary Computation, 1993, 1(3): 191-211.
[109] Tavakkoli-Moghaddam R, Rahimi-Vahed A, Mirzaei AH. Hybrid multi-objective immune algorithm for a flow shop cheduling problem with bi-objectives: weighted mean completion time and weighted mean tardiness. Information Sciences, 2007, 177:5072–5090
[110] Tavakkoli-Moghaddam R, Rahimi-Vahed A, Mirzaei AH. Solving a multi-objective no-wait flow shop scheduling problem with an immune algorithm. International Journal of Advanced Manufacturing Technology, 2008, 36:968–981
[111]杨建国,丁惠敏,李蓓智.解决多目标Flow-shop问题的生物免疫调度算法.机械设计与研究, 2002,18(4):28-31
[112]师瑞峰,周泓.一种求解双目标flow shop排序问题的进化算法.管理科学学报, 2007, 10(5):11-20, 27
[113] Behnamian J, Fatemi Ghomi S M T, Zandieh M. A multi-phase covering Pareto-optimal front method to multi-objective scheduling in a realistic hybrid flowshop using a hybrid metaheuristic. Expert Systems with Applications, 2009, 36: 11057-11069
[114] Behnamian J, Fatemi Ghomi S M T(2010) Hybrid flowshop scheduling with machine and resource-dependent processing times. Applied Mathematical Modelling ( in press)
[115] Naderi B, Tavakkoli-Moghaddam R, Khalili M. Electromagnetism-like mechanism and simulated annealing algorithms for flowshop scheduling problems minimizing the total weighted tardiness and makespan. Knowledge-Based Systems, 2010, 23:77–85
[116] Janiak A, Kozan E, Lichtenstein M, et al. Metaheuristic approaches to the hybrid flow shop scheduling problem with a cost-related criterion. International Journal of Production Economics, 2007, 105(2):407–424
[117] Rahimi-Vahed A, Dangchi M, Rafiei H, et al. A novel hybrid multi-objective shuffled frog-leaping algorithm for a bi-criteria permutation flow shop scheduling problem. International Journal of Advanced Manufacturing Technology, 2009, 41:1227–1239
[118] Gonzalez T, Sahni S. Flowshop and jobshop schedules: Complexity and approximation. Operations Research, 1978, 26: 36–52
[119] Kalczynski P J, Kamburowski J. On the NEH heuristic for minimizing the makespan inpermutation flowshops. Omega, 2007,35 : 53–60
[120] Grabowski J, Wodecki M. A Very Fast Tabu Search Algorithm for the Permutation Flow Shop Problem with Makespan Criterion [J]. Computers and Operations Research, 2004, 31(11): 1891-1909
[121] Vallada E, Ruiz R. Genetic algorithms with path relinking for the minimum tardiness permutation flowshop problem.Omega, 2010, 38:57– 67
[122] Lian Z G, Gu X S, Jiao B. A similar particle swarm optimization algorithm for permutation flowshop scheduling to minimize makespan. Applied Mathematics and Computation , 2006,175: 773–785
[123] Tseng LY, Lin Y T. A hybrid genetic local search algorithm for the permutation flowshop scheduling problem. European Journal of Operational Research, 2009,198: 84–92.
[124] Tasgetiren M F, Liang Y C, Sevkli M et al. A particle swarm optimization algorithm for makespan and total flowtime minimization in the permutation flowshop sequencing problem. European Journal of Operational Research , 2007,177 : 1930–1947
[125] Wang L, Pan Q K, Tasgetiren M F.Minimizing the total flow time in a flow shop with blocking by using hybrid harmony search algorithms. Expert Systems with Applications ,2010
[126] Garey, M. R., D. S. Johnson, R. Sethi. 1976. The complexity of flowshopand jobshop scheduling. Math. Oper. Res. 117–129
[127] Reeves C R, Yamada T. Genetic Algorithms, Path Relinking and the Flowshop Sequencing Problem [J]. Evolutionary Computation journal, 1998, 6(1):230-234.
[128] Du J, Leung J YT. Minimizing total tardiness on one machine is NP-hard. Mathematics of Operations Research, 1990,15: 483-495
[129] Nowicki E, Smutnicki C. A Fast Tabu Search Algorithm for the Permutation Flow-Shop Problem [J]. European Journal of Operational Research, 1996, 91:160-175
[130] Pinedo M L. Scheduling: Theory, Algorithms, and Systems. Springer New York Processing, 3rd ed., SpringerLink, 2008, ch. 6: 153-155
[131]王凌.智能优化算法及其应用.北京:清华大学出版社,2001
[132] Bean J C, Genetic algorithm and random keys for sequencing and optimization. ORSA Journal on Computing, 1994,6 (2):154–160
[133] Ruiz R, Maroto C. A Comprehensive Review and Evaluation of Permutation Flowshop Heuristics [J]. European Journal of Operational Research, 2005, 165: 479-494
[134] Hansen P, Mladenovi? N. Variable Neighborhood Search. Computers in Operations Research, 1997, 24: 1097-1100
[135]高守玮.一类flowshop生产调度问题及其优化方法之分析与研究.上海交通大学,2007.
[136] Taillard E. Benchmarks for basic scheduling problems. European Journal of Operational Research, 1993, 64: 278–285.
[137] Nearchou A C. The effect of various operators on the genetic search for large scheduling problems [J]. International Journal of Production Economy, 2004, 88: 191–203
[138] Stuetzle T. An ant approach for the flow shop problem. In: Proceedings of the 6th European Congress on Intelligent Techniques and Soft Computing (EUFIT _98),vol. 3,Verlag Mainz,Aachen,Germany,1998: 1560-1564
[139] Lian Z G, Gu X S, Jiao B. A novel particle swarm optimization algorithm for permutation flow-shop scheduling to minimize makespan. Chaos, Solitons and Fractals, 2008,35:851–861
[140] Rad S F, Ruiz R, Boroojerdian N. New high performing heuristics for minimizing makespan in permutation flowshops. Omega,2009, 37:331– 34
[141]朱剑英.现代制造系统模式、建模方法及关键技术的新发展.机械工程学报,2000,36(8):1-5
[142] Vallada E, Ruiz R, Minella G. Minimising total tardiness in the mmachine flowshop problem: A review and evaluation of heuristics and metaheuristics. Computers and Operations Research, 2008,35, 1350–1373.
[143] Campbell H G, Dudek R A, Smith M L. A heuristic algorithm for the n-job, m-machine problem. Management Science, 1970,16(10): B630–B637
[144] Deb K, Samir A, Amrit P et al. 2000. A fast Elitist Non-Dominated Sorting GeneticAlgorithm for Multi-objective Optimization: NSGA-II. Parallel Problem Solving from Nature PPSN VI, Lecture Notes in Computer Science, 2000, 1917: 849-858
[145] Zitler E,Thiele L.SPEA2:Improving the strength pareto evolutionary algorithm for multiobjective optimization. EUROGEN 2001-Evolutionary methods for design,optimization and control with applications to industrial problems: TIK-Report 103
[2] Johnson S M. Optimal Two and Three-stage Production Scheduling with Set-up Times Included. Naval Research Logistics Quarterly, 1954, 1: 64-68
[3] Manne A S.On the job-shop scheduling problem. Operations Research,1960,8:219~223
[4] Selen W J, Hott D D. A mixed-integer goal-programming formulation of the standard flowshop scheduling problem.Journal of the Operations Research Society of Japan, 1986, 37 1121–1128.
[5] Wilson, J M. Alternative formulations of a flowshop scheduling problem. Journal of the Operations Research Society of Japan,1989,40: 395–399
[6] French S. Sequencing and scheduling-an introduction to the mathematics of the job-shop. Ellis Horwood, John-Wiley &Sons, New York,1982
[7] Luh P B ,Hoitomt F J , Max E. Scheduling Generation and Con2figuration for Parallel Machines . IEEE Trans Robotics and Automation . 1990 , 6(6) :687– 696
[8] Lageweg B J, Lenstra J K, Kan A. A General Bounding Scheme for the Permutation Flow-Shop Problem. Operations Research, 1978, 26(1): 53-67.
[9] Carlier J, Rebai I. Two Branch and Bound Algorithms for the Permutation Flowshop Problem. European Journal of Operational Research, 1996, 90: 238-251.
[10] Haouari M, Ladhari T. A Branch-and-Bound-Based Local Search Method for the Flow Shop Problem. Journal of the Operational Research Society, 2003, 54(10): 1076-1084.
[11] Nawaz M, Enscore E, Ham I. A Heuristic Algorithm for the m Machine, n Job Flow Shop. OMEGA: The International Journal of Management Sciences,1983, 11(1): 91-95.
[12] Taillard E. Some Efficient Heuristic Methods for the Flow Shop Sequencing Problem. European Journal of Operational Research, 1990, 47(1): 65-74.
[13] Ruiz R, Maroto C. A Comprehensive Review and Evaluation of Permutation Flowshop Heuristics. European Journal of Operational Research, 2005, 165: 479-494.
[14] Osman I H, Potts C N. Simulated Annealing for Permutation Flow-Shop Scheduling. Omega(Oxford), 1989, 17(6): 551-557.
[15] Zegordi S H, Itoh K, Enkawa T. Minimizing Makespan for Flow Shop Scheduling by Combining Simulated Annealing with Sequencing Knowledge. European Journal of Operational Research, 1995, 85(3): 515-531.
[16] Ben-Daya M, Al-Fawzan M. A Tabu Search Approach for the Flow Shop Scheduling Problem. European Journal of Operational Research, 1998, 109(1): 88-95
[17] Chen C L, Vempati V S, Aljaber N. An Application of Genetic Algorithms for FlowShop Problems. European Journal of Operational Research, 1995, 80:389–396
[18]宁正元,林大辉,李丽珊等.置换流水车间调度问题的离散粒子群优化算法.集美大学学报(自然科学版,2008,13(2): 97-101.
[19]刘延风,刘三阳.置换流水车间调度的蚁群优化算法.计算机应用,2008,28(2):302-304.
[20] Wang L, Zheng D Z. An Effective Hybrid Heuristic for Flow Shop Scheduling. International Journal of Advanced Manufacturing Technology, 2003, 21(1): 38-44.
[21] Kai S, Genke Y. An Effective Hybrid Optimization Algorithm for the Flow Shop Scheduling Problem. Information Acquisition, 2006 IEEE International Conference on. 2006. 1234-1238.
[22] Sun Y, Liu M, Zhang C Y, et al. New High Performing Hybrid Particle Swarm Optimization for PermutationFlow Shop Scheduling Problem with Minimization of Makespan. The 2010 IEEE International Conference on Industrial Engineering and Engineering Management(on line)
[23] T’kindt V, Biliant J . Multicriteria scheduling: theory model s and algorithms . 2nd ed. Berlin , Germany Springer, 2005
[24] Carlos Coello, Gary Lamont,David Veldhuizen. Evolutionary Algorithms for Solving Multi-objective Problems, 2nd ed,vol. 2. Springer US, 2007: 5-60
[25] Fourman M P. Compaction of Symbolic Layout Using Genetic Algorithms. In Grefenstette JJ (editor). Genetic and Algorithms and Their Applications: Proceedings of the Frist International Conference on Genetic Algorithms. Lawrence Erlbaum, Hillsdale, New Jersey,1985:141-153
[26] T’kindt V, Gupta J N D, Billaut J C. Two-machine flowshop scheduling with a secondary criterion. Computers & Operations Research, 2003 (30): 505–526
[27] Gupta J N D, Neppalli V R, Werner F. Minimizing total flow time in a two-machine flowshop problem with minimum makespan. International Journal of Production Economics, 2001, 69: 323–338
[28] Lemesre J, Dhaenens C, Talbi E G. An exact parallel method for a biobjective permutation flowshop problem. European Journal of Operational Research,2007, 177: 1641–1655
[29] Naderi B, Zandieh M, Balagh A K G et al. An improved simulated annealing for hybrid flowshops with sequence-dependent setup and transportation times to minimize total completion time and total tardiness. Expert Systems with Applications, 2009,(36): 9625-9633
[30] Eren T, Güner E. A bi-criteria flowshop scheduling problem with setup time. Applied Mathematics and Computation, 2006,183: 1292–1300
[31] T’kindt V, Monmarche N, Tercinet F et al. An ant colony optimization algorithm to solve a 2-machine bi-criteria flowshop scheduling problem. European Journal of Operational Research , 2002, 142: 250–257
[32] Tseng C T, Liao C J. A discrete particle swarm optimization for lot-streaming flowshop scheduling problem. European Journal of Operational Research, 2008, 191:360–373
[33] Ravindran D, Haq A N, Selvakuar S J et al. Flow shop scheduling with multiple objective of minimizing makespan and total flow time. International Journal of Advanced Manufacturing Technology, 2005, 25: 1007–1012
[34] Murata T, Ishibuchi H, Tanaka H. Multiobjective genetic algorithm and its applications to flowshop scheduling. Computers & Industrial Engineering,1996b, 30: 957–968
[35] Nagar A, Heragu S S, Haddock J. A branch-and-bound approach for a two-machine flowshop scheduling problem. Journal of the Operational Research Society, 1995, 46: 721–734
[36] Ishibuchi H, Murata T. A multiobjective genetic local search algorithm and its application to flowshop scheduling. IEEE Transactions on Systems Man and Cybernetics Part C-Applications and Reviews, 1998, 28(3):392–403
[37] Qian B, Wang L, Huang D X et al. Multi-objective flow shop scheduling using differential evolution. Lecture Notes in Control and Information Sciences, 2006, 345: 1125-1136
[38] Tavakkoli-Moghaddam R, Rahimi-Vahed A, Mirzaei A H. A hybrid multi-objective immune algorithm for a flow shop scheduling problem with bi-objectives: weighted mean completion time and weighted mean tardiness. Information Sciences, 2007, 177: 5072–5090
[39] Brintrup AM, Ramsden J, Tiwari A. An interactive genetic algorithm-based framework for handling qualitative criteria in design optimization. Computers In Industry, 2007, 58: 279–291
[40] Tantar E, Dhaenens C, Figueira J R et al. A priori landscape analysis in guiding interactive multi-objective metaheuristics, CEC , (IEEE World Congress on Computational Intelligence), 2008. 4104– 4111
[41] Kuo C C. Capacitor placement and scheduling using interactive bi-objective programming with valuable trade off approach. Energy Conversion and Management, 2009, 50: 995–1003
[42] Land AH, Doig A G. An automatic method for solving discrete programming problems. Econometrica, 1960, 28:497-520
[43] Nagar A, Heragu S S, Haddock J. A branch-and-bound approach for a two-machine flowshop scheduling problem. Journal of the Operational Research Society, 1995, 46: 721–734
[44] Liao C J, Yu W C, Joe C B. Bicriterion scheduling in the two-machine flowshop. Journal of the Operations Research Society of Japan, 1997, 48: 929–935
[45] Say?n S, Karabat? S. A bicriteria approach to the two machine flow shop schedulingproblem. European Journal of Operational Research, 1999, 113: 435–449
[46] Sivrikaya-Serifo?lu F, Ulusoy G. A bicriteria two-machine permutation flowshop problem. European Journal of Operational Research, 1998, 107:414–430
[47] Yeh W C. A new branch-and-bound approach for the n/2/flowshop/αF +βCmax flowshop scheduling problem. Computers & Operations Research, 1999, 26:1293–1310
[48] Yeh W C. An efficient branch-and-bound algorithm for the two-machine bi-criteria flowshop scheduling problem. Journal of Manufacturing Systems, 2001, 20: 113–123
[49] Lee W C, Wu C C. Minimizing the total flow time and the tardiness in a two-machine flow shop. International Journal of Systems Science, 2001, 32: 365–373
[50] Lin B M T, Wu J M. Bi-criteria scheduling in a two-machine permutation flowshop. International Journal of Production Research, 2006, 44: 2299–2312
[51] Lemesre J, Dhaenens C, Talbi E G. An exact parallel method for a biobjective permutation flowshop problem. European Journal of Operational Research, 2007, 177: 1641–1655
[52] Metropolis N, Rosenblatt A N, Rosenblatt M N, et al. Equation of State Calculation by Fast Computing Machines. The Journal of Chemical Physics, 1953, 21(6):1087-1092.
[53] Kirkpatrick S ,Gelatt C ,Vecchi P. Optimization by Simulated Annealing. Science , 1983, (220) :671– 679.
[54] Suresh R K, Mohanasundaram K M. Pareto archived simulated annealing for permutation flow shop scheduling with multiple objectives. Proceedings of IEEE Conference on Cybernetics and Intelligent Systems, Singapore, December 1-3, 2004(2). 712-717
[55] Loukil T, Teghem J, Tuyttens D. Solving multiobjective production scheduling problems using metaheuristics. European Journal of Operational Research, 2005, 161: 42–61
[56] Varadharajan T K, Rajendran C. A multiobjective simulated annealing algorithm for scheduling in flowshops to minimize the makespan and total flow time of jobs. European Journal of Operational Research, 2005, 167: 772–795
[57] Hatami S, Ebrahimnejad S, Tavakkoli-Moghaddam R, Maboudian Y. Two meta-heuristics for three-stage assembly flowshop scheduling with sequence- dependent setup times. International Journal of Advanced Manufacturing Technology, 2010, 50:1153–1164
[58] Glover F. Future Paths for Integer programming and Links to Artificial Intelligence. Computer Operations, 1986 ,13(5) :533- 549.
[59] Armentano V A, Arroyo J E C. An application of a multiobjective tabu search algorithm to a bi-criteria flowshop problem. Journal of Heuristics, 2004, 10: 463–481
[60] Eren T, Güner E. A bi-criteria flowshop scheduling with a learning effect. Applied Mathematics and Computation, 2008a, 32(9): 1719–1733
[61] Eren T, Güner E. The triceiteria flowshop scheduling problem. International Journal of Advanced Manufacturing Technology, 2008b, 36: 1210–1220
[62] Loukil T, Teghem J, Fortemps P. Solving multiobjective production scheduling problems with tabu search. Control Cybernetics, 2000, 29(3): 819–828
[63] Holland J H. Adaptation in Natural and Artificial Systems. Ann Arbor, The University of Michigan Press, 1975
[64] Koza J R. Genetic Programming: on the Programming of Computers by Means of Natural Selection and Genetics. MIT Press, Cambridge MA, 1992.
[65] Verela R, Vela C R, Puente J, et al. A Knowledge-based Evolutionary Strategy for Scheduling Problems with Bottlenecks. European Journal of Operational Research, 2003, 145: 57-71
[66] Fogel L J, Owens A J, Walsh M J. Artificial Intelligence Through Simulated Evolution. New York: John Wiley and Sons, 1966.
[67]卫忠,徐晓飞,邓胜春.基于演化多目标算法的混合流水作业调度优化.南京理工大学学报,2006,30(3): 327-331
[68] Figueira J R, Liefooghe A, Talbi E G, et al. A parallel multiple reference point approach for multi-objective optimization. European Journal of Operational Research, 2010, 205:390–400
[69] Neppalli V R, Chen C L, Gupta J N D. Genetic algorithms for the two-stage bi-criteria flowshop problem. European Journal of Operational Research, 1996, 95: 356–373
[70] Murata T, Ishibuchi H, Gen M. Specification of genetic search directions in cellular multiobjective genetic algorithms. In: Zitzler E, Deb K, Thiele L, et al, editors, First International Conference on Evolutionary Multi-Criterion Optimization, Lecture Notes in Computer Science, 2001. 82–95
[71] Karimi, N, Zandieh M, Karamooz H R. Bi-objective group scheduling in hybridflexible flowshop: A multi-phase approach. Expert Systems with Applications, 2010, 37: 4024–4032
[72] Bagchi T P .Pareto-optimal solutions for multiobjective production scheduling problems. International Conference on Evolutionary Multi-Criterion Optimization, Lecture Notes in Computer Science,2001(1993)458-471
[73] Chang P C, Hsieh J C, Lin S G. The development of gradual-priority weighting approach for the multiobjective flowshop scheduling problem. International Journal of Production Economics, 2002, 79:171–183
[74] Dugardin F, Yalaoui F, Amodeo L. New multi-objective method to solve reentrant hybrid flow shop scheduling problem. European Journal of Operational Research, 2010, 203: 22–31
[75] Yeh W C. A memetic algorithm for the n/2/flowshop/αF +βCmax scheduling problem. International Journal of Advanced Manufacturing Technology, 2002, 20:464–473
[76] Ishibuchi H, Yoshida T, Murata T. Balance between genetic search and local search in memetic algorithms for multiobjective permutation flowshop scheduling. IEEE Transactions on Evolutionary Computation, 2003, 7: 204–223
[77] Arroyo J E C, Armentano, V. A. Genetic local search for multiobjective flowshop scheduling problems. European Journal of Operational Research1, 2005, 67:717–738
[78] Sridhar J, Rajendran C. Scheduling in flowshop and cellular manufacturing systems with multiple objectives: A genetic algorithmic approach. Production Planning Control, 1996, 7: 374–382
[79] Cavalieri S, Gaiardelli P. Hybrid genetic algorithms for a multiple-objective scheduling problem. Journal of Intelligent Manufacturing, 1998, 9:361–367
[80] Ponnambalam S G, Jagannathan H, Kataria M, et al. A TSP-GA multiobjective algorithm for flow-shop scheduling. International Journal of Advanced Manufacturing Technology, 2004, 23: 909–915
[81] Pasupathy T, Rajendran C, Suresh R K. A multiobjective genetic algorithm for scheduling in flow shops to minimize the makespan and total flow time of jobs. International Journal of Advanced Manufacturing Technology, 2006, 27: 804–815
[82] Melab N, Mezmaz M, Talbi E G. Parallel cooperative meta-heuristics on the computational grid. A case study: The biobjective flow-shop problem. Parallel Computing, 2006, 32:643–659
[83] Li B B, Wang L. A hybrid quantum-inspired genetic algorithm for multi-objective flow shop scheduling. IEEE Transactions on Systems, Man, and Cybernetics- Part B: Cybernetics, 2007, 37:576–591
[84] Chang P C, Chen S H, Liu C H. Sub-population genetic algorithm with mining genestructures for multi-objective flow shop scheduling problems. Expert Systems with Applications, 2007, 33: 762–771
[85] Dorigo M. Optimization, Learning and Natural Algorithms (in Italian). PhD Thesis. Milano, Italy: Dipartimento di Elettronica, Politecnico di Milano, 1992.
[86] Dorigo M, Maniezzo V, Colorni A. The ant system: Optimization by a colony of cooperating agents. IEEE Transactions on Systems, Man and Cybernetics—Part B, 1996, 26: 29–41.
[87] Rajendran C, Ziegler H. Ant-colony algorithms for permutation flow shop scheduling to minimize makespan/total flow time of jobs. European Journal of Operational Research, 2004, 155:426–438
[88] Marimuthu S, Ponnambalamb S G, Jawahar N. Threshold accepting and Ant-colony optimization algorithms for scheduling m-machine flow shops with lot streaming. Journal of Materials Processing Technology, 2009, 209: 1026–1041
[89] Pasia J M, Hartl R F, Doerner K F (2006) Solving a bi-objective flowshop scheduling problem by Pareto-ant colony optimization. Lecture notes in computer science, Ant colony optimization and swarm intelligence,2006 ( 4150). 294–305
[90] Yagmahan B, Yenisey M M. Ant colony optimization for multi-objective flow shop scheduling problem. Computers & Industrial Engineering, 2006, 54: 411– 420
[91] Yagmahan B, Yenisey M M. A multi-objective ant colony system algorithm for flow shop scheduling problem. Expert Systems with Applications, 2010, 37: 1361–1368
[92] Huang R H, Yang C L. Solving a multi-objective overlapping flow-shop scheduling. International Journal of Advanced Manufacturing Technology, 2009, 42:955–962
[93] Kennedy J, Eberhart RC. Particle swarm optimization. Process IEEE International Conference on Neural Networks,1 995:1942–1948
[94]王凌.微粒群算法及其应用.北京:清华大学出版社, 2008
[95]高亮,高海兵,周驰.基于粒子群优化的开放式车间调度.机械工程学报, 2006,42(2): 129-134.
[96]彭传勇,高亮,邵新宇,周驰.求解作业车间调度问题的广义粒子群优化算法.计算机集成制造系统, 2006, 12(6): 911-917.
[97] Guo W Z, Chen G L, Huang M, et al. A discrete particle swarm optimization algorithm for the multi-objective permutation flow shop sequencing problem. Proceeding of International Conference on Fuzzy Information and Engineering, 2007:323–331
[98] Li B B, Wang L, Liu B. An effective PSO-based hybrid algorithm for multiobjective permutation flow shop scheduling. IEEE Transactions on Systems, Man, and Cybernetics-Part A: Systems and Humans, 2008, 38 (4): 818-831
[99] Liao C J, Tseng C T, Luarn P. A discrete version of particle swarm optimization for flowshop scheduling problems. Computers & Operations Research, 2007, 34:3099–3111
[100] Sha D Y, Lin H H. A particle swarm optimization for multi-objective flowshop scheduling. International Journal of Advanced Manufacturing Technology, 2009, 45:749–758
[101] Rahimi-Vahed A R, Mirghorbani S M. A multiobjective particle swarm for a flow shop scheduling problem. Journal of Combinatorial Optimization, 2007, 13:79–102
[102] Storn R, Price K. Differential evolution—a simple and efficient adaptive scheme for global optimization over continuous spaces. Journal of Global Optimization 1997, 11:341–59.
[103] Qian B, Wang L, Huang D X,et al. Multi-objective flow shop scheduling using differential evolution. Lecture Notes in Control and Information Sciences, 2006, 345: 1125-1136
[104] Qian B, Wang L, Huang D X, et al. Mutli-objective no-wait flow-shop scheduling with a memetic algorithm based on differential evolution. Soft Computing, 2009a, 13: 847–869
[105] Qian B, Wang L, Huang D X, et al.An effective hybrid DE-based algorithm for multi-objective flow shop scheduling with limited buffers. Computers & Operations Research, 2009b, 36: 209– 233
[106] Pan Q K, Wang L, Qian B. A novel differential evolution algorithm for bi-criteria no-wait flow shop scheduling problems. Computers & Operations Research, 2009, 36:2498-251
[107] Zheng T M, Yamashiro M. Solving flow shop scheduling problems by quantum differential evolutionary algorithm. International Journal of Advanced Manufacturing Technology, 2010, 49:643–662
[108] Forrest S,Javornik B,Smith R, et al.Using Genetic Algorithms to Explore Pattern Recognition in the Immune System. Evolutionary Computation, 1993, 1(3): 191-211.
[109] Tavakkoli-Moghaddam R, Rahimi-Vahed A, Mirzaei AH. Hybrid multi-objective immune algorithm for a flow shop cheduling problem with bi-objectives: weighted mean completion time and weighted mean tardiness. Information Sciences, 2007, 177:5072–5090
[110] Tavakkoli-Moghaddam R, Rahimi-Vahed A, Mirzaei AH. Solving a multi-objective no-wait flow shop scheduling problem with an immune algorithm. International Journal of Advanced Manufacturing Technology, 2008, 36:968–981
[111]杨建国,丁惠敏,李蓓智.解决多目标Flow-shop问题的生物免疫调度算法.机械设计与研究, 2002,18(4):28-31
[112]师瑞峰,周泓.一种求解双目标flow shop排序问题的进化算法.管理科学学报, 2007, 10(5):11-20, 27
[113] Behnamian J, Fatemi Ghomi S M T, Zandieh M. A multi-phase covering Pareto-optimal front method to multi-objective scheduling in a realistic hybrid flowshop using a hybrid metaheuristic. Expert Systems with Applications, 2009, 36: 11057-11069
[114] Behnamian J, Fatemi Ghomi S M T(2010) Hybrid flowshop scheduling with machine and resource-dependent processing times. Applied Mathematical Modelling ( in press)
[115] Naderi B, Tavakkoli-Moghaddam R, Khalili M. Electromagnetism-like mechanism and simulated annealing algorithms for flowshop scheduling problems minimizing the total weighted tardiness and makespan. Knowledge-Based Systems, 2010, 23:77–85
[116] Janiak A, Kozan E, Lichtenstein M, et al. Metaheuristic approaches to the hybrid flow shop scheduling problem with a cost-related criterion. International Journal of Production Economics, 2007, 105(2):407–424
[117] Rahimi-Vahed A, Dangchi M, Rafiei H, et al. A novel hybrid multi-objective shuffled frog-leaping algorithm for a bi-criteria permutation flow shop scheduling problem. International Journal of Advanced Manufacturing Technology, 2009, 41:1227–1239
[118] Gonzalez T, Sahni S. Flowshop and jobshop schedules: Complexity and approximation. Operations Research, 1978, 26: 36–52
[119] Kalczynski P J, Kamburowski J. On the NEH heuristic for minimizing the makespan inpermutation flowshops. Omega, 2007,35 : 53–60
[120] Grabowski J, Wodecki M. A Very Fast Tabu Search Algorithm for the Permutation Flow Shop Problem with Makespan Criterion [J]. Computers and Operations Research, 2004, 31(11): 1891-1909
[121] Vallada E, Ruiz R. Genetic algorithms with path relinking for the minimum tardiness permutation flowshop problem.Omega, 2010, 38:57– 67
[122] Lian Z G, Gu X S, Jiao B. A similar particle swarm optimization algorithm for permutation flowshop scheduling to minimize makespan. Applied Mathematics and Computation , 2006,175: 773–785
[123] Tseng LY, Lin Y T. A hybrid genetic local search algorithm for the permutation flowshop scheduling problem. European Journal of Operational Research, 2009,198: 84–92.
[124] Tasgetiren M F, Liang Y C, Sevkli M et al. A particle swarm optimization algorithm for makespan and total flowtime minimization in the permutation flowshop sequencing problem. European Journal of Operational Research , 2007,177 : 1930–1947
[125] Wang L, Pan Q K, Tasgetiren M F.Minimizing the total flow time in a flow shop with blocking by using hybrid harmony search algorithms. Expert Systems with Applications ,2010
[126] Garey, M. R., D. S. Johnson, R. Sethi. 1976. The complexity of flowshopand jobshop scheduling. Math. Oper. Res. 117–129
[127] Reeves C R, Yamada T. Genetic Algorithms, Path Relinking and the Flowshop Sequencing Problem [J]. Evolutionary Computation journal, 1998, 6(1):230-234.
[128] Du J, Leung J YT. Minimizing total tardiness on one machine is NP-hard. Mathematics of Operations Research, 1990,15: 483-495
[129] Nowicki E, Smutnicki C. A Fast Tabu Search Algorithm for the Permutation Flow-Shop Problem [J]. European Journal of Operational Research, 1996, 91:160-175
[130] Pinedo M L. Scheduling: Theory, Algorithms, and Systems. Springer New York Processing, 3rd ed., SpringerLink, 2008, ch. 6: 153-155
[131]王凌.智能优化算法及其应用.北京:清华大学出版社,2001
[132] Bean J C, Genetic algorithm and random keys for sequencing and optimization. ORSA Journal on Computing, 1994,6 (2):154–160
[133] Ruiz R, Maroto C. A Comprehensive Review and Evaluation of Permutation Flowshop Heuristics [J]. European Journal of Operational Research, 2005, 165: 479-494
[134] Hansen P, Mladenovi? N. Variable Neighborhood Search. Computers in Operations Research, 1997, 24: 1097-1100
[135]高守玮.一类flowshop生产调度问题及其优化方法之分析与研究.上海交通大学,2007.
[136] Taillard E. Benchmarks for basic scheduling problems. European Journal of Operational Research, 1993, 64: 278–285.
[137] Nearchou A C. The effect of various operators on the genetic search for large scheduling problems [J]. International Journal of Production Economy, 2004, 88: 191–203
[138] Stuetzle T. An ant approach for the flow shop problem. In: Proceedings of the 6th European Congress on Intelligent Techniques and Soft Computing (EUFIT _98),vol. 3,Verlag Mainz,Aachen,Germany,1998: 1560-1564
[139] Lian Z G, Gu X S, Jiao B. A novel particle swarm optimization algorithm for permutation flow-shop scheduling to minimize makespan. Chaos, Solitons and Fractals, 2008,35:851–861
[140] Rad S F, Ruiz R, Boroojerdian N. New high performing heuristics for minimizing makespan in permutation flowshops. Omega,2009, 37:331– 34
[141]朱剑英.现代制造系统模式、建模方法及关键技术的新发展.机械工程学报,2000,36(8):1-5
[142] Vallada E, Ruiz R, Minella G. Minimising total tardiness in the mmachine flowshop problem: A review and evaluation of heuristics and metaheuristics. Computers and Operations Research, 2008,35, 1350–1373.
[143] Campbell H G, Dudek R A, Smith M L. A heuristic algorithm for the n-job, m-machine problem. Management Science, 1970,16(10): B630–B637
[144] Deb K, Samir A, Amrit P et al. 2000. A fast Elitist Non-Dominated Sorting GeneticAlgorithm for Multi-objective Optimization: NSGA-II. Parallel Problem Solving from Nature PPSN VI, Lecture Notes in Computer Science, 2000, 1917: 849-858
[145] Zitler E,Thiele L.SPEA2:Improving the strength pareto evolutionary algorithm for multiobjective optimization. EUROGEN 2001-Evolutionary methods for design,optimization and control with applications to industrial problems: TIK-Report 103