Brief Announcement : Approximation of Scheduling with Calibrations on Multiple Machines

Research output: Chapters, Conference Papers, Creative and Literary Works (RGC: 12, 32, 41, 45)32_Refereed conference paper (with ISBN/ISSN)Not applicablepeer-review

View graph of relations

Author(s)

Detail(s)

Original languageEnglish
Title of host publicationProceeding SPAA'19 The 31st ACM Symposium on Parallelism in Algorithms and Architectures
PublisherAssociation for Computing Machinery
Pages237-239
ISBN (Print)9781450361842
Publication statusPublished - Jun 2019

Publication series

NameAnnual ACM Symposium on Parallelism in Algorithms and Architectures

Conference

Title31st ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 2019)
PlaceUnited States
CityPhoenix
Period22 - 24 June 2019

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.

Research Area(s)

  • Approximation Algorithm, Scheduling, Calibration, PTAS

Citation Format(s)

Brief Announcement : Approximation of Scheduling with Calibrations on Multiple Machines. / Chen, Lin; Lin, Guohui; Li, Minming; Wang, Kai.

Proceeding SPAA'19 The 31st ACM Symposium on Parallelism in Algorithms and Architectures. Association for Computing Machinery, 2019. p. 237-239 (Annual ACM Symposium on Parallelism in Algorithms and Architectures).

Research output: Chapters, Conference Papers, Creative and Literary Works (RGC: 12, 32, 41, 45)32_Refereed conference paper (with ISBN/ISSN)Not applicablepeer-review