Time–dependent Simple Temporal Networks: Properties and Algorithms
Cédric Pralet; Gérard Verfaillie
RAIRO - Operations Research - Recherche Opérationnelle (2013)
- Volume: 47, Issue: 2, page 173-198
- ISSN: 0399-0559
Access Full Article
topAbstract
topHow to cite
topPralet, Cédric, and Verfaillie, Gérard. "Time–dependent Simple Temporal Networks: Properties and Algorithms." RAIRO - Operations Research - Recherche Opérationnelle 47.2 (2013): 173-198. <http://eudml.org/doc/275014>.
@article{Pralet2013,
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.},
author = {Pralet, Cédric, Verfaillie, Gérard},
journal = {RAIRO - Operations Research - Recherche Opérationnelle},
keywords = {temporal constraints; time-dependent scheduling; constraint propagation; agile satellites},
language = {eng},
number = {2},
pages = {173-198},
publisher = {EDP-Sciences},
title = {Time–dependent Simple Temporal Networks: Properties and Algorithms},
url = {http://eudml.org/doc/275014},
volume = {47},
year = {2013},
}
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
PB - EDP-Sciences
VL - 47
IS - 2
SP - 173
EP - 198
AB - 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.
LA - eng
KW - temporal constraints; time-dependent scheduling; constraint propagation; agile satellites
UR - http://eudml.org/doc/275014
ER -
References
top- [1] R. Bellman, On a routing problem. Quart. Appl. Math.16 (1958) 87–90. Zbl0081.14403MR102435
- [2] 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. Zbl1019.68527
- [3] T. Benoist, B. Estellon, F. Gardi, R. Megel and K. Nouioua, LocalSolver 1.x: a black-box local-search solver for 0-1 programming. 4OR: A Quart. J. Oper. Res. 9 (2011) 299–316. Zbl1231.90318MR2825783
- [4] R. Cervoni, A. Cesta and A. Oddi, Managing dynamic temporal constraint networks. in Proc. of AIPS-94 (1994) 13–18.
- [5] A. Cesta and A. Oddi, 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] T. Cheng, Q. Ding and B. Lin, A concise survey of scheduling with time-dependent processing times. Eur. J. Oper. Res. (2004) 152 1–13. Zbl1030.90023MR2004434
- [8] P. Codognet and D. Diaz, Compiling constraints in clp(FD). J. Logic Program.27 (1996) 185–226. Zbl0874.68054MR1389434
- [9] R. Dechter, I. Meiri and J. Pearl, Temporal constraint networks. Artif. Intell.49 (1991) 61–95. Zbl0737.68070MR1112649
- [10] R.W. Floyd, Algorithm 97: shortest path. Commun. ACM 5 (1962) 345.
- [11] L.R. Ford and D.R. Fulkerson, Flows in networks. Princeton University Press (1962). Zbl1216.05047MR159700
- [12] S. Gawiejnowicz, Time-dependent scheduling. Springer (2008). Zbl1155.90004MR2494065
- [13] A. Gerevini, A. Perini and F. Ricci, Incremental algorithms for managing temporal constraints, in Proc. of ICTAI-96 (1996) 360–365.
- [14] 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). Zbl1295.05234MR2893005
- [15] P. Van Hentenryck, Y. Deville and C. Teng, A generic arc-consistency algorithm and its specializations. Artif. Intell.57 (1992) 291–321. Zbl0763.68059MR1183765
- [16] P. Van Hentenryck and L. Michel, Constraint-based local search. The MIT Press (2005). Zbl1160.68556
- [17] M. Lemaître, G. Verfaillie, F. Jouhaud, J.-M. Lachiver and N. Bataille, Selecting and scheduling observations of agile satellites. Aerospace Science and Technology6 (2002) 367–381.
- [18] U. Montanari, Networks of constraints: fundamental properties and applications to picture processing. Inf. Sci.7 (1974) 95–132. Zbl0284.68074MR413625
- [19] 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. Zbl1152.68567
- [20] 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.
- [21] 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.
- [22] C. Pralet and G. Verfaillie, Réseaux temporels simples étendus. Application à la gestion de satellites agiles, in Proc. of JFPC-12 (2012) 264–273.
- [23] C. Pralet and G. Verfaillie, Time-dependent simple temporal networks, in Proc. of CP-12 (2012) 608–623. Zbl1267.68218
- [24] L. Roditty and U. Zwick, Improved dynamic reachability algorithms for directed graphs. SIAM J. Comput.37 (2008) 1455–1471. Zbl1225.68276MR2386276
- [25] 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.
- [26] K. Stergiou and M. Koubarakis, Backtracking algorithms for disjunctions of temporal constraints. Artif. Intell.120 (2000) 81–117. Zbl0945.68038MR1765185
- [27] T. Vidal and H. Fargier, Handling contingency in temporal constraint networks: from consistency to controllabilities. J. Exp. Theor. Artif. Intell.11 (1999) 23–45. Zbl1054.68664
- [28] T. Warshall, A theorem on Boolean matrices. J. ACM9 (1962) 11–12. Zbl0118.33104MR149688
- [29] L. Xu and B. Choueiry, A new efficient algorithm for solving the simple temporal problem, in Proc. TIME-ICTL-03 (2003) 210–220.
NotesEmbed ?
topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.