国外升船机改造一例

PLANNING THE RECONSTRUCTION OF A SHIPLIFT BY SIMULATION OF A STOCHASTIC PETRI NET MODEL Matthias Becker Thomas Bessey Institute of Systems Engineering, University of Hannover Welfengarten 1, 30167 Hannover, Germany {xmb,tby}@sim.uni-hannover.de KEYWORDS Shiplift, Case Study, Stochastic Petri Net ABSTRACT In this case study, two alternatives for reconstruc- tion of an existing shiplift are evaluated. At the mo- ment, the shiplift consists of two long chambers. One chamber is to be rebuilt. Instead of rebuilding it in its original length, a shorter and cheaper chamber could also be built. In this paper, a stochastic Petri net model of the shiplift is used to simulate the shiplift and to evaluate the two alternatives, taking performance, load and customer satisfaction into consideration. The Petri net model has been chosen because Petri nets are a universal modeling language that allows a quick creation, validation and evaluation of models of arbitrary systems. Petri nets furthermore offer a graphical illustration/animation that is useful for the communication with the non-simulationists that are involved. INTRODUCTION At the moment, the shiplift located in Lower Saxony, Germany consists of two parallel chambers, where each chamber has a length of 220 meters. One cham- ber will be too old for safe operation in approxi- mately twelve years. The alternatives that have to be considered then are to renovate or completely re- build this chamber. A complete rebuild offers more alternatives, either to rebuild it in its original size, or to build a shorter and thus cheaper chamber of 110 meters length. These three alternatives have to be considered under financial, environmental and polit- ical aspects which are out of scope here. This work concentrates on the question whether the building of a shorter chamber will be able to cope with current and projected traffic. In the next section, we give details about the shiplift. Then its stochastic Petri net model is explained. Af- ter that we describe the simulation experiments and their results. We conclude by discussing advantages and drawbacks of our approach. THE SHIPLIFT The shiplift consists of two parallel chambers that are operated independently. If a ship arrives at the shiplift and finds at least one chamber open, it enters the chamber and is brought to the other side. In case the ship finds both chambers closed, it has to wait. The operator of the shiplift decides whether to assign a chamber for the waiting ship or to wait for a ship on the other side that is known to arrive soon because of a radio announcement. The number of ships fitting into one chamber de- pends on their length. There are eight classes rang- ing from 40 to 110 meters. We rearrange these classes into three classes: • Small ships up to 50 meters make up 10.0 per- cent of the traffic. • Very large ships with a length of 110 meters make up 24.6 percent. • The rest of the traffic are middle class ships (65.4 percent). The reason for this abstraction is that it is crucial to have the very large ships in one class, because only two of them fit into one long chamber, and only one would fit into a short chamber. The small ships are only a small share of the overall traffic and in most cases they still fit into a partly filled chamber. Two ships of medium size fit into a long chamber and only one into a short chamber. We will come back to this when describing the model. The mean interarrival time between ships is 29.6 minutes from downstream as well as from upstream. This mean was calculated from the total number of ships of the last year and the sum of the periods that the shiplift has been operational. We had no data of exact arrival times. We only had the times of the ships as they entered a chamber, from three days. Note that these entrance times are not the ar- rival times, since, while one ship waits for the cham- ber, another ship may arrive and enter the chamber concurrently. Thus the entrance times show a more ’batchy’ pattern than the actual arrival times. Dis- tribution fitting of the entrance times showed that a Poisson arrival process can be assumed. The overall time needed for a ship to enter one cham- ber, close the gates, raise or lower the water level, open gates and leave the chamber is 28.0 minutes. The action of operating the gates and adjusting the water level can assumed to be deterministic. From these numbers it can easily be concluded that utilization of the shiplift is relatively low for two long chambers. But the arrival process is not determin- istic, thus queueing occurs despite the low utiliza- tion. And especially when substituting one of the long chambers by a shorter one, the question is what the average waiting time is and also what the proba- bility for a non-acceptable waiting time/queue length is. THE PETRI NET MODEL Since there is no special simulation software for this problem, we decided to use Generalized Stochastic Petri Nets (GSPN) as described e.g. in [1, 4]. GSPN are a universal modeling language that allows a quick creation, validation and performance evaluation of models of arbitrary systems. In our case, commu- nication with non-simulationists has been necessary, thus a graphical representation and animation of the model was desirable. GSPN provide this graphical representation, that is easier to understand for non- specialists than e.g. the simulation code written in some programming language. In GSPN, the system state is modeled by tokens in places (small filled dots inside circles), i.e. the mark- ing. State changes are modeled by transitions (bars). If the state change needs some time, then a timed transition is used (unfilled bar), while for timeless state changes immediate transitions are used (filled bars). When an action occurs, transitions move as many tokens from and to places as indicated by the arcs connecting the places and the transitions. See e.g. [1, 4] for details of the dynamics of GSPN. Figure 1 shows the GSPN model of the shiplift as constructed with the tool TimeNET [2], which en- ables simulation of the GSPN as well as performance analysis (based on its Markov chain) and qualitative analysis. The transitions arrival_ds and arrival_us model the Poisson arrival process of ships from upstream and downstream, with a mean interarrival time of 29.6 minutes. Ships arrive at harbours denoted by the places harbour_ds and harbour_us. The mark- ing of places chamber_us, chamber_ds, chamber_ds2 and chamber_us2 indicate whether the current wa- ter level in chamber one/two is adjusted either to the upstream or downstream level. The transitions enterxy test via inhibitor arcs, whether a chamber is in the correct position and also whether the chamber is empty. If there is only one ship to enter a cham- ber, then this ship enters. If more than one ship is waiting, then the transitions enterxy decide based on specific probabilities which are derived from the given distribution of shiplengths (as discussed ear- lier), how many ships enter the chamber. Note that in the Petri net used here, all ships are uniformly modeled as tokens without any information, so ships cannot be distinguished with respect to their lengths. This approach introduces a certain level of abstrac- tion of the model, which was not easy to understand for the engineers concerned with the reconstruction of the shiplift. Thus we also built a more detailed model with colored Petri nets [3] of the Renew type [5], where each ship has been modeled as a colored token carrying more detailed information like the length of the ship. The loading of the chambers has also been modeled in detail, that means that it was tested for each ship at the front of a queue, if it still fits into a chamber or not. This detailed model showed nearly the same results, but it is much more complicated and less intuitive. However it gave the engineers more confidence in Petri net models. It is out of the scope of this paper also to explain the colored Petri net model. Once ships have entered a chamber, the filling or emptying of the chamber begins. This is modeled by the four deterministic transitions fill_chamber, empty_chamber, fill_chamber2, empty_chamber2, each taking 28.0 minutes. Chambers may only be op- erated if a token is present in place trigger_chamber / trigger_chamber2. Such token is generated when either ships entered the chamber, or waiting ships re- quest a chamber if all two chambers have the wrong water level. After the chamber’s operation time, the ships are released into places ds1, ds2, us1 and us2. The marking dependent arc weights ensure that always the proper number of ships is moved. RESULTS • First we validated the model by simulating the current configuration with two long chambers. The mean number of ships in one chamber in our model is then 0.91 for chamber one and 0.88 for chamber two. If a ship needs to request a chamber, then it will request only chamber one; this explains the slight asymmetry of these two values. The mean number of waiting ships (on both sides) sums to 1.09. Both the mean number of ships in the cham- bers and the mean number of waiting ships cor- respond very well to the measured data at the real shiplift. • Then we simulated the design alternative with one shorter chamber. The mean number of ships in the shorter chamber is then 0.86 and that in the longer chamber is 0.93. The overall number of waiting ships has in- creased to 1.32. (All simulations have been done with 98% confidence level and a maximal relative error of 5%.) CONCLUSION In this case study, design alternatives for the layout of a shiplift have been evaluated. Despite the shiplift having a low utilization, queueing occurs due to the stochastic arrival process of ships. It showed that also the alternative layout with less capacity (i.e. one shorter chamber) would suffice and only minimally raise queue length and waiting time. Thus the de- cision probably will be determined by financial and political aspects. The conclusion we draw from this case study is that is has been very convenient to use GSPN for this pur- pose. GSPN offer a universal formal modeling lan- guage making creation and debugging of the model faster and easier than e.g. using C-code. Further- more, GSPN have a graphical representation and an- imation at no extra cost. In our case, these benefits proved to be very useful for communication with the non-simulationists. REFERENCES [1] M. Ajmone Marsan, G. Balbo, and G. Conte. A class of generalized stochastic Petri nets for the performance analysis of multiprocessor sys- tems. ACM Transactions on Computer Systems, 2(2):93 – 122, 1984. [2] R. German, C. Kelling, A. Zimmermann, and G. Hommel. TimeNET — A toolkit for evalu- ating non-Markovian stochastic Petri nets. Per- formance Evaluation, 24:69–87, 1995. [3] K. Jensen. Coloured Petri Nets – Basic Concepts, Analysis Methods and Practical Use, Vol. 1: Ba- sic Concepts. EATCS Monographs on Theoret- ical Computer Science. Springer-Verlag, Berlin, 1992. [4] M. Marsan, G. Balbo, G. Conte, S. Donatelli, and G. Franceschinis. Modeling with General- ized Stochastic Petri Nets. John Wiley and Sons, Chichester England, 1995. [5] Renew – the reference net workshop. Website at www.renew.de. ha rb ou r_ ds ch am be r_ ds ch am be r_ us ch am be r_ 11 u s2 ds 2 ch am be r_ 12 ha rb ou r_ us ch am be r_ 21 ch am be r_ ds 2 ch am be r_ us 2 Sc hi ffe in 21 tr ig ge r_ ch am be r tr ig ge r_ ch am be r2 u s1 ds 1 ar riv al _d s en te r1 en te r2 2� 2� fil l_ ch am be r m ar k- de p. � m ar k- de p. � em pt y_ ch am be rm ar k- de p. � m ar k- de p. � en te r4 1 en te r4 2 2� 2� ar riv al _u s fil l_ ch am be r2 m ar k- de p. � m ar k- de p. � em pt y_ ch am be r2 m ar k- de p. � m ar k- de p. � en te r1 1 en te r2 1 2� 2� en te r2 2 2� 2� en te r1 2 4� 4� en te r4 4� 4� en te r3 1 4� 4� en te r4 3 4� 4� en te r3 2 de m an d_ us de m an d_ ds Figure 1: The Petri Net Model of the Shiplift (TimeNET) c0: Proceedings 15th European Simulation Symposium Alexander Verbraeck, Vlatka Hlupic (Eds.) (c) SCS European Council / SCS Europe BVBA, 2003 ISBN 3-936150-28-1 (book) / 3-936150-29-X (CD)