The Asymptotic Optimality of the SPT Rule for the Flow Shop Mean Completion Time Problem

Philip Kaminsky () and David Simchi-Levi ()
Additional contact information
Philip Kaminsky: Industrial Engineering and Operations Research, University of California, Berkeley, California 94720
David Simchi-Levi: Massachusetts Institute of Technology, Cambridge, Massachusetts 02139-4307

Operations Research, 2001, vol. 49, issue 2, 293-304

Abstract: In the flow shop mean completion time problem, a set of jobs has to be processed on m -machines. Every machine has to process each one of the jobs, and every job has the same routing through the machines. The objective is to determine a sequence of the jobs on the machines so as to minimize the sum of the completion times of all jobs on the final machine. In this paper, we prove the asymptotic optimality of the Shortest Processing Time algorithm for any continuous, independent, and identically distributed job processing times.

Keywords: Production/scheduling: multiple machine sequencing; Flow shop weighted completion time problem; shortest processing time dispatch rule; Analysis of algorithms: probabilistic analysis (search for similar items in EconPapers)
Date: 2001
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.49.2.293.13536 (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:49:y:2001:i:2:p:293-304

Access Statistics for this article

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