Job-shop scheduling: Limits of the binary disjunctive formulation

The deterministic job-shop scheduling problem exhibits the fundamental computational difficulty implicit in determining an optimal timetable for sharing production resources among competing production activities. While adaptation of the formal model to industrial practice is fraught with difficulties, the authors show that the underlying binary-disjunctive formulation itself is more robust than might be immediately apparent. Straightforward extensions of the underlying model are sufficient to capture such practical problem features as assembly and disassembly sequences, due-dates and out-processing operations, scheduled maintenance, non-zero release times and dispatch operations, certain sequence-dependent set-ups and materials handling delays, and a great range of operational side-constraints. Technological sequences need not be total orders, job priorities can be assigned explicitly or implicitly, and any regular measure of performance can be represented. The principal structural limitation is that machining sequences must represent total orders over component operations to preserve the model form. For this reason, concurrent or parallel processing (as in machining centres or cells) and indefinite cyclical process flows (as are sometimes required for rework) cannot be modelled directly. An example problem is provided which illustrates these extensions and an industrial application employing the extended model is briefly considered.