中文摘要：

研究具有等级约束的三台机在线排序问题．机器和工件的等级数均为1或2，工件只能在等级数不超过自身等级的机器上加工，且加工允许中断，目标是极小化最大工件完工时间．如果有两台机器等级为1，给出竞争比为3／2的在线算法，并证明算法是最好可能的；如果只有一台等级为1的机器，也给出竞争比为3／2的在线算法．

英文摘要：

We consider online scheduling on three machines with hierarchies. Each job, as well as each machine, has a hierarchy of either 1 or 2 associated with it. A job can be scheduled on a machine only when its hierarchy is no smaller than that of the machine. Preemption is allowed. The objective is to minimize the maximum completion time of jobs. If there are two machines of hierarchy 1, then we give an online algorithm with competitive ratio 3/2 and prove that it is best possible. If only one machine has a hierarchy of 1, then a 3/2-competitive algorithm is also provided.