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) |
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] |
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.
|
[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.
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).
|
[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.
|
[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
|
[1] | ZHU J Z,WANG C,LI X K,et al. A deep reinforcement learning based on discrete state transition algorithm for solving fuzzy flexible job shop scheduling problem[J]. Journal of Beijing University of Aeronautics and Astronautics,2025,51(4):1385-1394 (in Chinese). doi: 10.13700/j.bh.1001-5965.2023.0211. |
[2] | LI F,LI Z H,CHEN A G. Boltzmann-Rykov model equation gas-kinetic unified algorithm and nozzle flow[J]. Journal of Beijing University of Aeronautics and Astronautics,2025,51(2):553-562 (in Chinese). doi: 10.13700/j.bh.1001-5965.2023.0054. |
[3] | MA S H,ZHANG D,WANG M Y,et al. Directed interactive topology optimization design for multi-agent affine formation maneuver control[J]. Journal of Beijing University of Aeronautics and Astronautics,2025,51(4):1367-1376 (in Chinese). doi: 10.13700/j.bh.1001-5965.2023.0180. |
[4] | HUANG Zhijie, LIU Wei, GUO Zhiqiang. Optimization Design of LLC Resonant Converters for Efficiency and Power Density Based on Genetic Algorithm[J]. Journal of Beijing University of Aeronautics and Astronautics. doi: 10.13700/j.bh.1001-5965.2024.0891 |
[5] | HAN Wei, HAN Xiaohua, SU Xichao, WANG Liusong, WU Haonan. Research on integrated scheduling of shipboard helicopters sortie operation on amphibious assault ship[J]. Journal of Beijing University of Aeronautics and Astronautics. doi: 10.13700/j.bh.1001-5965.2024.0085 |
[6] | LU M M,LIU C H,DONG Z L. Dynamic communication resource allocation for multi-UAV area coverage[J]. Journal of Beijing University of Aeronautics and Astronautics,2024,50(9):2939-2950 (in Chinese). doi: 10.13700/j.bh.1001-5965.2022.0745. |
[7] | LIU Y J,HAN W,SU X C,et al. Carrier aircraft landing scheduling problem based on improved gray wolf optimization[J]. Journal of Beijing University of Aeronautics and Astronautics,2024,50(3):803-813 (in Chinese). doi: 10.13700/j.bh.1001-5965.2022.0280. |
[8] | LI Yun-hong, ZHANG Fu-xing, SU Xue-ping, LI Li-min, WANG Mei, LIANG Cheng-ming. Real-time UAV image segmentation algorithm with enhanced contextual feature interaction[J]. Journal of Beijing University of Aeronautics and Astronautics. doi: 10.13700/j.bh.1001-5965.2023.0830 |
[9] | LUO Y L,LIAO Y R,LI Z M,et al. Strong tracking CKF adaptive interactive multiple model tracking algorithm based on hypersonic target[J]. Journal of Beijing University of Aeronautics and Astronautics,2024,50(7):2272-2283 (in Chinese). doi: 10.13700/j.bh.1001-5965.2022.0587. |
[10] | SHI T X,CHEN L S,LI T S,et al. Distributed adaptive anti-disturbance control for power systems based on multi-agents[J]. Journal of Beijing University of Aeronautics and Astronautics,2024,50(5):1685-1692 (in Chinese). doi: 10.13700/j.bh.1001-5965.2022.0496. |
[11] | DING G,CUI L J,HAN C,et al. Simulation evaluation and analysis of aircraft group support based on multi-agent[J]. Journal of Beijing University of Aeronautics and Astronautics,2023,49(9):2306-2316 (in Chinese). doi: 10.13700/j.bh.1001-5965.2021.0685. |
[12] | HU Qiang-liang, CHEN Lin, SHANG Ming-sheng. Pedestrian attribute recognition algorithm based on multi-label adversarial domain adaptation[J]. Journal of Beijing University of Aeronautics and Astronautics. doi: 10.13700/j.bh.1001-5965.2023.0386 |
[13] | TANG Y Q,LI C H,SONG Y F,et al. Adaptive mutation sparrow search optimization algorithm[J]. Journal of Beijing University of Aeronautics and Astronautics,2023,49(3):681-692 (in Chinese). doi: 10.13700/j.bh.1001-5965.2021.0282. |
[14] | SHI X S,LIN Z Y. Fixed-time distributed convex algorithm over second-order multi-agent systems under bounded disturbances[J]. Journal of Beijing University of Aeronautics and Astronautics,2023,49(11):2951-2959 (in Chinese). doi: 10.13700/j.bh.1001-5965.2022.0060. |
[15] | ZHANG Y H,LYU N,MIAO J C,et al. Improved intelligent detection algorithm for SPMA protocol channel state based on recurrent neural network[J]. Journal of Beijing University of Aeronautics and Astronautics,2023,49(3):735-744 (in Chinese). doi: 10.13700/j.bh.1001-5965.2021.0309. |
[16] | WANG Z Q,LI J,LI J,et al. UAV swarm decision methods under weak information interaction conditions[J]. Journal of Beijing University of Aeronautics and Astronautics,2023,49(12):3489-3499 (in Chinese). doi: 10.13700/j.bh.1001-5965.2022.0066. |
[17] | XING Na, DI Hao-tian, YIN Wen-jie, HAN Ya-jun, ZHOU Yang. Path planning for agents based on adaptive polymorphic ant colony optimization[J]. Journal of Beijing University of Aeronautics and Astronautics. doi: 10.13700/j.bh.1001-5965.2023.0432 |
[18] | SHI T,ZHUANG X B,LIN Z J,et al. Satellite selection based on parallel genetic algorithm for high orbit autonomous satellite navigation[J]. Journal of Beijing University of Aeronautics and Astronautics,2023,49(12):3528-3536 (in Chinese). doi: 10.13700/j.bh.1001-5965.2022.0118. |
[19] | YANG B,HE Y Z,XU F,et al. Using improved genetic algorithm for software fault localization aided test case generation[J]. Journal of Beijing University of Aeronautics and Astronautics,2023,49(9):2279-2288 (in Chinese). doi: 10.13700/j.bh.1001-5965.2022.0524. |
[20] | ZHANG Libo, LI Yupeng, ZHU Deming, FU Yongling. Inverse kinematic solution of nursing robot based on genetic algorithm[J]. Journal of Beijing University of Aeronautics and Astronautics, 2022, 48(10): 1925-1932. doi: 10.13700/j.bh.1001-5965.2021.0042 |