Static scheduling of directed acyclic data flow graphs onto multiprocessors using particle swarm optimization

An efficient method based on particle swarm optimization (PSO) is developed to solve the Multiprocessor Task Scheduling Problem (MPTSP). To efficiently execute parallelized programs on a multiprocessor environment, a scheduling problem must be solved to determine the assignment of tasks to the processors, the execution order of the tasks, and the starting time of each task, such that some optimality criteria are met. The scheduling problem is known as an NP-complete problem even when the target processors are fully connected and no communication delay is considered among the tasks in the task graph. The complexity of the scheduling problem depends on the number of tasks (N), the number of processors (M), the task processing time and the precedence constraints. The Directed Acyclic Graph (DAG) was exploited to represent the tasks and their precedence constraints. The proposed algorithm was compared with the Genetic Algorithm (GA) and the Duplication Scheduling Heuristic (DSH). We also provide a systematic investigation on the effect of varying problem settings. The results show that the proposed algorithm could not outperform the DSH while it could outperform the GA in some cases.