Online parallel machines scheduling with two hierarchies

This paper investigates an online hierarchical scheduling problem on m parallel identical machines. Each job, as well as each machine, has a hierarchy associated with it. A job can be scheduled on a machine only when its hierarchy is no higher than that of the machine. The objective is to minimize the makespan. In addition, we assume that there are only two hierarchies, and k machines have a higher hierarchy which can schedule all jobs. We present an online algorithm with a competitive ratio of for any k and m. The performance for some pairs of k and m is further improved by another algorithm. Lower bounds for various pairs of k and m are also presented.