Economical Duplication Based Task Scheduling for Heterogeneous and Homogeneous Computing Systems

Abstract

Task duplication based scheduling algorithms generate shorter schedules without sacrificing efficiency but leave the computing resources over consumed due to the heavily duplications. In this paper, we try to optimize the duplications after generating a schedule without affecting the overall schedule length (makespan). Here, we suggested two workflow scheduling algorithms with economical duplication i.e. Reduced duplication for homogeneous systems (RD) and heterogeneous economical duplication (HED) for heterogeneous systems respectively. In these algorithms, a static task schedule is generated using an insertion-based task-duplication scheduling strategy and try to optimized by removing some duplicated tasks in the schedule whose removal does not affect the makespan adversely. Further, in some situations, the earlier schedule of a task becomes unproductive after it has been duplicated later on different processor(s). The algorithms investigate and remove such schedules in order to reduce processor consumption. Removing such useless tasks generate larger scheduling holes in the schedule, which can be better utilized for scheduling other parallel and distributed applications such as in grid environment. The simulation results show that RD and HED algorithms generate better schedule with lesser number of duplications and remarkably less processor consumption as compared with SD, CPFD for homogeneous systems and HLD, LDBS for heterogeneous systems.