预知两种信息带准备时间的两台同型机半在线排序

作者：李蒙; 孙秋媚; 封汉颖

来源：数学的实践与认识, 2011, (20): 184-187.

• 同型机排序
• 半在线
• 近似算法
• 竞争比 identical machine scheduling
• semi-online
• approximation algorithm
• competitive ratio

研究了P2,r_j/decr,opt/Cmax问题,即预知工件大小非增排列decr和最优目标值opt的两台同型机的带准备时间的半在线问题,并给出了竞争比为7/6的半在线算法.

• 单位
  中国人民解放军陆军工程大学