留言板

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

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

基于混合多智能体遗传算法的作业车间调度问题研究

李小涛 彭翀

李小涛, 彭翀. 基于混合多智能体遗传算法的作业车间调度问题研究[J]. 北京航空航天大学学报, 2017, 43(2): 410-416. doi: 10.13700/j.bh.1001-5965.2016.0103
引用本文: 李小涛, 彭翀. 基于混合多智能体遗传算法的作业车间调度问题研究[J]. 北京航空航天大学学报, 2017, 43(2): 410-416. doi: 10.13700/j.bh.1001-5965.2016.0103
LI Xiaotao, PENG Chong. Hybrid multiagent genetic algorithm for job shop scheduling problem[J]. Journal of Beijing University of Aeronautics and Astronautics, 2017, 43(2): 410-416. doi: 10.13700/j.bh.1001-5965.2016.0103(in Chinese)
Citation: LI Xiaotao, PENG Chong. Hybrid multiagent genetic algorithm for job shop scheduling problem[J]. Journal of Beijing University of Aeronautics and Astronautics, 2017, 43(2): 410-416. doi: 10.13700/j.bh.1001-5965.2016.0103(in Chinese)

基于混合多智能体遗传算法的作业车间调度问题研究

doi: 10.13700/j.bh.1001-5965.2016.0103
基金项目: 

国家重大科技专项 2015ZX04005005

详细信息
    作者简介:

    李小涛, 男, 硕士研究生。主要研究方向:智能优化算法理论及其应用

    彭翀, 男, 博士, 高级实验师。主要研究方向:制造过程优化方法研究及应用、数控装备可靠性技术

    通讯作者:

    彭翀, E-mail:pch@buaa.edu.cn

  • 中图分类号: TP301.6;F406.2

Hybrid multiagent genetic algorithm for job shop scheduling problem

Funds: 

National Science and Technology Major Project 2015ZX04005005

