Scheduling with Finite Capacity Input Buffers

Nicholas G. Hall, Marc E. Posner and Chris N. Potts
Additional contact information
Nicholas G. Hall: The Ohio State University, Columbus, Ohio
Marc E. Posner: The Ohio State University, Columbus, Ohio
Chris N. Potts: University of Southampton, Southampton, England

Operations Research, 1998, vol. 46, issue 3-supplement-3, S154-S159

Abstract: In many scheduling problems, a newly released job must be stored in an input buffer while it waits to begin processing. The lack of attention given to these buffers in the classical scheduling literature results from the implicit assumption that they have infinite capacity. In modern manufacturing environments, however, there are several important reasons for limiting buffer capacity. We study nonpreemptive single machine dynamic scheduling problems under the assumption that some jobs may be lost, either because of insufficient input buffer capacity, or because due dates cannot be met. The objective is to minimize the weighted or unweighted number of lost jobs. We study problems with zero, fixed or arbitrary buffer capacity, with unit or arbitrary processing times, and with unit or arbitrary buffer storage requirements. We present a complexity classification in which, for each problem, either an efficient algorithm is derived, or a proof is given that such an algorithm is unlikely to exist.

Keywords: Production/scheduling; scheduling with limited input storage capacity; Deterministic; single machine sequencing (search for similar items in EconPapers)
Date: 1998
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.46.3.S154 (application/pdf)

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:inm:oropre:v:46:y:1998:i:3-supplement-3:p:s154-s159

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().