TY - GEN
T1 - Weighted throughput maximization with calibrations
AU - Chau, Vincent
AU - Feng, Shengzhong
AU - Li, Minming
AU - Wang, Yinling
AU - Zhang, Guochuan
AU - Zhang, Yong
N1 - Publisher Copyright:
© Springer Nature Switzerland AG 2019.
PY - 2019
Y1 - 2019
N2 - The scheduling problem with calibrations was introduced by Bender et al. (SPAA 2013). In sensitive applications, machines need to be periodically calibrated to ensure that they run correctly. Formally, we are given a set of n jobs with release times, deadlines and weights. Calibrating a machine requires a cost and remains calibrated for a period of T time units, after which it must be recalibrated before it can resume running jobs. Moreover, we are given a budget of K calibrations. The objective is to schedule a set of jobs such that the total weight is maximized on m identical machines with at most K calibrations. In this paper, we present a (1/3) -approximation polynomial time algorithm when jobs have unit processing time. For the arbitrary processing time case, we give a ((1 - ε)/3) -approximation pseudo-polynomial time algorithm and a ((1 - ε)/18) -approximation polynomial time algorithm.
AB - The scheduling problem with calibrations was introduced by Bender et al. (SPAA 2013). In sensitive applications, machines need to be periodically calibrated to ensure that they run correctly. Formally, we are given a set of n jobs with release times, deadlines and weights. Calibrating a machine requires a cost and remains calibrated for a period of T time units, after which it must be recalibrated before it can resume running jobs. Moreover, we are given a budget of K calibrations. The objective is to schedule a set of jobs such that the total weight is maximized on m identical machines with at most K calibrations. In this paper, we present a (1/3) -approximation polynomial time algorithm when jobs have unit processing time. For the arbitrary processing time case, we give a ((1 - ε)/3) -approximation pseudo-polynomial time algorithm and a ((1 - ε)/18) -approximation polynomial time algorithm.
UR - https://www.scopus.com/pages/publications/85070649747
U2 - 10.1007/978-3-030-24766-9_23
DO - 10.1007/978-3-030-24766-9_23
M3 - 会议稿件
AN - SCOPUS:85070649747
SN - 9783030247652
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 311
EP - 324
BT - Algorithms and Data Structures - 16th International Symposium, WADS 2019, Proceedings
A2 - Friggstad, Zachary
A2 - Salavatipour, Mohammad R.
A2 - Sack, Jörg-Rüdiger
PB - Springer Verlag
T2 - 16th International Symposium on Algorithms and Data Structures, WADS 2019
Y2 - 5 August 2019 through 7 August 2019
ER -