2.793

2018影响因子

(CJCR)

  • 中文核心
  • EI
  • 中国科技核心
  • Scopus
  • CSCD
  • 英国科学文摘

留言板

尊敬的读者、作者、审稿人, 关于本刊的投稿、审稿、编辑和出版的任何问题, 您可以本页添加留言。我们将尽快给您答复。谢谢您的支持!

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

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

王大志 刘士新 郭希旺

王大志, 刘士新, 郭希旺. 求解总拖期时间最小化流水车间调度问题的多智能体进化算法. 自动化学报, 2014, 40(3): 548-555. doi: 10.3724/SP.J.1004.2014.00548
引用本文: 王大志, 刘士新, 郭希旺. 求解总拖期时间最小化流水车间调度问题的多智能体进化算法. 自动化学报, 2014, 40(3): 548-555. doi: 10.3724/SP.J.1004.2014.00548
WANG Da-Zhi, LIU Shi-Xin, GUO Xi-Wang. A Multi-agent Evolutionary Algorithm for Solving Total Tardiness Permutation Flow-shop Scheduling Problem. ACTA AUTOMATICA SINICA, 2014, 40(3): 548-555. doi: 10.3724/SP.J.1004.2014.00548
Citation: WANG Da-Zhi, LIU Shi-Xin, GUO Xi-Wang. A Multi-agent Evolutionary Algorithm for Solving Total Tardiness Permutation Flow-shop Scheduling Problem. ACTA AUTOMATICA SINICA, 2014, 40(3): 548-555. doi: 10.3724/SP.J.1004.2014.00548

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


DOI: 10.3724/SP.J.1004.2014.00548
详细信息
    作者简介:

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

    通讯作者: 王大志
  • 基金项目:

    国家自然科学基金(61333006,71171038),中央高校基本科研业务费(N110404024)资助

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

