Efficient tasks scheduling is critical for achieving high performa nce in heterogeneous computing systems. The tasks scheduling problem is NP-hard in general. In order to obtain better solutions, many scheduling heuristics were presented in the literature. Based on genetic algorithm and MCT(minimum complet ion time) algorithm, a new hybrid genetic algorithm was presented for independe nt tasks scheduling in heterogeneous computing systems. Genetic algorithm was us ed to evolve a priority queue first, and then the priority queue was mapped to a schedule using MCT algorithm. The simulation results comparing with other sched uling algorithm show that it produces better results in terms of schedule length , and it has good convergent speed.
Armstrong R, Hensgen D, Kidd T. The relative performance of various mapping algorithms is independent of sizable variances in run-time predictions . In:7th IEEE Heterogeneous Computing Workshop , 1998. 79~87
Freund R, Gherrity M, Ambrosius S, et al. Scheduling resources in multi-user, heterogeneous, computing environments with SmartNet . In:7th IEEE Heterogeneous Computing Workshop , 1998. 184~199
Ibarra O, Kim C. Heuristic algorithms for scheduling independent tasks on nonidentical processors[J]. Journal of the ACM, 1977, 77(2):280~289
Wang L, Siegel H J, Roychowdhury V P, et al. Task matching and scheduling in heterogeneous computing environments using a genetic-algorithm-based a pproach[J].Journal of Parallel and Distributed Computing.1997, 47(1):1-15
Braun T, Siegel H, Beck N, et al. A comparison study of static mapping heuristics for a class of meta-tasks on heterogeneous computing systems . In:8th IEEE Heterogeneous Computing Workshop , 1999. 15~29
Wu Minyou, Shu Wei, Zhang Hong. Segmented Min-min:a static mapping algorithm for meta-tasks on heterogeneous computing systems . In:9th IEEE He terogeneous Computing Workshop , 2000. 375~385
����ǿ, �ܼ���, �� ��,��. �Ŵ��㷨�Ļ���������Ӧ��[M]. ����:��ѧ������, 2002 Li Minqiang, Guan Jisong, Lin Dan, et al. The basic theory and application of genetic algorithm[M]. Beijing:Science Press, 2002(in Chinese)