Guided local search with shifting bottleneck for job shop scheduling

被引:268
作者
Balas, E [1 ]
Vazacopoulos, A
机构
[1] Carnegie Mellon Univ, Grad Sch Ind Adm, Pittsburgh, PA 15213 USA
[2] Fairleigh Dickinson Univ, Madison, NJ 07940 USA
关键词
job shop scheduling; local search; shifting bottleneck; neighborhood trees;
D O I
10.1287/mnsc.44.2.262
中图分类号
C93 [管理学];
学科分类号
12 ; 1201 ; 1202 ; 120202 ;
摘要
Many recently developed local search procedures for job shop scheduling use interchange of operations, embedded in a simulated annealing or tabu search framework. We develop a new variable depth search procedure, GLS (Guided Local Search), based on an interchange scheme and using the new concept of neighborhood trees. Structural properties of the neighborhood are used to guide the search in promising directions. While this procedure competes successfully with others even as a stand-alone, a hybrid procedure that embeds GLS into a Shifting Bottleneck framework and takes advantage of the differences between the two neighborhood structures proves to be particularly efficient. We report extensive computational testing on all the problems available from the literature.
引用
收藏
页码:262 / 275
页数:14
相关论文
共 33 条
[1]  
AARTS EHL, 1994, ORSA J COMPUTING, V6, P108
[2]   THE SHIFTING BOTTLENECK PROCEDURE FOR JOB SHOP SCHEDULING [J].
ADAMS, J ;
BALAS, E ;
ZAWACK, D .
MANAGEMENT SCIENCE, 1988, 34 (03) :391-401
[3]  
[Anonymous], PARALLEL INSTANCE SO
[4]  
Applegate D., 1991, ORSA J COMPUTING, V3, DOI 10.1287/ijoc.3.2.149
[5]  
Baker KR., 1974, Introduction to Sequencing and Scheduling
[7]   THE ONE-MACHINE PROBLEM WITH DELAYED PRECEDENCE CONSTRAINTS AND ITS USE IN JOB-SHOP SCHEDULING [J].
BALAS, E ;
LENSTRA, JK ;
VAZACOPOULOS, A .
MANAGEMENT SCIENCE, 1995, 41 (01) :94-109
[8]  
BALAS E, 1995, 609 MSRR GSIA CARN M
[9]   SOLVING THE JOB-SHOP SCHEDULING PROBLEM WITH TABU SEARCH [J].
BARNES, JW ;
CHAMBERS, JB .
IIE TRANSACTIONS, 1995, 27 (02) :257-263
[10]  
Blazewicz J, 1992, SCHEDULING COMPUTER