A genetic-algorithm-based approach for subtask matching and scheduling in heterogeneous computing environments and a comparative study of parallel genetic algorithms

To exploit a heterogeneous computing (HC) environment (e.g., a suite of interconnected different high-performance machines), an application task may be decomposed into subtasks that have data dependencies. Subtask matching and scheduling consist of assigning subtasks to machines, ordering subtask execution for each machine, and ordering inter-machine data transfers. The goal is to achieve the minimal completion time for the task. A heuristic approach based on a genetic algorithm (GA) is developed to do matching and scheduling in HC environments. It is applicable to the static scheduling of production jobs and can be readily used to collectively schedule a set of tasks that are decomposed into subtasks. Some parameters and the selection scheme of the GA were chosen experimentally to achieve the best performance. Extensive simulation tests were conducted. For small-sized problems (e.g., a small number of subtasks and a small number of machines), exhaustive searches were used to verify that this GA-based approach found the optimal solutions. Simulation results for larger-sized problems showed that this GA-based approach outperformed two non-evolutionary heuristics and a random search. Parallel algorithms have been developed to reduce the large execution times that are associated with serial GAs. They have also been used to solve larger problems and to find better solutions. This thesis surveys existing parallel genetic algorithm (PGA) approaches and identifies some design issues. Three novel PGAs are developed, using the traveling salesman problem as a case study. They are compared with two existing approaches. Extensive experimental studies show that the algorithm using chromosome migrations and the algorithm combining migration with tour segmentation and recombination achieved the best performance. In conclusion, two completed research projects are presented: a GA-based approach for task matching and scheduling in HC environments and a comparative study on PGAs. They make significant contributions to the advancement of computer engineering, especially in the areas of heterogeneous computing, parallel processing, and GAs