Probabilistic analysis of the minimum weighted flowtime scheduling problem

The minimum weighted flow time scheduling problem is studied from a probabilistic point of view. A probability distribution is specified over its problem instances, and the asymptotics of the optimal solution value are derived. Rewriting this value as a U-statistic perturbed by a small term allows us to use results from the well-established theory on these statistics. We derive a law of large numbers, a law of the iterated logarithm and a central limit theorem. As a byproduct we obtain a proof of asymptotic optimality almost surely of a greedy heuristic (the shortest weighted processing time first rule) for the solution of the NP-complete problem with more than one machine.