A Novel ACO Based Static Task Scheduling Approach for Multiprocessor Environments
AbstractOptimized task scheduling is one of the most important challenges in parallel and distributed systems. In such architectures during compile step, each program is decomposed into the smaller segments so called tasks. Tasks of a program may be dependent; some tasks may need data generated by the others to start. To formulate the problem, precedence constraints, required execution times of tasks, and communication costs among them are modeled using a directed acyclic graph (DAG) named task graph. The tasks must be assigned to a predefined number of processors in such a way that the program completion time is minimized, and the precedence constraints are preserved. It is well known to be NP hard in general form and most restricted cases; therefore, a number of heuristic and meta heuristic approaches have so far been proposed in the literature to find near optimum solutions for this problem. We believe that ant colony optimization (ACO) is one of the best methods to cope with such kind of problems pres.
Int. J. Comput. Intell. Syst.