Tight Approximation Algorithms for Scheduling with Fixed Jobs and Non-Availability

zum Volltext (518 kB)   ZIP
Beteiligte Person(en) / Institution(en)Autor :
DatumErschienen :
  • September 2010
Seitenbereich21 S.

We study two closely related problems in non-preemptive scheduling of jobs on identical parallel machines. In these two settings there are either fixed jobs or non-availability intervals during which the machines are not available; in both cases, the objective is to minimize the makespan. Both formulations have different applications, e.g. in turnaround scheduling or overlay computing. For both problems we contribute approximation algorithms with an improved ratio of 3/2. For scheduling with fixed jobs, a lower bound of 3/2 on the approximation ratio has been obtained by Scharbrodt, Steger & Weisser; for scheduling with non-availability we provide the same lower bound. We use dual approximation, creation of a gap structure and a PTAS for the multiple subset sum problem, combined with a post- processing step to assign large jobs
Statische URLhttps://www.uni-kiel.de/journals/receive/jportal_jparticle_00000071
 
URN:NBNurn:nbn:de:101:1-201202294317
IDNummer des Berichts :
  • TR_1011