An Optimal Fractional Algorithm For Online Hierarchical Scheduling On Uniform Machines

In this paper,we study the parallel machine scheduling problem under a grade of service(GoS)provision where the jobs and the machines are both graded.A job can be processed by a machine if and only if its grade is not lower than that of the machine.We discuss the online version of fractional scheduling,where each job can be arbitrarily split,and the obtained fragments can be processed on different machines simultaneously.The objective is to minimize the makespan.We present an optimal algorithm for the problem with four hierarchies in five cases.