Improved approximation schemes for scheduling unrelated parallel machines

• 成果类型: Article
• 署名作者: Jansen, K; Porkolab, L
• 署名单位: University of Kiel; Imperial College London
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.26.2.324.10559
• 发表日期: 2001
• 页码: 324-338
• 关键词: algorithms; processors

摘要

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.