Article ID: | iaor1994967 |
Country: | United States |
Volume: | 40 |
Issue: | 6 |
Start Page Number: | 843 |
End Page Number: | 862 |
Publication Date: | Oct 1993 |
Journal: | Naval Research Logistics |
Authors: | Kouvelis Panagiotis, Karabati Selcuk |
In this article the authors address the non-preemptive flow shop scheduling problem for minimization of the sum of the completion times. They 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. The present branch-and-bound procedure improves significantly upon the best available enumerative procedures in the current literature. Extensive computational results are used to qualify the above statements.