An Optimized Genetic Approach for Scheduling Task Duplication in Parallel Systems

Abstract

Task Scheduling deals with the set of tasks assigned to parallel multiprocessor system and the execution order of the schedule so that the total execution time is minimized. The role of a good scheduling algorithm is to efficiently assign each task to a processor depending on the resources needed, the communication overhead between related tasks is reduced and the precedence relations among tasks are satisfied. It can be efficiently used for tasks that have a large calculation, and have time constraints to complete the schedule. The efficient execution of the task scheduling on parallel system takes the structure of the task and the performance characteristics of the proposed genetic algorithm. It falls in the category of NP-complete problem. This study proposes a parallel genetic algorithm-based approach to schedule tasks on parallel system with task duplication heuristics. Task duplication can minimize inter-processor communication and hence results in shorter finish times. Its performance is measured in comparison with the Round Robin (RR), First Come First Serve (FCFS), and Multi-level queue scheduling (MQS), Shortest Job First (SJF), Largest Job First (LJF) and Priority scheduling methods.