.png){kind=icon}
返回
Scheduling parallel tasks with sequential heads and tails
.png){kind=icon}
PRE
AI
DOI：10.1023/A:1018964732122.png)
.png){kind=icon}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
This paper considers scheduling of parallel tasks in a multiprogrammed, multiprocessor system. The problem of preemptive scheduling of n tasks on m processors to minimize makespan is studied. Task j starts and finishes with sequential parts head(j) and tail(j) , respectively. Between these two, j runs its parallel part parallel(j). The sequential parts have to be executed by one processor at a time. The parallel part can be executed by more than one processor at a time. It is shown that this problem is NP-hard in the strong sense even if there are fewer tasks than processors. A linear program is presented to find an optimal schedule for a given sequence of completion times of heads and start times of tails. If the optimal schedule for tasks longer than the mth longest task is given, an efficient, polynomial-time merging algorithm is proposed to obtain an optimal schedule for all n tasks. The algorithm builds an optimal schedule with at most m - 1 tasks running their parallel parts on more than one processor at a time, the remaining tasks run their parallel parts as if they were sequential. Therefore, there always exist optimal schedules with only a few tasks exploiting the parallel processing capability of a parallel system. Finally, polynomially solvable cases are discussed, and the worst-case performance of three heuristics for the problem is analyzed.
Keyword:
parallel processing
multiprocessor tasks
preemptive scheduling
complexity analysis
AI总结
对已上传原文的论文进行重点信息的提取，主要内容包括：简要概述、研究摘要、背景介绍、关键亮点、图文解析、展望与总结。
