Abstract
In this paper we study the scheduling problem with calibration and time slot cost. In this model, the machine has to be calibrated to run a job and the calibration remains valid for a fixed time period of length T, after which it must be recalibrated before running more jobs. On the other hand, a certain cost will be incurred when the machine executes a job and the cost is determined by the time slots occupied by the job in the schedule. We work on the 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 propose dynamic programmings for different scenarios of this problem, as well as a greedy algorithm for the non-calibration version of this problem.
| Original language | English |
|---|---|
| Title of host publication | Algorithmic Aspects in Information and Management |
| Subtitle of host publication | Proceedings |
| Editors | Shaojie Tang, Ding-Zhu Du, David Woodruff, Sergiy Butenko |
| Publisher | Springer Nature Switzerland AG |
| Pages | 136-148 |
| ISBN (Electronic) | 9783030046187 |
| ISBN (Print) | 9783030046170 |
| DOIs | |
| Publication status | Published - Dec 2018 |
| Event | 12th International Conference on Algorithmic Aspects in Information and Management (AAIM 2018) - University of Texas , Dallas, United States Duration: 3 Dec 2018 → 4 Dec 2018 https://aaim2018.wordpress.com/ |
Publication series
| Name | Lecture Notes in Computer Science |
|---|---|
| Volume | LNCS 11343 |
| ISSN (Print) | 0302-9743 |
| ISSN (Electronic) | 1611-3349 |
Conference
| Conference | 12th International Conference on Algorithmic Aspects in Information and Management (AAIM 2018) |
|---|---|
| Abbreviated title | AAIM 2018 |
| Place | United States |
| City | Dallas |
| Period | 3/12/18 → 4/12/18 |
| Internet address |