O-line temporary tasks assignment

Abstract. In this paper we consider the temporary tasks assignment problem. In this problem, there are m parallel machines and n inde-pendent 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 ma-chine at a certain time is the sum of the weights of jobs assigned to it at that time. The objective is to nd 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 xed. We also show that for the case in which the number of machines is given as part of the input (i.e., not xed), no algorithm can achieve a better approximation ratio tha