TY - JOUR

T1 - Optimal algorithms for scheduling under time-of-use tariffs

AU - Chen, Lin

AU - Megow, Nicole

AU - Rischke, Roman

AU - Stougie, Leen

AU - Verschae, José

N1 - Funding Information:
Open Access funding enabled and organized by Projekt DEAL. This research was supported by the German Science Foundation (DFG) under contract ME 3825/1 and by Netherlands Organisation for Scientific Research (NWO) Gravitation Programme Networks 024.002.003.
Publisher Copyright:
© 2021, The Author(s).

PY - 2021/9

Y1 - 2021/9

N2 - We consider a natural generalization of classical scheduling problems to a setting in which using a time unit for processing a job causes some time-dependent cost, the time-of-use tariff, which must be paid in addition to the standard scheduling cost. We focus on preemptive single-machine scheduling and two classical scheduling cost functions, the sum of (weighted) completion times and the maximum completion time, that is, the makespan. While these problems are easy to solve in the classical scheduling setting, they are considerably more complex when time-of-use tariffs must be considered. We contribute optimal polynomial-time algorithms and best possible approximation algorithms. For the problem of minimizing the total (weighted) completion time 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 preemptively 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. For the more general problem, in which jobs may have individual weights, we develop a polynomial-time approximation scheme (PTAS) based on a dual scheduling approach introduced for scheduling on a machine of varying speed. As the weighted problem is strongly NP-hard, our PTAS is the best possible approximation we can hope for. For preemptive scheduling to minimize the makespan, we show that there is a comparably simple optimal algorithm with polynomial running time. This is true even in a certain generalized model with unrelated machines.

AB - We consider a natural generalization of classical scheduling problems to a setting in which using a time unit for processing a job causes some time-dependent cost, the time-of-use tariff, which must be paid in addition to the standard scheduling cost. We focus on preemptive single-machine scheduling and two classical scheduling cost functions, the sum of (weighted) completion times and the maximum completion time, that is, the makespan. While these problems are easy to solve in the classical scheduling setting, they are considerably more complex when time-of-use tariffs must be considered. We contribute optimal polynomial-time algorithms and best possible approximation algorithms. For the problem of minimizing the total (weighted) completion time 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 preemptively 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. For the more general problem, in which jobs may have individual weights, we develop a polynomial-time approximation scheme (PTAS) based on a dual scheduling approach introduced for scheduling on a machine of varying speed. As the weighted problem is strongly NP-hard, our PTAS is the best possible approximation we can hope for. For preemptive scheduling to minimize the makespan, we show that there is a comparably simple optimal algorithm with polynomial running time. This is true even in a certain generalized model with unrelated machines.

KW - Dynamic programming

KW - Makespan

KW - Polynomial-time approximation scheme (PTAS)

KW - Scheduling

KW - Time-of-use tariffs

KW - Total weighted completion time

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

U2 - 10.1007/s10479-021-04059-3

DO - 10.1007/s10479-021-04059-3

M3 - Article

AN - SCOPUS:85103875505

VL - 304

SP - 85

EP - 107

JO - Annals of Operations Research

JF - Annals of Operations Research

SN - 0254-5330

IS - 1-2

ER -