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 -