On the asymptotic optimality of the SPT rule for the flow shop average completion time problem

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 p rocessed in the same order on each of the machines. The objective is to det ermine such an order of the jobs, often referred to as a permutation schedu le, so as to minimize the total completion time of all jobs on the final ma chine. We show that when the processing times are statistically exchangeabl e across machines and independent across jobs, the Shortest Processing Time first (SPT) scheduling rule, based on the total service requirement of eac h job on all M machines, is asymptotically optimal as the total number of j obs goes to infinity. This extends a recent result of Kaminsky and Simchi-L evi (1996), in which a crucial assumption is that the processing times on a ll 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 th e asymptotic optimality of the weighted SPT rule for the Flow Shop Weighted Completion Time Problem.