A Genetic Algorithm for Scheduling Splittable Tasks with Precedence Constraints

In many applications, the logic of the program can be described using a task graph, where the data dependencies and execution time of each task are described. These dependencies create precedence constraints among tasks, which are requirements that some tasks must be finished before some other tasks. Many efforts have been put into scheduling parallelizable tasks that synchronically use multiple cores. In some cases, the task can be chunked into smaller pieces and scheduled independently, allowing further flexible schedules. However, it is usually either assumed that such splitting has no overhead, or that precedence constraints are not present, or that the user has to provide the way of splitting. This paper addresses the problem where these factors are considered together, that is scheduling splittable tasks with precedence constraints, where splitting introduces an overhead and the splitting of tasks are determined by the algorithm. The objective is to minimize the makespan of the schedule. We first present a mixed-integer quadratic program (MIQP) formulation of the problem. Then, a genetic algorithm (GA) is devised and its performance is compared with the MIQP solutions. We show that the genetic algorithm can produce reasonably good schedules compared with MIQP output within a significantly shorter time, and it has the potential to handle large task graphs.