Abstract
The problem considered in this paper is an important extension of the classical job-shop scheduling problem, where the same operation can be performed on more than one machine. The problem is to assign each operation to a machine and to sequence the operations on the machines, such that the makespan of a set of jobs is minimized. We introduce an extended version of the disjunctive graph model, that is able to take into account the fact that operations have to be assigned to machines. This allows us to present an integrated approach, by defining a neighborhood structure for the problem where there is no distinction between reassigning or resequencing an operation. This neighborhood is proved to be connected. A tabu search procedure is proposed and computational results are provided.
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, Management Science 34(1988)391–401.
P. Brandimarte, Routing and scheduling in a flexible job shop by tabu search, Annals of Operations Research 41(1993)57–183.
P. Brucker and R. Schlie, Job-shop scheduling with multi-purpose machines, Computing 45(1990) 369–375.
P. Brucker, B. Jurisch and B. Sievers, A branch and bound algorithm for the job-shop scheduling problem, Discrete Applied Mathematics 49(1994)107–127.
S. Dauzère-Pérès, A connected neighborhood structure for the multiprocessor job-shop scheduling problem, Management Report Series No. 180, Rotterdam School of Management, Erasmus Universiteit Rotterdam, The Netherlands, 1994.
S. Dauzère-Pérès and J. Paulli, Solving the general multiprocessor job-shop scheduling problem, Management Report Series No. 182, Rotterdam School of Management, Erasmus Universiteit Rotterdam, The Netherlands, 1994.
H. Fisher and G.L. Thompson, Probabilistic learning combinations of local job-shop scheduling rules, in: Industrial Scheduling, J.F. Muth and G.L. Thompson, eds., Prentice Hall, Englewood Cliffs, 1963, pp. 225–251.
M.R. Garey, D.S. Johnson and R. Sethi, The complexity of flowshop and jobshop scheduling, Mathematics of Operations Research 1(1976)117–129.
F. Glover, Tabu Search — Part I, ORSA Journal on Computing 1(1989)190–206.
F. Glover, Tabu Search — Part II, ORSA Journal on Computing 2(1990)4–32.
F. Glover, E. Taillard and D. de Werra, A user's guide to tabu search, Annals of Operations Research 41(1993)3–28.
F. Glover, M. Laguna, E. Taillard and D. de Werra (eds.), Tabu search, Annals of Operations Research 41(1993) (the complete volume).
J. Hurink, B. Jurisch and M. Thole, Tabu search for the job-shop scheduling problem with multipurpose machines, OR Spektrum 15(1994)205–215.
E. Nowicki and C. Smutnicki, A fast taboo search algorithm for the job shop problem, Preprint 8/93, Institute of Engineering Cybernetics, Technical University of Wroclaw, 1993.
J. Paulli, A hierarchical approach for the FMS scheduling problem, to appear in European Journal of Operational Research, 1995.
B. Roy and B. Sussman, Les problèmes d'ordonnancement avec contraintes disjonctives, Note DS No. 9 bis, SEMA, Montrouge, 1964.
E. Taillard, Parallel taboo search techniques for the job shop scheduling problem, ORSA Journal on Computing 6(1994)108–117.
R.J.M. Vaessens, E.H.L. Aarts and J.K. Lenstra, Job shop scheduling by local search, Memorandum COSOR 94-05, Eindhoven University of Technology, The Netherlands, 1994.
P.M. van Laarhoven, E.H.L. Aarts and J.K. Lenstra, Job shop scheduling by simulated annealing, Operations Research 40(1992)113–125.
Rights and permissions
About this article
Cite this article
Dauzère-Pérès, S., Paulli, J. An integrated approach for modeling and solving the general multiprocessor job-shop scheduling problem using tabu search. Annals of Operations Research 70, 281–306 (1997). https://doi.org/10.1023/A:1018930406487
Issue Date:
DOI: https://doi.org/10.1023/A:1018930406487