An update on the asymptotic optimality of the longest processing time heuristic
摘要
When independent jobs are to be scheduled onto identical machines, the typical goal is to minimize the makespan. A simple and efficient heuristic consists in scheduling first the job with the longest processing time (LPT heuristic), and to plan its execution as soon as possible. While the performance of LPT has already been largely studied, in particular its asymptotic performance, we revisit results and propose a novel analysis for the case of jobs generated through uniform integer compositions. Also, we perform extensive simulations to compare and empirically assess the asymptotic performance of five classical heuristics, including LPT. The results show that the absolute error rapidly tends to zero for several distributions of job processing times, including distributions studied by theoretical models, and realistic distributions coming from benchmarks.