MINIMIZING TOTAL TARDINESS IN PERMUTATION FLOWSHOPS

Abstract

We consider the permutation flowshop scheduling problem with the objective of minimizing total tardiness. Presented are several properties that are used to calculate lower bounds on total tardiness of jobs for a given partial sequence and to identify sequences dominated by others. We develop a branch and bound algorithm using these bounds and a dominance rule. Results of computational experiments on randomly generated problems are reported.