Scheduling in Multiprocessor System using Genetic Algorithm

Abstract

Task scheduling is essential for the suitable operation of multiprocessor systems. The task scheduling is prime significance of multiprocessor parallel systems. In this paper, an efficient method based on genetic algorithms is developed to solve the multiprocessor scheduling problem. The paper also aims to provide a comparative study of incorporating heuristics such as ‘Earliest Deadline First (EDF) ’ and ‘Shortest Computation Time First (SCTF) ’ separately with genetic algorithms. We exhibit efficiency of Node duplication Genetic Algorithm (NGA) based technique by comparing against some of the existing deterministic scheduling techniques for minimizing inter processor traffic communication. A comparative study of the results obtained from simulations shows that genetic algorithm can be used to schedule tasks to meet deadlines, in turn to obtain high processor utilization. Performance analysis of NGA is compared with GA, FCFS and List Scheduler. Experimental results show that the NGA is betters than the others. Performance of NGA, GA, List Scheduling, and FCFS is almost 64.1%, 55.55%, 52.08, and 41.033 % respectively.