ALCOMFT-TR-03-93

Harald Räcke, Christian Sohler and Matthias Westermann
Online Scheduling for Sorting Buffers
Paderborn. Work package 4. November 2003.

Abstract: In this paper, we introduce the online scheduling problem for sorting buffers and present deterministic scheduling strategies for this problem. We are given a service station and a sorting buffer. An input sequence of items which are only characterized by a specific attribute has to be processed by the service station which benefits from consecutive items with the same attribute value. The sorting buffer which is a random access buffer with storage capacity for k items can be used to rearrange the input sequence. The goal is to minimize the cost of the service station, i.e., the number of maximal subsequences in its sequence of items containing only items with the same attribute value. This problem is motivated by many applications in computer science and economics.

We analyze our strategies in a competitive model in which the cost of the online strategies are compared with the cost of an optimal offline strategy. First, we show that several standard strategies are unsuitable for sorting buffers. In detail, we prove an Omega(\sqrt{k}) lower bound on the competitive ratio for the First In First Out (FIFO) and Least Recently Used (LRU) strategy and an Omega(k) lower bound on the competitive ratio for the Largest Color First (LCF) strategy. Our main result is the deterministic \bw strategy which achieves a competitive ratio of O(log² k). We believe that the \bw strategy is well suited for the application in practice because the strategy is simple and has a provably good performance.

Postscript file: ALCOMFT-TR-03-93.ps.gz (63 kb).