Name
Abstract | ||
|---|---|---|
The recently proposed Integrated Stockpile Evaluation (ISE) problem extends a classic offline scheduling problem where n jobs, each with arrival times and deadlines, must be scheduled nonpreemptively on m machines. The additional constraint in the ISE problem is that a machine may only be used if it has been calibrated recently. The goal is to minimize the number of calibrations necessary to complete all the jobs before their deadlines. This paper presents a good polynomial-time approximation algorithm for the ISE problem general case where each job may have a different processing time. (Prior work was restricted to unit processing times.) The ISE problem generalizes a classic interval-scheduling problem where the goal is to minimize the number of machines. We show constructively that the other direction is also true, i.e., that the interval-scheduling bounds are also achievable. Specifically, suppose we have a black-box interval scheduling algorithm that finds an s-speed α m-machine solution to the interval scheduling problem. Then our ISE algorithm finds an O(α-approximation for number of calibrations using O(α m) machines with s-speed augmentation. |
Year | DOI | Venue |
|---|---|---|
2015 | 10.1145/2755573.2755605 | ACM Symposium on Parallelism in Algorithms and Architectures |
Keywords | Field | DocType |
Integrated Stockpile Evaluation,approximation algorithms,calibration,resource allocation,scheduling | Approximation algorithm,Stockpile,Mathematical optimization,Job shop scheduling,Computer science,Scheduling (computing),Interval scheduling,Parallel computing,Resource allocation,Calibration | Conference |
Citations | PageRank | References |
4 | 0.60 | 10 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Jeremy T. Fineman | 1 | 587 | 36.10 |
| Brendan Sheridan | 2 | 4 | 0.93 |