  Bender et al. (SPAA 2013) have proposed a theoretical framework for testing
in contexts where safety mistakes must be avoided. Testing in such a context is
made by machines that need to be often calibrated. Given that calibration
costs, it is important to study policies minimizing the calibration cost while
performing all the necessary tests. We focus on the single-machine setting and
we extend the model proposed by Bender et al. by considering that the jobs have
arbitrary processing times and that the preemption of jobs is allowed. For this
case, we propose an optimal polynomial time algorithm. Then, we study the case
where there are several types of calibrations with different lengths and costs.
We first prove that the problem becomes NP-hard for arbitrary processing times
even when the preemption of the jobs is allowed. Finally, we focus on the case
of unit-time jobs and we show that a more general problem, where the
recalibration of the machine is not instantaneous but takes time, can be solved
in polynomial time.

Data Structures and Algorithms