Online scheduling of precedence constrained tasks

Yumei Huo, Joseph Y.T. Leung

Research output: Contribution to journalArticlepeer-review

6 Scopus citations


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
Issue number3
StatePublished - 2005

All Science Journal Classification (ASJC) codes

  • General Computer Science
  • General Mathematics


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


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

Cite this