Automated Design of Production Scheduling Heuristics: A Review

被引:318
作者
Branke, Juergen [1 ]
Su Nguyen [2 ]
Pickardt, Christoph W. [1 ]
Zhang, Mengjie [2 ]
机构
[1] Univ Warwick, Warwick Business Sch, Coventry CV4 7AL, W Midlands, England
[2] Victoria Univ Wellington, Evolutionary Computat Res Grp, Wellington 6140, New Zealand
关键词
Evolutionary design; genetic programming (GP); hyper-heuristic; scheduling; DISPATCHING RULES; JOB-SHOP; GENETIC ALGORITHM; SINGLE-MACHINE; HYPER-HEURISTICS; PRIORITY RULES; SEARCH; SIMULATION; TARDINESS; GENERATION;
D O I
10.1109/TEVC.2015.2429314
中图分类号
TP18 [人工智能理论];
学科分类号
081104 ; 0812 ; 0835 ; 1405 ;
摘要
Hyper-heuristics have recently emerged as a powerful approach to automate the design of heuristics for a number of different problems. Production scheduling is a particularly popular application area for which a number of different hyper-heuristics have been developed and are shown to be effective, efficient, easy to implement, and reusable in different shop conditions. In particular, they seem to be a promising way to tackle highly dynamic and stochastic scheduling problems, an aspect that is specifically emphasized in this survey. Despite their success and the substantial number of papers in this area, there is currently no systematic discussion of the design choices and critical issues involved in the process of developing such approaches. This paper strives to fill this gap by summarizing the state-of-the-art approaches, suggesting a taxonomy, and providing the interested researchers and practitioners with guidelines for the design of hyper-heuristics in production scheduling. This paper also identifies challenges and open questions and highlights various directions for future work.
引用
收藏
页码:110 / 124
页数:15
相关论文
共 101 条
[21]  
Cheng V. H. L., 1999, Proceedings of the 1999 IEEE International Conference on Control Applications (Cat. No.99CH36328), P249, DOI 10.1109/CCA.1999.806209
[22]   Investigating the use of genetic programming for a classic one-machine scheduling problem [J].
Dimopoulos, C ;
Zalzala, AMS .
ADVANCES IN ENGINEERING SOFTWARE, 2001, 32 (06) :489-498
[23]   EVOLUTION BASED LEARNING IN A JOB-SHOP SCHEDULING ENVIRONMENT [J].
DORNDORF, U ;
PESCH, E .
COMPUTERS & OPERATIONS RESEARCH, 1995, 22 (01) :25-40
[24]  
Eguchi T., 1999, Global Production Management. IFIP WG5.7 International Conference on Advances in Production Management Systems, P152
[25]   A robust scheduling rule using a Neural Network in dynamically changing job-shop environments [J].
Graduate School of Engineering, Hiroshima University, 1-4-1, Kagamiyama, Higashi-Hiroshima, 739-8527, Japan ;
不详 ;
不详 ;
不详 .
Int. J. Manuf. Technol. Manage., 2008, 3-4 (266-288) :266-288
[26]   Sequencing jobs on a single machine: A neural network approach [J].
El-Bouri, A ;
Balakrisknan, S ;
Popplewell, N .
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2000, 126 (03) :474-490
[28]  
Fisher H, 1963, IND SCHEDULING, P225
[29]   Evolutionary algorithms for the resource constrained scheduling problem [J].
Frankola, Toni ;
Golub, Marin ;
Jakobovic, Domagoj .
PROCEEDINGS OF THE ITI 2008 30TH INTERNATIONAL CONFERENCE ON INFORMATION TECHNOLOGY INTERFACES, 2008, :715-722
[30]  
Garey M. R., 1976, Mathematics of Operations Research, V1, P117, DOI 10.1287/moor.1.2.117