Minimizing total tardiness in a two-machine flowshop scheduling problem with availability constraint on the first machine

This paper deals with a two-machine flowshop problem in which the machine at the first stage requires preventive maintenance activities that have to be started within a given cumulative working time limit after the previous maintenance. That is, a maintenance activity can be started at any time unless the cumulative working time after the end of the previous maintenance exceeds the given limit. For the problem with the objective of minimizing total tardiness, we develop dominance properties and lower bounds for this scheduling problem as well as a heuristic algorithm, and suggest a branch and bound algorithm in which these properties, lower bounds, and heuristic algorithm are used. Computational experiments are performed to evaluate the algorithm and the results are reported.