Journal
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH
Volume 143, Issue 3, Pages 498-517Publisher
ELSEVIER SCIENCE BV
DOI: 10.1016/S0377-2217(01)00338-1
Keywords
scheduling; job shop; blocking; no-wait
Ask authors/readers for more resources
In this paper, we study the job-shop scheduling problem with blocking and/or no-wait constraints. A blocking constraint models the absence of storage capacity between machines, while a no-wait constraint occurs when two consecutive operations in a job must be processed without any interruption. We formulate the problem by means of a generalization of the disjunctive graph of Roy and Sussman, that we call an alternative graph, and investigate the applicability to the blocking and no-wait cases of some of the most effective ideas from the literature on the job shop with unlimited buffers. We show that several key properties, used to design heuristic procedures, do not hold in the blocking and no-wait cases, while some of the most effective ideas used to develop branch and bound algorithms can be easily extended. We presents several complexity results and solution procedures. Computational results for fast heuristics and exact algorithms are also reported. (C) 2002 Elsevier Science B.V. All rights reserved.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available