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

Federico Della Croce; Vincent t'Kindt

doi:10.1016/j.orl.2010.08.002

Journal articles

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

Federico Della Croce ¹ Vincent t'Kindt ²

1 DAUIN - Department of Computer Engineering

2 ERL CNRS 6305 Ordonnancement et Conduite

LIFAT - Laboratoire d'Informatique Fondamentale et Appliquée de Tours

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.

Keywords : Single machine scheduling Lower bound Preemption Maximum lateness

Document type :

Journal articles

Domain :

Computer Science [cs] / Operations Research [cs.RO]

Complete list of metadata

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 : Thursday, June 10, 2021 - 10:28:01 AM

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

Identifiers

Collections

Citation

Export

Metrics

129

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

Identifiers

Collections

Citation

Export

Share

Metrics

129