CPL - Chalmers Publication Library
| Utbildning | Forskning | Styrkeområden | Om Chalmers | In English In English Ej inloggad.

Nonserial Dynamic Programming with Applications in Smart Home Appliances Scheduling – Part II: Nonserial Dynamic Programming

Kin Cheong Sou (Institutionen för matematiska vetenskaper, matematik) ; Henrik Sandberg ; Karl Henrik Johansson
13th European Control Conference, ECC 2014, Strasbourg, France, 24-27 June 2014 p. 1663-1668. (2014)
[Konferensbidrag, refereegranskat]

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 intro- duced 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.

Article number 6862548

Den här publikationen ingår i följande styrkeområden:

Läs mer om Chalmers styrkeområden  

Denna post skapades 2014-07-16. Senast ändrad 2016-01-20.
CPL Pubid: 200530


Läs direkt!

Länk till annan sajt (kan kräva inloggning)

Institutioner (Chalmers)

Institutionen för matematiska vetenskaper, matematik (2005-2016)


Informations- och kommunikationsteknik

Chalmers infrastruktur