Randomized algorithms for fully online multiprocessor scheduling with testing
share
We contribute the first randomized algorithm that is an integration of arbitrarily many deterministic algorithms for the fully online multiprocessor scheduling with testing problem. When there are only two machines, we show that with 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 multiprocessor scheduling with testing, in which the jobs arrive in sequence so that the testing decision needs to be made at the job arrival as well as the designated machine. We first use Yao's principle to prove lower bounds of 1.6682 and 1.6522 on the expected competitive ratio for any randomized algorithm at the presence of at least three machines and only two machines, respectively, and then propose an expected (√(φ + 3) + 1) (≈ 3.1490)-competitive randomized algorithm as a non-uniform probability distribution over arbitrarily many deterministic algorithms, where φ = √(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 expected 3 φ + 3 √(13 - 7φ)/4 (≈ 2.1839)-competitive, while proving a lower bound of 2.2117 on the competitive ratio for any deterministic algorithm.
READ FULL TEXT