TY - JOUR

T1 - Off-line temporary tasks assignment

AU - Azar, Yossi

AU - Regev, Oded

AU - Sgall, Jiří

AU - Woeginger, Gerhard J.

N1 - Funding Information:
A preliminary version of this paper appears in the proceedings of the 7th European Symp. on Algorithms (ESA), Lecture Notes in Comput. Sci. 1643, Springer, Berlin, 1999, pp. 163–171. ∗Corresponding author. E-mail addresses: [email protected] (Y. Azar), [email protected] (O. Regev), [email protected] (J. Sgall), [email protected] (G.J. Woeginger). 1Research supported in part by the Israel Science Foundation and by the US-Israel Binational Science Foundation (BSF). 2Partially supported by grant A1019901 of GA AV CR,. postdoctoral grant 201=97=P038 of GA CR,. cooperative research grant INT-9600919=ME-103 from the NSF and MSMT. CR, and project LN00A056 of MSMT. CR. 3This research has been supported by the START program Y43-MAT of the Austrian Ministry of Science.

PY - 2002/9/28

Y1 - 2002/9/28

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 3/2 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 3/2 unless P = NP.

UR - http://www.scopus.com/inward/record.url?scp=0037190354&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0037190354&partnerID=8YFLogxK

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

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

M3 - Conference article

AN - SCOPUS:0037190354

SN - 0304-3975

VL - 287

SP - 419

EP - 428

JO - Theoretical Computer Science

JF - Theoretical Computer Science

IS - 2

T2 - Algorthims (ESA'99)

Y2 - 16 July 1999 through 18 July 1999

ER -