A note on sorting buffrs offline

H.L. Chan, N. Megow, R.A. Sitters, R. van Stee

Research output: Contribution to JournalArticleAcademicpeer-review

Abstract

We consider the offline sorting buffer problem. The input is a sequence of items of different types. All items must be processed one by one by a server. The server is equipped with a random-access buffer of limited capacity which can be used to rearrange items. The problem is to design a scheduling strategy that decides upon the order in which items from the buffer are sent to the server. Each type change incurs unit cost, and thus, the objective is to minimize the total number of type changes for serving the entire sequence. This problem is motivated by various applications in manufacturing processes and computer science, and it has attracted significant attention in the last few years. The main focus has been on online competitive algorithms. Surprisingly little is known on the basic offline problem. In this paper, we show that the sorting buffer problem with uniform cost is NP-hard and, thus, close one of the most fundamental questions for the offline problem. On the positive side, we give an O(1)-approximation algorithm when the scheduler is given a buffer only slightly larger than double the original size. We also sketch a fast dynamic programming algorithm for the special case of buffer size 2. © 2011 Elsevier B.V. All rights reserved.
Original languageEnglish
Pages (from-to)11-18
JournalTheoretical Computer Science
Volume423
DOIs
Publication statusPublished - 2012

Fingerprint

Sorting
Buffer
Servers
Server
Approximation algorithms
Dynamic programming
Computer science
Costs
Scheduling
Random Access
Scheduler
Dynamic Programming
Approximation Algorithms
Computer Science
NP-complete problem
Manufacturing
Entire
Minimise
Unit

Cite this

Chan, H.L. ; Megow, N. ; Sitters, R.A. ; van Stee, R. / A note on sorting buffrs offline. In: Theoretical Computer Science. 2012 ; Vol. 423. pp. 11-18.
@article{aad05e8eb792409ba2785f11659b2d7a,
title = "A note on sorting buffrs offline",
abstract = "We consider the offline sorting buffer problem. The input is a sequence of items of different types. All items must be processed one by one by a server. The server is equipped with a random-access buffer of limited capacity which can be used to rearrange items. The problem is to design a scheduling strategy that decides upon the order in which items from the buffer are sent to the server. Each type change incurs unit cost, and thus, the objective is to minimize the total number of type changes for serving the entire sequence. This problem is motivated by various applications in manufacturing processes and computer science, and it has attracted significant attention in the last few years. The main focus has been on online competitive algorithms. Surprisingly little is known on the basic offline problem. In this paper, we show that the sorting buffer problem with uniform cost is NP-hard and, thus, close one of the most fundamental questions for the offline problem. On the positive side, we give an O(1)-approximation algorithm when the scheduler is given a buffer only slightly larger than double the original size. We also sketch a fast dynamic programming algorithm for the special case of buffer size 2. {\circledC} 2011 Elsevier B.V. All rights reserved.",
author = "H.L. Chan and N. Megow and R.A. Sitters and {van Stee}, R.",
year = "2012",
doi = "10.1016/j.tcs.2011.12.077",
language = "English",
volume = "423",
pages = "11--18",
journal = "Theoretical Computer Science",
issn = "0304-3975",
publisher = "Elsevier",

}

A note on sorting buffrs offline. / Chan, H.L.; Megow, N.; Sitters, R.A.; van Stee, R.

In: Theoretical Computer Science, Vol. 423, 2012, p. 11-18.

Research output: Contribution to JournalArticleAcademicpeer-review

TY - JOUR

T1 - A note on sorting buffrs offline

AU - Chan, H.L.

AU - Megow, N.

AU - Sitters, R.A.

AU - van Stee, R.

PY - 2012

Y1 - 2012

N2 - We consider the offline sorting buffer problem. The input is a sequence of items of different types. All items must be processed one by one by a server. The server is equipped with a random-access buffer of limited capacity which can be used to rearrange items. The problem is to design a scheduling strategy that decides upon the order in which items from the buffer are sent to the server. Each type change incurs unit cost, and thus, the objective is to minimize the total number of type changes for serving the entire sequence. This problem is motivated by various applications in manufacturing processes and computer science, and it has attracted significant attention in the last few years. The main focus has been on online competitive algorithms. Surprisingly little is known on the basic offline problem. In this paper, we show that the sorting buffer problem with uniform cost is NP-hard and, thus, close one of the most fundamental questions for the offline problem. On the positive side, we give an O(1)-approximation algorithm when the scheduler is given a buffer only slightly larger than double the original size. We also sketch a fast dynamic programming algorithm for the special case of buffer size 2. © 2011 Elsevier B.V. All rights reserved.

AB - We consider the offline sorting buffer problem. The input is a sequence of items of different types. All items must be processed one by one by a server. The server is equipped with a random-access buffer of limited capacity which can be used to rearrange items. The problem is to design a scheduling strategy that decides upon the order in which items from the buffer are sent to the server. Each type change incurs unit cost, and thus, the objective is to minimize the total number of type changes for serving the entire sequence. This problem is motivated by various applications in manufacturing processes and computer science, and it has attracted significant attention in the last few years. The main focus has been on online competitive algorithms. Surprisingly little is known on the basic offline problem. In this paper, we show that the sorting buffer problem with uniform cost is NP-hard and, thus, close one of the most fundamental questions for the offline problem. On the positive side, we give an O(1)-approximation algorithm when the scheduler is given a buffer only slightly larger than double the original size. We also sketch a fast dynamic programming algorithm for the special case of buffer size 2. © 2011 Elsevier B.V. All rights reserved.

U2 - 10.1016/j.tcs.2011.12.077

DO - 10.1016/j.tcs.2011.12.077

M3 - Article

VL - 423

SP - 11

EP - 18

JO - Theoretical Computer Science

JF - Theoretical Computer Science

SN - 0304-3975

ER -