Nonserial Dynamic Programming with Applications in Smart Home Appliances Scheduling - Part II: Nonserial Dynamic Programming
2014 (English)In: 2014 European Control Conference (ECC), IEEE , 2014, 1663-1668 p.Conference paper (Refereed)
In this paper a dynamic programming (DP) solution approach to a nonconvex resource allocation problem (RAP) is presented. The problem in this paper generalizes the smart home appliances scheduling problem introduced in the companion paper (i.e., Part I). The computation difficulty with solving the RAP depends on the decision variable coupling, which can be described by an interaction graph. This paper proposes a DP algorithm to solve the RAP in the special setting where the interaction graph is a tree. This extends the applicability result of DP to RAP beyond the standard serial case where the interaction graph is a line. The extension of the result is achieved by establishing that even in the tree case DP computation effort is polynomial in the number of decision variables. For RAP in its general form, this paper proposes a modification to the nonserial DP procedure originally introduced by Bertele and Brioschi. Contrary to that of the previous method, the computation effort of the proposed method can be characterized by a well-known minimum feedback vertex set problem. Case studies on known examples indicate that both nonserial DP methods are similarly efficient.
Place, publisher, year, edition, pages
IEEE , 2014. 1663-1668 p.
Automation, Decision making, Domestic appliances, Forestry, Intelligent buildings, Scheduling, Trees (mathematics), Computation effort, Decision variables, Interaction graphs, Minimum feedback vertex set, Nonconvex, Resource allocation problem, Scheduling problem, Solution approach
IdentifiersURN: urn:nbn:se:kth:diva-163500DOI: 10.1109/ECC.2014.6862552ISI: 000349955701158ScopusID: 2-s2.0-84911496201ISBN: 978-3-9524269-1-3OAI: oai:DiVA.org:kth-163500DiVA: diva2:801150
13th European Control Conference, ECC 2014, Strasbourg Convention and Exhibition Center Place de Bordeaux Strasbourg, France, 24 June 2014 through 27 June 2014
QC 201504082015-04-082015-04-072015-04-08Bibliographically approved