Englert, Matthias. (2012) An overview of some results for reordering buffers. Computer Science - Research and Developmen, Vol.27 (No.3). pp. 217-223. ISSN 1865-2034

Full text not available from this repository.

Abstract

Lookahead is a classic concept in the theory of online scheduling. An online algorithm without lookahead has to process tasks as soon as they arrive and without any knowledge about future tasks. With lookahead, this strict assumption is relaxed. There are different variations on the exact type of information provided to the algorithm under lookahead but arguably the most common one is to assume that, at every point in time, the algorithm has knowledge of the attributes of the next k tasks to arrive. This assumption is justified by the fact that, in practice, tasks may not always strictly arrive one-by-one and therefore, a certain number of tasks are always waiting in a queue to be processed. In recent years, so-called reordering buffers have been studied as a sensible generalization of lookahead. The basic idea is that, in problem settings where the order in which the tasks are processed is not important, we can permit a scheduling algorithm to choose to process any task waiting in the queue. This stands in contrast to lookahead, where the algorithm has knowledge of all the tasks in the queue but still has to process them in the order they arrived. We discuss some of the results for reordering buffers for different scheduling problems.

Item Type:	Journal Article
Divisions:	Faculty of Science > Mathematics
Journal or Publication Title:	Computer Science - Research and Developmen
Publisher:	Springer
ISSN:	1865-2034
Date:	2012
Volume:	Vol.27
Number:	No.3
Page Range:	pp. 217-223
Identification Number:	10.1007/s00450-011-0180-2
Status:	Peer Reviewed
Publication Status:	Published
URI:	http://wrap.warwick.ac.uk/id/eprint/50258

Request changes to a record

Actions (login required)

View Item