摘要
我们将探讨一种称为实时吞吐量最大化问题的实时调度问题的推广。输入为一系列作业，包括其释放时间、截止时间和处理时间。我们假设作业在其释放时间之前或同时被宣布。在每个时间步，算法必须基于迄今为止的信息决定是否调度一个作业。目标是最大化在截止时间之前完成的作业的处理时间总和，这通常称为实时吞吐量，带有比例权重。
我们通过定义一个(t)-提前通知的概念来扩展这个问题，该概念衡量每个作业相对于其处理时间的提前通知程度。我们证明存在一类参数为某个值(\tau \in [1,\infty))的算法(\tau-\textsc{Persist})。如果输入序列具有(t)-提前通知，则(\tau-\textsc{Persist})的竞争比为(\frac{\tau - 1}{\tau^2 + \tau - 1})。特别地，我们证明，对于任何(t \leq \frac{1}{2})，存在一个算法可以实现(\frac{t-t^2}{1+t-t^2})-竞争性；而对于任何(t \geq \frac{1}{2})，存在一个算法可以实现(\frac{1}{5})-竞争性。我们还给出了任何依赖于输入序列具有(t)-提前通知的算法的上界。我们证明，无论给出多少提前通知，任何算法的竞争比最多为(\frac{t}{2t+1})。特别地，无论提前通知的程度如何，没有算法可以达到(\frac{1}{2})-竞争性。
博主点评： 该研究深入探讨了实时调度中的提前通知机制，揭示了不同通知时间对调度竞争力的影响，提供了有价值的理论指导，为实际调度算法的设计提供了新的视角与思路。尤其是对于实时系统的优化调度，具有重要的参考价值。