Off-line temporary task assignment

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

doi:10.1016/S0304-3975(01)00254-7

Off-line temporary task assignment

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

Discrete Mathematics and Mathematical Programming

Research output: Contribution to journal › Article › Academic › peer-review

3 Citations (Scopus)

1 Downloads (Pure)

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 language	English
Pages (from-to)	419-428
Journal	Theoretical computer science
Volume	287
DOIs	https://doi.org/10.1016/S0304-3975(01)00254-7
Publication status	Published - 2002

Keywords

METIS-208621

Access to Document

10.1016/S0304-3975(01)00254-7

Cite this

@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",

}

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

SN - 0304-3975

VL - 287

SP - 419

EP - 428

JO - Theoretical computer science

JF - Theoretical computer science

ER -

Off-line temporary task assignment

Abstract

Keywords

Access to Document

Fingerprint

Cite this