Minimizing the cost of batch calibrations

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journal

View graph of relations

Author(s)

Related Research Unit(s)

Detail(s)

Original languageEnglish
Pages (from-to)55-64
Journal / PublicationTheoretical Computer Science
Volume828–829
Online published4 May 2020
Publication statusOnline published - 4 May 2020

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, i.e., the cost function is denoted as f(x) where x is the number of calibrations in the batch. 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 program to solve the case with an arbitrary cost function. Then, we propose several faster approximation algorithms for different cost functions: an optimal algorithm when f(x)=b, a 3-approximation algorithm when f(x)=x and a (m+b)/(b+1)-approximation algorithm when (x)=x+b. The running time of these algorithms are O(n2).

Research Area(s)

  • Approximation, Calibration, Dynamic programming, Scheduling

Citation Format(s)

Minimizing the cost of batch calibrations. / Chau, Vincent; Li, Minming; Wang, Elaine Yinling; Zhang, Ruilong; Zhao, Yingchao.

In: Theoretical Computer Science, Vol. 828–829, 06.08.2020, p. 55-64.

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journal