## 7.3.1 Event-Paced Simulation of a Spatially Distributed Queueing SystemWe now present an example that illustrates the event-paced method for advancing the clock as well as some ideas that are often used in the simulation of queueing systems. The specific example that we shall use is identical to the emergency
repair problem described in Section 5.2, with one exception: it will be
assumed that, whenever there is a queue of calls waiting for service at
a time when the repair unit is busy serving a call at point ( To be specific, let us assume that the service region in this case is a
2- by 1-mile rectangle (Figure 7.23); a right-angle metric is in effect,
with directions of travel parallel to the sides of the region; the
effective travel speed is constant at 20 mph; calls for service are
generated in a Poisson manner at the rate of three per hour; the
locations of calls for service are independent and uniformly distributed
over the service region; and the amount of time on the scene needed for
the emergency repair has the pdf shown in Figure 7.24. Times on the
scene needed for successive calls are statistically independent.
The total service time to a call consists of the sum of travel time to the location of the call plus time on the scene. Despite the independence of successive on-the-scene times, successive total service times are not independent, because of the "nearest-point" criterion of
priority. To understand why, observe that, after a call which requires a
long service time, it is more likely that the repair unit will be
dispatched to a relatively nearby point (owing to the increased
probability of several spatially distributed calls in queue).
Because of this dependence between service times, this situation cannot be analyzed (exactly) through classical queueing theory models. We shall therefore use simulation. Suppose that we wish to simulate this spatially distributed queueing system over a period of, say, 12 hours and to collect some statistics such as the average time between reception of a call and the instant when the unit arrives on the scene, the maximum observed queue length, and so on. We shall assume that at time It should be noted that service to a call begins as soon as the trip of the repair unit toward the location of that call begins. We shall use the index j to denote calls in order of reception by the
repair unit's dispatcher. Associated with call j is the time of its
arrival, t, and the
location of the call (_{j}x). The current location
of the repair unit
is denoted by (_{j}, y_{j}x). Then the travel time
needed to travel at 20 mph
to a call at (_{0}, y_{0}x) once the unit completes
service at a location (_{j}, y_{j}x) is given in minutes by
_{0}, y_{0}Finally, we shall use two random-number generators, one for probabilistic quantities related to time and the other for the locations of the incidents. We shall use r = 1, 2, . . .) and
_{1k}(kr = 1, 2, . . .),
respectively, to denote
random numbers provided by the two generators. It is important to keep
in mind that every appearance of _{2m}(mr or _{1k}r
in a logical box of a
flowchart implies that the computer must draw a new random number from
the appropriate random-number generator each time this box is entered during the
execution of the program.
_{2m}
The computer program that simulates the foregoing problem is now
outlined in flowchart form in Figure 7.25. The program consists of an
initialization step (upper left-hand box), a main program, and a number
of subroutines (subprograms). The main program-the "scheduler" -is
concerned with finding out which is the next "event" that takes place
and then instructs the computer to execute a subroutine accordingly. The
events of interest are
of four kinds: an arrival of a new call, the initiation of service to a
call, the completion of service to a call, and the end of the
simulation. The latter event occurs just once in the simulation.
Thus, the main program is just the logical box indicated as MP in Figure 7.25. Note that the actions that the computer takes upon the occurrence of each event are repetitive. For instance, following the arrival of a new call, at time t = t, the computer first records the time and
location of the call and then checks to find out whether the repair unit
is idle or not. If it is idle (_{nc}N = 0), it immediately assigns the newly
arrived call to the unit I = I + 1). In either case, the time of
arrival of the next call is projected
and we return to the main program.
_{ss} = t). If it is busy, the newly arrived call
must join the existing queue and the length of the queue must,
therefore, be increased by one (The reader should now review carefully the rest of the flowchart. It is
particularly important to gain an understanding of how the time, r sequence that controls the timing of events). We could, of
course, have used more than two random-number generators.
_{1k}How does the simulation end? Eventually, t, _{nc}t, _{ss}t, and _{sf}t. This
signifies that the simulation has run for the desired length of time and
that we can now tabulate and print the desired statistics and then stop.
This should also make clear to the reader the somewhat confusing reason
for using the number 999, to which _{l}t and _{ss}t are reset every once in a
while. Obviously, there is nothing special about the value 999: any
number greater than 720 would do. All that is required is a number large
enough to keep _{sf}t and/or _{ss}t from ever being chosen as the minimum of
the four variables when they are not supposed to be. We also make sure,
in this way, that the simulation will eventually end.
_{sf}
in the t subroutine. Note that this equation requires the generation
of two independent random numbers.
_{ss}We conclude this section by noting that the flowchart of Figure 7.25 can be easily modified to simulate a wide variety of other queueing situationsincluding much more complicated ones. We could, for instance, with the same basic logic simulate many cases involving classes of calls with priorities assigned according to class of the call, queueing systems with finite queue sizes, spatially distributed queueing systems with time-dependent arrival and service rates, and so on. Extensions of this type are explored in Problems 7.8 and 7.9. |