Choosing the Job Sequence and Processing Times to Minimize Total Processing Plus Flow Cost on a Single Machine

R. G. Vickson
Additional contact information
R. G. Vickson: University of Waterloo, Ontario, Canada

Operations Research, 1980, vol. 28, issue 5, 1155-1167

Abstract: This paper treats the problem of minimizing the total weighted flow cost plus job-processing cost in a single machine sequencing problem for jobs having processing costs which are linear functions of processing times. The optimal job sequence and processing times are obtainable from the solution of an associated problem of optimal row and column selection in a symmetric matrix. Some sufficient conditions for expediting certain jobs are proved. In order to handle cases in which these conditions fail to complete the solution to the problem a heuristic algorithm with a provable performance bound is developed. The heuristic solutions are compared with optimal solutions obtained by branch and bound in numerous randomly generated problems and are found to be optimal in most cases.

Date: 1980
References: Add references at CitEc
Citations: View citations in EconPapers (35)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.28.5.1155 (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:28:y:1980:i:5:p:1155-1167

Access Statistics for this article

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