| Ser. |
|
557
|
| Title |
|
Robust sequencing on a single machine
|
| Abstract |
|
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(s) |
|
Alberto Marchetti-Spaccamela, Nicole Megow, Martin Skutella, Leen Stougie
|
| PS-File |
|
robust.ps
|
| PDF-File |
|
robust.pdf
|
| Reviewing Referee |
|
Prof. Dr. Rolf Möhring |
| Projects |
|
B13 |
| |
|
|
