@inproceedings{b7c84e36cb584945ac589d4f6223c27c,
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 length T. 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, Scheduling, Calibration, PTAS",
author = "Lin Chen and Guohui Lin and Minming Li and Kai Wang",
year = "2019",
month = jun,
doi = "10.1145/3323165.3323173",
language = "English",
isbn = "9781450361842",
series = "Annual ACM Symposium on Parallelism in Algorithms and Architectures",
publisher = "Association for Computing Machinery",
pages = "237--239",
booktitle = "Proceeding SPAA'19 The 31st ACM Symposium on Parallelism in Algorithms and Architectures",
address = "United States",
note = "31st ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 2019), SPAA 2019 ; Conference date: 22-06-2019 Through 24-06-2019",
}