Brief announcement: Approximation of scheduling with calibrations on multiple machines

Lin Chen, Guohui Lin, Minming Li, Kai Wang

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

2 Scopus citations

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.

Original languageEnglish
Title of host publicationSPAA 2019 - Proceedings of the 31st ACM Symposium on Parallelism in Algorithms and Architectures
PublisherAssociation for Computing Machinery
Pages237-239
Number of pages3
ISBN (Electronic)9781450361842
DOIs
StatePublished - Jun 17 2019
Event31st ACM Symposium on Parallelism in Algorithms and Architectures, SPAA 2019 - Phoenix, United States
Duration: Jun 22 2019Jun 24 2019

Publication series

NameAnnual ACM Symposium on Parallelism in Algorithms and Architectures

Conference

Conference31st ACM Symposium on Parallelism in Algorithms and Architectures, SPAA 2019
Country/TerritoryUnited States
CityPhoenix
Period06/22/1906/24/19

Keywords

  • Approximation Algorithm
  • Calibration
  • PTAS
  • Scheduling

Fingerprint

Dive into the research topics of 'Brief announcement: Approximation of scheduling with calibrations on multiple machines'. Together they form a unique fingerprint.

Cite this