Zhejiang Daxue xuebao. Lixue ban (Nov 2005)

Semi-online scheduling on two identical processors with two types of partial information(预知两种信息的两台并行处理器半在线调度)

  • LULu(卢璐),
  • TANZhi-yi(谈之奕),
  • HEYong(何勇)

DOI
Journal volume & issue
Vol. 32, no. 6
pp. 638 – 643

Abstract

Read online

在调度理论中，问题常常被分为“在线”和“离线”两类，但在实际生产生活中，情况经常介于两者之间，即预先知道任务的部分信息，人们希望通过这些附加的部分信息改进算法的性能，此类问题即为“半在线”问题.文章讨论了经典并行处理器调度的两个半在线问题，目标为极大化处理器最早完工时间.对已知所有任务总加工时间和最大任务加工时间的半在线问题，给出了竞争比为4/5的最优半在线算法；对已知所有任务总加工时间，并且任务按加工时间非增顺序到达的半在线问题，给出了竞争比为8/9的最优半在线算法.从结果可以看出，预知两种信息比只知道一种信息的情况能更有效地解决问题.

Keywords