An Optimal Scheduling Algorithm for Fork-Join Task Graphs

摘要：

The task duplication based scheduling is a new approach to the scheduling problems. This is known as an NP-Complete problem. Although some algorithms are able to find an optimal schedule under certain conditions, they ignored to economize processors and minimize the total completion time. In this paper, we presents a Task Duplication based Balance Scheduling (TDBS) algorithm which can schedule a class of fork-join task graph with a complexity of of O(| V|2),where |V| is the number of tasks. The proposed algorithm generates an optimal schedule with high speedup and efficiency. Simulation results showed that our algorithm has better scheduling length, less completion time and less number of processors than any of compared algorithms.

关键词： Optimal Scheduling Algorithm Task Duplication Fork-Join Task Graph

作者: Qinghua LI Youlin RUAN Shida YANG Tingyao JIANG

作者单位: Department of Computer Science and Technology HuaZhong University of Science and Technology, Wuhan, 430074, China

会议类型: 国际会议

会议名称: Proceedings of The Fourth International Conference on Parallel and Distribyted Computing,Applications and Technologies(第四届并行与分布式计算应用与技术国际会议)

会议地点: 成都

会议语种:英文

页码: 587-589

在线出版日期: 2003-08-27（万方平台首次上网日期，不代表论文的发表时间）