-
摘要:
针对作业车间调度问题（JSP）的非确定性多项式特性与解空间分布的大山谷属性，本文提出一种多智能体遗传算法（MAGA）与自适应模拟退火算法（ASA）的混合优化算法，用于寻找最大完工时间最短的调度。首先，将每个染色体视作独立的智能体并采用工序编码方式随机初始化每个智能体，结合多智能体协作与竞争理论设计了实现智能体之间交互作用的邻居交互算子，进而利用一定数量智能体进行全局搜索，找到多个适应度较高的可行解。其次，为避免算法陷入局部最优，采用ASA对每个智能体开展局部寻优。最后，通过基准测试库中典型实例的计算结果验证了该算法的有效性。
-
关键词:
- 作业车间调度(JSP) /
- 多智能体 /
- 遗传算法 /
- 邻居交互算子 /
- 自适应模拟退火算法(ASA)
Abstract:For the NP-hard characteristic of job shop scheduling problem (JSP) and big valley property of its solution space, this paper proposes a hybrid algorithm based multiagent genetic algorithm (MAGA) and adaptive simulated annealing algorithm (ASA) to obtain the minimal makespan schedule. First, each chromosome is regarded as independent agent which is randomly initialized under condition of operation-based encoding method. Combined with multiagent cooperation and competition theory, a neighborhood interaction operator is designed to realize the interaction between agents, and then a certain number of agents are utilized to do global searching to find several individuals with high fitness. Second, in order to prevent the algorithm from falling into local optimum, ASA is adopted to carry out local optimization for each agent. Finally, the effectiveness of the proposed hybrid algorithm is verified by the computational results of typical problems from benchmark library.
-
表 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.htmZHAO 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.shtmlTAO 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 -
下载:
点击查看大图
计量
- 文章访问数: 939
- HTML全文浏览量: 59
- PDF下载量: 667
- 被引次数: 0
