Online stochastic reordering buffer scheduling

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

Publikation: Beitrag in Buch/Bericht/KonferenzbandKonferenzbeitragBegutachtung

4 Zitate (Scopus)

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.

OriginalspracheEnglisch
TitelAutomata, Languages, and Programming - 41st International Colloquium, ICALP 2014, Proceedings
Herausgeber (Verlag)Springer Verlag
Seiten465-476
Seitenumfang12
AuflagePART 1
ISBN (Print)9783662439470
DOIs
PublikationsstatusVeröffentlicht - 2014
Veranstaltung41st International Colloquium on Automata, Languages, and Programming, ICALP 2014 - Copenhagen, Dänemark
Dauer: 8 Juli 201411 Juli 2014

Publikationsreihe

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
NummerPART 1
Band8572 LNCS
ISSN (Print)0302-9743
ISSN (elektronisch)1611-3349

Konferenz

Konferenz41st International Colloquium on Automata, Languages, and Programming, ICALP 2014
Land/GebietDänemark
OrtCopenhagen
Zeitraum8/07/1411/07/14

Fingerprint

Untersuchen Sie die Forschungsthemen von „Online stochastic reordering buffer scheduling“. Zusammen bilden sie einen einzigartigen Fingerprint.

Dieses zitieren