已知工件最大加工时间的平行机排序问题 (2008年)

研究了已知工件最大加工时间，目标为极小化最大机器负载的半在线平行机排序问题．证明了对于一般的 m(>6)台机器，任意的半在线算法的竞争比至少是(√33+3)/6．同时还设计了一个半在线算法，算法的竞争比为2-1/(m-1)．