Volltext-Downloads (blau) und Frontdoor-Views (grau)

Calibration scheduling with time slot cost

  • 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.

Export metadata

Additional Services

Search Google Scholar


Document Type:Article
Author:Kai WangORCiD
Center:Center for Advanced Studies in Management (CASiM)
Parent Title (English):Theoretical computer science
Issue:12 June 2020
Year of Completion:2020
First Page:1
Last Page:14
Tag:Calibration; Dynamic programming; Optimal algorithm; Scheduling
Content Focus:Academic Audience
Peer Reviewed:Yes
Rankings:SJR Ranking / Q2
Licence (German):License LogoUrheberrechtlich gesch├╝tzt