Name
Abstract | ||
|---|---|---|
We study the shared processor scheduling problem with a single shared processor to maximize total weighted overlap, where an overlap for a job is the amount of time it is processed on its private and shared processor in parallel. A polynomial-time optimization algorithm has been given for the problem with equal weights in the literature. This paper extends that result by showing an \(O(n \log n)\)-time optimization algorithm for a class of instances in which non-decreasing order of jobs with respect to processing times provides a non-increasing order with respect to weights—this instance generalizes the unweighted case of the problem. This algorithm also leads to a \(\frac{1}{2}\)-approximation algorithm for the general weighted problem. The complexity of the weighted problem remains open. |
Year | DOI | Venue |
|---|---|---|
2018 | 10.1007/s10951-018-0566-0 | J. Scheduling |
Keywords | DocType | Volume |
Divisible jobs, Scheduling, Shared processor | Journal | abs/1704.06361 |
Issue | ISSN | Citations |
6 | 1094-6136 | 0 |
PageRank | References | Authors |
0.34 | 0 | 2 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Dariusz Dereniowski | 1 | 178 | 26.76 |
| Wieslaw Kubiak | 2 | 540 | 62.61 |