Approximation results in parallel machines stochastic scheduling

The paper considers scheduling a batch of jobs with stochastic processing times on parallel machines. It derives various new formulae for the expected flowtime and weighted flowtime under general scheduling rules. Smith’s Rule, which orders job starts by decreasing ratio of weight to expected processing time provides a natural heuristic for this problem. The paper obtains a bound on the worst case difference between the expected weighted flowtime under Smith’s Rule and under an optimal policy. For a wide class of processing time distributions, this bound is of order O(1) and does not increase with the number of jobs.