Price of robustness in single machine scheduling



Leen Stougie
Dept. of Operations Research, Free University & CWI, Amsterdam

Monday  August 31, 2009
4:00 PM, 5130 Upson Hall



In general scheduling problems we assume that machines are always available until the set of assigned jobs is completed. However, in reality machines might not be available for preventive maintenance, they may slow down due to simultaneous utilization by other users, they may break down completely for some time, etc. In the latter cases unavailability is unpredictable.

Thus the quest for a schedule that is robust against machine calamities emerges: the only influence the scheduler has is on the order in which he offers his jobs to be processed.

We study this scheduling problem on a single machine when the objective is to minimize the sum of weighted completion times of the jobs. We compute a robust scheduling sequence in which the jobs are processed no matter how, unexpectedly, the machine may become unavailable and changes its processing speed. In case of a machine breakdown the job is preempted and resumed after the breakdown period.

We analyze the worst case performance by comparing the solution value provided by an algorithm with that of an optimal clairvoyant algorithm that knows the machine behavior in advance, and that is even allowed to preempt jobs at any time. Our main results are a deterministic and a randomized robust, prefixed, order of the jobs, computable in polynomial time, such that scheduling the jobs in this order will always yield a solution that remains within multiplicative factor 4 from clairvoyant optimal for the deterministic order and within multiplicative factor $e$ in expectation from optimal for the randomized order. We can adapt our algorithm to solve more general problem instances with certain types of precedence constraints without losing in the performance.

We complement these results with lower bounds that show that these ratios are best possible. This settles that the price of robustness for this scheduling problem is exactly 4 for deterministic and $e$ for randomized algorithms.