TY - JOUR

T1 - Scheduling with variable-length calibrations

T2 - Two agreeable variants

AU - Chen, Hua

AU - Chen, Lin

AU - Zhang, Guochuan

AU - Chau, Vincent

N1 - Funding Information:
A preliminary version [1] of this paper appeared in Proceedings of the 14th International Conference on Algorithmic Applications in Management (AAIM), Springer, 2020, pp. 286–297. Hua Chen and Guochuan Zhang are supported by NSFC (No. 11771365 ). Vincent Chau is supported by the National Key Research and Development Program of China under grant No. 2019YFB2102200 , and by the Fundamental Research Funds for the Central Universities .
Publisher Copyright:
© 2021 Elsevier B.V.

PY - 2021/9/13

Y1 - 2021/9/13

N2 - 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.

AB - 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.

KW - Approximation algorithms

KW - Calibration

KW - Dynamic programming

KW - Scheduling

UR - http://www.scopus.com/inward/record.url?scp=85111618624&partnerID=8YFLogxK

U2 - 10.1016/j.tcs.2021.07.021

DO - 10.1016/j.tcs.2021.07.021

M3 - Article

AN - SCOPUS:85111618624

SN - 0304-3975

VL - 886

SP - 94

EP - 105

JO - Theoretical Computer Science

JF - Theoretical Computer Science

ER -