Approximation Schemes for Scheduling on Uniformly Related and Identical Parallel Machines

We give a polynomial approximation scheme for the problem of scheduling on uniformly related parallel machines for a large class of objective functions that depend only on the machine completion times, including minimizing the l p norm of the vector of completion times. This generalizes and simplifies many previous results in this area. 1 Introduction We are given n jobs with processing times p j , j 2 J = f1; : : : ; ng and m machines M 1 , M 2 , : : : , Mm , with speeds s 1 , s 2 , : : : , s m . A schedule is an assignment of the n jobs to the m machines. Given a schedule, for 1 i m, T i denotes the weight of machine M i which is the total processing time of all jobs assigned to it, and C i denotes the completion time of M i , which is T i =s i . Our objective is, for some fixed function f : [0; +1) ! [0; +1), one of the following (I) minimize P m i=1 f(C i ), (II) minimize max m i=1 f(C i ), (III) maximize P m i=1 f(C i ), or (IV) maximize min m i=1 f(C i ). Most of such ..