Improved Genetic Algorithm (IGA) for Scheduling Task Graphs in Multiprocessor Systems

The problem of multiprocessor scheduling can be stated as finding a schedule for a general task graph to be executed on a multiprocessor system such that the schedule length can be minimized. The last job must be completed as early as possible. Multiprocessor task scheduling is an important and computationally difficult problem. Multiprocessor computing environment requires an efficient algorithm to determine when and on which processor a given task should execute. A task can be partitioned into a group of subtasks and represented as a DAG (Directed Acyclic Graph), that problem can be stated as finding a schedule for a DAG to be executed in a parallel multiprocessor system. The problem of scheduling and mapping meta-tasks to a machine is shown to be NP-complete. The solutions of NP-complete problems are based on heuristics approach. The execution time requirements of the applications' tasks are assumed to be stochastic. Genetic algorithm (GA) is one of the widely used techniques for constrained optimization. Performance of genetic algorithm can be improved with the introduction of some knowledge about the scheduling problem represented by the use of a min-min heuristic. In this paper the problem of same completion time and same precedence is resolved by using concept of Bottom-level (b-level). This combined approach named as improved genetic algorithm (IGA) based on min-min heuristic and b-level precedence resolution is finally compared with a pure genetic algorithm, min-min heuristic and First Come First Serve (FCFS) approach. Results of the experiments show that the improved genetic algorithm produces much better results in terms of quality of solutions.