@inproceedings{d511b01f5535471b90b8968876b04edd,
title = "Brief announcement: Approximation of scheduling with calibrations on multiple machines",
abstract = "We study the scheduling problem with calibrations. In 2013, Bender et al. (SPAA'13) proposed a theoretical framework for the problem. Jobs of unit processing time with release times and deadlines are to be scheduled on parallel identical machines. The machines need to be calibrated to run jobs while a single calibration remains valid on a machine only for a time period of lengthT. The objective is to find a schedule that completes all jobs within their timing constraints and minimizes the total number of calibrations. In this paper, we aim to design an approximation algorithm to solve the problem. We propose a dynamic programming algorithm with polynomial running time when the number of machines is constant. In addition, we give a PTAS when the number of machines is input.",
keywords = "Approximation Algorithm, Calibration, PTAS, Scheduling",
author = "Lin Chen and Guohui Lin and Minming Li and Kai Wang",
note = "Publisher Copyright: {\textcopyright} 2019 Association for Computing Machinery.; 31st ACM Symposium on Parallelism in Algorithms and Architectures, SPAA 2019 ; Conference date: 22-06-2019 Through 24-06-2019",
year = "2019",
month = jun,
day = "17",
doi = "10.1145/3323165.3323173",
language = "English",
series = "Annual ACM Symposium on Parallelism in Algorithms and Architectures",
publisher = "Association for Computing Machinery",
pages = "237--239",
booktitle = "SPAA 2019 - Proceedings of the 31st ACM Symposium on Parallelism in Algorithms and Architectures",
}