A Benders decomposition approach to the weighted number of tardy jobs scheduling problem on unrelated parallel machines with production costs

This paper addresses the problem of scheduling on-time jobs on unrelated parallel machines with machine production costs. The objective is to maximise the net profit which is the sum of the weights of on-time jobs and the cost of using the machines. This scheduling problem is very important and frequent in industrial settings. It is herein solved using an exact approach that applies Benders decomposition to obtain tight upper and lower bounds and uses the bounds within a branch and bound. The computational investigation shows the efficacy of the approach in solving large instances. Most importantly, the proposed approach provides a new venue for solving large-scale scheduling problems.