Abstract:
Scheduling with testing is a recent online optimization problem in the framework of explorable uncertainty which models situations where some preliminary action can decrease the duration of tasks. The problem is motivated by real-world applications including production planning, market demand predictions, distributed computing, and medical diagnoses. A given number of jobs with uncertain processing times has to be assigned to a set of given machines. Jobs can be run in one of two possible configurations: Running a job tested reveals the previously unknown processing time, and the job can then be executed on some machine. Running the job untested takes a predetermined amount of time which is always at least as large the job’s actual processing time. The difficulty of the scheduling with testing problem lies in balancing the uncertain but possibly beneficial investment into the test and the fallback strategy of running the job untested with a fixed duration.
We study the problem on a single machine as well as on multiple identical machines and examine the objectives of minimizing the makespan and the total completion time of the
schedule. We also differentiate between non-preemptive, test-preemptive, and preemptive settings for both objectives. We provide several new, theoretical algorithms and lower bounds for the problem and study their performance based on the concept of competitive analysis. For this, we utilize testing schemes based on job parameters, pairwise examination of contributions to the completion time of jobs, and elaborate sorting procedures. We also adapt and extend well-known algorithms from the literature, like List Scheduling and Round Robin, to our problem.
For the makespan objective, we prove optimal algorithms and lower bounds on a single machine, both for the deterministic and the randomized case. On multiple machines, we present several algorithms with constant competitive ratios for the non-preemptive setting, which are complemented by a lower bound with constant value. In addition, we give an algorithm and a lower bound which apply to both test-preemptive and preemptive settings and are optimal if the number of machines approaches infinity. We also consider an extension of the problem to sequential online arrivals of jobs, for which we provide improved lower bounds. For the sum of completion times, we examine constant-competitive algorithms for the test-preemptive and the preemptive setting on one machine and show that such a result cannot exist in the nonpreemptive variant. Additionally, we present a lower bound for the preemptive setting as well as an improved result for randomized algorithms.