求解总拖期时间最小化流水车间调度问题的多智能体进化算法

王大志; 刘士新; 郭希旺

doi:10.3724/SP.J.1004.2014.00548

求解总拖期时间最小化流水车间调度问题的多智能体进化算法

doi: 10.3724/SP.J.1004.2014.00548

王大志^1,2, ,,
刘士新^1,2,
郭希旺^1,2

1.
东北大学信息科学与工程学院系统工程研究所沈阳 110819;
2.
流程工业综合自动化教育部重点实验室沈阳 110819

基金项目:

国家自然科学基金（61333006，71171038），中央高校基本科研业务费（N110404024）资助

详细信息

作者简介:
刘士新东北大学信息科学与工程学院系统工程研究所教授. 主要研究方向为项目管理, 生产计划与调度, 最优化理论与应用.E-mail：sxliu@mail.neu.edu.cn

通讯作者:
王大志

计量
- 文章访问数: 1830
- HTML全文浏览量: 120
- PDF下载量: 1325
- 被引次数: 0
出版历程
- 收稿日期: 2012-12-12
- 修回日期: 2013-04-19
- 刊出日期: 2014-03-20

A Multi-agent Evolutionary Algorithm for Solving Total Tardiness Permutation Flow-shop Scheduling Problem

WANG Da-Zhi^{1,2
, ,},
LIU Shi-Xin^1,2,
GUO Xi-Wang^1,2

1.
Institute of Systems Engineering, School of Information Science and Engineering, Northeastern University, Shenyang 110819;
2.
State Key Laboratory of Synthetical Automation for Process Industries, Northeastern University, Shenyang 110819

Funds:

Supported by National Natural Science Foundation of China (61333006, 71171038), the Fundamental Research Funds for the Central Universities (N110404024)

摘要

摘要: 针对总拖期时间最小化的置换流水车间调度问题（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.
- Permutation flow-shop scheduling problem (PFSP) /
- total tardiness /
- multi-agent /
- evolutionary algorithm

HTML全文

参考文献(21)

[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

施引文献

资源附件(0)

访问统计

计量

文章访问数: 1830
HTML全文浏览量: 120
PDF下载量: 1325
被引次数: 0

姓名
邮箱
手机号码
标题
留言内容
验证码

留言板

求解总拖期时间最小化流水车间调度问题的多智能体进化算法

doi: 10.3724/SP.J.1004.2014.00548

作者简介:
刘士新东北大学信息科学与工程学院系统工程研究所教授. 主要研究方向为项目管理, 生产计划与调度, 最优化理论与应用.E-mail：sxliu@mail.neu.edu.cn

通讯作者:
王大志

计量

A Multi-agent Evolutionary Algorithm for Solving Total Tardiness Permutation Flow-shop Scheduling Problem

计量

目录

留言板

求解总拖期时间最小化流水车间调度问题的多智能体进化算法

doi: 10.3724/SP.J.1004.2014.00548

作者简介: 刘士新 东北大学信息科学与工程学院系统工程研究所教授. 主要研究方向为项目管理, 生产计划与调度, 最优化理论与应用.E-mail：sxliu@mail.neu.edu.cn

通讯作者: 王大志

计量

出版历程

A Multi-agent Evolutionary Algorithm for Solving Total Tardiness Permutation Flow-shop Scheduling Problem

计量

出版历程

目录

作者简介:
刘士新东北大学信息科学与工程学院系统工程研究所教授. 主要研究方向为项目管理, 生产计划与调度, 最优化理论与应用.E-mail：sxliu@mail.neu.edu.cn

通讯作者:
王大志