Approximation Algorithms for Scheduling Parallel Jobs: Breaking the Approximation Ratio of 2

zum Volltext (477 kB)   ZIP
Beteiligte Person(en) / Institution(en)Autor :
DatumErschienen :
  • September 2008
Seitenbereich52 S.

In this paper we study variants of the non-preemptive parallel job scheduling problem in which 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. Unless P = NP, this is the best possible result (in the sense of approximation ratio), since the problem is strongly NP-hard. For the case, where all jobs must be allotted to a subset of consecutive machines, 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. Furthermore, we extend both algorithms to the case of malleable jobs with the same approximation ratios.
Statische URLhttps://www.uni-kiel.de/journals/receive/jportal_jparticle_00000111
 
URN:NBNurn:nbn:de:101:1-201203215161
IDNummer des Berichts :
  • TR_0808