Premium
The permutation flow shop problem with sum‐of‐completion times performance criterion
Author(s) -
Karabati Selcuk,
Kouvelis Panagiotis
Publication year - 1993
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(199310)40:6<843::aid-nav3220400608>3.0.co;2-a
Subject(s) - bounding overwatch , mathematical optimization , branch and bound , upper and lower bounds , flow shop scheduling , scheduling (production processes) , heuristic , computer science , scheme (mathematics) , job shop scheduling , minification , permutation (music) , mathematics , schedule , artificial intelligence , mathematical analysis , physics , acoustics , operating system
In this article we address the non‐preemptive flow shop scheduling problem for minimization of the sum of the completion times. We present a new modeling framework and give a novel game‐theoretic interpretation of the scheduling problem. A lower‐bound generation scheme is developed by solving appropriately defined linear assignment problems. This scheme can also be used as a heuristic approach for the solution of the problem with satisfactory results. Its main use, however, is as a bounding scheme within a branch‐and‐bound procedure. Our branch‐and‐bound procedure improves significantly upon the best available enu‐merative procedures in the current literature. Extensive computational results are used to qualify the above statements. © 1993 John Wiley & Sons, Inc.