<p>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.</p>

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Optimal Competitive Analysis for Fractional Hierarchical Scheduling on Related Machines

  • Tao Li,
  • Zhao-Hui Liu,
  • Wei Yu

摘要

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.