More Information
  • Fund Project:

    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个测试问题,并将测试结果与一些代表算法进行比较,验证了该算法的有效性.
  • [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
  • [1] 李金忠, 刘关俊, 闫春钢, 蒋昌俊. 排序学习研究进展与展望[J]. 自动化学报, 2018, 44(8): 1345-1369. doi: 10.16383/j.aas.2018.c170246
    [2] 张晓东, 高绍姝, 刘新平. 多速率分布式预测控制及其在热连轧活套系统中的应用[J]. 自动化学报, 2018, 44(5): 935-942. doi: 10.16383/j.aas.2017.c160355
    [3] 王芳, 唐秋华, 饶运清, 张超勇, 张利平. 求解柔性流水车间调度问题的高效分布估算算法[J]. 自动化学报, 2017, 43(2): 280-293. doi: 10.16383/j.aas.2017.c150873
    [4] 陈美蓉, 郭一楠, 巩敦卫, 杨振. 一类新型动态多目标鲁棒进化优化方法[J]. 自动化学报, 2017, 43(11): 2014-2032. doi: 10.16383/j.aas.2017.c160300
    [5] 陈振兴, 严宣辉, 吴坤安, 白猛. 融合张角拥挤控制策略的高维多目标优化[J]. 自动化学报, 2015, 41(6): 1145-1158. doi: 10.16383/j.aas.2015.c140555
    [6] 李长生, 王玉振. 端口受控哈密顿多智能体系统的输出一致性协议设计[J]. 自动化学报, 2014, 40(3): 415-422. doi: 10.3724/SP.J.1004.2014.00415
    [7] 罗小元, 杨帆, 李绍宝, 关新平. 多智能体系统的最优持久编队生成策略[J]. 自动化学报, 2014, 40(7): 1311-1319. doi: 10.3724/SP.J.1004.2014.01311
    [8] 于坤杰, 王昕, 王振雷. 基于反馈的精英教学优化算法[J]. 自动化学报, 2014, 40(9): 1976-1983. doi: 10.3724/SP.J.1004.2014.01976
    [9] 李中奇, 杨辉, 张坤鹏, 付雅婷. 基于多智能体模型的动车组分布式预测控制[J]. 自动化学报, 2014, 40(11): 2625-2631. doi: 10.3724/SP.J.1004.2014.02625
    [10] 高维尚, 邵诚. 复杂非凸约束优化难题与迭代动态多样进化算法[J]. 自动化学报, 2014, 40(11): 2469-2479. doi: 10.3724/SP.J.1004.2014.02469
    [11] 曾莉, 胡广大. 含通信延时及输入延时的线性多智能体的一致性[J]. 自动化学报, 2013, 39(7): 1133-1140. doi: 10.3724/SP.J.1004.2013.01133
    [12] 罗小元, 邵士凯, 关新平, 赵渊洁. 多智能体最优持久编队动态生成与控制[J]. 自动化学报, 2013, 39(9): 1431-1438. doi: 10.3724/SP.J.1004.2013.01431
    [13] 王圣尧, 王凌, 许烨, 周刚. 求解混合流水车间调度问题的分布估计算法[J]. 自动化学报, 2012, 38(3): 437-443. doi: 10.3724/SP.J.1004.2012.00437
    [14] 余宏旺, 郑毓蕃. 多智能体系统在分布式采样控制下的动力学行为[J]. 自动化学报, 2012, 38(3): 357-365. doi: 10.3724/SP.J.1004.2012.00357
    [15] 严卫生, 李俊兵, 王银涛. 受损多智能体系统的信息一致性[J]. 自动化学报, 2012, 38(11): 1880-1884. doi: 10.3724/SP.J.1004.2012.01880
    [16] 郭锐, 吴敏, 彭军, 彭姣, 曹卫华. 一种新的多智能体Q学习算法[J]. 自动化学报, 2007, 33(4): 367-372. doi: 10.1360/aas-007-0367
    [17] 李翔龙, 殷国富, 罗红波. 进化神经网络在机床工具损耗预测中的应用[J]. 自动化学报, 2004, 30(1): 114-119.
    [18] 唐立新, 吴亚萍. 混合流水车间调度的遗传下降算法[J]. 自动化学报, 2002, 28(4): 637-641.
    [19] 欧海涛, 张卫东, 许晓鸣. 基于一般和随机对策论框架下的多智能体学习[J]. 自动化学报, 2002, 28(3): 423-426.
    [20] 丁永生, 任立红, 邵世煌. 采用新的DNA进化算法自动设计Takagi-Sugeno模糊控制器[J]. 自动化学报, 2001, 27(4): 510-520.
  • 加载中
计量
  • 文章访问数:  1102
  • HTML全文浏览量:  58
  • PDF下载量:  1263
  • 被引次数: 0
出版历程
  • 收稿日期:  2012-12-12
  • 修回日期:  2013-04-19
  • 刊出日期:  2014-03-20

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

doi: 10.3724/SP.J.1004.2014.00548
    基金项目:

    国家自然科学基金(61333006,71171038),中央高校基本科研业务费(N110404024)资助

    作者简介:

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

    通讯作者: 王大志

摘要: 针对总拖期时间最小化的置换流水车间调度问题(Total tardiness permutation flow-shop scheduling problem) 提出了一种基于多智能体的进化搜索算法. 在该算法中,采用基于延迟时间排序的学习搜索策略(Tardiness rank based learning),快速产生高质量的新个体,并根据概率更新模型进行智能体网格的更新进化. 同时通过实验设计的方法探讨了算法参数设置对算法性能的影响. 为了验证算法的性能,求解了Vallada标准测试集中540个测试问题,并将测试结果与一些代表算法进行比较,验证了该算法的有效性.

English Abstract

王大志, 刘士新, 郭希旺. 求解总拖期时间最小化流水车间调度问题的多智能体进化算法. 自动化学报, 2014, 40(3): 548-555. doi: 10.3724/SP.J.1004.2014.00548
引用本文: 王大志, 刘士新, 郭希旺. 求解总拖期时间最小化流水车间调度问题的多智能体进化算法. 自动化学报, 2014, 40(3): 548-555. doi: 10.3724/SP.J.1004.2014.00548
WANG Da-Zhi, LIU Shi-Xin, GUO Xi-Wang. A Multi-agent Evolutionary Algorithm for Solving Total Tardiness Permutation Flow-shop Scheduling Problem. ACTA AUTOMATICA SINICA, 2014, 40(3): 548-555. doi: 10.3724/SP.J.1004.2014.00548
Citation: WANG Da-Zhi, LIU Shi-Xin, GUO Xi-Wang. A Multi-agent Evolutionary Algorithm for Solving Total Tardiness Permutation Flow-shop Scheduling Problem. ACTA AUTOMATICA SINICA, 2014, 40(3): 548-555. doi: 10.3724/SP.J.1004.2014.00548
参考文献 (21)

目录

    /

    返回文章
    返回