Off-line temporary task assignment

Yossi Azar, Oded Regev, Jirí Sgall, Gerhard Woeginger

Research output: Contribution to journalArticleAcademicpeer-review

3 Citations (Scopus)

Abstract

In this paper we consider the temporary tasks assignment problem. In this problem, there are m parallel machines and n independent jobs. Each job has an arrival time, a departure time and some weight. Each job should be assigned to one machine. The load on a machine at a certain time is the sum of the weights of jobs assigned to it at that time. The objective is to find an assignment that minimizes the maximum load over machines and time.

We present a polynomial time approximation scheme for the case in which the number of machines is fixed. We also show that for the case in which the number of machines is given as part of the input (i.e., not fixed), no polynomial algorithm can achieve a better approximation ratio than 32 unless P=NP.
Original languageEnglish
Pages (from-to)419-428
JournalTheoretical computer science
Volume287
DOIs
Publication statusPublished - 2002

Fingerprint

Task Assignment
Polynomials
Line
Polynomial Time Approximation Scheme
Arrival Time
Polynomial Algorithm
Parallel Machines
Assignment Problem
Assignment
Minimise
Approximation

Keywords

  • METIS-208621

Cite this

Azar, Y., Regev, O., Sgall, J., & Woeginger, G. (2002). Off-line temporary task assignment. Theoretical computer science, 287, 419-428. https://doi.org/10.1016/S0304-3975(01)00254-7
Azar, Yossi ; Regev, Oded ; Sgall, Jirí ; Woeginger, Gerhard. / Off-line temporary task assignment. In: Theoretical computer science. 2002 ; Vol. 287. pp. 419-428.
@article{2ef90f6c62604dc2965208a02d4725b1,
title = "Off-line temporary task assignment",
abstract = "In this paper we consider the temporary tasks assignment problem. In this problem, there are m parallel machines and n independent jobs. Each job has an arrival time, a departure time and some weight. Each job should be assigned to one machine. The load on a machine at a certain time is the sum of the weights of jobs assigned to it at that time. The objective is to find an assignment that minimizes the maximum load over machines and time.We present a polynomial time approximation scheme for the case in which the number of machines is fixed. We also show that for the case in which the number of machines is given as part of the input (i.e., not fixed), no polynomial algorithm can achieve a better approximation ratio than 32 unless P=NP.",
keywords = "METIS-208621",
author = "Yossi Azar and Oded Regev and Jir{\'i} Sgall and Gerhard Woeginger",
year = "2002",
doi = "10.1016/S0304-3975(01)00254-7",
language = "English",
volume = "287",
pages = "419--428",
journal = "Theoretical computer science",
issn = "0304-3975",
publisher = "Elsevier",

}

Azar, Y, Regev, O, Sgall, J & Woeginger, G 2002, 'Off-line temporary task assignment' Theoretical computer science, vol. 287, pp. 419-428. https://doi.org/10.1016/S0304-3975(01)00254-7

Off-line temporary task assignment. / Azar, Yossi; Regev, Oded; Sgall, Jirí; Woeginger, Gerhard.

In: Theoretical computer science, Vol. 287, 2002, p. 419-428.

Research output: Contribution to journalArticleAcademicpeer-review

TY - JOUR

T1 - Off-line temporary task assignment

AU - Azar, Yossi

AU - Regev, Oded

AU - Sgall, Jirí

AU - Woeginger, Gerhard

PY - 2002

Y1 - 2002

N2 - In this paper we consider the temporary tasks assignment problem. In this problem, there are m parallel machines and n independent jobs. Each job has an arrival time, a departure time and some weight. Each job should be assigned to one machine. The load on a machine at a certain time is the sum of the weights of jobs assigned to it at that time. The objective is to find an assignment that minimizes the maximum load over machines and time.We present a polynomial time approximation scheme for the case in which the number of machines is fixed. We also show that for the case in which the number of machines is given as part of the input (i.e., not fixed), no polynomial algorithm can achieve a better approximation ratio than 32 unless P=NP.

AB - In this paper we consider the temporary tasks assignment problem. In this problem, there are m parallel machines and n independent jobs. Each job has an arrival time, a departure time and some weight. Each job should be assigned to one machine. The load on a machine at a certain time is the sum of the weights of jobs assigned to it at that time. The objective is to find an assignment that minimizes the maximum load over machines and time.We present a polynomial time approximation scheme for the case in which the number of machines is fixed. We also show that for the case in which the number of machines is given as part of the input (i.e., not fixed), no polynomial algorithm can achieve a better approximation ratio than 32 unless P=NP.

KW - METIS-208621

U2 - 10.1016/S0304-3975(01)00254-7

DO - 10.1016/S0304-3975(01)00254-7

M3 - Article

VL - 287

SP - 419

EP - 428

JO - Theoretical computer science

JF - Theoretical computer science

SN - 0304-3975

ER -