Minimization of Time-Varying Costs in Single-Machine Scheduling

E. L. Lawler and B. D. Sivazlian
Additional contact information
E. L. Lawler: University of California, Berkeley, California
B. D. Sivazlian: University of Florida, Gainesville, Florida

Operations Research, 1978, vol. 26, issue 4, 563-569

Abstract: Suppose n jobs are to be processed consecutively by a single machine, without interruption and without idle time. Each job j has a known processing time p j and has associated with it a time-varying cost density function c j . The cost of processing job j in the time interval [ t − p j , t ] is C j ( t ) = ∫ t − p j t c j ( u ) du . We show that if the cost density functions of the jobs satisfy certain simple conditions, a sequence minimizing total cost is easily obtained. This result generalizes the well-known “ratio rule” of W. E. Smith for minimizing total weighted completion time and is applicable to problems involving discounted linear delay costs, discounted linear processing costs, discounted resetting and processing costs, and linear combinations of these costs. Moreover, we show that for such costs, sequences that are optimal subject to series parallel precedence constraints can be found in 0( n log n ) time.

Date: 1978
References: Add references at CitEc
Citations: View citations in EconPapers (3)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.26.4.563 (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:26:y:1978:i:4:p:563-569

Access Statistics for this article

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