关键词: 排序, 服务等级, 3台机器, 半在线算法, 竞争比

Abstract: This paper studies a semi-online hierarchical scheduling problem on three identical machines. In the problem, there is only one machine with hierarchy 1 and two machines with hierarchy 2, and the goal is to minimize the makespan. When the total size of low-hierarchy is known, an online algorithm with the competitive ratio of 5/3 and the lower bound of 3/2 is given. When the total size of high-hierarchy is known, an online algorithm with the competitive ratio of 9/5 and the lower bound of 3/2 is given. When the total size of each hierarchy is known, an online algorithm with the competitive ratio of 3/2 and the lower bound of 4/3 is given. When the total size of jobs is known, a best possible online algorithm with the competitive ratio of 3/2 is given.

Key words: scheduling, grade of service, three machines, semi-online algorithm, competitive ratio