5.2 USING THE M / G / 1 MODEL
Perhaps the simplest type of server-to-customer queueing system is a singleserver system. Here requests for service are geographically distributed throughout the service region. The service unit may be prepositioned at a fixed location when idle or free, or it may be mobile (such as a patrolling police car). The unit is dispatched to service requests as they arrive, and queued requests are handled according to some queue discipline (such as FCFS). Service time consists of time to travel to the scene of the service request, on-scene service time, and perhaps followup off-scene time.
This type of system can often be modeled accurately employing the standard M / G / 1 model. A detailed example of this type of application was developed in Chapter 4 for the case of an ambulance service. However, sometimes the M / G / 1 model does not apply exactly because of its assumption of independent, identically distributed service times. In particular, for a service that only provides on-scene service (and no follow-up off-scene service) the time to service the first customer in a busy period may be different from the time to service the remaining customers.
We can see this in an emergency repair context. Suppose that an emergency repair unit (when idle) is dispatched from its home location to the scene of a required repair; the total service time random variable is the sum of the travel time from the home location to the repair site plus the on-scene time. During this first service time, a second repair request may occur, requiring a back-to-back assignment of the repair unit;1 in this case the unit would travel directly from its first repair site (a random location) to the second site. The total service time in this second case would be travel time from one random location to another plus the on-scene service time. Since the travel-time random variable would differ from the travel-time random variable for the first repair, so would the total service time be different. Assuming a FCFS queue discipline, any other service times during that one busy period would be distributed identically to the service time experienced by the second customer. A slight dependence of successive service times arises from the fact that one service time begins at the geographical location at which its immediate predecessor ends. However, as examples will indicate, this dependence is usually small enough to ignore in most applications.
In the situation described above, the M / G / 1 model "almost fits," with the exception that the first service time during a busy period is different from all remaining service times. Odoni has analyzed such a modified M / G / 1 queue in detail and, using transform methods, has developed expressions for the mean number in queue and the mean waiting time [ODON 69]. The results are summarized as follows:
Then we require, for steady state to exist,
2 < 1
Given this condition, we have
Paralleling the standard M / G / 1 queue, these results indicate that for this modified M / G / 1 queue, the mean wait and mean number in line depend on the two service-time distributions only through their means and variances. If these means are equal and if the variances are equal, the result reduces to the standard M / G / 1 result. You might try some limiting cases of parameter values to gain additional insight into the behavior of this modified M / G / 1 queue; a structured way of doing this is outlined in Problem 5. 1.
It is not difficult to propose additional modifications to queue behavior to arrive at a virtually intractable model. For instance, the solution for the M / G / 1 queue is not known for the case in which the queue discipline is "dispatch to the closest waiting customer." This is because successive service times are not independent, as discussed in Chapter 7.
1We assume that the likelihood of a dispatch occurring during travel back to the home location is negligibly small.