Preemptive scheduling with finite capacity input buffers

Nicholas Hall, Marc Posner and Chris Potts

Annals of Operations Research, 1997, vol. 70, issue 0, 399-413

Abstract: In many scheduling problems, an arriving job is stored in an input buffer until it starts to be processed. Also, it may be necessary to hold a partially completed preempted job in an input buffer until processing of this job resumes. In the scheduling literature, most problems have been studied using the implicit assumption that the buffer has infinite capacity. We study preemptive single machine scheduling problems where the buffer capacity is finite. In this scheduling environment, jobs may be lost either because of insufficient input buffer capacity, or because due date requirements cannot be met. We examine problems where the objective is to minimize the weighted or unweighted number of lost jobs. Various assumptions about the generality of the data are examined. We present a complexity classification for various problems, either by deriving an efficient algorithm, or by proving that such an algorithm is unlikely to exist. Copyright Kluwer Academic Publishers 1997

Keywords: Preemptive single machine scheduling; finite input buffers; polynomial time algorithm; NP-complete (search for similar items in EconPapers)
Date: 1997
References: Add references at CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://hdl.handle.net/10.1023/A:1018990625142 (text/html)
Access to full text is restricted to subscribers.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:annopr:v:70:y:1997:i:0:p:399-413:10.1023/a:1018990625142

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10479

DOI: 10.1023/A:1018990625142

Access Statistics for this article

Annals of Operations Research is currently edited by Endre Boros

More articles in Annals of Operations Research from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().