Note on scheduling intervals on-line

Note on scheduling intervals on-line

0.00 Avg rating0 Votes
Article ID: iaor1997863
Country: Netherlands
Volume: 58
Issue: 1
Start Page Number: 13
End Page Number: 17
Publication Date: Mar 1995
Journal: Discrete Applied Mathematics
Authors: ,
Keywords: graphs, optimization
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 algoirthm is proved by showing that it perfroms 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.

Reviews

Required fields are marked *. Your email address will not be published.