Applying tabu search to the job-shop scheduling problem. (English) Zbl 0771.90056

Dell’Amico, Mauro; Trubian, Marco

Ann. Oper. Res. 41, No. 1-4, 231-252 (1993).

Summary: We apply the tabu search technique to the job-shop scheduling problem, a notoriously difficult problem in combinatorial optimization. We show that our implementation of this method dominates both a previous approach with tabu search and the other heuristics based on iterative improvements.

MSC:

90B35	Deterministic scheduling theory in operations research
90-08	Computational methods for problems pertaining to operations research and mathematical programming
90C27	Combinatorial optimization

Keywords:

tabu search; job-shop scheduling

Software:

JOBSHOP

References:

[1]	J. Adams, E. Balas and D. Zawack, The shifting bottleneck procedure for job-shop scheduling, Manag. Sci. 34(1988)391–401. · Zbl 0637.90051
[2]	D. Applegate and W. Cook, A computational study of the job-shop scheduling problem, ORSA J. Comput. 3(1990)149–156. · Zbl 0755.90039
[3]	P. Brucker, B. Jurisch and B. Sievers, A fast branch and bound algorithm for the job-shop scheduling problem, Internal Report 136, Fachbereich Mathematik/Informatik, Universität Osnabrück (1991). · Zbl 0802.90057
[4]	J. Carlier and E. Pinson, An algorithm for solving the job-shop problem, Manag. Sci. 35(1989)164–176. · Zbl 0677.90036
[5]	T. Feo, K. Venkatraman and J.F. Bard, A GRASP for single machine scheduling with due dates and earliness penalties, Internal Report, OR Group, Department of Mechanical Engineering, University of Texas, Austin, TX (1989).
[6]	M.R. Garey, D.S. Johnson and R. Sethi, The complexity of flowshop and jobshop scheduling, Math. Oper. Res. 1(1976)117–129. · Zbl 0396.90041
[7]	F. Glover, Tabu search, Part I, ORSA J. Comput. 1(1989)190–206.
[8]	F. Glover, Tabu search, Part II, ORSA J. Comput. 2(1990)4–32.
[9]	R.L. Graham, E.L. Lawler, J.K. Lenstra and A.H.G. Rinnooy Kan, Optimization and approximation in deterministic sequencing and scheduling: a survey, Ann. Discr. Math. 5(1979)287–326. · Zbl 0411.90044
[10]	J.P. Hart and A.W. Shogan, Semi-greedy heuristics: an empirical study, Oper. Res. Lett. 6(1987)107–114. · Zbl 0615.90082
[11]	S. Lawrence, Resource constrained project scheduling: an experimental investigation of heuristic scheduling techniques, GSIA, Carnegie-Mellon University (1984).
[12]	H. Matsuo, C.J. Suh and R.S. Sullivan, A controlled search simulated annealing method for the general jobshop scheduling problem, Working Paper 03-44-88, Graduate School of Business, University of Texas, Austin, TX (1988).
[13]	J.F. Muth and G.L. Thompson,Industrial Scheduling (Prentice-Hall, Englewood Cliffs, 1963).
[14]	R. Nakano and T. Yamada, Conventional genetic algorithm for job shop problems,Proc. 4th Int. Conf. on Geneting Algorithms, San Diego, CA (1991) pp. 474–479.
[15]	S.S. Panwalker and W. Iskander, A survey of scheduling rules, Oper. Res. 25(1977)45–61. · Zbl 0369.90054
[16]	B. Roy and B. Sussmann, Les Problèmes d’ordonnancement avec contraintes disjonctives, Note DS n.9 bis, SEMA, Montrouge (1964).
[17]	E. Taillard, Parallel taboo search technique for the jobshop scheduling problem, Internal Report ORWP 89/11, Départment de Mathématiques, Ecole Polytechnique Fédérale de Lausanne, Lausanne (1989).
[18]	P.J.M. van Laahroven, E.H.L. Aarts and J.K. Lenstra, Job shop scheduling by simulated annealing, Report OS-R8809, Centre for Mathematics and Computer Science, Amsterdam (1988). · Zbl 0751.90039
[19]	S.M. Johnson, Optimal two- and three-stage production schedules with setup times included, Naval Res. Logist. Quart. 1(1954)61–68. · Zbl 1349.90359