Online interval scheduling
Richard Lipton · 1994
We introduce the online interval scheduling problem, in which a set of intervals of the positive real line is presented to a scheduling algorithm in order of start time. Upon seeing each interval, the algorithm must decide whether or not to "schedule " it. Overlapping intervals may not be scheduled together. We give a strongly 2-competitive algorithm for the case in which intervals must be one of two lengths, either length 1 or length k AE 1. For the general case in which intervals may have arbitrary lengths, \\Delta, the ratio of longest to shortest interval, is the important parameter. We give an algorithm with competitive factor O((log \\Delta) 1+ffl ), and show that no O(log \\Delta)- competitive algorithm can exist. Our algorithm need not know the ratio \\Delta in advance. 1 Introduction In the field of on-line scheduling, an algorithm must typically schedule a number of jobs, or tasks, without knowing how long each task will take to complete (e.g., [2]). Recently, however, a new...