Job-shop scheduling with blocking and no-wait constraints

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 present several complexity results and solution procedures. Computational results for fast heuristics and exact algorithms are also reported.