论文标题
在两台分层机器上进行的在线和半对线进行安排，该计算机有一个共同的截止日期，以最大程度地提前工作
Online and semi-online scheduling on two hierarchical machines with a common due date to maximize the total early work
论文作者
论文摘要
在这项研究中，我们在两台分层机上调查了几个在线和半对线的调度问题，该机器有一个共同的截止日期，以最大程度地提高早期工作。对于纯在线案例，我们设计了一种最佳的在线算法，其竞争比率为$ \ sqrt 2 $。对于已知总处理时间的情况，我们提出了一种最佳的半联盟算法，其竞争比为$ \ frac {4} {3} $。此外，对于最大的处理时间的情况，如果最大的工作是较低的层次结构，则给出了$ \ frac {6} {5} $的最佳算法，如果最大的工作是最大的工作，则最大的工作是较低的层次。
In this study, we investigated several online and semi-online scheduling problems on two hierarchical machines with a common due date to maximize the total early work. For the pure online case, we designed an optimal online algorithm with a competitive ratio of $\sqrt 2$. For the case when the total processing time is known, we proposed an optimal semi-online algorithm with a competitive ratio of $\frac{4}{3}$. Additionally, for the cases when the largest processing time is known, we gave optimal algorithms with a competitive ratio of $\frac{6}{5}$ if the largest job is a lower hierarchy one, and of $\sqrt 5-1$ if the largest job is a higher hierarchy one, respectively.
