Simulation-based optimization of discrete event systems with alternative structural configurations using distributed computation and the Petri net paradigm
Restricted accessResearch articleFirst published online November, 2013
Simulation-based optimization of discrete event systems with alternative structural configurations using distributed computation and the Petri net paradigm
Decision-making on discrete event systems with alternative structural configurations is a field with application to the efficient design and operation of many systems, ranging from manufacturing facilities to communication networks. The solution of this problem may be afforded by its transformation into an optimization problem. A variety of statements for this optimization problem can be presented by using different formalisms able to describe the model of the system. These different statements allow developing diverse optimization algorithms for solving the problem, which may be very demanding for a computer. In this paper, several approaches are presented in order to reduce the computing requirements needed by the mentioned algorithms, some of them are implemented in one processor and others are based on distributed computing. In particular, this paper presents a new distributed methodology, which associates sets of alternative structural configurations of the system to different alternative aggregation Petri net (AAPNs), regarding the number of available processors. Under certain conditions, this methodology alleviates the computational requirements for every processor and speeds up the optimization process. A case-study is presented and different techniques are applied to solve it, for illustrating diverse distributed and non-distributed methodologies, regarding the available processors, as well as for comparing their relative performance.
CassandrasCGLafortuneS. Introduction to discrete event systems. New York: Springer, 2008.
2.
SilvaMTeruelE. Petri nets for the design and operations of manufacturing systems. Euro J Control1997; 3: 82–199.
3.
ZimmermannARodríguezDSilvaM. A two phase optimisation method for Petri net models of manufacturing systems. J Intell Manufact2001; 12: 409–420.
4.
LatorreJIJiménezEPérezM. A genetic algorithm and Petri nets approach for decision problems stated on discrete event systems. In: 12th international conference on computer modelling and simulation (UKSIM2010), Cambridge, UK, 24–26 March 2010, pp. 86–91.
5.
NarcisoMPieraMAGuaschA. A methodology for solving logistic optimization problems through simulation. SIMULATION2010; 86: 369–389.
6.
MustafeeNTaylorSJEKatsaliakiK. Facilitating the analysis of a UK National Blood Service supply chain using distributed simulation. SIMULATION2009; 85(2): 113–128.
7.
TangYPerumallaKSFujimotoRM. Optimistic parallel discrete event simulations of physical systems using reverse computation. In: Workshop on principles of advanced and distributed simulation (PADS’05), Washington, DC, USA, 1–3 June 2005.
FerschaA. Parallel and distributed simulation of discrete event systems. In: ZomayaAY (ed) Parallel and distributed computing handbook, New York: McGraw Hill, 1995, pp. 1003–1041.
10.
PageEHLitwinLMcMahonMT. Goal-directed grid-enabled computing for legacy simulations. In: 2012 12th IEEE/ACM international symposium on cluster, cloud and grid computing (CCGRID ’12), Ottawa, Canada, 13–16 May 2012, pp. 873–879.
11.
AndjelkovićBLitovskiVBZerbeV. Grid-enabled parallel simulation based on parallel equation formulation. ETRI J2010; 32: 555–565.
12.
EvansNSGauthierDickeyCGrothoffC. Simplifying parallel and distributed simulation with the DUP system. In: 43rd annual simulation symposium (ANSS’10), Orlando, Florida, USA, 12–15 April 2010, pp. 208–215.
13.
MurshedMBuyyaRAbramsonD. GridSim: a toolkit for the modeling and simulation of global grids. Technical report, Monash-CSSE 2001/102, Monash University, Australia, 2001.
14.
WozniakJMBrennerPThainD. Generosity and gluttony in GEMS: grid enabled molecular simulations. In: 14th IEEE international symposium on high performance distributed computing (HPDC 2005), Research Triangle Park, North Carolina, USA; July 24–27, 2005.
15.
WainerGLiuQChazalJ. Performance analysis of web-based distributed simulation in DCD++: a case study across the Atlantic Ocean. In: 2008 spring simulation multiconference (SpringSim), April 2008, pp. 413–420.
16.
TimmIJPawlaszczykD. Large scale multiagent simulation on the grid. In: 5th IEEE international symposium on cluster, computing and the grid (CCGRID ’05), Cardiff, UK, 9–12 May 2005, vol. 01, pp. 334–341.
17.
D’AngeloGBracutoM. Distributed simulation of large-scale and detailed models. Int J Sim Process Modelling2009; 5: 120–131.
18.
MartinJM. Parallel discrete event simulation of large scale wireless ad-hoc networks. PhD Dissertation, University of California, Los Angeles, USA, 2002.
19.
FujimotoRMPerumallaKParkA. Large-scale network simulation: how big? how fast? In: 11TH IEEE/ACM international symposium on modeling, analysis and simulation of computer telecommunications systems (MASCOTS’03), Orlando, Florida, USA, 2003, pp. 116–123.
20.
TheodoropoulosGZhangYChenD. Large scale distributed simulation on the grid. In: CCGRID 2006 workshop: international workshop on distributed simulation on the grid, Singapore, 16–19 May 2006.
21.
AydtHTurnerSJCaiW. Symbiotic simulation systems: an extended definition motivated by symbiosis. In: 22nd workshop on principles of advanced and distributed simulation (PADS ’08), Rome, Italy, 3–6 June 2008, pp. 109–116.
22.
ChiolaGFerschaA. Distributed simulation of Petri nets. IEEE J Parallel Distributed Tech1993; 1: 33–50.
23.
HulaasJ. An evolutive distributed algebraic Petri nets simulator. In: 10th European simulation multiconference ESM’96, Budapest, Hungary, 1996, pp. 348–352.
24.
HolvoetTVerbaetenP. Using agents for simulating and implementing Petri nets. In: 11th workshop on parallel and distributed simulation (PADS’97), Austria, 1997, pp. 134–137.
25.
KuoCH. Development of distributed agent-oriented Petri net simulation and control environment for discrete event dynamic systems. In: IEEE international conference on systems, man and cybemetics (SMC 2004), The Hague, The Netherlands, 10–13 October 2004, vol. 5, pp. 5001–5006.
KnokeMKühlingFZimmermannA. Towards correct distributed simulation of high-level Petri nets with fine-grained partitioning. In: Lecture notes in computer science, vol. 3358: parallel and distributed processing and applications: second international symposium, ISPA 2004 (eds CaoJYangLTGuoM.), Hong Kong, China, 13–15 December 2004, pp. 64–74. New York/Heidelberg: Springer-Verlag.
28.
ZimmermannAKnokeMHommelG. Complete event ordering for time-warp simulation of stochastic discrete event systems. In: 4th symposium on design, analysis and simulation of distributed systems (DASD 2006), Huntsville, Alabama, USA, 2–6 April 2006.
29.
HaggartyOJKnottenbeltWJBradleyJT. Distributed response time analysis of GSPN models with MapReduce. SIMULATION2009; 85: 497–509.
30.
YooTChoHYücesanE. Web services-based parallel replicated discrete event simulation for large-scale simulation optimization. SIMULATION2009; 85: 461–475.
31.
ZuberekWM. Performance study of distributed generation of state spaces using coloured Petri nets. In: 4th workshop and tutorial on practical use of coloured Petri nets and the CPN tools CPN’02 (ed JensenK), Aarhus, Denmark, 28–30 August 2002, pp. 81–98.
32.
ZhouMVenkateshK. Modelling, simulation and control of flexible manufacturing systems. A Petri net approach. Singapore: WS World Scientific, 1999.
33.
MušičG. Petri net based scheduling approach combining dispatching rules and local search. In: 21st European modelling and simulation symposium (EMSS 09), Puerto de la Cruz, Spain, September 2009, vol. 2, pp. 27–32.
34.
PieraMAMušičG. Coloured Petri net scheduling models: timed state space exploration shortages. Math Comp Sim2011; 82: 428–441.
35.
BaiQRenFZhangM. Using colored Petri nets to predict future states in agent-based scheduling and planning systems. J Multiagent Grid Systems - Advances Agent-mediated Auto Neg Archive2010; 6; 527–542.
36.
NishiTMaenoR. Petri net decomposition approach to optimization of route planning problems for AGV systems. IEEE Trans Auto Sci Engr2010; 7: 523–537.
37.
TsinarakisGJTsourveloudisNCValavanisKP. Petri net modeling of routing and operation flexibility in production systems. In: 13th Mediterranean conference on control and automation, Limassol, Cyprus, 27–29 June 2005, pp. 352–357.
38.
SilvaM. Introducing Petri nets. In: DiCesareF (ed) Practice of Petri nets in manufacturing. London: Chapman and Hall, 1993, pp. 1–62.
39.
BalboGSilvaM (eds). Performance models for discrete event systems with synchronizations: formalisms and analysis techniques. Saragosse, Spain: Editorial Kronos, 1998.
40.
DavidRAllaH. Discrete, continuous and hybrid Petri nets. Berlin: Springer, 2005.
41.
RecaldeLSilvaMEzpeletaJ. Petri nets and manufacturing systems: an examples-driven tour. Lectures on concurrency and Petri nets: advances in Petri nets. In: DeselJReisigWRozenbergG (eds) Lecture notes in computer science. New York: Heidelberg: Springer-Verlag, 2004, vol. 3098, pp. 742–788.
42.
LatorreJIJiménezEPérezM. The optimization problem based on alternatives aggregation Petri nets as models for industrial discrete event systems. SIMULATION2013; 89: 346–361.
43.
Latorre-BielJIJiménez-MacíasEPérezM. The exclusive entities in the formalization of a decision problem based on a discrete event system by means of Petri nets. In: 23rd European modelling and simulation symposium (EMSS 11), Rome, Italy; September 2011, pp. 580–586.
44.
LatorreJIJiménezEPérezM. The alternatives aggregation Petri nets as a formalism to design discrete event systems. Inter J Sim Process Modeling2010; 6: 152–164.
45.
RotaGC. The number of partitions of a set. Amer Math Monthly1964; 71: 498–504.
46.
BellET. Exponential numbers. Amer Math Monthly1934; 41: 411–419.
47.
JoarderAMahmoodM. An inductive derivation of stirling numbers of the second kind and their applications in statistics. J Applied Math Decision Sci1997; 1: 151–157.
