Treffer: Randomized algorithms for fully online multiprocessor scheduling with testing.

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 arrives with an upper bound on the processing time and a testing operation of length ; one can choose to execute for time, or to test for time to obtain the exact processing time followed by immediately executing the job for 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 -expected-competitive randomized algorithm as a non-uniform probability distribution over arbitrarily many deterministic algorithms, where is the Golden ratio. When there are only two machines, we show that our randomized algorithm based on two deterministic algorithms is already -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. [ABSTRACT FROM AUTHOR]

Copyright of Annals of Operations Research is the property of Springer Nature and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)