TY - GEN

T1 - Optimal algorithms and a PTAS for cost-aware scheduling

AU - Chen, Lin

AU - Megow, Nicole

AU - Rischke, Roman

AU - Stougie, Leen

AU - Verschae, José

N1 - Publisher Copyright:
© Springer-Verlag Berlin Heidelberg 2015.
Copyright:
Copyright 2015 Elsevier B.V., All rights reserved.

PY - 2015

Y1 - 2015

N2 - 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 difficult 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.

AB - 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 difficult 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.

UR - http://www.scopus.com/inward/record.url?scp=84944563577&partnerID=8YFLogxK

U2 - 10.1007/978-3-662-48054-0_18

DO - 10.1007/978-3-662-48054-0_18

M3 - Conference contribution

AN - SCOPUS:84944563577

SN - 9783662480533

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 211

EP - 222

BT - Mathematical Foundations of Computer Science 2015 - 40th International Symposium, MFCS 2015, Proceedings

A2 - Italiano, Giuseppe F.

A2 - Pighizzini, Giovanni

A2 - Sannella, Donald T.

PB - Springer-Verlag

Y2 - 24 August 2015 through 28 August 2015

ER -