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

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.


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


Full Text: DOI


[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
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.