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 -