A branch and bound algorithm to minimize total tardiness of jobs in a two identical-parallel-machine scheduling problem with a machine availability constraint

Abstract

This research focuses on the problem of scheduling jobs on two identical parallel machines that are not continuously available with the objective of minimizing total tardiness. After processing a given number of jobs, each machine requires a preventive maintenance task, during which the machine cannot process jobs. We present dominance properties and lower bounds, and develop a branch and bound algorithm using these properties and lower bounds as well as an upper bound obtained from a heuristic algorithm. Performance of the algorithm is evaluated through a series of computational experiments on randomly generated instances and results are reported.

Keywords:

• scheduling
• identical parallel machines
• availability constraint
• total tardiness
• branch and bound