Complex-demand scheduling problem with application in smart grid

• Published in: Theoretical computer science 2019-02, Vol.761, p.34-50
• Main Authors: Khonji, Majid, Karapetyan, Areg, Elbassioni, Khaled, Chau, Sid Chi-Kin
• Format: Article
• Language: English
• Subjects: Algorithms; Knapsack; Scheduling; Smart grid; Unsplittable flow
• ISSN: 0304-3975; 1879-2294
• DOI: 10.1016/j.tcs.2018.08.023

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,π2], 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 12cos⁡ϕ2 and a running time complexity of only O(Nlog⁡N), N standing for the aggregate number of user demands, which can be implemented efficiently in practice.