Hostname: page-component-586b7cd67f-l7hp2 Total loading time: 0 Render date: 2024-11-30T20:31:21.414Z Has data issue: false hasContentIssue false
  • English
  • Français

Time–dependent Simple Temporal Networks: Properties and Algorithms∗

Published online by Cambridge University Press:  18 April 2013

Cédric Pralet  and
Gérard Verfaillie
Cédric Pralet
Affiliation:
ONERA – The French Aerospace Lab, 31055, Toulouse, France. [email protected], [email protected]
Gérard Verfaillie
Affiliation:
ONERA – The French Aerospace Lab, 31055, Toulouse, France. [email protected], [email protected]
Get access

Abstract

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.

Keywords

Temporal constraintstime–dependent schedulingconstraint propagationagile satellites
Type
Research Article
Information
RAIRO - Operations Research , Volume 47 , Issue 2: ConstraintProgramming , April 2013 , pp. 173 - 198
Copyright
© EDP Sciences, ROADEF, SMAI, 2013

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Bellman, R., On a routing problem. Quart. Appl. Math. 16 (1958) 87–90. Google Scholar
M. Bender, R. Cole, E. Demaine, M. Farach-Colton and J. Zito, Two simplified algorithms for maintaining order in a list, in Proc. of ESA-02 (2002) 152–164.
Benoist, T., Estellon, B., Gardi, F., Megel, R. and Nouioua, K., LocalSolver 1.x: a black-box local-search solver for 0-1 programming. 4OR: A Quart. J. Oper. Res. 9 (2011) 299–316. Google Scholar
R. Cervoni, A. Cesta and A. Oddi, Managing dynamic temporal constraint networks. in Proc. of AIPS-94 (1994) 13–18.
A. Cesta and A. Oddi, Gaining efficiency and flexibility in the simple temporal problem. in Proc. TIME-96 (1996) 45–50.
Challenge ROADEF-03. Handling the mission of Earth observation satellites (2003). http://challenge.roadef.org/2003/fr/.
Cheng, T., Ding, Q. and Lin, B., A concise survey of scheduling with time-dependent processing times. Eur. J. Oper. Res. (2004) 152 1–13. Google Scholar
Codognet, P. and Diaz, D., Compiling constraints in clp(FD). J. Logic Program. 27 (1996) 185–226. Google Scholar
Dechter, R., Meiri, I. and Pearl, J., Temporal constraint networks. Artif. Intell. 49 (1991) 61–95. Google Scholar
Floyd, R.W., Algorithm 97: shortest path. Commun. ACM 5 (1962) 345. Google Scholar
L.R. Ford and D.R. Fulkerson, Flows in networks. Princeton University Press (1962).
S. Gawiejnowicz, Time-dependent scheduling. Springer (2008).
A. Gerevini, A. Perini and F. Ricci, Incremental algorithms for managing temporal constraints, in Proc. of ICTAI-96 (1996) 360–365.
B. Haeupler, T. Kavitha, R. Mathew, S. Sen and R. Tarjan, Incremental cycle detection, topological ordering, and strong component maintenance. ACM Trans. Algorithms 8 (2012).
Van Hentenryck, P., Deville, Y. and Teng, C., A generic arc-consistency algorithm and its specializations. Artif. Intell. 57 (1992) 291–321. Google Scholar
P. Van Hentenryck and L. Michel, Constraint-based local search. The MIT Press (2005).
Lemaître, M., Verfaillie, G., Jouhaud, F., Lachiver, J.-M. and Bataille, N., Selecting and scheduling observations of agile satellites. Aerospace Science and Technology 6 (2002) 367–381. Google Scholar
Montanari, U., Networks of constraints: fundamental properties and applications to picture processing. Inf. Sci. 7 (1974) 95–132. Google Scholar
P. Morris, R. Morris, L. Khatib, S. Ramakrishnan and A. Bachmann, Strategies for global optimization of temporal preferences, in Proc. of CP-04 (2004) 408–422. Springer.
L. Planken, M. de Weerdt and R. van der Krogt, P3C: a new algorithm for the simple temporal problem, in Proc. of ICAPS-08 (2008) 256–263.
L. Planken, M. de Weerdt and N. Yorke-Smith, Incrementally solving STNs by enforcing partial path consistency, in Proc. of ICAPS-10 (2010) 129–136.
C. Pralet and G. Verfaillie, Réseaux temporels simples étendus. Application à la gestion de satellites agiles, in Proc. of JFPC-12 (2012) 264–273.
C. Pralet and G. Verfaillie, Time-dependent simple temporal networks, in Proc. of CP-12 (2012) 608–623.
Roditty, L. and Zwick, U., Improved dynamic reachability algorithms for directed graphs. SIAM J. Comput. 37 (2008) 1455–1471. Google Scholar
I. Shu, R. Effinger and B. Williams, Enabling fast flexible planning through incremental temporal reasoning with conflict extraction, in Proc. of ICAPS-05 (2005) 252–261.
Stergiou, K. and Koubarakis, M., Backtracking algorithms for disjunctions of temporal constraints. Artif. Intell. 120 (2000) 81–117. Google Scholar
Vidal, T. and Fargier, H., Handling contingency in temporal constraint networks: from consistency to controllabilities. J. Exp. Theor. Artif. Intell. 11 (1999) 23–45. Google Scholar
Warshall, T., A theorem on Boolean matrices. J. ACM 9 (1962) 11–12. Google Scholar
L. Xu and B. Choueiry, A new efficient algorithm for solving the simple temporal problem, in Proc. TIME-ICTL-03 (2003) 210–220.