Decomposition Algorithms for Single-Machine Sequencing with Precedence Relations and Deferral Costs

Jeffrey B. Sidney
Additional contact information
Jeffrey B. Sidney: University of British Columbia, Vancouver, British Columbia

Operations Research, 1975, vol. 23, issue 2, 283-298

Abstract: A one-machine deterministic job-shop sequencing problem is considered. Associated with each job is its processing time and linear deferral cost. In addition, the jobs are related by a general precedence relation. The objective is to order the jobs so as to minimize the sum of the deferral costs, subject to the constraint that the ordering must be consistent with the precedence relation. A decomposition algorithm is presented, and it is proved that a permutation is optimal if and only if it can be generated by this algorithm. Four special network structures are then considered, and specializations of the general algorithm are presented.

Date: 1975
References: Add references at CitEc
Citations: View citations in EconPapers (23)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.23.2.283 (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:23:y:1975:i:2:p:283-298

Access Statistics for this article

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