On the asymptotic optimality of the SPT rule for the flow shop average completion time problem
成果类型：
Article
署名作者：
Xia, CH; Shanthikumar, JG; Glynn, PW
署名单位：
International Business Machines (IBM); IBM USA; University of California System; University of California Berkeley; University of California System; University of California Berkeley; Stanford University
刊物名称：
OPERATIONS RESEARCH
ISSN/ISSBN：
0030-364X
DOI：
10.1287/opre.48.4.615.12423
发表日期：
2000
页码：
615-622
关键词：
摘要：
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 Processing Time 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.