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

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

Logo BII



Citation style:
Could not load citation form.


Use and reproduction:No Creative Commons license - The provisions of the German Copyright Act (UrhG) apply.Please note that individual components of the publication may be subject to other licensing or copyright conditions.