  Scheduling with testing falls under the umbrella of the research on
optimization with explorable uncertainty. In this model, each job has an upper
limit on its processing time that can be decreased to a lower limit (possibly
unknown) by some preliminary action (testing). Recently, D{\"{u}}rr et al.
\cite{DBLP:journals/algorithmica/DurrEMM20} has studied a setting where testing
a job takes a unit time, and the goal is to minimize total completion time or
makespan on a single machine. In this paper, we extend their problem to the
budget setting in which each test consumes a job-specific cost, and we require
that the total testing cost cannot exceed a given budget. We consider the
offline variant (the lower processing time is known) and the oblivious variant
(the lower processing time is unknown) and aim to minimize the total completion
time or makespan on a single machine.
  For the total completion time objective, we show NP-hardness and derive a
PTAS for the offline variant based on a novel LP rounding scheme. We give a
$(4+\epsilon)$-competitive algorithm for the oblivious variant based on a
framework inspired by the worst-case lower-bound instance. For the makespan
objective, we give an FPTAS for the offline variant and a
$(2+\epsilon)$-competitive algorithm for the oblivious variant. Our algorithms
for the oblivious variants under both objectives run in time
$O(poly(n/\epsilon))$. Lastly, we show that our results are essentially optimal
by providing matching lower bounds.
