Randomized algorithms for fully online multiprocessor scheduling with testing

Mingyang Gong

doi:10.1007/s10479-025-06804-4

2025-09-02

PRE

Mingyang Gong

Zhi‐Zhong Chen

陈

陈光亭 (Guangting Chen) *

Guohui Lin *

王

王路生 (Lusheng Wang)

DOI：10.1007/s10479-025-06804-4

原文链接

原文求助

摘要

En 中文

我们提出了第一个针对完全在线多处理器调度与测试问题的随机算法，该算法集成了任意多个确定性算法，旨在最小化完成时间。当机器数量仅为两台时，我们证明使用两个组件算法，其期望竞争比已经严格小于已证明的最佳确定性竞争比下界。此类算法结果在文献中极为罕见。多处理器调度是首批获得广泛研究的组合优化问题之一。近期，多个研究小组研究了其测试变种，在该变种中，每个作业 \(J_j\) 带有处理时间的上界 \(u_j\) 和测试操作长度 \(t_j\)；可以选择执行 \(J_j\) \(u_j\) 时间，或测试 \(J_j\) \(t_j\) 时间以获取精确处理时间 \(p_j\)，随后立即执行作业 \(p_j\) 时间。我们的目标问题是完全在线版本，作业按顺序到达，需要在作业到达时或之后同时做出测试决策及指定机器。我们提出一个 \((\sqrt{\varphi + 3} + 1) (\approx 3.1490)\) -期望竞争比的随机算法，作为对任意多个确定性算法的非均匀概率分布，其中 \(\varphi = \frac{\sqrt{5} + 1}{2}\) 为黄金比例。当机器数量仅为两台时，我们证明基于两个确定性算法的随机算法已经是 \(\frac{3 \varphi + 3 \sqrt{13 - 7\varphi }}{4} (\approx 2.1839)\) -期望竞争比。此外，我们使用Yao原理证明在至少三台机器和仅两台机器的情况下，任何随机算法的期望竞争比下界分别为1.5376和1.6105，并证明在仅两台机器时，任何确定性算法的竞争比下界为2.2117。

Keyword:

Online multiprocessor scheduling

Scheduling with testing

Makespan

Randomized algorithm

Inapproximability