A Genetic Algorithm for Scheduling Splittable Tasks with Precedence Constraints

Research output: Chapter in Book/Conference proceedingConference contributionpeer-review

Abstract

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.

Original languageEnglish
Title of host publication2021 IEEE Congress on Evolutionary Computation, CEC 2021 - Proceedings
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages1808-1816
Number of pages9
ISBN (Electronic)9781728183923
DOIs
Publication statusPublished - 2021
Event2021 IEEE Congress on Evolutionary Computation, CEC 2021 - Virtual, Krakow, Poland
Duration: 28 Jun 20211 Jul 2021

Publication series

Name2021 IEEE Congress on Evolutionary Computation, CEC 2021 - Proceedings

Conference

Conference2021 IEEE Congress on Evolutionary Computation, CEC 2021
Country/TerritoryPoland
CityVirtual, Krakow
Period28/06/211/07/21

Keywords

  • Genetic algorithms
  • Mathematical programming
  • Optimization
  • Processor scheduling
  • Quadratic programming
  • Scheduling algorithms

ASJC Scopus subject areas

  • Modelling and Simulation
  • Computational Mathematics

Fingerprint

Dive into the research topics of 'A Genetic Algorithm for Scheduling Splittable Tasks with Precedence Constraints'. Together they form a unique fingerprint.

Cite this