Scheduling Many Types of Calibrations

Machines usually require maintenance after a fixed period. We need to perform a calibration before using the machine again. Such an operation requires a non-negligible cost. Thus finding a schedule minimizing the total cost of calibrations is of great importance. This paper studies the following scheduling problem. We have a single machine, n jobs where each job j is characterized by its release time r:j, deadline d:j, and processing time p:j. Moreover, there are K types of calibrations, i.e., when the machine performs a calibration of type (Formula Presented) instantaneously, it can maintain calibrated for a fixed length T:k with a corresponding cost f:k. Jobs can only be processed when the machine is in the calibrated state. Our goal is to find a feasible schedule that minimizes the total cost of calibrations. We consider two classes of models: the costs of the calibrations are arbitrary, and the costs of the calibrations are equal to their length. For the first model, we propose a pseudo-polynomial time algorithm and a (Formula Presented)-approximation algorithm when jobs have agreeable deadlines (later release time implies a later deadline). For the second model, we give a 2-approximation algorithm.