Pareto Front Based Realistic Soft Real-Time Task Scheduling with Multi-objective Genetic Algorithm on Arbitrary Heterogeneous Multiprocessor System

Abstract

Task scheduling is an essential aspect of parallel processing system. This problem assumes fully connected processors and ignores contention on the communication links. However, as arbitrary processor network (APN), communication contention has a strong influence on the execution time of a parallel application. In this paper, we propose a multi-objective genetic algorithm to solve task scheduling problems with time constraints on arbitrary heterogeneous processors to find the scheduling with minimum makespan and total tardiness. To optimize objectives, we use Pareto front based technique and vector based method. In this problem, just like tasks, we schedule messages on suitable links during the minimization of the makespan and total tardiness. To find a path to transfer a message between processors we use a classic routing algorithm. We compare our method with bubble scheduling and allocation (BSA) method that is a well known algorithm. Experimental results show our method is better than BSA and yields better makespan and total tardiness.