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

•We consider a two-machine flowshop scheduling problem minimizing total tardiness.•The machine at the first stage requires preventive maintenance activities.•We present a branch and bound algorithm to minimize the total tardiness of jobs.•For the algorithm, we develop dominance properties and lower bounds.•The branch and bound algorithm solves moderate-size problems in a reasonable time.

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.