带复合信息的三台平行机半在线排序问题

摘要

本文讨论在已知加工工件总长度(sum)以及机器带一个缓冲区(buffer)两个复合信息下的同型平行机半在线排序问题.Dosa和He [1]研究了当机器数m=2时的情形,设计出竞争比为5/4的最优半在线算法.本文将其情况推广到三台机器,给出竞争比为4/3的半在线算法,并得到一个11/9的问题下界.%This paper investigates a semi on-line scheduling problem on three identical machines with combined partial information. We assume that the total processing time of all the jobs has been known in advance and a buffer is available. When the number of machines is m = 2, Dosa and He[1] present an algorithm with a competitive ratio of 5/4 and it has been the best possible. In this paper the author generalizes this problem by considering three identical machines. Firstly, an algorithm with a competitive ratio of 4/3 is proposed,then a lower bound of 11/9 is derived.