预知两种信息的两台并行处理器半在线调度

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

Semi-online scheduling on two identical processors with two types of partial information

In the scheduling theory, problems are often classified as on-line and off-line. But in practice, problems are often not really on-line and off-line but somehow in between. This means that, with respect to the on-line problem, some further information about tasks is available, which allows the improvement of the performance of the optimal on-line algorithms. Problems of this class are called semi-online. The classical multiprocessor scheduling to maximize the minimum machine completion time is considered. For the semi-online with known total processing time and largest processing time, an optimal semi-online algorithm with competitive ratio 4/5 is presented. For the semi- online with known total processing time and decreasing processing time, an optimal semi-online algorithm with competitive ratio 8/9 is presented. It can be concluded that two types of partial information are more useful than one.