1DAUIN - Department of Computer Engineering (Dipartimento di Automatica e Informatica Politecnico di Torino - Corso Duca degli Abruzzi, 24 - 10129 Torino, ITALY - Italy)
Abstract : 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.
https://hal-univ-tours.archives-ouvertes.fr/hal-01003786
Contributor : Vincent t'Kindt <>
Submitted on : Tuesday, June 10, 2014 - 4:28:22 PM Last modification on : Wednesday, March 21, 2018 - 10:54:09 AM
Federico Della Croce, Vincent t'Kindt. Improving the preemptive bound for the single machine dynamic maximum lateness problem. Operations Research Letters, Elsevier, 2010, 38 (10), pp.589-591. ⟨10.1016/j.orl.2010.08.002⟩. ⟨hal-01003786⟩