On contiguous and non-contiguous parallel task scheduling - Mines Saint-Étienne Accéder directement au contenu
Article Dans Une Revue Journal of Scheduling Année : 2015

On contiguous and non-contiguous parallel task scheduling

Résumé

In this paper we study differences between contiguous and non-contiguous parallel task schedules. Parallel tasks can be executed on more than one processor simultaneously. In the contiguous schedules, indices of the processors assigned to a task must be a sequence of consecutive numbers. In the non-contiguous schedules, processor indices may be arbitrary. Optimum non-preemptive schedules are considered. Given a parallel task instance, the optimum contiguous and non-contiguous schedules can be of different lengths. We analyze minimal instances where such a difference may arise, provide bounds on the difference of the two schedules lengths, and prove that deciding whether the difference in schedule length exists is NP-complete.
Fichier principal
Vignette du fichier
bladek.drozdowski.guinand.schepler.2015.hal.pdf (353.06 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

emse-01225177 , version 1 (06-03-2020)

Identifiants

Citer

Iwo Bładek, Maciej Drozdowski, Frédéric Guinand, Xavier Schepler. On contiguous and non-contiguous parallel task scheduling. Journal of Scheduling, 2015, 18 (5), pp.487-495. ⟨10.1007/s10951-015-0427-z⟩. ⟨emse-01225177⟩
81 Consultations
79 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More