A tabu search method guided by shifting bottleneck for the job shop scheduling problem

被引:222
作者
Pezzella, F [1 ]
Merelli, E [1 ]
机构
[1] Univ Ancona, Ist Informat, I-60131 Ancona, Italy
关键词
production scheduling; jobshop; heuristics; tabu search;
D O I
10.1016/S0377-2217(99)00158-7
中图分类号
C93 [管理学];
学科分类号
12 [管理学]; 1201 [管理科学与工程]; 1202 [工商管理学]; 120202 [企业管理];
摘要
A computationally effective heuristic method for solving the minimum makespan problem of job shop scheduling is presented. The proposed local search method is based on a tabu search technique and on the shifting bottleneck procedure used to generate the initial solution and to refine the next-current solutions. Computational experiments on a standard set of problem instances show that, in several cases, our approach, in a reasonable amount of computer time, yields better results than the other heuristic procedures discussed in the literature. (C) 2000 Elsevier Science B.V. All rights reserved.
引用
收藏
页码:297 / 310
页数:14
相关论文
共 27 条
[1]
AARTS E, 1997, LOCAL SEARCH COMBINA
[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], 1997, Tabu Search
[4]
Applegate D., 1991, ORSA Journal on Computing, V3, P149, DOI 10.1287/ijoc.3.2.149
[6]
BLAAS E, 1994, MSRR609 GSIA CARN ME
[7]
THE ONE-MACHINE SEQUENCING PROBLEM [J].
CARLIER, J .
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 1982, 11 (01) :42-47
[8]
AN ALGORITHM FOR SOLVING THE JOB-SHOP PROBLEM [J].
CARLIER, J ;
PINSON, E .
MANAGEMENT SCIENCE, 1989, 35 (02) :164-176
[9]
Dell'Amico M., 1993, Annals of Operations Research, V41, P231, DOI 10.1007/BF02023076
[10]
Fisher H., 1963, IND SCHEDULING, P225