Online scheduling of precedence constrained tasks

Yumei Huo, Joseph Y.T. Leung

Research output: Contribution to journalArticlepeer-review

6 Scopus citations

Abstract

A fundamental problem in scheduling theory is that of scheduling a set of n tasks, with precedence constraints, on m ≥ 1 identical and parallel processors so as to minimize the makespan (schedule length). In the past, research has focused on the setting whereby all tasks are available for processing at the beginning (i.e., at time t = 0). In this article we consider the situation where tasks, along with their precedence constraints, are released at different times, and the scheduler has to make scheduling decisions without knowledge of future releases. In other words, the scheduler has to schedule tasks in an online fashion. We consider both preemptive and nonpreemptive schedules. We show that optimal online algorithms exist for some cases, while for others it is impossible to have one. Our results give a sharp boundary delineating the possible and the impossible cases.

Original languageEnglish (US)
Pages (from-to)743-762
Number of pages20
JournalSIAM Journal on Computing
Volume34
Issue number3
DOIs
StatePublished - Jun 30 2005

All Science Journal Classification (ASJC) codes

  • Computer Science(all)
  • Mathematics(all)

Keywords

  • Intrees
  • Online and offline scheduling
  • Outtrees
  • Parallel and identical processors
  • Precedence constraints
  • Preemptive and nonpreemptive scheduling
  • Schedule length

Fingerprint Dive into the research topics of 'Online scheduling of precedence constrained tasks'. Together they form a unique fingerprint.

Cite this