Parallel evolutionary algorithms for scheduling on heterogeneous computing and grid environments
This thesis studies the application of sequential and parallel evolutionary algorithms to the scheduling problem in heterogeneous computing and grid environments, a key problem when executing tasks in distributed computing systems. Since the 1990's, this class of systems has been increasingly employ...
Saved in:
| Main Author: | |
|---|---|
| Format: | doctoralThesis |
| Language: | English |
| Published: |
2010
|
| Subjects: | |
| Online Access: | http://hdl.handle.net/20.500.12008/2958 |
| Tags: |
No Tags, Be the first to tag this record!
|
| Summary: | This thesis studies the application of sequential and parallel evolutionary algorithms to the scheduling problem in heterogeneous computing and grid environments, a key problem when executing tasks in distributed computing systems. Since the 1990's, this class of systems has been increasingly employed to provide support for solving complex problems using high-performance computing techniques. The scheduling problem in heterogeneous computing systems is an NP-hard optimization problem, which has been tackled using several optimization methods in the past. Among many new techniques for optimization, evolutionary computing methods have been successfully applied to this class of problems. In this work, several evolutionary algorithms in their sequential and parallel variants are specically designed to provide accurate solutions for the problem, allowing to compute an eficient planning for heterogeneous computing and grid environments. New problem instances, far more complex than those existing in the related literature, are introduced in this thesis in order to study the scalability of the presented parallel evolutionary algorithms. In addition, a new parallel micro-CHC algorithm is developed, inspired by useful ideas from the multiobjective optimization field. Eficient numerical results of this algorithm are reported in the experimental analysis performed on both well-known problem instances and the large instances specially designed in this work. The comparative study including traditional methods and evolutionary algorithms shows that the new parallel micro-CHC is able to achieve a high problem solving eficacy, outperforming previous results already reported for the problem and also having a good scalability behavior when solving high dimension problem instances. |
|---|