Universal Sequencing on a Single Machine

L. Epstein, A. Levin, A. Marchetti-Spaccamela, N. Megow, J. Mestre, M. Skutella, L. Stougie

Research output: Contribution to JournalArticleAcademicpeer-review

225 Downloads (Pure)


We consider scheduling on an unreliable machine that may experience unexpected changes in processing speed or even full breakdowns. We aim for a universal solution that performs well without adaptation for any possible machine behavior. For the objective of minimizing the total weighted completion time, we design a polynomial time deterministic algorithm that finds a universal scheduling sequence with a solution value within 4 times the value of an optimal clairvoyant algorithm that knows the disruptions in advance. A randomized version of this algorithm attains in expectation a ratio of e. We also show that both results are best possible among all universal solutions. As a direct consequence of our results, we answer affirmatively the question of whether a constant approximation algorithm exists for the offline version of the problem when machine unavailability periods are known in advance. When jobs have individual release dates, the situation changes drastically. Even if all weights are equal, there are instances for which any universal solution is a factor of Ω(log n/ log log n) worse than an optimal sequence. Motivated by this hardness, we study the special case when the processing time of each job is proportional to its weight. We present a non-trivial algorithm with a small constant performance guarantee. © 2010 Springer-Verlag.
Original languageEnglish
Pages (from-to)230-243
JournalLecture Notes in Computer Science
Publication statusPublished - 2010
EventIPCO, Lausanne, Switzerland - Berlin
Duration: 9 Jun 201011 Jun 2010

Bibliographical note

Proceedings title: Proceedings of the 14th Conference on Integer Programming and Combinatorial Optimization
Publisher: Springer Verlag
Place of publication: Berlin


Dive into the research topics of 'Universal Sequencing on a Single Machine'. Together they form a unique fingerprint.

Cite this