Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Nonserial Dynamic Programming with Applications in Smart Home Appliances Scheduling - Part II: Nonserial Dynamic Programming
KTH, School of Electrical Engineering (EES), Automatic Control. KTH, School of Electrical Engineering (EES), Centres, ACCESS Linnaeus Centre.ORCID iD: 0000-0003-1835-2963
KTH, School of Electrical Engineering (EES), Automatic Control. KTH, School of Electrical Engineering (EES), Centres, ACCESS Linnaeus Centre.ORCID iD: 0000-0001-9940-5929
2014 (English)In: 2014 European Control Conference (ECC), IEEE , 2014, 1663-1668 p.Conference paper, Published paper (Refereed)
Abstract [en]

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.
Keyword [en]
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
National Category
Control Engineering
Identifiers
URN: urn:nbn:se:kth:diva-163500DOI: 10.1109/ECC.2014.6862552ISI: 000349955701158Scopus ID: 2-s2.0-84911496201ISBN: 978-3-9524269-1-3 (print)OAI: oai:DiVA.org:kth-163500DiVA: diva2:801150
Conference
13th European Control Conference, ECC 2014, Strasbourg Convention and Exhibition Center Place de Bordeaux Strasbourg, France, 24 June 2014 through 27 June 2014
Note

QC 20150408

Available from: 2015-04-08 Created: 2015-04-07 Last updated: 2015-04-08Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full textScopus

Authority records BETA

Sandberg, HenrikJohansson, Karl Henrik

Search in DiVA

By author/editor
Sandberg, HenrikJohansson, Karl Henrik
By organisation
Automatic ControlACCESS Linnaeus Centre
Control Engineering

Search outside of DiVA

GoogleGoogle Scholar

doi
isbn
urn-nbn

Altmetric score

doi
isbn
urn-nbn
Total: 18 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf