具有服务等级的平行机在线排序问题研究

In this project, we mainly study the online hierarchical service scheduling problems on parallel machines. Firstly, we study online hierarchical scheduling problem for load balancing on uniform machines; Secondly, we consider online hierarchical scheduling problem on uniform machines to minimize makespan; Finally, we discuss online hierarchical scheduling problem on identical machines with release dates. For these problems, we design effective online algorithms respectively, which can provide more efficient service strategy for managers.

本项目主要研究具有服务等级的平行机在线排序问题。首先，研究具有服务等级的同类机在线机器负载平衡问题；其次，考虑目标为最小化最大完工时间的具有服务等级的同类机在线排序问题；最后，讨论具有服务等级的同型机按时在线排序问题。对这些问题，分别设计有效的在线算法，从而可以为管理者提供更有效的生产服务策略。

排序问题是运筹学与组合优化领域内的一类重要问题，对排序理论的研究具有重要的理论意义和广阔的实际应用前景。本项目主要研究具有服务等级的在线排序及其相关问题。首先，我们考虑了具有服务等级的两台同型机实时在线排序问题，给出了竞争比为7/4的在线算法。其次，我们研究了工件带有拒绝费用的三台同类机在线排序问题，提出了具有参数竞争比的在线算法。最后，我们讨论了工件带有拒绝费用的m台同型机在线排序问题并设计了在线算法，该算法的竞争比也为参数竞争比。