Note on scheduling intervals on-line

Share/Save/Bookmark

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
[img]
Preview
PDF
383kB
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
Link to this item:http://purl.utwente.nl/publications/30095
Official URL:http://dx.doi.org/10.1016/0166-218X(95)00112-5
Export this item as:BibTeX
EndNote
HTML Citation
Reference Manager

 

Repository Staff Only: item control page

Metis ID: 140734