On contiguous and non-contiguous parallel task scheduling

Abstract : 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.
Type de document :
Article dans une revue
Journal of Scheduling, Springer Verlag, 2015, 〈10.1007/s10951-015-0427-z〉
Liste complète des métadonnées

https://hal-emse.ccsd.cnrs.fr/emse-01225177
Contributeur : Xavier Schepler <>
Soumis le : jeudi 5 novembre 2015 - 16:20:25
Dernière modification le : samedi 27 octobre 2018 - 01:23:29

Lien texte intégral

Identifiants

Citation

Xavier Schepler, Iwo Bładek, Maciej Drozdowski, Frédéric Guinand. On contiguous and non-contiguous parallel task scheduling. Journal of Scheduling, Springer Verlag, 2015, 〈10.1007/s10951-015-0427-z〉. 〈emse-01225177〉

Partager

Métriques

Consultations de la notice

89