The Library
An overview of some results for reordering buffers
Tools
Englert, Matthias (2012) An overview of some results for reordering buffers. Computer Science - Research and Developmen, Vol.27 (No.3). pp. 217-223. doi:10.1007/s00450-011-0180-2 ISSN 1865-2034.
Research output not available from this repository.
Request-a-Copy directly from author or use local Library Get it For Me service.
Official URL: http://dx.doi.org/10.1007/s00450-011-0180-2
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, Engineering and Medicine > Science > Mathematics | ||||
Journal or Publication Title: | Computer Science - Research and Developmen | ||||
Publisher: | Springer | ||||
ISSN: | 1865-2034 | ||||
Official Date: | 2012 | ||||
Dates: |
|
||||
Volume: | Vol.27 | ||||
Number: | No.3 | ||||
Page Range: | pp. 217-223 | ||||
DOI: | 10.1007/s00450-011-0180-2 | ||||
Status: | Peer Reviewed | ||||
Publication Status: | Published |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |