Scheduling with variable-length calibrations: Two agreeable variants

Abstract Machines usually require maintenance after running a fixed period. A calibration at a cost has to be performed during the process. Finding a feasible schedule minimizing the total cost of calibrations is of great importance. In this paper, we deal with a single machine scheduling model with K types of calibrations. A calibration of type k ∈ { 1 , … , K } can be made instantaneously at any time point, which incurs a cost f k and can keep the machine active for a length T k . Given a set of n jobs with release times, deadlines, and processing times, the goal is to minimize the total cost of calibrations by assigning all jobs in the calibrated state, where job preemption is allowed. We investigate two agreeable settings. Regarding agreeable jobs, later release times imply later deadlines. We establish a pseudo-polynomial time optimal algorithm and a ( 3 + e ) -approximation algorithm. Moreover, if the largest job processing time is no more than any calibration length, it admits a ( 2 + e ) -approximation algorithm. As for agreeable calibrations, where the cost of each calibration is proportional to its length, a 2-approximation algorithm is presented.