TY - GEN
T1 - Scheduling Many Types of Calibrations
AU - Chen, Hua
AU - Chau, Vincent
AU - Chen, Lin
AU - Zhang, Guochuan
N1 - Funding Information:
Hua Chen and Guochuan Zhang are supported by NSFC (No. 11531014). Vincent Chau is supported by the CAS President’s International Fellowship Initiative no 2020FYT0002, 2018PT0004.
Publisher Copyright:
© 2020, Springer Nature Switzerland AG.
PY - 2020
Y1 - 2020
N2 - 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.
AB - 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.
KW - Approximation algorithms
KW - Calibration
KW - Scheduling
UR - http://www.scopus.com/inward/record.url?scp=85089719115&partnerID=8YFLogxK
U2 - 10.1007/978-3-030-57602-8_26
DO - 10.1007/978-3-030-57602-8_26
M3 - Conference contribution
AN - SCOPUS:85089719115
SN - 9783030576011
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 286
EP - 297
BT - Algorithmic Aspects in Information and Management - 14th International Conference, AAIM 2020, Proceedings
A2 - Zhang, Zhao
A2 - Li, Wei
A2 - Du, Ding-Zhu
PB - Springer
Y2 - 10 August 2020 through 12 August 2020
ER -