Simple Temporal Networks (STN) allow conjunctions of minimum and maximum distance constraints between pairs of temporal positions to be represented. This paper introduces an extension of STN called Time-dependent STN (TSTN), which covers temporal constraints for which the minimum and maximum distances required between two temporal positions x and y are not necessarily constant but may depend on the assignments of x and y. Such constraints are useful to model problems in which the duration of an activity may depend on its starting time, or problems in which the transition time required between two activities may depend on the time at which the transition is triggered. Properties of the new framework are analyzed, and standard STN solving techniques are extended to TSTN. The contributions are applied to the management of temporal constraints for so-called agile Earth observation satellites.
Mots-clés : temporal constraints, time-dependent scheduling, constraint propagation, agile satellites
@article{RO_2013__47_2_173_0,
author = {Pralet, C\'edric and Verfaillie, G\'erard},
title = {Time-dependent {Simple} {Temporal} {Networks:} {Properties} and {Algorithms}},
journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
pages = {173--198},
publisher = {EDP-Sciences},
volume = {47},
number = {2},
year = {2013},
doi = {10.1051/ro/2013033},
mrnumber = {3055157},
zbl = {1267.68218},
language = {en},
url = {http://archive.numdam.org/articles/10.1051/ro/2013033/}
}
TY - JOUR AU - Pralet, Cédric AU - Verfaillie, Gérard TI - Time-dependent Simple Temporal Networks: Properties and Algorithms JO - RAIRO - Operations Research - Recherche Opérationnelle PY - 2013 SP - 173 EP - 198 VL - 47 IS - 2 PB - EDP-Sciences UR - http://archive.numdam.org/articles/10.1051/ro/2013033/ DO - 10.1051/ro/2013033 LA - en ID - RO_2013__47_2_173_0 ER -
%0 Journal Article %A Pralet, Cédric %A Verfaillie, Gérard %T Time-dependent Simple Temporal Networks: Properties and Algorithms %J RAIRO - Operations Research - Recherche Opérationnelle %D 2013 %P 173-198 %V 47 %N 2 %I EDP-Sciences %U http://archive.numdam.org/articles/10.1051/ro/2013033/ %R 10.1051/ro/2013033 %G en %F RO_2013__47_2_173_0
Pralet, Cédric; Verfaillie, Gérard. Time-dependent Simple Temporal Networks: Properties and Algorithms. RAIRO - Operations Research - Recherche Opérationnelle, Tome 47 (2013) no. 2, pp. 173-198. doi : 10.1051/ro/2013033. http://archive.numdam.org/articles/10.1051/ro/2013033/
[1] , On a routing problem. Quart. Appl. Math. 16 (1958) 87-90. | MR | Zbl
[2] , , , and , Two simplified algorithms for maintaining order in a list, in Proc. of ESA-02 (2002) 152-164. | Zbl
[3] , , , and , LocalSolver 1.x: a black-box local-search solver for 0-1 programming. 4OR: A Quart. J. Oper. Res. 9 (2011) 299-316. | MR | Zbl
[4] , and , Managing dynamic temporal constraint networks. in Proc. of AIPS-94 (1994) 13-18.
[5] and , Gaining efficiency and flexibility in the simple temporal problem. in Proc. TIME-96 (1996) 45-50.
[6] Challenge ROADEF-03. Handling the mission of Earth observation satellites (2003). http://challenge.roadef.org/2003/fr/.
[7] , and , A concise survey of scheduling with time-dependent processing times. Eur. J. Oper. Res. (2004) 152 1-13. | MR | Zbl
[8] and , Compiling constraints in clp(FD). J. Logic Program. 27 (1996) 185-226. | MR | Zbl
[9] , and , Temporal constraint networks. Artif. Intell. 49 (1991) 61-95. | MR | Zbl
[10] , Algorithm 97: shortest path. Commun. ACM 5 (1962) 345.
[11] and , Flows in networks. Princeton University Press (1962). | MR | Zbl
[12] , Time-dependent scheduling. Springer (2008). | MR | Zbl
[13] , and , Incremental algorithms for managing temporal constraints, in Proc. of ICTAI-96 (1996) 360-365.
[14] , , , and , Incremental cycle detection, topological ordering, and strong component maintenance. ACM Trans. Algorithms 8 (2012). | MR | Zbl
[15] , and , A generic arc-consistency algorithm and its specializations. Artif. Intell. 57 (1992) 291-321. | MR | Zbl
[16] and , Constraint-based local search. The MIT Press (2005).
[17] , , , and , Selecting and scheduling observations of agile satellites. Aerospace Science and Technology 6 (2002) 367-381.
[18] , Networks of constraints: fundamental properties and applications to picture processing. Inf. Sci. 7 (1974) 95-132. | MR | Zbl
[19] , , , and , Strategies for global optimization of temporal preferences, in Proc. of CP-04 (2004) 408-422. Springer. | Zbl
[20] , and , P3C: a new algorithm for the simple temporal problem, in Proc. of ICAPS-08 (2008) 256-263.
[21] , and , Incrementally solving STNs by enforcing partial path consistency, in Proc. of ICAPS-10 (2010) 129-136.
[22] and , Réseaux temporels simples étendus. Application à la gestion de satellites agiles, in Proc. of JFPC-12 (2012) 264-273.
[23] and , Time-dependent simple temporal networks, in Proc. of CP-12 (2012) 608-623.
[24] and , Improved dynamic reachability algorithms for directed graphs. SIAM J. Comput. 37 (2008) 1455-1471. | MR | Zbl
[25] , and , Enabling fast flexible planning through incremental temporal reasoning with conflict extraction, in Proc. of ICAPS-05 (2005) 252-261.
[26] and , Backtracking algorithms for disjunctions of temporal constraints. Artif. Intell. 120 (2000) 81-117. | MR | Zbl
[27] and , Handling contingency in temporal constraint networks: from consistency to controllabilities. J. Exp. Theor. Artif. Intell. 11 (1999) 23-45. | Zbl
[28] , A theorem on Boolean matrices. J. ACM 9 (1962) 11-12. | MR | Zbl
[29] and , A new efficient algorithm for solving the simple temporal problem, in Proc. TIME-ICTL-03 (2003) 210-220.
Cité par Sources :
