Minimizing the Weighted Number of Late Semi-resumable Jobs with Deterministic Machine Availability Constraints

We investigate the problem of minimizing the weighted number of tardy jobs on a single machine subject to availability constraints. We consider the case of semi-resumable jobs (1, hk|ri, sr – a|S wiUi). We show that the problem is equivalent to a similar problem without availability constraints, but where the processing times of jobs are a stepwise function of their starting time. We design a Mixed Integer Linear Program (MILP) to model the problem and solve it with help of a commercial MILP solver. Computational experiments on randomly generated instances show that using this method allows solving optimally most 300-job problems within 1000 seconds, and provides excellent heuristic solutions in 100 seconds.