Note on scheduling intervals on-line


Faigle, Ulrich and Nawijn, Willem M. (1995) Note on scheduling intervals on-line. Discrete applied mathematics, 58 (1). pp. 13-17. ISSN 0166-218X

open access
Abstract:An optimal on-line algorithm is presented for the following optimization problem, which constitutes the special case of the k-track assignment problem with identical time windows. Intervals arrive at times ti and demand service time equal to their length. An interval is considered lost if it is not assigned to one of k identical service stations immediately or if its service is interrupted. Minimizing the losses amounts to coloring a maximal set of intervals in the associated interval graph properly with at most k colors. Optimality of the on-line algorithm is proved by showing that it performs as well as the optimal greedy k-coloring algorithm due to Faigle and Nawijn and, independently, to Carlisle and Lloyd for the same problem under full a priori information.
Item Type:Article
Copyright:© 1995 Elsevier Science
Electrical Engineering, Mathematics and Computer Science (EEMCS)
Research Group:
Link to this item:
Official URL:
Export this item as:BibTeX
HTML Citation
Reference Manager


Repository Staff Only: item control page

Metis ID: 140734