In this paper we study variants of the non-preemptive parallel job scheduling problem where the number of machines is polynomially bounded in the number of jobs. For this problem we show that a schedule with length at most (1 + ε) OPT can be calculated in polynomial time, which is the best possible result (in the sense of approximation ratio), since the problem is strongly NP-hard. For the case when all jobs must be allotted to a subset of machines with consecutive indices a schedule with length at most (1.5 + ε) OPT can be calculated in polynomial time. The previously best known results are algorithms with absolute approximation ratio 2.
展开▼
