Evolutionary Algorithm-Based Multiprocessor Task Scheduler

As a key issue in parallel and distributed systems, multiprocessor task scheduling is a NP-complete problem in many cases. It is of great significance for both theoretical research and practical application to schedule tasks to different processors effectively and efficiently within the whole multiprocessor system.Different with the dominant list scheduling algorithm, evolutionary multiprocessor task scheduling algorithm is a probabilistic global search algorithm. By maintaining a population of codes of the schedule queues and applying evolutionary operations, such as selection, crossover and mutation on them, evolutionary algorithm can converge to the optimal schedule in finite generations. That is principle of evolutionary computation.But as we know, almost all evolutionary scheduling algorithms extended the coding method and evolutionary operations by integrating with domain knowledge of task scheduling problem. As we thought, such expansions completely departure from the origin of evolutionary computation, and completely lost the essence of evolutionary algorithm. Therefore, we introduce the Classical Evolutionary (Genetic) Algorithm which is based on simple binary code and domain knowledge-independent operations. We discussed and compared the two algorithms, and proved that classical evolutionary algorithm is obviously superior to extended genetic algorithm in simplicity, consistence, applicability and reusability, and it can reach the same performance level as the extended algorithm by carefully designing fitness function.By penetratingly analyzing multiprocessor task scheduling problem, we designed three classes of evolutionary multiprocessor task scheduler. From communication cost-ignored form, to heterogeneous system-oriented general form, these algorithms solved the problems reasonably as their definitions. The design and implementation of these scheduling algorithms also proved the unusual flexibility of classical evolutionary algorithm.Performance evaluation is very important in research on multiprocessor task scheduling problem. But as we know, there is no unified standard for evaluation. In this thesis, we discussed this problem definitely, analyzed the principles of performance evaluation, and designed the benchmarks for evolutionary...