TY - GEN
T1 - Minimizing the Cost of Batch Calibrations
AU - Chau, Vincent
AU - Li, Minming
AU - Wang, Yinling
AU - Zhang, Ruilong
AU - Zhao, Yingchao
N1 - Full text of this publication does not contain sufficient affiliation information. With consent from the author(s) concerned, the Research Unit(s) information for this record is based on the existing academic department affiliation of the author(s).
PY - 2019/7
Y1 - 2019/7
N2 - We study the scheduling problem with calibrations. We are given a set of n jobs that need to be scheduled on a set of m machines. However, a machine can schedule jobs only if a calibration has been performed beforehand and the machine is considered as valid during a fixed time period of T, after which it must be recalibrated before running more jobs. In this paper, we investigate the batch calibrations, calibrations occur in batch and at the same moment. It is then not possible to perform any calibrations during a period of T. We consider different cost function depending on the number of machines we calibrate at a given time. Moreover, jobs have release time, deadline and unit processing time. The objective is to schedule all jobs with the minimum cost of calibrations. We give a dynamic programming to solve the case with arbitrary cost function. Then, we propose several faster approximation algorithm for different cost function.
AB - We study the scheduling problem with calibrations. We are given a set of n jobs that need to be scheduled on a set of m machines. However, a machine can schedule jobs only if a calibration has been performed beforehand and the machine is considered as valid during a fixed time period of T, after which it must be recalibrated before running more jobs. In this paper, we investigate the batch calibrations, calibrations occur in batch and at the same moment. It is then not possible to perform any calibrations during a period of T. We consider different cost function depending on the number of machines we calibrate at a given time. Moreover, jobs have release time, deadline and unit processing time. The objective is to schedule all jobs with the minimum cost of calibrations. We give a dynamic programming to solve the case with arbitrary cost function. Then, we propose several faster approximation algorithm for different cost function.
UR - http://www.scopus.com/inward/record.url?scp=85070188814&partnerID=8YFLogxK
UR - https://www.scopus.com/record/pubmetrics.uri?eid=2-s2.0-85070188814&origin=recordpage
U2 - 10.1007/978-3-030-26176-4_7
DO - 10.1007/978-3-030-26176-4_7
M3 - 32_Refereed conference paper (with ISBN/ISSN)
SN - 978-3-030-26175-7
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 78
EP - 89
BT - Computing and Combinatorics - 25th International Conference, COCOON 2019, Proceedings
A2 - Du, Ding-Zhu
A2 - Duan, Zhenhua
A2 - Tian, Cong
PB - Springer, Cham
T2 - 25th International Computing and Combinatorics Conference, COCOON 2019
Y2 - 29 July 2019 through 31 July 2019
ER -