Efficient Tasks Scheduling for Heterogeneous Multiprocessor Parallel Computing using Enhanced Genetic Algorithm

Jaspal Singh, Jasbir Singh Gill and Tarandeep Singh Walia

P. G. Department of Computer Science, Guru Gobind Singh Khalsa College, Sarhali (Tarn Taran), Punjab, India.


The prime function of the effective utilization of heterogeneous multiprocessor system is accurately mapping of tasks and makes their scheduling on different processors for reducing their total finish time. Total runtime is time taken time for all jobs with the individual runtime of tasks and their communication cost among tasks. An optimal scheduling of parallel tasks with some precedence relationship onto a multiprocessor system is considered as NP-complete problem. The scheduling problem considered in this paper is bringing out the optimal mapping of tasks and their efficiently possible execution stream on multiprocessor system configuration. Several solutions and heuristics are proposed to solve this problem. We exhibit efficiency of Enhanced GA based technique by comparing against some of the existing deterministic scheduling techniques.

Keywords: Parallel system with heterogeneous processors, Arbitrary search, Task scheduling, Enhanced genetic algorithm (EGA).

     Back to TOC