Scheduling with variable-length calibrations: Two agreeable variants

Hua Chen, Lin Chen, Guochuan Zhang, Vincent Chau

Research output: Contribution to journalArticlepeer-review


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 fk and can keep the machine active for a length Tk. 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.

Original languageEnglish
Pages (from-to)94-105
Number of pages12
JournalTheoretical Computer Science
StatePublished - Sep 13 2021


  • Approximation algorithms
  • Calibration
  • Dynamic programming
  • Scheduling


Dive into the research topics of 'Scheduling with variable-length calibrations: Two agreeable variants'. Together they form a unique fingerprint.

Cite this