• search hit 12 of 13
Back to Result List

Robust sequencing on a single machine

Please always quote using this URN:urn:nbn:de:0296-matheon-5640
  • We consider scheduling to minimize the weighted sum of completion times on a single machine that may experience unexpected changes in processing speed or even full breakdowns. We design a polynomial time deterministic algorithm that finds a robust prefixed scheduling sequence with a solution value within~$4$ times the value an optimal clairvoyant algorithm can achieve, knowing the disruptions in advance and even being allowed to interrupt jobs at any moment. A randomized version of this algorithm attains in expectation a ratio of~$e$ w.r.t. a clairvoyant optimum. We show that such a ratio can never be achieved by any deterministic algorithm by proving that the price of robustness of any such algorithm is at least~$1+\sqrt{3} \approx 2.73205>e$. As a direct consequence of our results, the question whether a constant approximation algorithm exists for the problem with given machine unavailability periods is answered affirmatively. We complement this result by an FPTAS for the preemptive and non-preemptive special case with a single non-available period.

Download full text files

Export metadata

Additional Services

Share in Twitter Search Google Scholar
Metadaten
Author:Alberto Marchetti-Spaccamela, Nicole Megow, Martin Skutella, Leen Stougie
URN:urn:nbn:de:0296-matheon-5640
Referee:Rolf H. Möhring
Document Type:Preprint, Research Center Matheon
Language:English
Date of first Publication:2009/02/20
Release Date:2009/02/20
Institute:Technische Universität Berlin
Preprint Number:557
Verstanden ✔
Diese Webseite verwendet technisch erforderliche Session-Cookies. Durch die weitere Nutzung der Webseite stimmen Sie diesem zu. Unsere Datenschutzerklärung finden Sie hier.