Weighted Throughput Maximization with Calibrations

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)

  • Vincent Chau
  • Shengzhong Feng
  • Yinling Wang
  • Guochuan Zhang
  • Yong Zhang

Related Research Unit(s)

Detail(s)

Original languageEnglish
Title of host publicationAlgorithms and Data Structures
Subtitle of host publication16th International Symposium, WADS 2019, Proceedings
EditorsZachary Friggstad, Jörg-Rüdiger Sack, Mohammad R. Salavatipour
PublisherSpringer
Pages311-324
ISBN (Electronic)978-3-030-24766-9
ISBN (Print)978-3-030-24765-2
Publication statusPublished - Aug 2019

Publication series

NameLecture Notes in Computer Science (including subseries Theoretical Computer Science and General Issues)
PublisherSpringer
Volume11646
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Title16th International Algorithms and Data Structures Symposium (WADS 2019)
PlaceCanada
CityEdmonton
Period5 - 7 August 2019

Abstract

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.

Bibliographic Note

Full text of this publication does not contain sufficient affiliation information. With consent from the author(s) concerned, the Research Unit(s) information for this record is based on the existing academic department affiliation of the author(s).

Citation Format(s)

Weighted Throughput Maximization with Calibrations. / Chau, Vincent; Feng, Shengzhong; Li, Minming; Wang, Yinling; Zhang, Guochuan; Zhang, Yong.

Algorithms and Data Structures: 16th International Symposium, WADS 2019, Proceedings. ed. / Zachary Friggstad; Jörg-Rüdiger Sack; Mohammad R. Salavatipour. Springer, 2019. p. 311-324 (Lecture Notes in Computer Science (including subseries Theoretical Computer Science and General Issues); Vol. 11646).

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