Universal Sequencing on an Unreliable Machine

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

Research output: Contribution to JournalArticleAcademicpeer-review

Abstract

We consider scheduling on an unreliable machine that may experience unexpected changes in processing speed or even full breakdowns. Our objective is to minimize ?wjf(Cj) for any nondecreasing, nonnegative, differentiable cost function f(Cj ). We aim for a universal solution that performs well without adaptation for all cost functions for any possible machine behavior. We design a 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 machine behavior in advance. A randomized version of this algorithm attains in expectation a ratio of e. We also show that both performance guarantees are best possible for any unbounded cost function. Our algorithms can be adapted to run in polynomial time with slightly increased cost. 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 O(log n/ log log n) worse than an optimal sequence for any unbounded cost function. Motivated by this hardness, we study the special case when the processing time of each job is proportional to its weight. We present a nontrivial algorithm with a small constant performance guarantee. © 2012 Society for Industrial and Applied Mathematics.
Original languageEnglish
Pages (from-to)565-586
JournalSIAM Journal on Computing
Volume41
Issue number3
DOIs
Publication statusPublished - 2012

Fingerprint

Sequencing
Cost Function
Cost functions
Performance Guarantee
Scheduling
Release Dates
Deterministic Algorithm
Applied mathematics
Optimal Algorithm
Hardness
Breakdown
Differentiable
Polynomial time
Processing
Directly proportional
Non-negative
Minimise
Polynomials
Costs

Cite this

Epstein, L., Levin, A., Marchetti-Spaccamela, A., Megow, N., Mestre, J., Skutella, M., & Stougie, L. (2012). Universal Sequencing on an Unreliable Machine. SIAM Journal on Computing, 41(3), 565-586. https://doi.org/10.1137/110844210
Epstein, L. ; Levin, A. ; Marchetti-Spaccamela, A. ; Megow, N. ; Mestre, J. ; Skutella, M. ; Stougie, L. / Universal Sequencing on an Unreliable Machine. In: SIAM Journal on Computing. 2012 ; Vol. 41, No. 3. pp. 565-586.
@article{255f600ff8fb44ed8aa612d83c3b263c,
title = "Universal Sequencing on an Unreliable Machine",
abstract = "We consider scheduling on an unreliable machine that may experience unexpected changes in processing speed or even full breakdowns. Our objective is to minimize ?wjf(Cj) for any nondecreasing, nonnegative, differentiable cost function f(Cj ). We aim for a universal solution that performs well without adaptation for all cost functions for any possible machine behavior. We design a 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 machine behavior in advance. A randomized version of this algorithm attains in expectation a ratio of e. We also show that both performance guarantees are best possible for any unbounded cost function. Our algorithms can be adapted to run in polynomial time with slightly increased cost. 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 O(log n/ log log n) worse than an optimal sequence for any unbounded cost function. Motivated by this hardness, we study the special case when the processing time of each job is proportional to its weight. We present a nontrivial algorithm with a small constant performance guarantee. {\circledC} 2012 Society for Industrial and Applied Mathematics.",
author = "L. Epstein and A. Levin and A. Marchetti-Spaccamela and N. Megow and J. Mestre and M. Skutella and L. Stougie",
year = "2012",
doi = "10.1137/110844210",
language = "English",
volume = "41",
pages = "565--586",
journal = "SIAM Journal on Computing",
issn = "0097-5397",
publisher = "Society for Industrial and Applied Mathematics Publications",
number = "3",

}

Epstein, L, Levin, A, Marchetti-Spaccamela, A, Megow, N, Mestre, J, Skutella, M & Stougie, L 2012, 'Universal Sequencing on an Unreliable Machine' SIAM Journal on Computing, vol. 41, no. 3, pp. 565-586. https://doi.org/10.1137/110844210

Universal Sequencing on an Unreliable Machine. / Epstein, L.; Levin, A.; Marchetti-Spaccamela, A.; Megow, N.; Mestre, J.; Skutella, M.; Stougie, L.

In: SIAM Journal on Computing, Vol. 41, No. 3, 2012, p. 565-586.

Research output: Contribution to JournalArticleAcademicpeer-review

TY - JOUR

T1 - Universal Sequencing on an Unreliable Machine

AU - Epstein, L.

AU - Levin, A.

AU - Marchetti-Spaccamela, A.

AU - Megow, N.

AU - Mestre, J.

AU - Skutella, M.

AU - Stougie, L.

PY - 2012

Y1 - 2012

N2 - We consider scheduling on an unreliable machine that may experience unexpected changes in processing speed or even full breakdowns. Our objective is to minimize ?wjf(Cj) for any nondecreasing, nonnegative, differentiable cost function f(Cj ). We aim for a universal solution that performs well without adaptation for all cost functions for any possible machine behavior. We design a 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 machine behavior in advance. A randomized version of this algorithm attains in expectation a ratio of e. We also show that both performance guarantees are best possible for any unbounded cost function. Our algorithms can be adapted to run in polynomial time with slightly increased cost. 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 O(log n/ log log n) worse than an optimal sequence for any unbounded cost function. Motivated by this hardness, we study the special case when the processing time of each job is proportional to its weight. We present a nontrivial algorithm with a small constant performance guarantee. © 2012 Society for Industrial and Applied Mathematics.

AB - We consider scheduling on an unreliable machine that may experience unexpected changes in processing speed or even full breakdowns. Our objective is to minimize ?wjf(Cj) for any nondecreasing, nonnegative, differentiable cost function f(Cj ). We aim for a universal solution that performs well without adaptation for all cost functions for any possible machine behavior. We design a 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 machine behavior in advance. A randomized version of this algorithm attains in expectation a ratio of e. We also show that both performance guarantees are best possible for any unbounded cost function. Our algorithms can be adapted to run in polynomial time with slightly increased cost. 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 O(log n/ log log n) worse than an optimal sequence for any unbounded cost function. Motivated by this hardness, we study the special case when the processing time of each job is proportional to its weight. We present a nontrivial algorithm with a small constant performance guarantee. © 2012 Society for Industrial and Applied Mathematics.

U2 - 10.1137/110844210

DO - 10.1137/110844210

M3 - Article

VL - 41

SP - 565

EP - 586

JO - SIAM Journal on Computing

JF - SIAM Journal on Computing

SN - 0097-5397

IS - 3

ER -

Epstein L, Levin A, Marchetti-Spaccamela A, Megow N, Mestre J, Skutella M et al. Universal Sequencing on an Unreliable Machine. SIAM Journal on Computing. 2012;41(3):565-586. https://doi.org/10.1137/110844210