TY - GEN A1 - Marchetti-Spaccamela, Alberto A1 - Megow, Nicole A1 - Skutella, Martin A1 - Stougie, Leen T1 - Robust sequencing on a single machine N2 - 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. Y1 - 2009 UR - https://opus4.kobv.de/opus4-matheon/frontdoor/index/index/docId/564 UR - https://nbn-resolving.org/urn:nbn:de:0296-matheon-5640 ER -