Abstract
During the last four years, tabu search has been shown to be a remarkably effective method in solving difficult combinatorial optimization problems. Nowhere has this success been more marked than in the timely and very important area of production scheduling. In this paper, we review some of the research that has contributed to that success. We also give a synthesis of the various tabu search mechanisms that have been employed, giving special attention to advances that have led to major improvements. In the final section of the paper, we suggest directions for future research.
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)
K.R. Baker,Introduction to Sequencing and Scheduling (Wiley, 1974).
K.R. Baker and G.D. Scudder, Sequencing with earliness and tardiness penalties: A review, Oper. Res. 38(1990)22–36.
E. Balas, Machine sequencing via disjunctive graphs: An implicit enumeration algorithm, Oper. Res. 17(1969)941–957.
J.W. Barnes and J. Brennan, An improved algorithm for scheduling jobs on identical machines, AIIE Trans. 9(1977).
J.W. Barnes and L. Vanston, Scheduling jobs with linear delay penalties and sequence dependent set-up costs, J. Oper. Res. 29(1981.
J.W. Barnes and M. Laguna, Solving the multiple-machine weighted flow time problem using tabu search, IIE Trans. (1992) in press.
J. Beardwood, J.H. Halton and J.M. Hammersley, The shortest path through many points, Proc. Cambridge Phil. Soc. 55(1959)299–327.
R.W. Conway, W.L. Maxwell and L.W. Miller,Theory of Scheduling (Addison-Wesley, Reading, MA, 1970).
D. de Werra and A. Hertz, Tabu search techniques: A tutorial and an application to neural networks, OR Spectrum 11(1989)132–141.
J. Evans, Structural analysis of local search heuristics in combinatorial optimization, Comp. Oper. Res. 14(1987)465–477.
T.F. Feo and M. Resende, A probabilistic heuristic for a computationally difficult set covering problem, Oper. Res. Lett. 8(1989)67–71.
S. French,Sequencing and Scheduling (Ellis Horwood, 1982).
M. Gendreau, A. Hertz and G. Laporte, A tabu search heuristic for the vehicle routing problem, Centre de Recherche sur les Transports, publication #777 (June 1991).
F. Glover, Heuristics for integer programming using surrogate constraints, Dec. Sci. 8(1977)156–166.
F. Glover, Future paths for integer programming and links to artificial intelligence, Comp. Oper. Res. 13(1986)533–549.
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.
F. Glover, Tabu search: A tutorial, Interfaces 29(1990)74–94.
F. Glover, E. Taillard and D. de Werra, A user's guide to tabu search, Ann. Oper. Res. (1993), this volume.
A. Hertz and D. de Werra, The tabu search metaheuristic: How we used it, Ann. Math. Art. Int. 1(1990)111–121.
M. Laguna, Tabu search primer, Graduate School of Business and Administration, University of Colorado at Boulder (March 1992).
M. Laguna, J.W. Barnes and F. Glover, Tabu search methods for a single machine scheduling problem, J. Int. Manufacturing 2(1991)63–73.
M. Laguna and J.L. Gonzalez-Velarde, A search heuristic for just-in-time scheduling in parallel machines, J. Int. Manufacturing 2(1991)253–260.
M. Laguna, J.W. Barnes and F. Glover, Scheduling jobs with linear delay penalties and sequence dependent setup costs and times using tabu search, Appl. Int. (1992) in press.
M. Laguna and F. Glover, Integrating target analysis and tabu search for improved scheduling systems, Exp. Syst. Appl. (1992) in press.
J. Lam, An efficient simulated annealing schedule, Ph.D. Dissertation, Report 8818. Department of Computer Science, Yale University (September 1988).
E.L. Lawler, J.K. Lenstra, A Rinnooy Kan and D.B. Shmoys, Sequencing and scheduling: Algorithms and complexity, Report BS-R8909, Centre for Mathematics and Computer Science, Amsterdam, The Netherlands (1989).
T.L. Morin and R.E. Marsten, Branch and bound strategies for dynamic programming, Oper. Res. 24(1976)611–627.
M.E. Nawaz, E. Enscore and I. Ham, A heuristic algorithm for them-machine,n-job flow shop sequencing problem, OMEGA 11(1983).
F. Semet and E. Taillard, Solving real-life vehicle routing problems efficiently using tabu search, École Polytechnique Fédérale de Lausanne, ORWP 91/03 (April 1991).
E. Taillard, Parallel taboo search technique for the job shop scheduling problem, Research Report ORWP 89/11, École Polytechnique Fédérale de Lausanne, Départment de Mathématiques (July 1989).
M. Troyon, Quelques heuristiques et résultats asymptotiques pour trois problèmes d'optimisation combinatoire, Thèse No. 754, École Polytechnique Fédérale de Lausanne, Switzerland (1988).
S. Tsubakitani and J.R. Evans, Optimizing tabu list size for the traveling salesman problem, College of Business Administration, University of Cincinnati (June 1991).
P. van Laarhoven, E. Aarts and J. Lenstra, Job shop scheduling by simulated annealing, Report OSR8809, Centrum voor Wiskunde en Informatica, Amsterdam, The Netherlands (1988)
M. Widmer and A. Hertz, A new method for the flow sequencing problem, Eur. J. Oper. Res. 41(1989)186–193.
M. Widmer, Job shop scheduling with tooling constraints: a tabu search approach, J. Oper. Res. Soc. 24(1991)75–82.
D.L Woodruff and M.L. Spearman, Sequencing and batching for two classes of jobs with deadlines and setup times, J. Prod. Oper. Manag. Soc. (1992) in press.
D.L Woodruff and E. Zemel, Hashing vectors for tabu search, Ann. Oper. Res. (1993), this volume.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Barnes, J.W., Laguna, M. A tabu search experience in production scheduling. Ann Oper Res 41, 139–156 (1993). https://doi.org/10.1007/BF02023072
Issue Date:
DOI: https://doi.org/10.1007/BF02023072