A new heuristic for task scheduling in heterogeneous computing environment

作者：Munir Ehsan Ullah^*; Li Jian zhong; Shi Sheng fei; Zou Zhao nian; Rasool Qaisar

来源：Journal of Zhejiang University-Science A(Applied Physics & Engineering), 2008, 9(12): 1715-1723.

DOI：10.1631/jzus.A0820007

• Heterogeneous computing
• Task scheduling
• Greedy heuristics
• High standard deviation first (HSTDF) heuristic
• TP3

Heterogeneous computing (HC) environment utilizes diverse resources with different computational capabilities to solve computing-intensive applications having diverse computational requirements and constraints. The task assignment problem in HC environment can be formally defined as for a given set of tasks and machines, assigning tasks to machines to achieve the minimum makespan. In this paper we propose a new task scheduling heuristic, high standard deviation first (HSTDF), which considers the standard deviation of the expected execution time of a task as a selection criterion. Standard deviation of the expected execution time of a task represents the amount of variation in task execution time on different machines. Our conclusion is that tasks having high standard deviation must be assigned first for scheduling. A large number of experiments were carried out to check the effectiveness of the proposed heuristic in different scenarios, and the comparison with the existing heuristics (Max-min, Sufferage, Segmented Min-average, Segmented Min-min, and Segmented Max-min) clearly reveals that the proposed heuristic outperforms all existing heuristics in terms of average makespan.

• 出版日期2008-12
• 单位哈尔滨工业大学