A heuristic for task scheduling based on hasse diagram

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.