Improved Approximation Algorithms for Scheduling with Fixed Jobs

Abstract : We study two closely related problems in non-preemptive scheduling of sequential 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 either case, 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 + ε, respectively. 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. In total, our approximation ratio for both problems is essentially tight via suitable inapproximability results. We use dual approximation, creation of a gap structure and job configurations, and a PTAS for the multiple subset sum problem. However, the main feature of our algorithms is a new technique for the assignment of large jobs via flexible rounding. Our new technique is based on an interesting cyclic shifting argument in combination with a network flow model for the assignment of jobs to large gaps
Type de document :
Communication dans un congrès
Proceedings of the 20th ACM-SIAM Symposium on Discrete Algorithms, 2009, New York, United States. pp.675-684, 2009
Liste complète des métadonnées

https://hal.inria.fr/hal-00800419
Contributeur : Grégory Mounié <>
Soumis le : mercredi 13 mars 2013 - 16:22:00
Dernière modification le : lundi 13 octobre 2014 - 15:43:25

Identifiants

  • HAL Id : hal-00800419, version 1

Citation

Florian Diedrich, Klaus Jansen. Improved Approximation Algorithms for Scheduling with Fixed Jobs. Proceedings of the 20th ACM-SIAM Symposium on Discrete Algorithms, 2009, New York, United States. pp.675-684, 2009. 〈hal-00800419〉

Partager

Métriques

Consultations de la notice

22