### Abstract

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 | |

Publication status | Published - 2002 |

### Fingerprint

### Keywords

- METIS-208621

### Cite this

*Theoretical computer science*,

*287*, 419-428. https://doi.org/10.1016/S0304-3975(01)00254-7

}

*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.

Research output: Contribution to journal › Article › Academic › peer-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 -