A tutorial survey of job-shop scheduling problems using genetic algorithms, part II: hybrid genetic search strategies

被引:222
作者
Cheng, RW [1 ]
Gen, M
Tsujimura, Y
机构
[1] Northeastern Univ, Coll Informat Sci & Engn, Dept Syst Engn, Shenyang 110006, Peoples R China
[2] Ashikaga Inst Technol, Dept Ind Engn & Informat Syst, Ashikaga 3268558, Japan
关键词
genetic algorithms; job-shop scheduling; combinatorial optimization problem; hybrid heuristics;
D O I
10.1016/S0360-8352(99)00136-9
中图分类号
TP39 [计算机的应用];
学科分类号
081203 ; 0835 ;
摘要
Job-shop scheduling problem is one of the well-known hardest combinatorial optimization problems. During the last three decades, this problem has captured the interest of a significant number of researchers. A lot of literature has been published, but no efficient solution algorithm has been found yet for solving it to optimality in polynomial time. This has led to recent interest in using genetic algorithms to address the problem. How to adapt genetic algorithms to the job-shop scheduling problems is very challenging but frustrating. Many efforts have been made in order to give an efficient implementation of genetic algorithms to the problem. During the past decade, two important issues have been extensively studied. One is how to encode a solution of the problem into a chromosome so as to ensure that a chromosome will correspond to a feasible solution. The other issue is how to enhance the performance of genetic search by incorporating traditional heuristic methods. Because the genetic algorithms are not well suited for fine-tuning of solutions around optima, various methods of hybridization have been suggested to compensate for this shortcoming. The purpose of the paper is to give a tutorial survey of recent works on various hybrid approaches in genetic job-shop scheduling practices; The research on how to adapt the genetic algorithms to the job-shop scheduling problem provide very rich experiences for the constrained combinatorial optimization problems. All of the techniques developed for the problem are very useful for other scheduling problems in modern flexible manufacturing systems and other difficult-to-solve combinatorial optimization problems. (C) 1999 Published by Elsevier Science Ltd. All rights reserved.
引用
收藏
页码:343 / 364
页数:22
相关论文
共 34 条
[1]   THE SHIFTING BOTTLENECK PROCEDURE FOR JOB SHOP SCHEDULING [J].
ADAMS, J ;
BALAS, E ;
ZAWACK, D .
MANAGEMENT SCIENCE, 1988, 34 (03) :391-401
[2]  
[Anonymous], 1991, Handbook of genetic algorithms
[3]  
Applegate D., 1991, ORSA Journal on Computing, V3, P149, DOI 10.1287/ijoc.3.2.149
[4]  
Baker KR., 1974, Introduction to Sequencing and Scheduling
[5]   A STATE-OF-THE-ART SURVEY OF DISPATCHING RULES FOR MANUFACTURING JOB SHOP OPERATIONS [J].
BLACKSTONE, JH ;
PHILLIPS, DT ;
HOGG, GL .
INTERNATIONAL JOURNAL OF PRODUCTION RESEARCH, 1982, 20 (01) :27-45
[6]   OPTIMIZATION STRATEGIES GLEANED FROM BIOLOGICAL EVOLUTION [J].
BRADY, RM .
NATURE, 1985, 317 (6040) :804-806
[7]  
BROUCKER P, 1998, SCHEDULING ALGORITHM
[8]  
Cheng R., 1997, THESIS TOKYO I TECHN
[9]   A tutorial survey of job-shop scheduling problems using genetic algorithms .1. Representation [J].
Cheng, RW ;
Gen, M ;
Tsujimura, Y .
COMPUTERS & INDUSTRIAL ENGINEERING, 1996, 30 (04) :983-997
[10]  
Davis L, 1985, P 9 INT JOINT C ARTI, V1, P162