Minimizing the Cost of Batch Calibrations

Research output: Chapters, Conference Papers, Creative and Literary WorksRGC 32 - Refereed conference paper (with host publication)peer-review

1 Scopus Citations
View graph of relations

Author(s)

Related Research Unit(s)

Detail(s)

Original languageEnglish
Title of host publicationComputing and Combinatorics - 25th International Conference, COCOON 2019, Proceedings
EditorsDing-Zhu Du, Zhenhua Duan, Cong Tian
PublisherSpringer, Cham
Pages78-89
ISBN (electronic)978-3-030-26176-4
ISBN (print)978-3-030-26175-7
Publication statusPublished - Jul 2019

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume11653 LNCS
ISSN (Print)0302-9743
ISSN (electronic)1611-3349

Conference

Title25th International Computing and Combinatorics Conference, COCOON 2019
PlaceChina
CityXi'an
Period29 - 31 July 2019

Abstract

We study the scheduling problem with calibrations. We are given a set of n jobs that need to be scheduled on a set of m machines. However, a machine can schedule jobs only if a calibration has been performed beforehand and the machine is considered as valid during a fixed time period of T, after which it must be recalibrated before running more jobs. In this paper, we investigate the batch calibrations, calibrations occur in batch and at the same moment. It is then not possible to perform any calibrations during a period of T. We consider different cost function depending on the number of machines we calibrate at a given time. Moreover, jobs have release time, deadline and unit processing time. The objective is to schedule all jobs with the minimum cost of calibrations. We give a dynamic programming to solve the case with arbitrary cost function. Then, we propose several faster approximation algorithm for different cost function.

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)

Minimizing the Cost of Batch Calibrations. / Chau, Vincent; Li, Minming; Wang, Yinling et al.
Computing and Combinatorics - 25th International Conference, COCOON 2019, Proceedings. ed. / Ding-Zhu Du; Zhenhua Duan; Cong Tian. Springer, Cham, 2019. p. 78-89 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 11653 LNCS).

Research output: Chapters, Conference Papers, Creative and Literary WorksRGC 32 - Refereed conference paper (with host publication)peer-review