Games, critical paths and assignment problems in permutation flow shops and cyclic scheduling flow line environments

In this paper the authors address the non-preemptive flow shop scheduling problem for makespan minimization in a new modelling framework. A lower bound generation scheme is developed by using appropriately defined linear assignment problems and, based on this new approach, a special class of permutation flow shop problems is identified. The authors present a game theoretic interpretation of the present modelling approach which leads to an integer programming formulation of the scheduling problem. A new branch and bound scheme is developed based on these results. The major advantage of the present modelling framework and branch-and-bound approach is that it can be easily extended to address a general class of cyclic scheduling problems for production flow lines with blocking. After a discussion of this extension, the authors report on computational experience that indicates the very satsifactory performance of the new optimal solution procedure for cyclic scheduling with finite capacity buffers.