关键词: 等级, 重排, 竞争比, 半在线算法

Abstract: 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.

Key words: hierarchy, reassignment, competitive ratio, semi-online algorithm.