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.
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 |