期刊
JOURNAL OF SCHEDULING
卷 18, 期 5, 页码 487-495出版社
SPRINGER
DOI: 10.1007/s10951-015-0427-z
关键词
Parallel tasks; Contiguous scheduling; Non-contiguous scheduling
资金
- Polish National Science Center
- French National Research Ministry
- PHC Polonium project [28935RA]
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.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据