Genetic algorithm solution for scheduling jobs in multiprocessor environment

Multiprocessor task scheduling is considered to be the most important and very difficult issue in High Performance Computing. Task scheduling is performed to match the resource requirement of the job with the available resources resulting in effective utilization of multiprocessor systems. In this paper, a Genetic algorithm (GA) is proposed for static, non-preemptive scheduling problem in homogeneous fully connected multiprocessor systems with the objective of minimizing the job completion time. The proposed GA is used to determine suitable priorities that lead to a sub-optimal solution. To compare the performance of proposed algorithm, Static algorithms of BNP (Bounded Number of Processors) scheduling class i.e. HLFET (Highest Level with First Estimated Time) and MCP (Modified Critical Path) are implemented. HLFET, MCP and proposed GA are tested by mapping our tasks in a directed acyclic graph (DAG). Performance analysis of HLFET, MCP and proposed GA for a given job scheduling problem proves that GA results in better sub-optimal solutions.