Static task scheduling with a unified objective on time and resource domains

Abstract

Task scheduling for parallel and distributed systems is an NP-complete problem, which is well documented and studied in the literature. A large set of proposed heuristics for this problem mainly target to minimize the completion time or the schedule length of the output schedule for a given task graph. An additional objective, which is not much studied, is the minimization of number of processors allocated for the schedule. These two objectives are both conflicting and complementary, where the former is on the time domain targeting to improve task utilization and the latter is on the resource domain targeting to improve processor utilization. In this paper, we unify these two objectives with a weighting scheme that allows to personalize the importance of the objectives. In this paper, we present a new genetic search framework for task scheduling problem by considering the new objective. The performance of our genetic algorithm is compared with the scheduling algorithms in the literature that consider the heterogeneous processors. The results of the synthetic benchmarks and task graphs that are extracted from well-known applications clearly show that our genetic algorithm-based framework outperforms the related work with respect to normalized cost values, for various task graph characteristics.