带两个服务等级的三台机最优在线算法

研究了带服务等级约束的三台平行机在线排序问题.每台机器和每个工件的服务等级为1或者2,工件只能在等级不高于它的机器上加工,即等级为1的工件只能在等级为1的机器上加工,等级为2的工件可在所有机器上加工.每个工件的加工时间为一个单位,目标是极小化所有工件的总完工时间.考虑两种情形:当一台机器等级为1,两台机器等级为2时,给出了竞争比为17/14的最优在线算法;当两台机器等级为1,一台机器等级为2时,给出了竞争比为43/36的最优在线算法.

Optimal online algorithms for hierarchical scheduling on three parallel machines

This paper investigates an online hierarchical scheduling problem on three parallel identical machines. Each job has a unit processing time and a hierarchy 1 or 2. Each machine has also a hierarchy 1 or 2. The job with a hierarchy 1 can only be processed on the machine with hierarchy 1 and the job with a hierarchy 2 can be processed on any one of three machines. The goal is to minimize the total completion time of all jobs. For the case where one machine with hierarchy 1 and two machines with hierarchy 2, an optimal online algorithm with competitive ratio of 17/14 is presented. For the case where two machines with hierarchy 1 and one machine with hierarchy 2, an optimal online algorithm with competitive ratio of 43/36 is presented.