2017
Approximability of average completion time scheduling on unrelated machines
Publication
Publication
Mathematical Programming , Volume 161 - Issue 1 p. 135- 158
We show that minimizing the average job completion time on unrelated machines is (Formula presented.)-hard if preemption of jobs is allowed. This provides one of the last missing pieces in the complexity classification of machine scheduling with (weighted) sum of completion times objective. The proof is based on a mixed integer linear program. This means that verification of the reduction is partly done by an ILP-solver. This gives a concise proof which is easy to verify. In addition, we give a deterministic 1.698-approximation algorithm for the weighted version of the problem. The improvement is made by modifying and combining known algorithms and by the use of new lower bounds. These results improve on the known (Formula presented.)-hardness and 2-approximability.
| Additional Metadata | |
|---|---|
| doi.org/10.1007/s10107-016-1004-8 | |
| Mathematical Programming | |
|
Sitters, R. (2017). Approximability of average completion time scheduling on unrelated machines. Mathematical Programming, 161(1), 135–158. doi:10.1007/s10107-016-1004-8 |
|
