An effective genetic algorithm for the flexible job-shop scheduling problem

被引：341
作者：
Zhang, Guohui [2 ]
Gao, Liang [1 ]
Shi, Yang [1 ]
机构：
[1] Huazhong Univ Sci & Technol, State Key Lab Digital Mfg Equipment & Technol, Wuhan 430074, Peoples R China
[2] Zhengzhou Inst Aeronaut Ind Management, Zhengzhou 450015, Peoples R China
来源：
EXPERT SYSTEMS WITH APPLICATIONS | 2011年 / 38卷 / 04期
基金：
中国国家自然科学基金;
关键词：
Genetic algorithm; Flexible job-shop scheduling; Chromosome representation; Initialization;
D O I：
10.1016/j.eswa.2010.08.145
中图分类号：
TP18 [人工智能理论];
学科分类号：
081104 ; 0812 ; 0835 ; 1405 ;
摘要：
In this paper, we proposed an effective genetic algorithm for solving the flexible job-shop scheduling problem (FJSP) to minimize makespan time. In the proposed algorithm, Global Selection (GS) and Local Selection (LS) are designed to generate high-quality initial population in the initialization stage. An improved chromosome representation is used to conveniently represent a solution of the FJSP, and different strategies for crossover and mutation operator are adopted. Various benchmark data taken from literature are tested. Computational results prove the proposed genetic algorithm effective and efficient for solving flexible job-shop scheduling problem. (C) 2010 Elsevier Ltd. All rights reserved.
引用
收藏
页码：3563 / 3573
页数：11
相关论文
共 32 条
[1]  
[Anonymous], 1996, TECHNICAL REPORT SER
[2]  
Brandimarte P., 1993, Annals of Operations Research, V41, P157, DOI 10.1007/BF02023073
[3]   JOB-SHOP SCHEDULING WITH MULTIPURPOSE MACHINES [J].
BRUCKER, P ;
SCHLIE, R .
COMPUTING, 1990, 45 (04) :369-375
[4]  
Chen HX, 1999, ICRA '99: IEEE INTERNATIONAL CONFERENCE ON ROBOTICS AND AUTOMATION, VOLS 1-4, PROCEEDINGS, P1120, DOI 10.1109/ROBOT.1999.772512
[5]   An integrated approach for modeling and solving the general multiprocessor job-shop scheduling problem using tabu search [J].
DauzerePeres, S ;
Paulli, J .
ANNALS OF OPERATIONS RESEARCH, 1997, 70 (0) :281-306
[6]  
Fisher H, 1963, IND SCHEDULING, P225
[7]  
Gambardella L, 1996, J SCHEDULING, V3, P3, DOI [10.1002/(SICI)1099-1425(200001/02)3:13::AID-JOS323.0.CO
[8]  
2-Y, DOI 10.1002/(SICI)1099-1425(200001/02)3]
[9]   A hybrid genetic and variable neighborhood descent algorithm for flexible job shop scheduling problems [J].
Gao, Jie ;
Sun, Linyan ;
Gen, Mitsuo .
COMPUTERS & OPERATIONS RESEARCH, 2008, 35 (09) :2892-2907
[10]  
Garey M. R., 1976, Mathematics of Operations Research, V1, P117, DOI 10.1287/moor.1.2.117
1234