Minimum tardiness scheduling in flow shops: Construction and evaluation of alternative solution approaches

Surveys of industrial scheduling practice show that meeting customer due dates is a critical concern for many manufacturing systems. While there is considerable research on the effectiveness of scheduling rules in job shops, very little work is reported on flow shops. Although scheduling rules developed for job shops can be applied in other systems as well, it is shown that the inherent structure of a flow shop can be utilized to construct effective solution procedures. In particular, for the total tardiness problem, conditions for local optimality are developed in a 2-machine flow shop, and these results are used to generate an efficient improvement heuristic procedure. Solution methods that utilize the notion of shifting bottlenecks are also constructed. The present computational experience reveals the superiority and robustness of the proposed approaches under a variety of problem scenarios. The results of this study also indicate the need to look beyond permutation schedules for solving the flow shop tardiness problem. Furthermore, they suggest that the criterion for determining machine criticality needs to take the scheduling objective into consideration. While it appears intuitive to impute criticality on the basis of machine workloads and, therefore, emphasize the bottleneck machine for generating the shop schedule, this approach may frequently result in inferior system performance.