We consider the problem of scheduling n independent jobs on m unrelated parallel machines where each job has to be processed by exactly one machine, processing job j on machine i requires p(ij) time units, and the objective is to minimize the makespan, i.e., the maximum job completion time. Focusing on the case when m is fixed, we present for both preemptive and nonpreemptive variants of the problem fully polynomial approximation schemes whose running times depend only linearly on n. We also study an extension of the problem where processing job j on machine i incurs a cost of c(ij), and thus there are two optimization criteria: makespan and cost. We show that, for any tired m. there is a fully polynomial approximation scheme that, given values T and C, computes for any tired epsilon > 0 a schedule in O(n) time with makespan at most (1 + epsilon )T and cost at most (1 + epsilon )C, if there exists a schedule of makespan T and cost C. [References: 15]
展开▼
