TY - BOOK
T1 - The asymptotic optimality of the LPT rule
AU - Frenk, J.B.G.
AU - Rinnooy Kan, A.H.G.
PY - 1985
Y1 - 1985
N2 - For the problem of minimizing makes pan on parallel machines of different speed, the behaviour of list scheduling rules is subjected to a probabilistic analysis under the assumption that the processing requirements of the jobs are independent, identically distributed nonnegative random variables. Under mild conditions on the probability distribution, we obtain strong asymptotic optimality results for arbitrary list scheduling and even stronger ones for the LPT (Longest Processing Time) rule, in which the jobs are assigned to the machines in order of nonincreasing processing requirements.
Keywords: scheduling, parallel machines, list scheduling, LPT rule, probabilistic analysis, asymptotic optimality.
AB - For the problem of minimizing makes pan on parallel machines of different speed, the behaviour of list scheduling rules is subjected to a probabilistic analysis under the assumption that the processing requirements of the jobs are independent, identically distributed nonnegative random variables. Under mild conditions on the probability distribution, we obtain strong asymptotic optimality results for arbitrary list scheduling and even stronger ones for the LPT (Longest Processing Time) rule, in which the jobs are assigned to the machines in order of nonincreasing processing requirements.
Keywords: scheduling, parallel machines, list scheduling, LPT rule, probabilistic analysis, asymptotic optimality.
M3 - Report
T3 - Memorandum COSOR
BT - The asymptotic optimality of the LPT rule
PB - Technische Hogeschool Eindhoven
CY - Eindhoven
ER -