Scheduling with Finite Capacity Output 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, S84-S97

Abstract: In many scheduling problems, a job that completes processing may need to be held in an output buffer until the customer is ready to accept delivery. Buffer capacity is usually assumed to be infinite.We study a number of the best known single machine scheduling problems, under several alternative assumptions about the capacity of the output buffer. Specifically, we allow the buffer capacity to be either zero, fixed, or specified as part of problem input. We also consider situations in which all jobs have the same storage requirement in the buffer, and others where the storage requirement may vary. Further, we consider generalizations where there is a time interval within which a customer accepts delivery without cost to the producer.A classification scheme for these problems is provided. For each problem considered, we provide either an efficient algorithm or a proof that such an algorithm is unlikely to exist. Our results provide a mapping of the computational complexity of these problems which parallels those that are available for classical scheduling problems with infinite buffer capacity.

Keywords: Production/scheduling; scheduling with limited output 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 (3)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.46.3.S84 (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:s84-s97

Access Statistics for this article

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