A Multi-agent Evolutionary Algorithm for Solving Total Tardiness Permutation Flow-shop Scheduling Problem
-
摘要: 针对总拖期时间最小化的置换流水车间调度问题(Total tardiness permutation flow-shop scheduling problem) 提出了一种基于多智能体的进化搜索算法. 在该算法中,采用基于延迟时间排序的学习搜索策略(Tardiness rank based learning),快速产生高质量的新个体,并根据概率更新模型进行智能体网格的更新进化. 同时通过实验设计的方法探讨了算法参数设置对算法性能的影响. 为了验证算法的性能,求解了Vallada标准测试集中540个测试问题,并将测试结果与一些代表算法进行比较,验证了该算法的有效性.Abstract: In this research, we propose a multi-agent evolutionary algorithm for the permutation flow-shop scheduling problem (PFSP) considering the total tardiness minimization criterion. The algorithm includes the tardiness rank based learning scheme to generate high quality solution by using the specific knowledge of the related problem. We also develop and integrate the probability acceptance model into the proposed algorithm to evolve the whole agent lattice network. A complete calibration of the different parameters of the proposed algorithm by means of a design of experiment approach is given. Using the 540 benchmark problems, a comparative evaluation with other heuristic methods in the literature have been carried out. The results show that the proposed algorithm is effective and competitive.
-
[1] Vallada E, Rubn R. Cooperative metaheuristics for the permutation flowshop scheduling problem. European Journal of Operational Research, 2009, 193(2): 365-376 [2] [2] Vallada E, Rubn R, Gerardo M. Minimising total tardiness in the m-machine flowshop problem: a review and evaluation of heuristics and metaheuristics. Computers Operations Research, 2008, 35(4): 1350-1373 [3] [3] Liao J M, Huang C J. Tabu search for non-permutation flowshop scheduling problem with minimizing total tardiness. Applied Mathematics and Computation, 2010, 217(2): 557-567 [4] [4] Hasija S, Rajendran C. Scheduling in flowshops to minimize total tardiness of jobs. International Journal of Production Research, 2004, 42(11): 2289-2301 [5] [5] Armentano V A, Ronconi D P. Tabu search for total tardiness minimization in flowshop scheduling problems. Computers Operations Research, 1999, 26(3): 219-235 [6] [6] Talip K, Bilal T, John W. Elite guided steady-state genetic algorithm for minimizing total tardiness in flowshops. Computers Industrial Engineering, 2010, 58(2): 300-306 [7] [7] Li B B, Wang L, Liu B. An effective PSO-based hybrid algorithm for multi-objective permutation flow shop scheduling. IEEE Transactions on Systems, Man, and Cybernetics --Part A: Systems and Humans, 2008, 38(4): 818-831 [8] Jiao Li-Cheng, Liu Jing, Zhong Wei-Cai, Coevolutionary Computation and Multiagent Systems. Beijng: Science Press, 2006. 205-224(焦李成, 刘静, 钟伟才. 协同进化计算与多智能体系统. 北京: 科学出版社, 2006. 205-224) [9] [9] Sarker R A, Ray T. Agent-Based Evolutionary Search. Berlin: Springer-Verlag, 2010. 97-116 [10] Zhong Wei-Cai, Liu Jing, Jiao Li-Cheng. Optimal approximation of linear systems by multi-agent genetic algorithm. Acta Automatica Sinica, 2004, 30(6): 933-938(钟伟才, 刘静, 焦李成. 多智能体遗传算法用于线性系统逼近. 自动化学报, 2004, 30(6): 933-938) [11] Sttzle T. Applying iterated local search to the permutation flow shop problem, Technical Report, AIDA-98-04, FG Intellektik, FB Informatik, TU Darmstadt, 1998 [12] Osman I, Potts C. Simulated annealing for permutation flow-shop scheduling. Omega, 1989, 17(6): 551-557 [13] Montgomery D C. Design and Analysis of Experiments (5th Edition). Hoblken: John Wiley and Sons, 2000 [14] Ruiz R, Maroto C, Alcaraz J. Two new robust genetic algorithms for the flowshop scheduling problem. Omega, 2006, 34(5): 461-476 [15] Parthasarathy S, Rajendran C. A simulated annealing heuristic for scheduling to minimize mean weighted tardiness in a flowshop with sequence-dependent setup times of jobs --a case study. Production Planning and Control, 1997, 8(5): 475-483 [16] Hasija S, Rajendran C. Scheduling in flowshops to minimize total tardiness of jobs. International Journal of Production Research, 2004, 42(11): 2289-2301 [17] Vallada E, Rubn R. Genetic algorithms with path relinking for the minimum tardiness permutation flowshop problem. Omega, 2010, 38(1-2): 57-67 [18] Ruiz R, Sttzle T. A simple and effective iterated greedy algorithm for the permutation flowshop scheduling problem. European Journal of Operational Research, 2007, 177(3): 2033-2049 [19] Zemel E. Measuring the quality of approximate solutions to zero-one programming problems. Mathematics of Operations Research, 1981, 6(3): 319-332 [20] Kim Y D. Heuristics for flowshop scheduling problems minimizing mean tardiness. Journal of the Operational Research Society, 1993, 44(1): 19-28 [21] Kim Y D, Lim H G, Park M W. Search heuristics for a flow shop scheduling problem in a printed circuit board assembly process. European Journal of Operational Research, 1996, 91(1): 124-143
点击查看大图
计量
- 文章访问数: 1741
- HTML全文浏览量: 113
- PDF下载量: 1319
- 被引次数: 0