Multiprocessor scheduling with testing: improved online algorithms and numerical experiments

We investigate scheduling with testing in the multiprocessor environment. Scheduling with testing, disallowing job preemption, is a variant recently proposed by Dürr et al. and Albers et al. to model many real-life applications where the scheduler decides to either execute a job for a likely overestimated length of time, or test the job to obtain its exact processing time, followed by executing the job for the exact length of time on the same machine. We present an online algorithm with competitive ratio 2.8681, improving the previous best known guarantee of 2.9514; when every test operation takes one unit of time, we present an online algorithm with competitive ratio approaching 2.5276, improving the previous best known guarantee of 2.8081. Compared to the prior work, the novel design ideas in our algorithm for the general testing case are to set up multiple thresholds for job testing decision-making and to use multiple sorting/selection criteria to determine the job processing order. We also propose a way to construct a benchmark dataset from the one for the classic multiprocessor scheduling problem, and on this benchmark dataset we demonstrate the empirical performance of our algorithms against the prior algorithms.