Turnpike Optimality of Smith’s Rule in parallel machines stochastic scheduling

Consider scheduling a batch of jobs with stochastic processing times on parallel machines, with minimization of expected weighted flowtime as objective. Smith’s Rule, which orders job starts by decreasing ratio of weight to expected processing time, provides a natural heuristic for this problem. In a previous paper an upper bound was found for the difference between the expected objective under Smith’s Rule and under the optimal strategy. In this paper an upper bound is found on the expected number of times that Smith’s Rule differs from the optimal decision. Under some mild and reasonable assumptions these bounds remain constant when the number of jobs increases. Hence, under these conditions Smith’s Rule is asymptotically optimal, and it has a Turnpike Optimality property, that is, Smith’s Rule is optimal most of the time.