From Preemptive to Non-preemptive Scheduling Using Rejections

Giorgio Lucarelli 1, 2 Abhinav Srivastav 1, 2 Denis Trystram 1, 2
2 DATAMOVE - Data Aware Large Scale Computing
Inria Grenoble - Rhône-Alpes, LIG - Laboratoire d'Informatique de Grenoble
Abstract : We study the classical problem of scheduling a set of independent jobs with release dates on a single machine. There exists a huge literature on the preemptive version of the problem, where the jobs can be interrupted at any moment. However, we focus here on the non-preemptive case, which is harder, but more relevant in practice. For instance, the jobs submitted to actual high performance platforms cannot be interrupted or migrated once they start their execution (due to prohibitive management overhead). We target on the minimization of the total stretch objective, defined as the ratio of the total time a job stays in the system (waiting time plus execution time), normalized by its processing time. Stretch captures the quality of service of a job and the minimum total stretch reflects the fairness between the jobs. So far, there have been only few studies about this problem, especially for the non-preemptive case. Our approach is based to the usage of the classical and efficient for the preemptive case shortest remaining processing time (SRPT) policy as a lower bound. We investigate the (offline) transformation of the SRPT schedule to a non-preemptive schedule subject to a recently introduced resource augmentation model, namely the rejection model according to which we are allowed to reject a small fraction of jobs. Specifically, we propose a 2 ǫ-approximation algorithm for the total stretch minimization problem if we allow to reject an ǫ-fraction of the jobs, for any ǫ > 0. This result shows that the rejection model is more powerful than the other resource augmentations models studied in the literature, like speed augmentation or machine augmentation, for which non-polynomial or non-scalable results are known. As a byproduct, we present a O(1)-approximation algorithm for the total flow-time minimization problem which also rejects at most an \epsilon-fraction of jobs.
Type de document :
Communication dans un congrès
22nd International Computing and Combinatorics Conference (COCOON 2016), Aug 2016, Ho Chi Minh Ville, Vietnam. Lecture Notes in Computer Science, 9797, pp.510-519, 2016, 〈10.1007/978-3-319-42634-1_41〉
Liste complète des métadonnées

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

http://hal.univ-grenoble-alpes.fr/hal-01371023
Contributeur : Abhinav Srivastav <>
Soumis le : vendredi 23 septembre 2016 - 17:06:50
Dernière modification le : lundi 30 avril 2018 - 15:02:01

Fichier

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

Identifiants

Citation

Giorgio Lucarelli, Abhinav Srivastav, Denis Trystram. From Preemptive to Non-preemptive Scheduling Using Rejections. 22nd International Computing and Combinatorics Conference (COCOON 2016), Aug 2016, Ho Chi Minh Ville, Vietnam. Lecture Notes in Computer Science, 9797, pp.510-519, 2016, 〈10.1007/978-3-319-42634-1_41〉. 〈hal-01371023〉

Partager

Métriques

Consultations de la notice

299

Téléchargements de fichiers

111