Premium
Multiobjective flow‐shop scheduling
Author(s) -
Daniels Richard L.,
Chambers Robert J.
Publication year - 1990
Publication title -
naval research logistics (nrl)
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.665
H-Index - 68
eISSN - 1520-6750
pISSN - 0894-069X
DOI - 10.1002/1520-6750(199012)37:6<981::aid-nav3220370617>3.0.co;2-h
Subject(s) - tardiness , job shop scheduling , mathematical optimization , computer science , flow shop scheduling , scheduling (production processes) , schedule , set (abstract data type) , operations research , mathematics , programming language , operating system
Previous research on the scheduling of multimachine systems has generally focused on the optimization of individual performance measures. This article considers the sequencing of jobs through a multimachine flow shop, where the quality of the resulting schedule is evaluated according to the associated levels of two scheduling criteria, schedule makespan ( C max ) and maximum job tardiness ( T max ). We present constructive procedures that quantify the trade‐off between C max and T max . The significance of this trade‐off is that the optimal solution for any preference function involving only C max and T max must be contained among the set of efficient schedules that comprise the trade‐off curve. For the special case of two‐machine flow shops, we present an algorithm that identifies the exact set of efficient schedules. Heruistic procedures for approximating the efficient set are also provided for problems involving many jobs or larger flow shops. Computational results are reported for the procedures which indicate that both the number of efficient schedules and the error incurred by heuristically approximating the efficient set are quite small.