Scheduling with variable-length calibrations: Two agreeable variants

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 + ε ) -approximation algorithm. Moreover, if the largest job processing time is no more than any calibration length, it admits a ( 2 + ε ) -approximation algorithm. As for agreeable calibrations, where the cost of each calibration is proportional to its length, a 2-approximation algorithm is presented.

Authors

• Hua Chen
• Lin Chen University of Science and Technology of China
• Guochuan Zhang
• Vincent Chau Southeast University

Keywords

• Scheduling
• Calibration
• Approximation algorithms
• Dynamic programming