This Article Full Text (PDF) References Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Citing Articles Citing Articles via HighWire Citing Articles via Google Scholar Google Scholar Articles by Xia, C. H. Articles by Glynn, P. W. Search for Related Content

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

IBM Thomas J. Watson Research Center, PO Box 704, Yorktown Heights, New York 10598
Department of IEOR and the Walter A. Haas School of Business, University of California at Berkeley, Berkeley, California 94720
Department of EES & OR, Stanford University, Stanford, California 94305
hhcx{at}watson.ibm.com
jgshant{at}ieor.berkeley.edu
glynn{at}leland.stanford.edu

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.

Subject classifications: Asymptotically optimal scheduling: flow shop average completion time problem; Flow shop scheduling: average completion time, asymptotic optimality; Tandem queueing: asymptotic optimality of SPT.
History: Received September 1997; revision received October 1998; revision received December 1998; accepted December 1998.

This article has been cited by other articles:

				M. C. Chou, H. Liu, M. Queyranne, and D. Simchi-Levi On the Asymptotic Optimality of a Simple On-Line Algorithm for the Stochastic Single-Machine Weighted Completion Time Problem and Its Extensions Operations Research, May 1, 2006; 54(3): 464 - 474. [Abstract] [PDF]