Randomized algorithms for fully online multiprocessor scheduling with testing

doi:10.1007/s10479-025-06804-4

Randomized algorithms for fully online multiprocessor scheduling with testing

2025-09-02

0

PRE

AI

陈光亭 (Guangting Chen) *

DOI：10.1007/s10479-025-06804-4

Original

Original request for help

Save

Abstract

En 中文

We contribute the first randomized algorithm that is an integration of arbitrarily many deterministic algorithms for the fully online multiprocessor scheduling with testing problem to minimize the makespan. When there are only two machines, we show that using two component algorithms its expected-competitive ratio is already strictly smaller than the best proven deterministic competitive ratio lower bound. Such algorithmic results are rarely seen in the literature. Multiprocessor scheduling is one of the first combinatorial optimization problems that have received numerous studies. Recently, several research groups examined its testing variant, in which each job $$J_j$$ arrives with an upper bound $$u_j$$ on the processing time and a testing operation of length $$t_j$$ ; one can choose to execute $$J_j$$ for $$u_j$$ time, or to test $$J_j$$ for $$t_j$$ time to obtain the exact processing time $$p_j$$ followed by immediately executing the job for $$p_j$$ time. Our target problem is the fully online version, in which the jobs arrive in sequence so that the testing decision needs to be made as well as the designated machine at or after a job arrives. We propose a $$(\sqrt{\varphi + 3} + 1) (\approx 3.1490)$$ -expected-competitive randomized algorithm as a non-uniform probability distribution over arbitrarily many deterministic algorithms, where $$\varphi = \frac{\sqrt{5} + 1}{2}$$ is the Golden ratio. When there are only two machines, we show that our randomized algorithm based on two deterministic algorithms is already $$\frac{3 \varphi + 3 \sqrt{13 - 7\varphi }}{4} (\approx 2.1839)$$ -expected-competitive. Besides, we use Yao’s principle to prove lower bounds of 1.5376 and 1.6105 on the expected-competitive ratio for any randomized algorithm at the presence of at least three and only two machines, respectively, and prove a lower bound of 2.2117 on the competitive ratio for any deterministic algorithm when there are only two machines.

Keywords:

Online multiprocessor scheduling

Scheduling with testing

Makespan

Randomized algorithm

Inapproximability

Randomized algorithms for fully online multiprocessor scheduling with testing

Abstract

Journal

Organization

Cited Papers