Online stochastic reordering buffer scheduling

Hossein Esfandiari, Mohammadtaghi Hajiaghayi, Mohammad Reza Khani, Vahid Liaghat, Hamid Mahini, Harald Räcke

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

4 Scopus citations

Abstract

In this paper we consider online buffer scheduling problems 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. In the standard model initially introduced by Räcke, Sohler, and Westermann [31], the machine chooses an active color and processes items whose color matches that color until no item in the buffer has the active color (note that the buffer is refilled in each step). 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. Motivated by practical applications in real-world, we assume we have prior stochastic information about the input. In particular, we assume that the colors of items are drawn i.i.d. from a possibly unknown distribution, or more generally, the items are coming in a random order. In the random order setting, 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 Θ(loglogk) for both the standard and the block-operation models by Avigdor-Elgrabli and Rabani [8] and Adamaszek et al. [3]. 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. To the best of our knowledge this is the first result of this type which relates an algorithm for the standard model to an algorithm for the block-operation model. Last but not least, we show in the uniform distribution setting, in which the probabilities of appearances of all colors are the same, a simple greedy algorithm is the best online algorithm in both models.

Original languageEnglish
Title of host publicationAutomata, Languages, and Programming - 41st International Colloquium, ICALP 2014, Proceedings
PublisherSpringer Verlag
Pages465-476
Number of pages12
EditionPART 1
ISBN (Print)9783662439470
DOIs
StatePublished - 2014
Event41st International Colloquium on Automata, Languages, and Programming, ICALP 2014 - Copenhagen, Denmark
Duration: 8 Jul 201411 Jul 2014

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
NumberPART 1
Volume8572 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference41st International Colloquium on Automata, Languages, and Programming, ICALP 2014
Country/TerritoryDenmark
CityCopenhagen
Period8/07/1411/07/14

Fingerprint

Dive into the research topics of 'Online stochastic reordering buffer scheduling'. Together they form a unique fingerprint.

Cite this