Zhejiang Daxue xuebao. Lixue ban (Jan 2008)

Semi-online multiprocessor scheduling with the longest given processing time(已知工件最大加工时间的平行机排序问题)

  • WUYong(吴用),
  • HUANGYi-kun(黄宜坤),
  • YANGQi-fan(杨启帆)

DOI
Journal volume & issue
Vol. 35, no. 1
pp. 23 – 26

Abstract

Read online

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

Keywords