三台等级机器上带重排的半在线问题

Semi-online algorithms for hierarchical schedulingon three machines with reassignment

研究了3台机上带2种等级的重排问题,当所有工件都被分配之后,在等级约束下,可以重排一台机器上的最后一个工件,目标是最小化最大完工时间。3台机上带2种等级分为2种情形:第1种是有1台机器的等级为1,另2台机器的等级为2;第2种是2台机器的等级为1,另1台机器的等级为2。针对第1种情形给出了一个竞争比下界为3/2,并提出了一个竞争比至多为5/3的在线算法;针对第2种情形给出了一个竞争比下界为3/2,并提出了一个竞争比至多为12/7的在线算法。

This paper studies the rearrangement problem on three machines with two hierarchies.Under the constraints of hierarchy,after all jobs have been assigned,the last job on arbitrary machine can be rearranged,and the objective is to minimize the maximum machine load.There are two cases on three machines with two hierarchies.Case 1:When one machine s hierarchy is 1 and the other two machines hierarchy is 2,a low bound of competitive ratio 3/2 is given and an online algorithm with the competitive ratio of at most 5/3 is proposed.Case 2:When one machine's hierarchy s hierarchy is 2 and the other two machines hierarchy is 1,a low bound of competitive ratio 3/2 is given and an online algorithm with the competitive ratio of at most 12/7 is proposed.