2015
Optimal Algorithms and a PTAS for Cost-Aware Scheduling
Publication
Publication
Presented at the
International Symposium on Mathematical Foundations of Computer Science
We consider a natural generalization of classical scheduling
problems in which using a time unit for processing a job causes some
time-dependent cost which must be paid in addition to the standard
scheduling cost. We study the scheduling objectives of minimizing the
makespan and the sum of (weighted) completion times. It is not dicult
to derive a polynomial-time algorithm for preemptive scheduling to minimize
the makespan on unrelated machines. The problem of minimizing
the total (weighted) completion time is considerably harder, even on a
single machine. We present a polynomial-time algorithm that computes
for any given sequence of jobs an optimal schedule, i.e., the optimal set of
time-slots to be used for scheduling jobs according to the given sequence.
This result is based on dynamic programming using a subtle analysis
of the structure of optimal solutions and a potential function argument.
With this algorithm, we solve the unweighted problem optimally in polynomial
time. Furthermore, we argue that there is a (4+")-approximation
algorithm for the strongly NP-hard problem with individual job weights.
For this weighted version, we also give a PTAS based on a dual scheduling
approach introduced for scheduling on a machine of varying speed.
Additional Metadata | |
---|---|
doi.org/10.1007/978-3-662-48054-0-18 | |
International Symposium on Mathematical Foundations of Computer Science | |
Organisation | Evolutionary Intelligence |
Chen, L., Megow, N., Rischke, R., Stougie, L., & Verschae, J. (2015). Optimal Algorithms and a PTAS for Cost-Aware Scheduling. In Proceedings of International Symposium on Mathematical Foundations of Computer Science 2015 (MFCS 40) (pp. 211–222). doi:10.1007/978-3-662-48054-0-18 |