  The problem of scheduling with testing in the framework of explorable
uncertainty models environments where some preliminary action can influence the
duration of a task. In the model, each job has an unknown processing time that
can be revealed by running a test. Alternatively, jobs may be run untested for
the duration of a given upper limit. Recently, D\"urr et al. [5] have studied
the setting where all testing times are of unit size and have given lower and
upper bounds for the objectives of minimizing the sum of completion times and
the makespan on a single machine. In this paper, we extend the problem to
non-uniform testing times and present the first competitive algorithms. The
general setting is motivated for example by online user surveys for market
prediction or querying centralized databases in distributed computing.
Introducing general testing times gives the problem a new flavor and requires
updated methods with new techniques in the analysis. We present constant
competitive ratios for the objective of minimizing the sum of completion times
in the deterministic case, both in the non-preemptive and preemptive setting.
For the preemptive setting, we additionally give a first lower bound. We also
present a randomized algorithm with improved competitive ratio. Furthermore, we
give tight competitive ratios for the objective of minimizing the makespan,
both in the deterministic and the randomized setting.
