TY - JOUR

T1 - Complex-demand scheduling problem with application in smart grid

AU - Khonji, Majid

AU - Karapetyan, Areg

AU - Elbassioni, Khaled

AU - Chau, Sid Chi Kin

N1 - Publisher Copyright:
© 2018 Elsevier B.V.

PY - 2019/2/21

Y1 - 2019/2/21

N2 - We consider the problem of scheduling complex-valued demands over a discretized time horizon. Given a set of users, each user is associated with a set of demands representing different power consumption preferences. A demand is represented by a complex number, a time interval, and a utility value obtained if it is satisfied. At each time slot, the magnitude of the total selected demands should not exceed a given generation capacity. This naturally captures the supply constraints in alternating current (AC) electric systems. In this paper, we consider maximizing the aggregate user utility subject to power supply limits over a time horizon. We present approximation algorithms characterized by the maximum angle ϕ between any two complex-valued demands. More precisely, a PTAS is presented for the case ϕ∈[0,[Formula presented]], a bi-criteria FPTAS for ϕ∈[0,π-ε] for any polynomially small ε assuming the number of time slots in the discretized time horizon is a constant. Furthermore, if the number of time slots is part of the input, we present a reduction to the real-valued unsplittable flow problem on a path with only a constant approximation ratio. Finally, we present a practical greedy algorithm for the single time slot case with an approximation ratio of [Formula presented]cos[Formula presented] and a running time complexity of only O(NlogN), N standing for the aggregate number of user demands, which can be implemented efficiently in practice.

AB - We consider the problem of scheduling complex-valued demands over a discretized time horizon. Given a set of users, each user is associated with a set of demands representing different power consumption preferences. A demand is represented by a complex number, a time interval, and a utility value obtained if it is satisfied. At each time slot, the magnitude of the total selected demands should not exceed a given generation capacity. This naturally captures the supply constraints in alternating current (AC) electric systems. In this paper, we consider maximizing the aggregate user utility subject to power supply limits over a time horizon. We present approximation algorithms characterized by the maximum angle ϕ between any two complex-valued demands. More precisely, a PTAS is presented for the case ϕ∈[0,[Formula presented]], a bi-criteria FPTAS for ϕ∈[0,π-ε] for any polynomially small ε assuming the number of time slots in the discretized time horizon is a constant. Furthermore, if the number of time slots is part of the input, we present a reduction to the real-valued unsplittable flow problem on a path with only a constant approximation ratio. Finally, we present a practical greedy algorithm for the single time slot case with an approximation ratio of [Formula presented]cos[Formula presented] and a running time complexity of only O(NlogN), N standing for the aggregate number of user demands, which can be implemented efficiently in practice.

KW - Algorithms

KW - Knapsack

KW - Scheduling

KW - Smart grid

KW - Unsplittable flow

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

U2 - 10.1016/j.tcs.2018.08.023

DO - 10.1016/j.tcs.2018.08.023

M3 - Article

AN - SCOPUS:85053833841

SN - 0304-3975

VL - 761

SP - 34

EP - 50

JO - Theoretical Computer Science

JF - Theoretical Computer Science

ER -