Easy knapsacks and the complexity of energy allocation problems in the smart grid



Karaboghossian, T and Zito, M
(2018) Easy knapsacks and the complexity of energy allocation problems in the smart grid. Optimization Letters, 12 (7). pp. 1553-1568.

[img] Text
p.pdf - Author Accepted Manuscript

Download (274kB)

Abstract

Motivated by the growing interest in the smart grid and intelligent energy man- agement mechanisms we study two classes of domestic energy allocation problems. In the first case we work with a system that is tasked with scheduling the work on a number of appliances over a given time window. In the second one a collection of air conditioning appliances is used to control the temperature of a given domestic environment. Our frame- work for this case includes a simplified mechanism for modelling the heat exchange between the interior and the exterior of the given environment. We present various polynomial time algorithms and NP-hardness proofs. In particular the main result of the paper is a proof that although it is NP-hard to schedule the operation of a single air-conditioning (AC) unit, working at various temperature levels in a variable energy price regime, there is a polyno- mial time algorithm for controlling one such device working at a single temperature level, for houses with low thermal inertia. The algorithm analysis hinges on the properties of a polynomial time variant of the minimisation version of the knapsack problem which may be of independent interest.

Item Type: Article
Uncontrolled Keywords: Complexity, Optimization, Dyamic programming, Algorithms
Depositing User: Symplectic Admin
Date Deposited: 03 Nov 2017 16:14
Last Modified: 19 Jan 2023 06:51
DOI: 10.1007/s11590-017-1209-7
Related URLs:
URI: https://livrepository.liverpool.ac.uk/id/eprint/3011446