The permutation flow shop problem with sum‐of‐completion times performance criterion

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.