How to model planning and scheduling problems using constraint networks on timelines

Gérard Verfaillie; Cédric Pralet; Michel Lemaître; Gérard Verfaillie; Cédric Pralet; Michel Lemaître

doi:10.1017/S0269888910000172

Abstract: The CNT framework (Constraint Network on Timelines) has been designed to model discrete event dynamic systems and the properties one knows, one wants to verify, or one wants to enforce on them. In this article, after a reminder about the CNT framework, we show its modeling power and its ability to support various modeling styles, coming from the planning, scheduling, and constraint programming communities. We do that by producing and comparing various models of two mission management problems in the aerospace domain: management of a team of unmanned air vehicles and of an Earth observing satellite.

Other Articles By Authors

How to model planning and scheduling problems using constraint networks on timelines

2 av. Édouard Belin

Published online: 01 September 2010

Abstract: Abstract: The CNT framework (Constraint Network on Timelines) has been designed to model discrete event dynamic systems and the properties one knows, one wants to verify, or one wants to enforce on them. In this article, after a reminder about the CNT framework, we show its modeling power and its ability to support various modeling styles, coming from the planning, scheduling, and constraint programming communities. We do that by producing and comparing various models of two mission management problems in the aerospace domain: management of a team of unmanned air vehicles and of an Earth observing satellite.

HTML

[a..b] denotes the set of integers greater than or equal to integer a and less than or equal to integer b.

In general, ST is not included in the set of time references associated with the timelines in SX.

If A is an assignment and v a variable assigned by A, A[v] denotes the projection of A on v. By extension, if A is an assignment and V a set of variables assigned by A, A[V] denotes the projection of A on V.

As is usual in CP tools, a constraint c is considered equivalent to a boolean variable b equal to 1 if c is satisfied and 0 otherwise (constraint reification).

Rights and permissions

References (25)

About this article

Cite this article

Gérard Verfaillie, Cédric Pralet, Michel Lemaître. 2010. How to model planning and scheduling problems using constraint networks on timelines. The Knowledge Engineering Review. 25:172 doi: 10.1017/S0269888910000172

Gérard Verfaillie, Cédric Pralet, Michel Lemaître. 2010. How to model planning and scheduling problems using constraint networks on timelines. The Knowledge Engineering Review. 25:172 doi: 10.1017/S0269888910000172

{{lists.name}}

How to model planning and scheduling problems using constraint networks on timelines

Abstract

Rights and permissions

References

About this article

Cite this article

Article Metrics

Access History

Other Articles By Authors