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

Abstract

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

How to cite

top

Pralet, 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. [1] R. Bellman, On a routing problem. Quart. Appl. Math.16 (1958) 87–90. Zbl0081.14403MR102435
  2. [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. [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. [4] R. Cervoni, A. Cesta and A. Oddi, Managing dynamic temporal constraint networks. in Proc. of AIPS-94 (1994) 13–18. 
  5. [5] A. Cesta and A. Oddi, Gaining efficiency and flexibility in the simple temporal problem. in Proc. TIME-96 (1996) 45–50. 
  6. [6] Challenge ROADEF-03. Handling the mission of Earth observation satellites (2003). http://challenge.roadef.org/2003/fr/. 
  7. [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. [8] P. Codognet and D. Diaz, Compiling constraints in clp(FD). J. Logic Program.27 (1996) 185–226. Zbl0874.68054MR1389434
  9. [9] R. Dechter, I. Meiri and J. Pearl, Temporal constraint networks. Artif. Intell.49 (1991) 61–95. Zbl0737.68070MR1112649
  10. [10] R.W. Floyd, Algorithm 97: shortest path. Commun. ACM 5 (1962) 345. 
  11. [11] L.R. Ford and D.R. Fulkerson, Flows in networks. Princeton University Press (1962). Zbl1216.05047MR159700
  12. [12] S. Gawiejnowicz, Time-dependent scheduling. Springer (2008). Zbl1155.90004MR2494065
  13. [13] A. Gerevini, A. Perini and F. Ricci, Incremental algorithms for managing temporal constraints, in Proc. of ICTAI-96 (1996) 360–365. 
  14. [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. [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. [16] P. Van Hentenryck and L. Michel, Constraint-based local search. The MIT Press (2005). Zbl1160.68556
  17. [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. [18] U. Montanari, Networks of constraints: fundamental properties and applications to picture processing. Inf. Sci.7 (1974) 95–132. Zbl0284.68074MR413625
  19. [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. [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. [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. [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. [23] C. Pralet and G. Verfaillie, Time-dependent simple temporal networks, in Proc. of CP-12 (2012) 608–623. Zbl1267.68218
  24. [24] L. Roditty and U. Zwick, Improved dynamic reachability algorithms for directed graphs. SIAM J. Comput.37 (2008) 1455–1471. Zbl1225.68276MR2386276
  25. [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. [26] K. Stergiou and M. Koubarakis, Backtracking algorithms for disjunctions of temporal constraints. Artif. Intell.120 (2000) 81–117. Zbl0945.68038MR1765185
  27. [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. [28] T. Warshall, A theorem on Boolean matrices. J. ACM9 (1962) 11–12. Zbl0118.33104MR149688
  29. [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 ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.