AG 1   Info

AG Audience

English

30 Minutes

Saarbrücken

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+\eps 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+\eps 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.

Joint work with A. Marchetti-Spaccamela, M. Skutella, and L. Stougie.

Nicole Megow

--email hidden

passcode not visible

logged in users only