| 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. 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
|
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.
DownLoad:
