Len Gorney
POB 96 RD 1
Clarks Summit PA 18411

Queuing Theory,
the Science of Wait Control

Part 2: System Types

In part 1 we discussed the computer implementation of row and circular queues. Now, let us take a look at the structure of queues in the real world and see if they can be fitted to our previous programs. In the following discussion, the word queue refers to the waiting line in the system. The word facility refers to the service facility area located at the head of the queue.

System Types

There are four general types of queuing structures. The first, and simplest, is the single queue single facility System (figure 3). In this structure, there is one waiting line and one service area to be studied. A 1 pump gas station with one entrance is a real world example of this system.

Figure 3: A single queue single facility system with one waiting line and one service area.

We can extend this system to the single queue multifacility system (see figure 4). In this structure, customers line up in a single waiting line and are serviced at the first of a series of facilities. Upon departure from the first facility, the customers immediately enter another queue to await their turn at the second service facility. This insertion and deletion continues until the customer is eventually deleted; from the last facility and consequently the entire system. This structure is not unlike a cafeteria where you first line up for a sandwich, then line up for dessert, then for a drink, and finally, for the cash register.

Figure 4: Single queue multifacility system, in which the customer waits in a queue to use a facility, then waits in another queue for the second facility, and so on until all service facilities have been used.

Another basic queue structure is a multi-queue single facility system (see figure 5). This is the type of structure you see at a typical supermarket checkout counter area. Customers arrive at the queue with their purchases and choose one of many waiting lines. Each service facility offers the same service, that is, checking out the purchases, but each line holds different customers.

Figure 5: Multiqueue single facility system. An example of such a system is the supermarket checkout area. The checkout area has several service facilities, each with a corresponding queue, that all offer the same service.

The multiqueue, multifacility system in figure 6 is a combination of the previously mentioned structures. A number of initial queues feed into a series of facilities. When a customer enters a particular queue, that customer travels from each facility within that subsystem until the eventual deletion from the system. Once a customer is entered into a subsystem, that customer causes that subsystem to behave as does the single queue multifacility queue system.

Figure 6: Multiqueue, multifacility system. This system has a number of initial queues feeding into a series of facilities. A customer entering a particular queue stays within that particular subsystem until leaving the system.

Any waiting line can be fitted to one of the four queue structures just mentioned. Try it the next time you're waiting in a line.

After we are able to define the type of queue we have, the problem of analyzing the structure and arriving at answers most important in queuing problems is our next step. At this time we won't concern ourselves with the difference between a single server or a multiserver queue. The former represents a grocery store checkout counter arrangement where customers enter any line (usually the shortest or the fastest moving). The latter fits into the situation at a barbershop. One long line feeds into a large service area where a number of barbers (ie: the servers) wait for you to come to them.

Let's imagine a 1 pump gas station. At the start of the day, the operator (ie: server) opens the pump and waits for the first customer of the day to arrive. After some period of time, the first customer arrives and immediately drives up to the pump for service. This lucky first customer has no waiting time since the facility (at the head of the queue) is open and free of previous customers. The customer requires some period of time for service, and upon completion of this servicing time leaves the system. The operator sits back and waits for the next customer to arrive.

The second customer arrives, is immediately served, and leaves the system. If the only time a customer spends in a queue is the time required for service, no queue forms. What we need for a queue to form is to have customers arrive while there is a customer being serviced. Then a line will form with waiting customers. The queue will form based entirely upon the service requirements of the customer at the service area.

Randomness

A pure queuing problem requires that customer arrival and service times be different. In other words, while a customer is being serviced, other customers enter the system at random intervals during the simulation period to form a queue.

Formally speaking, the randomness of these arrivals follows a Poisson distribution and exponential interarrival times. Basically, this means that an arrival has an equal chance of arriving at the tail of the queue at any time during the simulation period of the problem. Typical nonqueue structures do not exhibit this random criterion. For example, a movie theater line is not a good queue problem because arrivals usually bunch up in a period 10 to 15 minutes before the new show starts. Therefore, during the simulation period, randomness is a key ingredient. Randomness causes the queue to lengthen and decrease based only on the service requirements of each customer.

Usually a customer must wait in a line at any business establishment before receiving the desired service. How the businessman treats these waiting customers is of prime importance as to the success or failure of most businesses. A typical customer will take one of the following actions when faced with a waiting line. The first action is to just wait in the line until service arrives. Once in line, that customer will remain in line until the end. The businessman has little worry over this customer because this customer will eventually be serviced and some profit will be realized.

A second alternative open to a waiting customer is for that customer to jockey from line to line. How many times have you seen this customer arrive at one queue, wait for a short period of time, move to another queue, wait again, then move again, and so on. This situation exists in the multiqueue system as is evidenced in a bank or large supermarket with many service facilities available for customer use.

The previous two actions should cause little concern. The customer remains in the system and will eventually be served, thereby yielding the business some profit. However, what happens when the customer leaves the system after entering or refuses to enter the system initially?

If a customer has entered the system and leaves before being serviced, that customer has reneged. This situation occurs quite often when the waiting lines are moving at a rate far too slow for the customers within the lines. The customer and possible profits are lost to the businessman when a customer's action takes him or her on this route.

The last, and most damaging to the businessman, is the situation where a customer doesn't initially enter the system. When a customer sees a long and slow moving line, that customer usually balks. This customer is surely lost because he doesn't even give the businessman a chance at the very outset.

Since time is money, the important questions relating to queuing systems must be solved with relation to the time involved in waiting and servicing customers.

What is the maximum amount of time a customer waits in a line? What is the average amount of time all the customers are expected to wait in line before being served and deleted? What is the maximum amount of service time for any one customer during a typical period of time? Any measurement involving customer waiting time and customer service time is vital to the success or failure of a business.

A Queuing Problem

The program shown in listing 3 is that of a typical queuing problem utilizing the circular queue as the queuing structure. What we may have here is a hypothetical 1 pump gas station. The system will therefore be described as a single queue single facility structure.

Listing 3: BASIC program that simulates a single queue single facility System such as a 1 pump gas station. The program incorporates several functions discussed in part 1.

