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

    Authors

    R. V. Rogers;K. P. White

    Comments

    Authors: contact us about adding a copy of your work at STARS@ucf.edu

    Abbreviated Journal Title

    IEEE Trans. Syst. Man Cybern.

    Keywords

    ALGORITHMS; HEURISTICS; Computer Science, Cybernetics; Engineering, Electrical & Electronic

    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/C(max)) 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.

    Journal Title

    Ieee Transactions on Systems Man and Cybernetics

    Volume

    21

    Issue/Number

    3

    Publication Date

    1-1-1991

    Document Type

    Letter

    Language

    English

    First Page

    693

    Last Page

    697

    WOS Identifier

    WOS:A1991GJ60000020

    ISSN

    0018-9472

    Share

    COinS