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
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;
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
DOI :
10.1109/BICTA.2010.5645109