Preemptive scheduling with variable profile, precedence constraints and due dates

Abstract : This paper is concerned with the problem of scheduling preemptive tasks subject to precedence constraints in order to minimize the maximum lateness and the makespan. The number of available parallel processors is allowed to vary in time. It is shown that when an earliest due date first algorithm provides an optimal nonpreemptive schedule for unit execution time tasks, then the preemptive priority scheduling algorithm, referred to as smallest laxity first, provides an optimal preemptive schedule for real-execution-time tasks. When the objective is to minimize the makespan, we get the same kind of result between highest level first schedules solving nonpremptive tasks with unit execution time and the longest remaining path first schedule for the corresponding preemptive scheduling problem with real-execution-time tasks. These results are applied to four specific profile scheduling problems and new optimality results are obtained.
Type de document :
Rapport
[Research Report] RR-1622, INRIA. 1992
Liste complète des métadonnées

https://hal.inria.fr/inria-00074939
Contributeur : Rapport de Recherche Inria <>
Soumis le : mercredi 24 mai 2006 - 17:01:12
Dernière modification le : jeudi 11 janvier 2018 - 16:20:45
Document(s) archivé(s) le : mardi 12 avril 2011 - 17:15:33

Fichiers

Identifiants

  • HAL Id : inria-00074939, version 1

Collections

Citation

Zhen Liu, Eric Sanlaville. Preemptive scheduling with variable profile, precedence constraints and due dates. [Research Report] RR-1622, INRIA. 1992. 〈inria-00074939〉

Partager

Métriques

Consultations de la notice

141

Téléchargements de fichiers

84