<p>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.</p>

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

An update on the asymptotic optimality of the longest processing time heuristic

  • Anne Benoit,
  • Louis-Claude Canon,
  • Redouane Elghazi,
  • Pierre-Cyrille Héam

摘要

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.