On the Asymptotic Optimality of the SPT Rule for the Flow Shop Average Completion Time Problem

Cathy H. Xia (), George J. Shanthikumar () and Peter W. Glynn ()
Additional contact information
Cathy H. Xia: IBM Thomas J. Watson Research Center, PO Box 704, Yorktown Heights, New York 10598
George J. Shanthikumar: Department of IEOR and the Walter A. Haas School of Business, University of California at Berkeley, Berkeley, California 94720
Peter W. Glynn: Department of EES & OR, Stanford University, Stanford, California 94305

Operations Research, 2000, vol. 48, issue 4, 615-622

Abstract: Consider a flow shop with M machines in series, through which a set of jobs are to be processed. All jobs have the same routing, and they have to be processed in the same order on each of the machines. The objective is to determine such an order of the jobs, often referred to as a permutation schedule, so as to minimize the total completion time of all jobs on the final machine. We show that when the processing times are statistically exchangeable across machines and independent across jobs, the Shortest ProcessingTime first (SPT) scheduling rule, based on the total service requirement of each job on all M machines, is asymptotically optimal as the total number of jobs goes to infinity. This extends a recent result of Kaminsky and Simchi-Levi (1996), in which a crucial assumption is that the processing times on all M machines for all jobs must be i.i.d.. Our work provides an alternative proof using martingales, which can also be carried out directly to show the asymptotic optimality of the weighted SPT rule for the Flow Shop Weighted Completion Time Problem.

Keywords: Asymptotically optimal scheduling: flow shop average completion time problem; Flow shop scheduling: average completion time; asymptotic optimality; Tandem queueing: asymptotic optimality of SPT (search for similar items in EconPapers)
Date: 2000
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (7)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.48.4.615.12423 (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:48:y:2000:i:4:p:615-622

Access Statistics for this article

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