Assigning sporadic tasks to unrelated machines

A. Marchetti-Spaccamela, C. Rutten, S.L. van der Ster, A. Wiese

Research output: Contribution to JournalArticleAcademicpeer-review

Abstract

We study the problem of assigning sporadic tasks to unrelated machines such that the tasks on each machine can be feasibly scheduled. Despite its importance for modern real-time systems, this problem has not been studied before. We present a polynomial-time algorithm which approximates the problem with a constant speedup factor of (Formula Presented.) and show that any polynomial-time algorithm needs a speedup factor of at least 2, unless P = NP. In the case of a constant number of machines we give a polynomial-time approximation scheme. Key to these results are two new relaxations of the demand bound function, the function that yields a sufficient and necessary condition for a task system on a single machine to be feasible. In particular, we present new methods to approximate this function to obtain useful structural properties while incurring only bounded loss in the approximation quality. For the constant speedup result we employ a very general rounding procedure for linear programs (LPs) which model assignment problems with capacity-type constraints. It ensures that the cost of the rounded integral solution is no more than the cost of the optimal fractional LP solution and the capacity constraints are violated only by a bounded factor, depending on the structure of the matrix that defines the LP. In fact, our rounding scheme generalizes the well-known 2-approximation algorithm for the generalized assignment problem due to Shmoys and Tardos.
Original languageEnglish
Pages (from-to)247-274
JournalMathematical Programming
Volume152
Issue number1-2
Early online date14 May 2014
DOIs
Publication statusPublished - 2015

Fingerprint

Linear Program
Speedup
Rounding
Polynomials
Polynomial-time Algorithm
Generalized Assignment Problem
Integral Solution
Polynomial Time Approximation Scheme
Capacity Constraints
Single Machine
Costs
Approximation algorithms
Assignment Problem
Real time systems
Structural Properties
Approximation Algorithms
Structural properties
Fractional
Real-time
Necessary Conditions

Cite this

Marchetti-Spaccamela, A., Rutten, C., van der Ster, S. L., & Wiese, A. (2015). Assigning sporadic tasks to unrelated machines. Mathematical Programming, 152(1-2), 247-274. https://doi.org/10.1007/s10107-014-0786-9
Marchetti-Spaccamela, A. ; Rutten, C. ; van der Ster, S.L. ; Wiese, A. / Assigning sporadic tasks to unrelated machines. In: Mathematical Programming. 2015 ; Vol. 152, No. 1-2. pp. 247-274.
@article{c899aef6bf204fabbeb392a9e0e2080b,
title = "Assigning sporadic tasks to unrelated machines",
abstract = "We study the problem of assigning sporadic tasks to unrelated machines such that the tasks on each machine can be feasibly scheduled. Despite its importance for modern real-time systems, this problem has not been studied before. We present a polynomial-time algorithm which approximates the problem with a constant speedup factor of (Formula Presented.) and show that any polynomial-time algorithm needs a speedup factor of at least 2, unless P = NP. In the case of a constant number of machines we give a polynomial-time approximation scheme. Key to these results are two new relaxations of the demand bound function, the function that yields a sufficient and necessary condition for a task system on a single machine to be feasible. In particular, we present new methods to approximate this function to obtain useful structural properties while incurring only bounded loss in the approximation quality. For the constant speedup result we employ a very general rounding procedure for linear programs (LPs) which model assignment problems with capacity-type constraints. It ensures that the cost of the rounded integral solution is no more than the cost of the optimal fractional LP solution and the capacity constraints are violated only by a bounded factor, depending on the structure of the matrix that defines the LP. In fact, our rounding scheme generalizes the well-known 2-approximation algorithm for the generalized assignment problem due to Shmoys and Tardos.",
author = "A. Marchetti-Spaccamela and C. Rutten and {van der Ster}, S.L. and A. Wiese",
year = "2015",
doi = "10.1007/s10107-014-0786-9",
language = "English",
volume = "152",
pages = "247--274",
journal = "Mathematical Programming",
issn = "0025-5610",
publisher = "Springer-Verlag GmbH and Co. KG",
number = "1-2",

}

Marchetti-Spaccamela, A, Rutten, C, van der Ster, SL & Wiese, A 2015, 'Assigning sporadic tasks to unrelated machines' Mathematical Programming, vol. 152, no. 1-2, pp. 247-274. https://doi.org/10.1007/s10107-014-0786-9

Assigning sporadic tasks to unrelated machines. / Marchetti-Spaccamela, A.; Rutten, C.; van der Ster, S.L.; Wiese, A.

In: Mathematical Programming, Vol. 152, No. 1-2, 2015, p. 247-274.

Research output: Contribution to JournalArticleAcademicpeer-review

TY - JOUR

T1 - Assigning sporadic tasks to unrelated machines

AU - Marchetti-Spaccamela, A.

AU - Rutten, C.

AU - van der Ster, S.L.

AU - Wiese, A.

PY - 2015

Y1 - 2015

N2 - We study the problem of assigning sporadic tasks to unrelated machines such that the tasks on each machine can be feasibly scheduled. Despite its importance for modern real-time systems, this problem has not been studied before. We present a polynomial-time algorithm which approximates the problem with a constant speedup factor of (Formula Presented.) and show that any polynomial-time algorithm needs a speedup factor of at least 2, unless P = NP. In the case of a constant number of machines we give a polynomial-time approximation scheme. Key to these results are two new relaxations of the demand bound function, the function that yields a sufficient and necessary condition for a task system on a single machine to be feasible. In particular, we present new methods to approximate this function to obtain useful structural properties while incurring only bounded loss in the approximation quality. For the constant speedup result we employ a very general rounding procedure for linear programs (LPs) which model assignment problems with capacity-type constraints. It ensures that the cost of the rounded integral solution is no more than the cost of the optimal fractional LP solution and the capacity constraints are violated only by a bounded factor, depending on the structure of the matrix that defines the LP. In fact, our rounding scheme generalizes the well-known 2-approximation algorithm for the generalized assignment problem due to Shmoys and Tardos.

AB - We study the problem of assigning sporadic tasks to unrelated machines such that the tasks on each machine can be feasibly scheduled. Despite its importance for modern real-time systems, this problem has not been studied before. We present a polynomial-time algorithm which approximates the problem with a constant speedup factor of (Formula Presented.) and show that any polynomial-time algorithm needs a speedup factor of at least 2, unless P = NP. In the case of a constant number of machines we give a polynomial-time approximation scheme. Key to these results are two new relaxations of the demand bound function, the function that yields a sufficient and necessary condition for a task system on a single machine to be feasible. In particular, we present new methods to approximate this function to obtain useful structural properties while incurring only bounded loss in the approximation quality. For the constant speedup result we employ a very general rounding procedure for linear programs (LPs) which model assignment problems with capacity-type constraints. It ensures that the cost of the rounded integral solution is no more than the cost of the optimal fractional LP solution and the capacity constraints are violated only by a bounded factor, depending on the structure of the matrix that defines the LP. In fact, our rounding scheme generalizes the well-known 2-approximation algorithm for the generalized assignment problem due to Shmoys and Tardos.

U2 - 10.1007/s10107-014-0786-9

DO - 10.1007/s10107-014-0786-9

M3 - Article

VL - 152

SP - 247

EP - 274

JO - Mathematical Programming

JF - Mathematical Programming

SN - 0025-5610

IS - 1-2

ER -

Marchetti-Spaccamela A, Rutten C, van der Ster SL, Wiese A. Assigning sporadic tasks to unrelated machines. Mathematical Programming. 2015;152(1-2):247-274. https://doi.org/10.1007/s10107-014-0786-9