DocumentCode :
3227895
Title :
A heuristic for task scheduling based on hasse diagram
Author :
Liang, Qiushi ; Li, Kenli ; Tesfazghi, Teklay ; Li, Muying
Author_Institution :
Sch. of Comput. & Commun., Hunan Univ., Changsha, China
fYear :
2010
fDate :
23-26 Sept. 2010
Firstpage :
1085
Lastpage :
1092
Abstract :
The problem of optimally mapping independent tasks onto heterogeneous machines such that the completion time of the last finishing task is minimized is NP-complete. Quite a lot of heuristics have been introduced to optimize the figure of merit. Among them, the algorithms HLTF (The Heterogeneous Largest Task First) and Segmented Min-Min have better makespans. However, the HLTF heuristic doesn´t explain how to describe the heterogeneity of tasks, and the segments of Segmented Min-Min are not unique. In this paper, by using hasse diagram, we investigates a new heuristic which not only implements the idea of HLTF and Segment Min-Min but also overcomes the deficiencies of them, the new heuristic and several related ones have been implemented on a simulated He environment which is based on simjava, the experimental results illuminate that our heuristic outperforms the traditional ones.
Keywords :
computational complexity; minimisation; scheduling; HLTF; NP-complete; finishing task; hasse diagram; heterogeneous largest task first; heterogeneous machines; segmented min-min; task scheduling; Complexity theory; HLTF; Hasse diagram; Heuristic; Scheduling; Segmented Min-Min;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Bio-Inspired Computing: Theories and Applications (BIC-TA), 2010 IEEE Fifth International Conference on
Conference_Location :
Changsha
Print_ISBN :
978-1-4244-6437-1
Type :
conf
DOI :
10.1109/BICTA.2010.5645109
Filename :
5645109
Link To Document :
بازگشت