Naslov
Scheduling Multiprocessor Tasks with Genetic Algorithms

Autori
Golub, Marin ; Kasapović, Suad

Vrsta, podvrsta i kategorija rada
Radovi u zbornicima skupova, cjeloviti rad (in extenso), znanstveni

Izvornik
Proceedings of the IASTED International Conference Applied Informatics / Hamza, M. H. - Innsbruck : ACTA Press, 2002, 273-278

Skup
International Symposium on Parallel and Distributed Computing and Networks

Mjesto i datum
Innsbruck, Austrija, 18.02.2002. - 21.02.2002

Vrsta sudjelovanja
Predavanje

Vrsta recenzije
Međunarodna recenzija

Ključne riječi
DAG; parallel processing; multiprocessor scheduling; genetic algorithms; optimisation; heuristics

Sažetak
In this paper, an efficient method based on genetic algorithms is developed to solve the multiprocessor scheduling problem. To efficiently execute programs in parallel on multiprocessor scheduling problem must be solved to determine the assignment of tasks to the processors and the execution order of the tasks so that the execution time is minimized. Even when the target processors is fully connected and no communication delay is considered among tasks in the task graph the scheduling problem is NP-complete. Complexity of scheduling problems dependent of number of processors (P), task processing time Ti and precedence constraints. This problem has been known as strong NP-hard intractable optimisation problem when it assumes arbitrary number of processors, arbitrary task processing time and arbitrary precedence constraints. We assumed fixed number of processors and tasks are represented by a directed acyclic graph (DAG) called “task graph”.

Izvorni jezik
Engleski

Znanstvena područja
Računarstvo

POVEZANOST RADA