In this paper we present a state space exploration method implemented as part of a Decision Support Tool designed to improve the performance of logistics and production systems. An efficient depth-first search strategy, together with a reduction method known as the ‘Old Node Method’, is introduced to improve the descendant path choice by means of an evaluation function that allows the selection of the most promising node to be expanded at any level of the path. The sub-set of the state space representing the most promising scenarios holds a set of feasible and quasi-optimal solutions.
PieraMANarcisoMGuaschARieraD. Optimization of logistic and manufacturing systems through simulation: A colored Petri net-based methodology. Simulation2004; 80: 121–130.
2.
JensenK. Coloured Petri nets: Basics concepts, analysis methods and practical use, Vols 1, 2 and 3, 2nd ed.Berlin: Springer, 1997.
3.
SilvaMValetteR. Petri nets and flexible manufacturing. In Advances in Petri nets (Lect. Notes Comput. Sci.Vol 424). Berlin: Springer, 1990, pp. 374–417.
4.
ZimmermannADalkowskiKHommelG. A case study in modeling and performance evaluation of manufacturing systems using colored Petri nets. In Proceedings of the 8th European Simulation Symposium, Genoa, Italy, 1996, pp. 282–286.
5.
PieraMAGuaschT. Coloured Petri net for simulation FMS model maintenance. In Proceedings of the 4th International EUROSIM 2001, Delft, The Netherlands. 2001.
6.
KristensenLMPetrucciL. An approach to distributed state space exploration for coloured Petri nets. In Applications and theory of Petri nets (Lect. Notes Comput. Sci.Vol 3099). Berlin: Springer, 2004, pp. 474–483.
7.
ValmariA. The state explosion problem. In Lectures on Petri nets I: Basic models. Advances in Petri nets (Lect. Notes Comput. Sci.Vol 1491). Berlin: Springer, 1998, pp. 429–528.
8.
ElgaardL. The symmetry method for coloured Petri nets - theory, tools, and practical use. PhD Thesis, Department of Computing Science, University of Aarhus, Denmark, 2002.
9.
KristensenLM. State space methods for coloured Petri nets. PhD Thesis, Department of Computing Science, University of Aarhus, Denmark, 2000.
10.
KristensenLMValmariA. Improved question-guided stubborn set methods for state properties. Application and theory of Petri nets (Lect. Notes Comput. Sci.Vol 1825). Berlin: Springer, 2000, pp. 282–302.
11.
MailundT. Sweeping the state space: A sweep-line state space exploration method. PhD Thesis, Department of Computing Science, University of Aarhus, Denmark, 2003.
12.
ReyesAYuHKelleherGLloydS. Integrating Petri nets and hybrid heuristic search for the scheduling of FMS. Comput Ind2002; 47: 123–138.
13.
YuHReyesACangSLloydS. Combined Petri netmodelling and AI-based heuristic hybrid search for flexible manufacturing systems-part I: Petri net modelling and heuristic search. Comput Ind Eng2003; 44: 527–543.
14.
YuHReyesACangSLloydS. Combined Petri net modelling and AI-based heuristic hybrid search for flexible manufacturing systems-part II: Heuristic hybrid search. Comput Ind Eng2003; 44: 545–566.
15.
KristensenLMMechlenborgPZhangLMitchellBGallaschGE. Model-based development of a course of action scheduling Tool. Int J Softw Tools Technol Trans2008; 10: 5–14.
16.
MitchellBKristensenLMZhangL. Formal Specification and state space analysis of an operational planning process. Int J Softw Tools Technol Trans2007; 9: 255–267.
17.
BillingtonJGallaschGEKristensenLMMailundT. Exploiting equivalence reduction and the sweep-line method for detecting terminal states. IEEE Trans Syst Man Cybern Syst Hum2004; 34: 23–37.
18.
ChristensenSJensenKMailundTKristensenLM. State space methods for timed coloured Petri nets. In Proceedings of 2nd International Colloquium on Petri Net Technologies for Modelling Communication Based Systems, Berlin, Germany, 2001.
19.
ChristensenSKristensenLMMailundT. Condensed state spaces for timed Petri nets. Applications and theory of Petri nets (Lect. Notes Comput. Sci.Vol 2075). Berlin: Springer, 2001, pp. 101–120.
20.
De FrancescoNSantoneAVagliniG. State spacereduction by non-standard semantics for deadlock analysis. Sci Comput Program1998; 30: 309–338.
21.
ElgaardL. Coloured Petri nets and state space generation with the symmetry method. In Proceedings of the Fourth International Workshop on Practical Use of Coloured Petri Nets and the CPN Tools, Aarhus, Denmark, 2002, pp. 121–138.
22.
GallaschGEKristensenLMMailundT. Sweep-line state space exploration for coloured Petri nets. In Proceedings of the Fourth International Workshop on Practical Use of Coloured Petri Nets and the CPN Tools, Aarhus, Denmark, 2002, pp. 101–119.
23.
JørgensenJBKristensenLM. Verification of coloured Petri nets using state spaces with equivalence classes. In Proceedings of Workshop on Petri Nets in System Engineering (PNSE’97) Modelling, Verification, and Validation, Hamburg, Germany, 1997, pp. 20–31.
24.
LorentsenL. Coloured Petri nets and state space generation with the symmetry method. In Proceedings of the Fourth International Workshop on Practical Use of Coloured Petri Nets and the CPN Tools, Aarhus, Denmark, 2002, pp. 121–138.
25.
VarpaaniemiK. On the stubborn set method in reduced state space generation. PhD Thesis, Department of Computer Science and Engineering, Helsinki University of Technology, Finland, 1998.
26.
JensenKKristensenLMWellsL. Coloured Petri nets and CPN tools for modelling and validation of concurrent systems. Int J Softw Tools Technol Trans2007; 9: 213–254.
27.
NarcisoMPieraMAGuaschA. A methodology for solving logistic optimization problems through simulation. Simulation2010; 86: 369–389.
28.
LakosCPetrucciL. Modular state space exploration for timed Petri nets. Int J Softw Tools Technol Trans2007; 9: 393–411.
29.
PieraMAMusicG. Coloured Petri net scheduling models: Timed state space exploration shortages. Math Comput Simulat2011; in press, doi:10.1016/j.matcom. 2010.10.01410.1016/j.matcom. 2010.10.014.
30.
StörrleH. ‘An Evaluation of High-end Tools for Petri-nets’, Technical Report/Bericht 9802, Ludwig-Maximilians-Universität München, Institut für Informatik, Germany, http://www.informatik.uni-hamburg.de/TGI/PetriNets/tools/ (1998, accessed 14 April 2011)
31.
NarcisoMEPieraMAGuaschA. A knowledge representation approach suitable to support heuristic search methods. In Artificial Intelligence Research and Development (Fr. Art. Int). Amsterdam: IOS Press, 2003; 100: 397–408.
NarcisoMEPieraMAGuaschA. A decision support system to tackle the vehicle routing problem. In Recent Advances in Artificial Intelligence Research and Development (Fr. Art. Int), IOS Press, Amsterdam, 2004; 113, 375–382.
34.
NarcisoMEPieraMAHennetJ-C. Generation de Plan par Exploration Selective d’un Arbre de Couverture. In Proceedings of 4e Conférence Francophone de Modélisation et Simulation, Toulouse, France, 2003.
35.
ZúñigaCPieraMANarcisoM. Revisiting the pallet loading problem using a discrete event system approach to minimise logistic costs. Int J Prod Res2011; 49: 2243–2264.
