Skip to Main content Skip to Navigation
Journal articles

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.
Document type :
Journal articles
Complete list of metadatas

Cited literature [24 references]  Display  Hide  Download

https://hal-emse.ccsd.cnrs.fr/emse-01225177
Contributor : Xavier Schepler <>
Submitted on : Friday, March 6, 2020 - 5:38:57 PM
Last modification on : Tuesday, March 10, 2020 - 4:33:09 PM

File

bladek.drozdowski.guinand.sche...
Files produced by the author(s)

Identifiers

Citation

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

Share

Metrics

Record views

248

Files downloads

149