Online scheduling of precedence constrained tasks

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.