Online Non-preemptive Scheduling in a Resource Augmentation Model based on Duality

Abstract : Resource augmentation is a well-established model for analyzing algorithms, particularly in the online setting. It has been successfully used for providing theoretical evidence for several heuris-tics in scheduling with good performance in practice. According to this model, the algorithm is applied to a more powerful environment than that of the adversary. Several types of resource augmentation for scheduling problems have been proposed up to now, including speed augmentation , machine augmentation and more recently rejection. In this paper, we present a framework that unifies the various types of resource augmentation. Moreover, it allows generalize the notion of resource augmentation for other types of resources. Our framework is based on mathematical programming and it consists of extending the domain of feasible solutions for the algorithm with respect to the domain of the adversary. This, in turn allows the natural concept of duality for mathematical programming to be used as a tool for the analysis of the algorithm's performance. As an illustration of the above ideas, we apply this framework and we propose a primal-dual algorithm for the online scheduling problem of minimizing the total weighted flow time of jobs on unrelated machines when the preemption of jobs is not allowed. This is a well representative problem for which no online algorithm with performance guarantee is known. Specifically, a strong lower bound of Ω(√ n) exists even for the offline unweighted version of the problem on a single machine. In this paper, we first show a strong negative result even when speed augmentation is used in the online setting. Then, using the generalized framework for resource augmentation and by combining speed augmentation and rejection, we present an (1+ s)-speed O(
Type de document :
Communication dans un congrès
European Symposium on Algorithms (ESA 2016), Aug 2016, Aarhus, Denmark. LIPIcs, 57 (63), pp.1-17, 〈10.4230/LIPIcs.ESA.2016.63〉
Liste complète des métadonnées

Littérature citée [11 références]  Voir  Masquer  Télécharger

http://hal.univ-grenoble-alpes.fr/hal-01334219
Contributeur : Abhinav Srivastav <>
Soumis le : lundi 20 juin 2016 - 16:04:30
Dernière modification le : mardi 1 mai 2018 - 01:22:42
Document(s) archivé(s) le : jeudi 22 septembre 2016 - 22:17:22

Fichier

full_paper.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Citation

Giorgio Lucarelli, Nguyen Kim Thang, Abhinav Srivastav, Denis Trystram. Online Non-preemptive Scheduling in a Resource Augmentation Model based on Duality. European Symposium on Algorithms (ESA 2016), Aug 2016, Aarhus, Denmark. LIPIcs, 57 (63), pp.1-17, 〈10.4230/LIPIcs.ESA.2016.63〉. 〈hal-01334219〉

Partager

Métriques

Consultations de la notice

817

Téléchargements de fichiers

216