Title

Algebraic, Mathematical Programming, And Network Models Of The Deterministic Job-Shop Scheduling Problem

Abstract

In the contemporary literature on deterministic machine scheduling, problems are formulated from three different, but equivalent, perspectives. Algebraic models provide a rigorous problem statement in the language of set theory and are typical of the more abstract development of scheduling theory in mathematics and computer science. Mathematical programming models rely on familiar concepts of nonlinear optimization and are generally the most accessible. Network models (disjunctive graphs) are best suited to the development of solution approaches and figure prominently in discussions of algorithm design and analysis. In this tutorial, it is shown how the minimum-makespan job-shop problem (n/m/G/Cmax) is realized in each of these three model forms. A common notation is developed and how the underlying structure and fundamental difficulty of the problem are expressed in each model is demonstrated. © 1991 IEEE

Publication Date

1-1-1991

Publication Title

IEEE Transactions on Systems, Man and Cybernetics

Volume

21

Issue

3

Number of Pages

693-697

Document Type

Article

Personal Identifier

scopus

DOI Link

https://doi.org/10.1109/21.97463

Socpus ID

0026156030 (Scopus)

Source API URL

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

This document is currently not available here.

Share

COinS