### Skapa referens, olika format (klipp och klistra)

**Harvard**

Sou, K., Sandberg, H. och Johansson, K. (2014) *Nonserial Dynamic Programming with Applications in Smart Home Appliances Scheduling - Part I: Precedence Graph Simplification*.

** BibTeX **

@conference{

Sou2014,

author={Sou, Kin Cheong and Sandberg, H. and Johansson, K. H.},

title={Nonserial Dynamic Programming with Applications in Smart Home Appliances Scheduling - Part I: Precedence Graph Simplification},

booktitle={13th European Control Conference, ECC 2014, Strasbourg, France, 24-27 June 2014},

isbn={978-3-9524269-1-3},

pages={1643-1648},

abstract={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.},

year={2014},

}

** RefWorks **

RT Conference Proceedings

SR Electronic

ID 217184

A1 Sou, Kin Cheong

A1 Sandberg, H.

A1 Johansson, K. H.

T1 Nonserial Dynamic Programming with Applications in Smart Home Appliances Scheduling - Part I: Precedence Graph Simplification

YR 2014

T2 13th European Control Conference, ECC 2014, Strasbourg, France, 24-27 June 2014

SN 978-3-9524269-1-3

SP 1643

OP 1648

AB 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.

LA eng

DO 10.1109/ECC.2014.6862548

LK http://dx.doi.org/10.1109/ECC.2014.6862548

OL 30