Calibration scheduling with time slot cost

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

1 Scopus Citations
View graph of relations


  • Kai Wang

Related Research Unit(s)


Original languageEnglish
Pages (from-to)1-14
Journal / PublicationTheoretical Computer Science
Online published30 Mar 2020
Publication statusPublished - 12 Jun 2020


We study the scheduling problem with calibrations and time slot costs. In this problem, the machine has to be calibrated to run a job and such a calibration only remains valid for a fixed time period of length T, after which it must be recalibrated in order to execute jobs. On the other hand, a certain cost will be incurred when the machine executes a job and such a cost is determined by the time slot that is occupied by the job in the schedule. We consider jobs with release times, deadlines and identical processing times. The objective is to schedule the jobs on a single machine and minimize the total cost while calibrating the machine at most K times. We investigate the structure of the optimal schedule and based on that we propose dynamic programs for different scenarios of the problem. At last, for another variant of the problem without the consideration of machine calibration, a greedy algorithm is proposed, which is based on matroid theory.

Research Area(s)

  • Calibration, Dynamic programming, Optimal algorithm, Scheduling

Citation Format(s)