Optimal Competitive Analysis for Fractional Hierarchical Scheduling on Related Machines
摘要
We investigate the online fractional hierarchical scheduling problem on related machines. In the problem, the jobs and machines have several different hierarchies, and a job can be processed on a machine if and only if its hierarchy is not below the hierarchy of the machine; furthermore, each job can be arbitrarily split among the machines available for it. The jobs arrive over list, and the objective is to determine the assignment scheme of the jobs so as to minimize the makespan. We first prove that for any configuration of machine speeds, the parametric optimal competitive ratio and algorithm for the problem can be obtained by solving a linear program, where the linear program only requires the parameters of machines, and hence can be solved offline before the jobs arrive. Then, we show that the overall optimal competitive ratio for the problem is equal to the number e.