A Problem in Single-Machine Sequencing with Nonlinear Delay Costs

Peter B. Henderson and Kenneth Steiglitz
Additional contact information
Peter B. Henderson: State University of New York at Stony Brook
Kenneth Steiglitz: Princeton University

Management Science, 1976, vol. 22, issue 12, 1342-1350

Abstract: We examine a class of single-machine sequencing problems which originate from scheduling considerations for a single-server queueing system with nonlinear costs of delay. Associated with each request awaiting service (sequencing) are a known service time, a known arrival time, and a nondecreasing cost function which is identical for each request. Two sequencing problems are considered; a request incurs cost from its arrival time to the time when it (1) commences service or (2) completes service. Our objective is a sequence which minimizes the total incurred cost. Necessary conditions for the optimal sequencing of requests are given for convex nondecreasing and quadratic cost functions. These conditions and a new lower bound function are used in a branch-and-bound algorithm to obtain computational results.

Date: 1976
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/mnsc.22.12.1342 (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:ormnsc:v:22:y:1976:i:12:p:1342-1350

Access Statistics for this article

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