Improving the preemptive bound for the single machine dynamic maximum lateness problem

Federico Della Croce (1) , Vincent t'Kindt (2)

1 DAUIN - Department of Computer Engineering
2 ERL CNRS 6305 Ordonnancement et Conduite

The preemptive lower bound is known to be the main available bound for the single machine dynamic maximum lateness problem. We propose an O(nlogn) time improvement to this bound which reduces by more than 80% the average the gap between the preemptive solution value and the optimal solution value.

Keywords: Single machine scheduling; Lower bound; Preemption; Maximum lateness

Domains: Computer Science [cs]; Operations Research [cs.RO]

Federico Della Croce, Vincent t'Kindt. Improving the preemptive bound for the single machine dynamic maximum lateness problem. Operations Research Letters, 2010, 38 (10), pp.589-591. ⟨10.1016/j.orl.2010.08.002⟩. ⟨hal-01003786⟩