Scheduling Multiprocessor Tasks with Decrease Chain Constrains on Three Identical Multiprocessors
-
摘要: 研究三个并行处理器环境中,具有递减链约束的多处理器任务的调度问题,调度目标 是最小化总处理时间,假设单项任务需单位处理时间.首先给出了减链调度问题的最优化性质 与条件,并说明了减链调度问题仍然是NP难的.随后基于两段flow-shop问题的Johnson's算 法的修正和减链调度问题最优化性质,提出了一个启发式算法,并从分析和仿真计算两方面说 明该算法是有效的和高效的.Abstract: This paper focuses on scheduling unit length multiprocessor tasks with decreasing chain precedence constrains on three identical processors so as to minimize makespan. First, a few properties for optimally scheduling decreasing chains are given. However, that optimally solving the problem is NP-hard is illustrated. Then, a heuristic algorithm is proposed which is based on a revision of well-known Johnson's algorithm for two-stage flow-shop problem and the optimal properties for scheduling decreasing chains. Finally, simulation illustrates that the heuristic algorithm is effective and efficient.
-
Key words:
- Scheduling /
- multiprocessor tasks /
- precedence constrains /
- heuristic
-
计量
- 文章访问数: 2342
- HTML全文浏览量: 58
- PDF下载量: 1037
- 被引次数: 0
下载:
