CATS-Apr-25-2014
Title[edit]
Online Stochastic Reordering Buffer Scheduling
Speaker[edit]
Hossein Esfandiari, University of Maryland
Abstract[edit]
In this work we consider online buffer scheduling problem in which an online stream of n items (jobs) with different colors (types) has to be processed by a machine with a buffer of size k. This problem has been considerd in two models, block-operation model and standard model. In the block-operation model, the machine chooses an active color and can--in each step--process all items of that color in the buffer. In the standard model, the machine process items whose color matches the active color until no items in the buffer have this color anymore (note that the buffer is refilled in each step).
Motivated by practical applications in real-world, we assume we have prior stochastic information about the input. In particular we know the colors of items are drawn i.i.d. from a possibly unknown distribution or more generally the items are coming in the random order setting in which an adversary determines the color of each item in advance, but then the items arrive in a random order in the input stream. To the best of our knowledge, this is the first work which considers the reordering buffer problem in stochastic settings. Our main result is demonstrating constant competitive online algorithms for both the standard model and the block operation model in the unknown distribution setting and more generally in the random order setting. This provides a major improvement of the competitiveness of algorithms in stochastic settings; the best competitive ratio in the adversarial setting is \Theta(log (log (k)) for both the standard and the block-operation models by Avigdor-elgrabli and Rabani and Adamaszek et al.
Along the way, we also show that in the random order setting designing competitive algorithms with the same competitive ratios (up to constant factors) in both the block operation model and the standard model are equivalent.