More Information
  • 摘要:

    针对作业车间调度问题(JSP)的非确定性多项式特性与解空间分布的大山谷属性,本文提出一种多智能体遗传算法(MAGA)与自适应模拟退火算法(ASA)的混合优化算法,用于寻找最大完工时间最短的调度。首先,将每个染色体视作独立的智能体并采用工序编码方式随机初始化每个智能体,结合多智能体协作与竞争理论设计了实现智能体之间交互作用的邻居交互算子,进而利用一定数量智能体进行全局搜索,找到多个适应度较高的可行解。其次,为避免算法陷入局部最优,采用ASA对每个智能体开展局部寻优。最后,通过基准测试库中典型实例的计算结果验证了该算法的有效性。

     

  • 图 1  析取图模型

    Figure 1.  Disjunctive graph model

    图 2  多智能体网格系统[14]

    Figure 2.  Multiagent lattice system[14]

    图 3  轮流交叉算子

    Figure 3.  Alternating position crossover operator

    图 4  基本倒位变异算子

    Figure 4.  Simple inversion mutation operator

    图 5  移位变异算子

    Figure 5.  Displacement mutation operator

    图 6  混合多智能体遗传算法流程图

    Figure 6.  Flowchart of hybrid MAGA

    图 7  La27的调度甘特图

    Figure 7.  Gantt chart of La27

    表  1  3工件3机器JSP

    Table  1.   3-job 3-machine job shop scheduling problem

    工件 机器序列 加工时间
    J1 M3-M2-M1 2-3-6
    J2 M1-M3-M2 4-5-2
    J3 M2-M1-M3 3-5-4
    下载: 导出CSV

    表  2  计算结果对比

    Table  2.   Comparison of computational results

    实例
    代号
    实例
    规模
    已知
    最优解
    最好结果
    新算法 文献[6] 文献[8] 文献[17]
    Ft06 6×6 55 55 55 55 55
    Ft10 10×10 930 930 930 930 930
    Ft20 20×5 1 165 1 165 1 165 1 165 1165
    La01 10×5 666 666 666 666 666
    La02 10×5 655 655 655 655 655
    La03 10×5 597 597 597 597 597
    La04 10×5 590 590 590 590 590
    La05 10×5 593 593 593 593 593
    La06 15×5 926 926 926 926 926
    La07 15×5 890 890 890 890 890
    La08 15×5 863 863 863 863 863
    La09 15×5 951 951 951 951 951
    La10 15×5 958 958 958 958 958
    La11 20×5 1 222 1 222 1 222 1 222 1 222
    La12 20×5 1 039 1 039 1 039 1 039 1 039
    La13 20×5 1 150 1 150 1 150 1 150 1 150
    La14 20×5 1 292 1 292 1 292 1 292 1 292
    La15 20×5 1 207 1 207 1 207 1 207 1 207
    La16 10×10 945 945 945 945 945
    La17 10×10 784 784 784 784 784
    La18 10×10 848 848 848 848 848
    La19 10×10 842 842 842 842 842
    La20 10×10 902 902 907 902 902
    La21 15×10 1 046 1 046 1 052 1 046 1 046
    La22 15×10 927 927 930 927 927
    La23 15×10 1 032 1 032 1 032 1 032 1 032
    La24 15×10 935 938 941 941 940
    La25 15×10 977 977 977 977 984
    La26 20×10 1 218 1 218 1 218 1 218 1 218
    La27 20×10 1 235 1 235 1 246 1 239 1 261
    La28 20×10 1 216 1 216 1 216 1 216 1 216
    La29 20×10 1 152 1 175 1 165 1 173 1 190
    La30 20×10 1 355 1 355 1 355 1 355 1 355
    La31 30×10 1 784 1 784 1 784 1 784 1 784
    La32 30×10 1 850 1 850 1 850 1 850 1 850
    La33 30×10 1 719 1 719 1 719 1 719 1 719
    La34 30×10 1 271 1 271 1 271 1 271 1 271
    La35 30×10 1 888 1 888 1 888 1 888 1 888
    La36 15×15 1 268 1 285 1 279 1 278 1 281
    La37 15×15 1 397 1 397 1 407 1 397 1 431
    La38 15×15 1 196 1 196 1 213 1 208 1 196
    La39 15×15 1 233 1 240 1 244 1 233 1 241
    La40 15×15 1 222 1 224 1 233 1 225 1 233
    下载: 导出CSV
  • [1] GAREY M R, JOHNSON D S, SETHI R.The complexity of flowshop and job shop scheduling[J].Mathematics of Operations Research, 1976, 1(2):117-129. doi: 10.1287/moor.1.2.117
    [2] GIFFLER B, THOMPSON G L.Algorithms for solving productionscheduling problems[J].Operations Research, 1960, 8(4):487-503. doi: 10.1287/opre.8.4.487
    [3] ADAMS J, BALAS E, ZAWACK D.The shifting bottleneck procedure for job shop scheduling[J].Management Science, 1988, 34(3):391-401. doi: 10.1287/mnsc.34.3.391
    [4] BEASLEY J E.OR-library:Distributing test problems by electronic mails[J].Journal of Operation Research Society, 1990, 41(11):1069-1072. doi: 10.1057/jors.1990.166
    [5] APPLEGATE D, COOK W.A computational study of the job shop scheduling problem[J].ORSA Journal on Computing, 1991, 3(2):149-156. doi: 10.1287/ijoc.3.2.149
    [6] 赵诗奎, 方水良, 顾新建.作业车间调度的空闲时间邻域搜索遗传算法[J].计算机集成制造系统, 2014, 20(8):1930-1940. http://www.cnki.com.cn/Article/CJFDTOTAL-JSJJ201408015.htm

    ZHAO S K, FANG S L, GU X J.Idle time neighborhood search genetic algorithm for job shop scheduling[J].Computer Integrated Manufacturing Systems, 2014, 20(8):1930-1940(in Chinese). http://www.cnki.com.cn/Article/CJFDTOTAL-JSJJ201408015.htm
    [7] VAN LAARHOVEN P J M, AARTS E H L, LENSTRA J K.Job shop scheduling by simulated annealing[J].Operations Research, 1992, 40(1):113-125. doi: 10.1287/opre.40.1.113
    [8] LIN T L, HORNG S J, KAO T W, et al.An efficient job-shop scheduling algorithm based on particle swarm optimization[J].Expert Systems with Applications, 2010, 37(3):2629-2636. doi: 10.1016/j.eswa.2009.08.015
    [9] WANG X, DUAN H B.A hybrid biogeography-based optimization algorithm for job shop scheduling problem[J].Computers & Industrial Engineering, 2014, 73:96-114. https://www.researchgate.net/publication/262191523_A_hybrid_biogeography-based_optimization_algorithm_for_job_shop_scheduling_problem
    [10] CHENG R, GEN M, TSUJIMURA Y.A tutorial survey of job shop scheduling problems using genetic algorithms-I.Representation[J].Computers & Industrial Engineering, 1996, 30(4):983-997.
    [11] GORDINI N.A genetic algorithm approach for SMEs bankruptcy prediction:Empirical evidence from Italy[J].Expert Systems with Applications, 2014, 41(14):6433-6445. doi: 10.1016/j.eswa.2014.04.026
    [12] KUMAR K S, PAULRAJ G.Genetic algorithm based deformation control and clamping force optimisation of workpiece fixture system[J].International Journal of Production Research, 2011, 49(7):1903-1935. doi: 10.1080/00207540903499438
    [13] 陶杨, 韩维.基于改进多目标遗传算法的舰尾紊流模拟方法[J].北京航空航天大学学报, 2015, 41(3):443-448. http://bhxb.buaa.edu.cn/CN/abstract/abstract13186.shtml

    TAO Y, HAN W.Carrier airwake simulation methods based on improved multi-objective genetic algorithm[J].Journal of Beijing University of Aeronautics and Astronautics, 2015, 41(3):443-448(in Chinese). http://bhxb.buaa.edu.cn/CN/abstract/abstract13186.shtml
    [14] ZHONG W C, LIU J, XUE M Z, et al.A multiagent genetic algorithm for global numerical optimization[J].IEEE Transactions on Systems, Man, and Cybernetics, Part B:Cybernetics, 2004, 34(2):1128-1141. doi: 10.1109/TSMCB.2003.821456
    [15] SIVASUBRAMANI S, SWARUP K S.Multiagent based differential evolution approach to optimal power flow[J].Applied Soft Computing, 2012, 12(2):735-740. doi: 10.1016/j.asoc.2011.09.016
    [16] BLUM C, ROLI A.Metaheuristics in combinatorial optimization:Overview and conceptual comparison[J].ACM Computing Surveys (CSUR), 2003, 35(3):268-308. doi: 10.1145/937503
    [17] GAO L, ZHANG G H, ZHANG L P, et al.An efficient memetic algorithm for solving the job shop scheduling problem[J].Computers & Industrial Engineering, 2011, 60(4):699-705. https://www.researchgate.net/publication/222993816_An_efficient_memetic_algorithm_for_solving_the_job_shop_scheduling_problem
    [18] XIA W, WU Z.An effective hybrid optimization approach for multi-objective flexible job-shop scheduling problems[J].Computers & Industrial Engineering, 2005, 48(2):409-425.
    [19] HUANG M D, ROMEO F, SANGIOVANNI V A K.Efficient general cooling schedule for simulated annealing[C]//Proceeding of IEEE International Conference on Computer Aided Design.Piscataway, NJ:IEEE Press, 1986:381-384.
    [20] POTTS C N.Analysis of a heuristic for one machine sequencing with release dates and delivery times[J].Operations Research, 1980, 28(6):1436-1441. doi: 10.1287/opre.28.6.1436
    [21] BALAS E, VAZACOPOULOS A.Guided local search with shifting bottleneck for job shop scheduling[J].Management Science, 1998, 44(2):262-275. doi: 10.1287/mnsc.44.2.262
    [22] BAKER K R.Introduction to sequencing and scheduling[M].New York:John Wiley & Sons, 1974.
    [23] BALAS E.Machine scheduling via disjunctive graphs:An implicit enumeration algorithm[J].Operation Research, 1969, 17(6):941-957. doi: 10.1287/opre.17.6.941
  • 加载中
图(7) / 表(2)
计量
  • 文章访问数:  557
  • HTML全文浏览量:  6
  • PDF下载量:  660
  • 被引次数: 0
出版历程
  • 收稿日期:  2016-01-26
  • 录用日期:  2016-02-29
  • 刊出日期:  2017-02-20

目录

    /

    返回文章
    返回
    常见问答