A Hybrid Algorithm for Task Scheduling in Heterogeneous Multi-core System

Propose a novel hybrid static scheduling algorithm named Hybrid Successor Concerned Heuristic-Genetic Scheduling (HSCGS) algorithm. The algorithm is a combination of heuristic and genetic scheduling algorithm. In the first phase we propose a heuristic algorithm named Successor Concerned List Heuristic Scheduling (SCLS) to generate a high quality scheduling result. SCLS algorithm takes the impact of current task's scheduling to its successor into account. The second phase implements an Improved Genetic Algorithm (IGA) for scheduling, to optimize the scheduling results of SCLS iteratively. The comparison experiments are based on both random generated applications and some real world applications. The performance of HSCGS is compared with some famous task scheduling algorithms, such as HEFT and DLS. The results show that HSCGS is the best of them, and the advantages go up with the increase of the heterogeneous factor of inter-core link bandwidth.