Abstract
In this paper, 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.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
J. Adams, E. Balas and D. Zawack, The shifting bottleneck procedure for job-shop scheduling, Manag. Sci. 34(1988)391–401.
D. Applegate and W. Cook, A computational study of the job-shop scheduling problem, ORSA J. Comput. 3(1990)149–156.
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).
J. Carlier and E. Pinson, An algorithm for solving the job-shop problem, Manag. Sci. 35(1989)164–176.
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).
M.R. Garey, D.S. Johnson and R. Sethi, The complexity of flowshop and jobshop scheduling, Math. Oper. Res. 1(1976)117–129.
F. Glover, Tabu search, Part I, ORSA J. Comput. 1(1989)190–206.
F. Glover, Tabu search, Part II, ORSA J. Comput. 2(1990)4–32.
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.
J.P. Hart and A.W. Shogan, Semi-greedy heuristics: an empirical study, Oper. Res. Lett. 6(1987)107–114.
S. Lawrence, Resource constrained project scheduling: an experimental investigation of heuristic scheduling techniques, GSIA, Carnegie-Mellon University (1984).
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).
J.F. Muth and G.L. Thompson,Industrial Scheduling (Prentice-Hall, Englewood Cliffs, 1963).
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.
S.S. Panwalker and W. Iskander, A survey of scheduling rules, Oper. Res. 25(1977)45–61.
B. Roy and B. Sussmann, Les Problèmes d'ordonnancement avec contraintes disjonctives, Note DS n.9 bis, SEMA, Montrouge (1964).
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).
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).
S.M. Johnson, Optimal two- and three-stage production schedules with setup times included, Naval Res. Logist. Quart. 1(1954)61–68.
Author information
Authors and Affiliations
Additional information
Partially supported by research contracts MPI 40% and 60% of the Italian Ministry of University and Scientific Research.
Rights and permissions
About this article
Cite this article
Dell'Amico, M., Trubian, M. Applying tabu search to the job-shop scheduling problem. Ann Oper Res 41, 231–252 (1993). https://doi.org/10.1007/BF02023076
Issue Date:
DOI: https://doi.org/10.1007/BF02023076