NOTE ON SCHEDULING INTERVALS ONLINE

An optimal on-line algorithm is presented for the following optimizati on problem, which constitutes the special case of the k-track assignme nt problem with identical time windows. Intervals arrive at times t(i) and demand service time equal to their length. An interval is conside red lost if it is not assigned to one of k identical service stations immediately or if its service is interrupted. Minimizing the losses am ounts to coloring a maximal set of intervals in the associated interva l graph properly with at most k colors. Optimality of the on-line algo rithm is proved by showing that it performs as well as the optimal gre edy k-coloring algorithm due to Faigle and Nawijn and, independently, to Carlisle and Lloyd for the same problem under full a priori informa tion.