TY - JOUR

T1 - Probabilistic analysis of the minimum weighted flowtime scheduling problem

AU - Marchetti Spaccamela, A.

AU - Rhee, W.S.

AU - Stougie, L.

AU - van de Geer, S.A.

N1 - 0761.90063

PY - 1992

Y1 - 1992

N2 - 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

AB - 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

U2 - 10.1016/0167-6377(92)90034-Z

DO - 10.1016/0167-6377(92)90034-Z

M3 - Article

SN - 0167-6377

VL - 11

SP - 67

EP - 71

JO - Operations Research Letters

JF - Operations Research Letters

IS - 2

ER -