Scheduling Multiprocessor Tasks with Genetic Algorithms (CROSBI ID 484931)
Prilog sa skupa u zborniku | izvorni znanstveni rad | međunarodna recenzija
Podaci o odgovornosti
Golub, Marin ; Kasapović, Suad
engleski
Scheduling Multiprocessor Tasks with Genetic Algorithms
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”.
DAG; parallel processing; multiprocessor scheduling; genetic algorithms; optimisation; heuristics
nije evidentirano
nije evidentirano
nije evidentirano
nije evidentirano
nije evidentirano
nije evidentirano
Podaci o prilogu
273-278-x.
2002.
objavljeno
Podaci o matičnoj publikaciji
Proceedings of the IASTED International Conference Applied Informatics
Hamza, M. H.
Innsbruck: ACTA Press
Podaci o skupu
International Symposium on Parallel and Distributed Computing and Networks
predavanje
18.02.2002-21.02.2002
Innsbruck, Austrija