Improved approximation schemes for scheduling unrelated parallel machines
Klaus Jansen, Lorant Porkolab · 1999
We consider the problem of scheduling n independent jobs on m unrelated parallel machines.Each job has to be processed by exactly one machine, processing job j on machine i requires p;j time units, and the objective is to minimize the makespan, i.e. the maximum job completion time.We focus on the caSe when n is fixed and develop a fully polynomial approximation scheme whose running time depends only linearly on n.In the second half of the paper we extend this result to a variant of the problem, where processing job j on machine i also incurs a cost of cij, and thus there are two optimization criteria: makespan and cost.We show that for any fixed m, there is a fully polynomial approximation scheme that, given values T and C, computes for any fixed E > 0 a schedule in O(n) time with makespan at most (1 + e)T and cost at most (1 + e)C, if there exists a schedule of makespan T and cost C.