1000 DIM Q(10)
1010 PRINT "MINUTES TO RUN SIMULATION=";
1020 INPUT M
1030 PRINT "MAXIMUM ARRIVALS/UNIT TIME=";
1040 INPUT A2
1050 PRINT "MINIMUM SERVICE TIME=";
1060 INPUT S2
1070 PRINT "MAXIMUM SERVICE TIME=";
1080 INPUT S3
1090 PRINT "QUEUE LENGTH=";
1100 INPUT H2
1110 PRINT "INPUT 1 FOR RUNNING OUTPUT, ELSE INPUT 0";
1120 INPUT P
1130 C = 0
1140 C2  =  0
1150 C3  =  0
1160 C4  =  0
1170 M2  =  0
1180 M3  =  0
1190 S4	 =  0
1200 H  =  H2
1210 T  =  H2
1220 FOR J2 = 1 TO H2
1230 Q(J2) = -9
1240 NEXT J2
1250 Q(T) = 0
1260 T = T - 1
1270 GOSUB 1610
1280 FOR J = 1 TO M
1290 FOR J2 = 1 TO H2
1300 IF Q(J2) = -9 THEN 1330
1310 C = C + 1
1320 Q(J2) = Q(J2) + 1
1330 NEXT J2
1340 C2 = C2 + C
1350 IF C <= C3 THEN 1370
1360 C3 = C
1370 C = 0
1380 IF P = 0 THEN 1410
1390 PRINT " PICTURE OF QUEUE AFTER ";J; " MINUTES"
1400 GOSUB 1680
1410 IF Q(H)<M3 THEN 1520
1420 M2 = M2 + M3
1430 C4  = C4  + 1
1440 S4  = S4  + S
1450 IF P = 0 THEN 1470
1460 GOSUB 1730
1470 GOSUB 2110
1480 GOSUB 1610
1490 IF P = 0 THEN 1520
1500 PRINT "PICTURE OF QUEUE AFTER DELETE"
1510 GOSUB 1680
1520 A3 = 1
1530 A = INT (RND(T) * A2
1540 IF A3 > A THEN 1580
1550 GOSUB 1900
1560 A3 = A3 + 1
1570 GOTO 1540
1580 NEXT J
1590 GOSUB 1730
1600 STOP
1610 S = INT (RND(1)*10) + (S3-9)
1620 IF Q(H) = -9 THEN 1640
1630 Q(H) = 0
1640 M3 = Q(H) + S
1650 IF P = 0 THEN 1670
1660 PRINT "REQUIRED SERVICE TIME=";S
1670 RETURN
1680 FOR J2 = 1 TO H2
1690 PRINT Q(J2);
1700 NEXT J2
1710 PRINT "TAIL=";T;"HEAD=";H
1720 RETURN
1730 PRINT C4;" FULLY SERVED CUSTOMERS IN ";J;" MINUTES"
1740 PRINT "MAXIMUM CUSTOMERS QUEUED=";C3
1750 M5 = M2/C4
1760 PRINT "AVERAGE WAIT TIME=";M5
1770 S5 = S4/C4
1780 PRINT "AVERAGE SERVICE TIME=";S5
1790 C5 = C2/J
1800 PRINT "AVERAGE NUMBER OF QUEUED CUSTOMERS=";C5
1810 RETURN
1850 REM
1860 REM    I N S E R T I O N    R O U T I N E
1870 REM
1880 REM CHECK TAIL AND HEAD POINTER VALUES
1890 REM
1900     IF H = T GOTO 1970
1910     IF H < T GOTO 2030
1920     IF T >= 1 GOTO 2030
1930     IF H = H2 GOTO 2080
1931 REM
1932 REM INSERT ITEM AT Q(H)
1933 REM SINCE QUEUE IS EMPTY
1934 REM
1940     Q(H2)=0
1950     T=H2-1
1960     GOTO 2050
1970     IF T<>0 0 GOTO 2000
1971 REM
1972 REM RESET POINTERS TO HEAD OF QUEUE
1973 REM
1980     H = H2
1990     T = H2
1991 REM
1992 REM CHECK IF Q(T) EMPTY FOR POSSIBLE INSERT
1993 REM
2000     IF Q(T) <> -9 GOTO 2080
2010     H = H2
2020     T = H2
2021 REM
2022 REM NORMAL TAIL INSERTION
2023 REM
2030     Q(T) = 0
2040     T = T - 1
2050     IF P = 0 THEN 2070
2060     PRINT "ARRIVAL"
2070     RETURN
2080     IF P = 0 THEN 2100
2090     PRINT "OVERFLOW"
2100     RETURN
2101 REM
2102 REM    D E L E T I O N   R O U T I NE
2103 REM
2104 REM CHECK POINTER VALUES FOR POSSIBLE DELETE
2105 REM
2110     IF H = T GOTO 2150
2120     IF H > 0 GOTO 2190
2130     H = H2
2140     GOTO 2180
2150     IF H <> 0 GOTO 2180
2160     H = H2
2170     T= H2
2171 REM
2172 REM DELETE FROM Q(H) IF Q(H) HAS AN ITEM
2173 REM ELSE QUEUE IS EMPTY, I. E. UNDERFLOW
2174 REM
2180     IF Q(H) = -9 GOTO 2240
2190     Q(H) = -9
2200     H = H - 1
2201 REM
2202 REM RESET POINTERS FOR NEXT DELETE
2203 REM
2210     IF H <> 0 GOTO 2260
2220     H = H2
2230     RETURN
2240     IF P = 0 THEN 2260
2250     PRINT "UNDERFLOW"
2260     RETURN
2270 END

[BASIC-Listing]

Past experience gives us some of the input parameters required for the problem solution. For example, our queue is dimensioned to ten locations, so only ten cars can fit in our service area. This parameter can be adjusted using input parameter questions at the beginning of the program. In addition to the queue length, the program asks for the minimum and maximum typical service times. The arrivals per unit time determine how many customers are arriving each minute during the simulation. The simulation is halted after the first parameter value is reached, namely, the amount of time to run the model.

Conclusion

For the serious reader, the list of reference material includes those texts which place a good emphasis on queuing theory. After digesting the ideas in this article, plunge into these texts. Now I can return to my reading queue and get to those lines of books and articles waiting on my bookshelf. I'm sure that somewhere out there is a line waiting for you!

BIBLIOGRAPHY

Cooper, Introduction to Queuing Theory, Macmillan, New York, 1972.
Cox, Smith, Queues, John Wiley and Sons, New York, 1961.
Gross, Harris, Fundamentals of Queuing Theory, John Wiley and Sons, New York 1974.
Harrison, Data Structures and Programming, Scott, Foresman, Glenview IL, 1973.
Hillier, Lieberman, Operations Research, Holden-Day, San Francisco, 1974.
Siemens, Marting, Greenwood, Operations Research, Macmillan, New York, 1973.
Wagner, Principles of Operations Research, Prentice-Hall, Englewood Cliffs NJ, 1975.

Queuing Theory, the Science of Wait Control

Part 2: System Types

Queuing Theory,
the Science of Wait Control