减链约束多处理器任务在三处理器中的调度

研究三个并行处理器环境中,具有递减链约束的多处理器任务的调度问题,调度目标 是最小化总处理时间,假设单项任务需单位处理时间.首先给出了减链调度问题的最优化性质 与条件,并说明了减链调度问题仍然是NP难的.随后基于两段flow-shop问题的Johnson's算 法的修正和减链调度问题最优化性质,提出了一个启发式算法,并从分析和仿真计算两方面说 明该算法是有效的和高效的.

Scheduling Multiprocessor Tasks with Decrease Chain Constrains on Three Identical Multiprocessors

This paper focuses on scheduling unit length multiprocessor tasks with de-creasing 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 heuris-tic 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 effi-cient.