| 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] | ZHANG Y L，MA Z Z，SHI L，et al. Multi-agent coverage control based on communication connectivity maintenance constraints[J]. Journal of Beijing University of Aeronautics and Astronautics，2024，50（2）：519-528 （in Chinese）. doi: 10.13700/j.bh.1001-5965.2022.0340. |
| [2] | LI Hong, XU Chenyan, LIU Hengyu. Research on geomagnetic sensing navigation method based on deep reinforcement learning + simulated annealing[J]. Journal of Beijing University of Aeronautics and Astronautics. doi: 10.13700/j.bh.1001-5965.2024.0340 |
| [3] | Xu Zhonghui, Rao Zhenyuan, Ma Yanli, Tang Zejing, Huang Xiaodong. An Ocean Predator Algorithm Incorporating Hybrid Search Operators and Competitive Learning and Applications[J]. Journal of Beijing University of Aeronautics and Astronautics. doi: 10.13700/j.bh.1001-5965.2024.0243 |
| [4] | 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 |
| [5] | 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. |
| [6] | LI R N，FENG X，YAO Y P，et al. Multi-objective optimization of airport runway construction schemes based on improved genetic algorithm[J]. Journal of Beijing University of Aeronautics and Astronautics，2024，50（12）：3720-3728 （in Chinese）. doi: 10.13700/j.bh.1001-5965.2022.0893. |
| [7] | 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. |
| [8] | WEN C，DONG W H，XIE W J，et al. Multi-UAVs 3D cooperative curve path planning method based on CEA-GA[J]. Journal of Beijing University of Aeronautics and Astronautics，2023，49（11）：3086-3099 （in Chinese）. doi: 10.13700/j.bh.1001-5965.2021.0787. |
| [9] | CHEN S Z，LI D C，XIANG J W. Design optimization of tow-steered composite structure targeting on manufacturing cost[J]. Journal of Beijing University of Aeronautics and Astronautics，2023，49（9）：2423-2431 （in Chinese）. doi: 10.13700/j.bh.1001-5965.2021.0677. |
| [10] | JIANG L，SUN R，LIU Z W，et al. Modeling and accuracy analysis of GNSS ionospheric error in EU-China based on GA-BP[J]. Journal of Beijing University of Aeronautics and Astronautics，2023，49（6）：1533-1542 （in Chinese）. doi: 10.13700/j.bh.1001-5965.2021.0476. |
| [11] | HE J C，HE Z X，WANG F S，et al. Circuit area optimization of multi-output MPRM based on ERWOA algorithm[J]. Journal of Beijing University of Aeronautics and Astronautics，2023，49（5）：1193-1200 （in Chinese）. doi: 10.13700/j.bh.1001-5965.2021.0410. |
| [12] | YAN Y，MA X L. Air freight route planning based on transshipment under air alliance[J]. Journal of Beijing University of Aeronautics and Astronautics，2023，49（1）：115-127 （in Chinese）. doi: 10.13700/j.bh.1001-5965.2021.0166. |
| [13] | 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. |
| [14] | MA Su-hui, ZHANG Dong, WANG Meng-yang, WANG Ting-hui, LIU Song-dan. Directed interactive topology optimization design for multi-agent affine formation maneuver control[J]. Journal of Beijing University of Aeronautics and Astronautics. doi: 10.13700/j.bh.1001-5965.2023.0180 |
| [15] | 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. |
| [16] | 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 |
| [17] | 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. |
| [18] | ZHU Jiazheng, WANG Cong, LI Xinkai, DONG Yingchao, ZHANG Hongli. A deep reinforcement learning based discrete state transition algorithm for fuzzy flexible job shop scheduling[J]. Journal of Beijing University of Aeronautics and Astronautics. doi: 10.13700/j.bh.1001-5965.2023.0211 |
| [19] | JIANG Hao, LIU Jixin, DONG Xinfang. Dynamic collaborative sequencing for departure flights based on traffic state[J]. Journal of Beijing University of Aeronautics and Astronautics, 2022, 48(10): 2048-2060. doi: 10.13700/j.bh.1001-5965.2021.0066 |
| [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 |
| 1. | 高慕云，李榜华，马浩亮，张福礼，贺可太. 基于Petri网和改进遗传算法的多资源调度问题. 计算机工程与设计. 2024(06): 1674-1682 .  | |
| 2. | 崔巍巍，王德芯，李连峰，王亮，刘冠军，陈志伟. 流程驱动的导弹装备保障资源配置仿真与优化. 系统工程与电子技术. 2024(09): 3040-3049 . | |
| 3. | 唐丽君，彭石燕. 混合花朵授粉算法在作业车间调度中的应用. 工程数学学报. 2022(06): 997-1004 . | |
| 4. | 李翰墨，叶军，杨立芳，张旭. 柔性作业车间调度问题及其算法的研究. 轴承. 2020(11): 19-23 . | |
| 5. | 何东东. 柔性作业车间调度优化的改进遗传退火算法. 制造业自动化. 2019(01): 83-88 . | |
| 6. | 王慧敏，周筑南，张凤航，郭慧，景一. 基于车间作业调度模型的RGV动态调度. 物联网技术. 2019(10): 64-66+70 . | |
| 7. | 仲美稣，杨勇生，周亚民，马泽宇. 基于群智能算法的自动化码头协同调度研究. 计算机应用研究. 2019(12): 3756-3759 . | |
| 8. | 朱兴林. 动态蚁群遗传混合算法在煤炭运输中的应用. 自动化与仪器仪表. 2018(09): 180-181+184 . | |
| 9. | 王艺翔，洪良，田海霖，王晓华. 基于时间Petri网的自动制造系统排产优化方法. 西安工程大学学报. 2018(05): 590-596 . | |
| 10. | 轩华，秦莹莹，王薛苑，张百林. 带恶化工件的PFS调度的混合遗传算法. 工业工程与管理. 2017(03): 1-6+15 . | |
| 11. | 黄俊生，广晓平. 关于生产车间作业优化调度效率仿真研究. 制造业自动化. 2017(10): 95-99 . |
Figures(7) / Tables(2)
Copyright © Journal of Beijing University of Aeronautics and Astronautics
Address: Editorial Department of Journal of Beijing University of Aeronautics and Astronautics, 37 Xueyuan Road, Haidian District, Beijing Post Code: 100191 Email: jbuaa@buaa.edu.cn
Supported by:
Beijing Renhe Information Technology Co., Ltd.
DING Chao, WEI Ruixuan, ZHOU Kaiet al. Distributed optimal rendezvous of multi-UAV systems in prescribed time based on time-domain mapping[J]. Journal of Beijing University of Aeronautics and Astronautics, 2021, 47(2): 315-322. doi: 10.13700/j.bh.1001-5965.2020.0215(in Chinese)
DownLoad:
