Abstract:

Parallel task scheduling of multiprocessors is a hot research topic, and also is a well known NP-hard problem. Focusing on this problem, a modified hybrid genetic algorithm (MHGA) is proposed, in which the heuristic algorithm, tabu search (TS) algorithm and simulated annealing (SA) algorithm are integrated. The modifications of the MHGA include: using the hierarchical scheduling based heuristic method to initialize the population so as to improve the quality of initial population; employing the TS based random number crossover to enhance the diversity of the population; adopting the SA based mutation to improve the quality of the individual. Experimental results show that the MHGA can obtain smaller task scheduling time and have ability to fast search better solution in comparison with other GAs.