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 I: Precedence Graph Simplification
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, 1643-1648 p.Conference paper, Published paper (Refereed)
Abstract [en]

In this and a companion paper a dynamic programming (DP) approach to solve a smart home appliances scheduling problem is considered. The challenge with solving the scheduling problem is the coupling of decision variables due to some time precedence constraints. In general, the system of precedence constraints may contain redundant constraints that offer opportunities for simplification. This simplification is desirable for reducing the computation effort of the nonserial DP procedure presented in the companion paper (i.e., Part II). The current paper establishes the uniqueness of the maximum set of redundant constraints and its polynomial-time solvability with optimality guarantee, under the sufficient and necessary condition that the precedence graph (a graph representation of the precedence constraints system) does not contain any cycle with nonnegative weight. A numerical case study indicates the efficiency of the proposed simplification algorithm versus the brute-force enumerative search. Besides helping to reduce the computation effort in the DP procedure described in the companion paper, the algorithm in the current paper solves a generalization of a precedence graph simplification problem arising from application areas such as parallel computing.

Place, publisher, year, edition, pages
IEEE , 2014. 1643-1648 p.
Keyword [en]
Automation, Domestic appliances, Dynamic programming, Intelligent buildings, Paper, Parallel architectures, Problem solving, Computation effort, Decision variables, Graph representation, Precedence constraints, Redundant constraints, Scheduling problem, Simplification algorithms, Sufficient and necessary condition
National Category
Control Engineering
Identifiers
URN: urn:nbn:se:kth:diva-163499DOI: 10.1109/ECC.2014.6862548ISI: 000349955701155Scopus ID: 2-s2.0-84911500559ISBN: 978-3-9524269-1-3 (print)OAI: oai:DiVA.org:kth-163499DiVA: diva2:801145
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: 20 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