Scheduling Many Types of Calibrations

Hua Chen, Vincent Chau, Lin Chen, Guochuan Zhang

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

1 Scopus citations

Abstract

Machines usually require maintenance after a fixed period. We need to perform a calibration before using the machine again. Such an operation requires a non-negligible cost. Thus finding a schedule minimizing the total cost of calibrations is of great importance. This paper studies the following scheduling problem. We have a single machine, n jobs where each job j is characterized by its release time r:j, deadline d:j, and processing time p:j. Moreover, there are K types of calibrations, i.e., when the machine performs a calibration of type (Formula Presented) instantaneously, it can maintain calibrated for a fixed length T:k with a corresponding cost f:k. Jobs can only be processed when the machine is in the calibrated state. Our goal is to find a feasible schedule that minimizes the total cost of calibrations. We consider two classes of models: the costs of the calibrations are arbitrary, and the costs of the calibrations are equal to their length. For the first model, we propose a pseudo-polynomial time algorithm and a (Formula Presented)-approximation algorithm when jobs have agreeable deadlines (later release time implies a later deadline). For the second model, we give a 2-approximation algorithm.

Original languageEnglish
Title of host publicationAlgorithmic Aspects in Information and Management - 14th International Conference, AAIM 2020, Proceedings
EditorsZhao Zhang, Wei Li, Ding-Zhu Du
PublisherSpringer
Pages286-297
Number of pages12
ISBN (Print)9783030576011
DOIs
StatePublished - 2020
Event14th International Conference on Algorithmic Aspects in Information and Management, AAIM 2020 - Jinhua, China
Duration: Aug 10 2020Aug 12 2020

Publication series

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

Conference

Conference14th International Conference on Algorithmic Aspects in Information and Management, AAIM 2020
Country/TerritoryChina
CityJinhua
Period08/10/2008/12/20

Keywords

  • Approximation algorithms
  • Calibration
  • Scheduling

Fingerprint

Dive into the research topics of 'Scheduling Many Types of Calibrations'. Together they form a unique fingerprint.

Cite this