Title

Job-Shop Scheduling: Limits Of The Binary Disjunctive Formulation

Abstract

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, we 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, nonzero 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. © 1990 Taylor & Francis Group, LLC.

Publication Date

1-1-1990

Publication Title

International Journal of Production Research

Volume

28

Issue

12

Number of Pages

2187-2200

Document Type

Article

Personal Identifier

scopus

DOI Link

https://doi.org/10.1080/00207549008942861

Socpus ID

0025595806 (Scopus)

Source API URL

https://api.elsevier.com/content/abstract/scopus_id/0025595806

This document is currently not available here.

Share

COinS