Task scheduling with conflicting objectives

Abstract

The task scheduling problem for parallel and distributed systems was extensively studied in the literature. The outcome is a large set of heuristics, each of which generate an output schedule of the given application graph by preserving the task dependency constraints with the objective of minimizing the schedule length. We extend the general task scheduling model with multiple objectives of minimizing the schedule length (for task utilization) and minimizing the number of processors used (for resource utilization). These two objectives are both conflicting and complementary, which are combined into a single objective of cost minimization in our study. In this paper, the task scheduling problem for heterogeneous systems with the unified objective is formulated by a genetic search framework.