An iterative lower bound algorithm for the Single-Machine Scheduling Problem Under a Non-Availability Constraint for Maximum Delivery Time Minimization
Résumé
We consider the single machine scheduling problem with release dates and tails, provided that the machine is unavailable during a fixed interval. This problem is strongly NP-hard. We use the Jackson's preemptive algorithm with precedence constraints to compute a lower bound and the Schrage's sequence as an upper bound. Then, we propose an improved lower bound which is based on an iterative procedure. Numerical experiments show the effectiveness of the bounds.