College and Research Libraries RONALD W. FORCE and JO ELLEN FORCE Access to Alternative Catalogs: A Simulation Model The advent of microfilm or on-line computer catalogs raises the question: How many terminals or readers are needed? A computer simulation model was developed to provide the library administrator with information to an- swer this question. Based on empirical data of arrival rates and service times, systems with two to fourteen terminals are simulated. The decision variables include average patron waiting time, number of patrons lost, and average terminal utilization . As LIBRARIES REPLACE CARD CATALOGS with microfilm or on-line computer-based catalogs, a new phenomenon must be dealt with by the library administrator: waiting to use the catalog. Although Bookstein pro- posed a model predicting the probability one will have to wait for a catalog drawer, 1 this rarely occurs in real life: there are sim- ply too many access points in a large card catalog. In a system using film readers or computer terminals , however, the number of access points is severely limited. The li- brarian is faced with the trade-off between investment in, and maintenance of, expen- sive equipment and patron dissatisfaction from excessive waiting times. The question of "How many terminals are enough?" is not amenable to solution by intuition. Morse presented analytical solutions of queuing models applied to book circulation and discussed performance measures of li- brary situations where queues develop. 2 Halperin discussed waiting line (queuing) theory in relation to the service points at a reference desk. 3 He used an analytical model that limits the number of service points. All analytical solutions to queuing Ronald W. Force is assistant director for pub- lic services, Washington State University Library, Pullman . ]o Ellen Force is visiting assistant pro- fessor, Forest Resources Quantitative Manage- ment Program, College of Forestry, Wildlife, and Range Sciences, University of Idaho , Moscow . 234 I problems require other simplifying assump- tions about arrivals and service times in order to solve the equations. Regazzi and Hersberger constructed a reference desk model for one or two service points using a manual simulation. 4 Thus one simulation (that is, one data point) is reported for each situation , and the simulation "runs" for only thirty minutes or twenty-five observations. Manual simulations have another draw- back: In order to have statistical validity , they must be repeated a large number of times, using random variation. Repeating these calculations the number of times re- quired is very tedious if not impossible in actuality. The accuracy and effectiveness of any model is dependent ·on how closely it simu- lates complex reality . We wish to discuss a computer simulation queuing model that can be used for any number of servife points and whose specifications can easily be varied to approximate the behavior of people in actual waiting lines. In this dis- cussion, we will refer to service points as terminals , although they could be film readers or book catalogs as well. CHARACfERISTICS OF THE MODEL Two types of empirical data are needed if the model is to accurately simulate reality: 1. Arrival rates: that is , the number of persons who arrive for service in a given time period. The data can also be expressed as an interarrival time, that is, the time be- tween arrivals. 2. Service times: the length of time needed for the user to accomplish the task. Arrivals Arrival rates at the catalog were collected in a large branch library over a period of several days. As expected, the arrival rates varied with the time of day-the afternoon and early evening being the busiest and the early morning and late evening the slowest. The day was divided into five time periods with different arrival rates: 8:00-10:00 a.m., 10:00 a.m.-1:00 p.m., 1:00-4:00 p.m., 4:00-8:00 p.m., and 8:00-10:00 p.m . Given enough data, as many time periods could be used as desired. The observations indicated that the as- sumption of a Poisson arrival process was acceptable and, th1..1s, was used in the simu- lation. Bookstein and Morse also assumed the Poisson distribution. 5 • 6 This distribu- tion assumes independent arrivals, and the probability that an arrival will occur at any given instant does not depend on the 10 15 Access to Alternatic,e Catalogs I 235 elapsed time since the previous arrival. This distribution is widely used in queuing models. Service Times The service time was based on 146 obser- vations of public terminal users in an operating system. These ranged from a few seconds to 60 minutes with a mean of 7.06 minutes. The GASP IV simulation program provides for storing the cumulative distribu- tion of the observed service times. This dis- tribution is exhibited in figure 1. Individual service times in the simulation were obtained by a Monte Carlo procedure as follows: When a new arrival occurs in the simulation, the computer generates a ran- dom number between 0 and 1. That number is then used in the program to select a service time for that arrival. For example, if the random number is 0.8 , the service time is 10.0 minutes (see dashed lines in figure 1). This prbcess is repeated for each arrival, using different random numbers to select different service times. In the case of a new system with un- 20 25 60 Minutes SERVICE TIME Fig. 1 Cumulative Distribution of Observed Service Times 236 I College & Research Libraries • May 1979 known service times, data could be extrapo- lated from similar systems, or one could as- sume a known distribution, such as a nor- mal or negative exponential. Queue Characteristics The model incorporates some assumptions about how people behave in waiting lines . There are two ways that people form queues. Either people wait behind each terminal, moving as a terminal becomes vacant or a nearby line becomes shorter, or they wait in a single line where they can move to the first open terminal. When the waiting line becomes too long, people will balk; i.e ., they leave, rather than join the line . If they are kept waiting too long in the line, they will renege, or .leave, after a certain period of time. With use of certain subjective impressions obtained during the collecting of service time observations, some fairly conservative assumptions were made about waiting be- havior. In simulation model A separate queues formed behind each terminal, and a line- hopping subroutine was included. Balking occurred if one person was waiting behind each terminal. Model B was developed to simulate the situation where the users form a single queue and move to the first avail- able terminal. In this model an arbitrary queue length of approximately half the number of terminals was allowed before balking occurred. The appropriate choice of a model for a given setting is dependent upon the physical arrangement of the ter- minals. In both models everyone was willing to wait in line for at least two minutes; how- ever, no one would wait more than five. The time of leaving if service had not begun was uniformly distributed between two and five minutes using a random process . That TABLE 1 ARRIVAL RATES IN BRANCH LIBRARY Time Periods 8:00-10:00 a.m. 10:00 a.m.-1:00 p.m. 1:00-4:00 p . m . 4:00-8:00 p . m. 8:00-10:00 p.m. Total Interarrival Times (Minutes) 15.00 6.00 3.30 4.30 10.00 Number of People 8.0 30.0 54.6 56.0 12.0 160.6 is, as many people would renege after wait- ing two minutes as after waiting five. Aver- age waiting times will always be rather low because they are calculated only for those patrons who remain for service in this simu- lation model. Output Summary statistics for the following parameters were obtained for each situation that was simulated: 1. Average waiting time per person. 2. Proportion of arrivals that had to wait for service. 3. The number who didn't wait because the line was too long (balking). 4. The number who left after waiting (re- neging). 5. Proportion of time each terminal was in use. To show how these data can be used for decision making, the model was first applied to the branch library using the observed ar- rival rates shown in table 1. Simulations of the fourteen-hour period were made for two, three, and four termi- nals. Thirty runs of each simulation were made using different random number generators in order to obtain statistically re- liable results. Simulation model A, one per- son waiting behind each terminal, was used for the branch library. The results are shown in table 2. TABLE 2 SIMULATION RESULTS WITH 161 ARRIVALS PER DAY Average Waiting Time Percent Who Have to Wait Number Who Balk Number Who Renege Average Percent Lost Average Terminal Utilization 0.20 min. 10.42% 0 4.4 2.70% 33.21% Number of Terminals 3 0.49 min. 23.24% 0.9 13.6 9.01% 41.41% 1.00 min. 40.95% 8.0 30.2 23.79% 51.81% Average waiting time is fairly low in all cases: one minute or less. However, in the case of two terminals, almost one-fourth of those who want service are frustrated. Most library administrators would consider this unacceptably high. The loss rate is bro- ken down by time period in table 3. It shows that for two terminals during the time period from 1:00 to 4:00 p.m., out of an average of 54.6 persons who arrive for service, 4.6 turn away because the lines are too long, and 13.1 give up after waiting in line. Thus 32.36 percent of the arrivals do not receive service during that time period. The addition of a third terminal reduces the overall loss rate to less than 10 percent, and fewer than one-fourth of those arriving have to wait at all (table 2). Even during the busiest time only 13.07 percent are lost (ta- ble 3). For a library manager the question then becomes: Is it worth the cost of adding yet a fourth terminal to reduce the overall loss rate to 2. 70 percent, or 4 out of 160 (table 3)? As the number of terminals increases, their average utilization decreases to the point that, with four terminals, they are in use less than one-third of the time despite the fact that virtually all potential users are being serviced. This is the case because an arrival rate of 160.6 per day and an average service time of 7.06 minutes requires only 1,133.84 minutes of terminal time, and 3,360 minutes (840 · 4) are available. The only way to increase utilization is to attract more users or increase service time. A different problem occurs in the case of two terminals. If all users were being ser- viced, again 1,133.84 minutes would be needed out of 1,680 minutes available, or 67.49 percent utilization. Because so many are lost. during peak periods, 51.81 percent is the average utilization. In order to reach maximum potential utilization of the termi- nals, the users who are lost would have to return during off-peak periods. To show how the same technique can be used with a larger system, a main library with the hypothesized arrival rates shown in table 4 was simulated. Simulation model B, i.e., people waiting in a single queue, was used for this simulation. Since the arrival rate is 3.3 times that of the branch library, the intuitive solution would be to provide Access to Alternative Catalogs I 237 "' ~ s: ~~~~~ 0) ~ ·~ t- c-:ic-ic-it-=ci ~ ~ ~M~~ Cl ~ ~ ...l - ·= ~gn;:;gs~ ~ ~M ~ 0 .....;-.::t'c-:io:ic-:i a) "' .... ~ t:l... "' ~ s: .,. ·e og~~g 0 t- ~ ci-.::t'c-ici c-i "' M""'~M~~ s: ~·~ cic-:ic-:ic-i.....;c) "' ~~ M .... ~ "' s: "' r:.:; w _g ] ~Mtr.lM""'~ > :::"'E c).....;(()lf)c)c-;i < ... "' ~ w "' .... ...:l ..0 0 ; :t z M ~ -; w w s: o~~~C'!~ Vl .,. ·e ...:l 0 ~ o~~o""' ~ :t < E-< E-< z 0 Vl u ~ -; s: 0~~~~~ (:::: ~·~ O""'MOOO < "' .... .... fJ) -" -; I:Q 0 ~ ..c: :::M·§ 00~~0~ ... ... "' "' 6 ..., " z ~ s: .,. ·e 000000 ~ - -------------- ----------------------------~ 238 I College & Research Libraries • May 1979 TABLE 4 ARRIVAL RATES IN MAIN LIBRARY Time Pe riods 8:00-10:00 a.m . 10:00 a.m.-1:00 p.m. 1:00--4 :00 p.m . 4:00-8:00 p .m. 8:00-10:00 p.m. Total Inte rarrival Times (Minutes) 4.50 1.80 1.00 1.30 3.00 Numbe r of Pe ople 26.7 100.0 180.0 184 .6 40.0 531.3 3.3 times as many terminals, that is, ten. However , as table 5 shows , a comparable loss rate can be achieved with seven termi- nals . When the arrival rate is doubled again (table 6), the results are as shown in table 7. During the busiest time, someone is arriv- ing every .thirty seconds for three hours. Yet once again the arrival rate does not double the terminal requirement. IMPLEMENTATION ISSUES The model was run on an IBM 370/168 operating under the MVS operating system and using the GASP IV simulation lan- guage. 7 After development and debugging of the program, the CPU time (i.e . , time required to compute, link, and execute the program) for the simulations reported here ranged from ten to twenty-five seconds. Lo- cally this cost approximately five dollars per simulation. In order to implement such a model to aid library decision making, a library man- ager must first collect the necessary obser- vations or estimate arrival rates and service times. Then someone with a background in industrial engineering or operations re- search who· has access to a computer system (which has available the GASP IV simula- tion language or another discrete state simu- TABLE 6 DOUBLE ARRIVAL RATES IN MAIN LIBRARY T ime Pe riod s 8:00-10:00 a . m. 10:00 a.m.-1:00 p.m. 1:00-4:00 p.m . 4:00-8:00 p .m . 8:00-10:00 p.m. Total Inte rarri val Times (Minutes) 2 .25 .90 .50 .65 1.50 Numbe r of Pe ople 53.3 200 .0 360.0 369.2 80.0 1,062.5 lation language) can easily design the model and write the program. It is important to note that even the most carefully planned simulation that is based on present patron behavior may fail to predict future user behavior when conditions change . Examples of such changes are : 1. When a complete union catalog can be accessed in all system branches that have a terminal, patrons may begin to use the most convenient branch, whereas previously it would have been necessary to go to the cen- tral union catalog. Thus arrival rates for the branch libraries and the central location would then be altered . 2. Users may find a new type of catalog easier or more difficult to use than a card catalog, and then service times may be shorter or longer than those anticipated from observations of users at a card catalog. 3 . The novelty of a computer terminal or film reader may attract more users. In some cases the convenience of being able to search large numbers of items while remain- ing seated in one location may encourage users to perform protracted searches that would not be observed at a card catalog. Many of these hypothetical situations can be explored because of the ease with · which system variables can be altered in the model and the relatively low cost of each TABLE 5 SIM ULATION RES ULTS WITH 531 ARRIVALS PER DAY Maximum Queue Length Average Waiting Time Percent Who Have to Wait Number Who Balk Number Who Renege Average Percent Lost Average Terminal Utilization 6 3.0 0.70 min. 37.82% 36.6 36.0 13.66% 63.63% Number of Terminals 7 4 .0 0.52 min . 29.57% 13.3 27 .0 7.57% 58.40% 10 5 .0 0. 12 min . 8.47% 1.5 5. 1 1.24% 43.99% Access to Alternative Catalogs I 239 TABLE 7 SIM ULATION RESULTS WITH 1,062 ARRI VALS PER DAY Maximum Queue Length Average Waiting Time Percent Who Have to Wait Number Who Balk Number Who Renege Average Percent Lost Average Terminal Utilization simulation. The consequences of equipment distribution or potential shifts in user be- havior can be predicted before changing to an alternative catalog and making the costly investment in terminals or readers. Com- 12 6.0 0.67 min . 40.73% 41.0 49.7 8.53% 68.13% Number of Te rminals 14 7.0 0.40 min. 27 .23% 13.9 26 .3 3.78% 61.60% puter simulation models give the library administrator a powerful but economical tool for anticipating the impact of new technologies on the library user and the li- brary budget. REFER ENC E S 1. Abraham Bookstein , "Congestion at Card and Book Catalogs: A Queuing Theory Approach ," Library Quarterly 42 :316-28 (July 1972). 2. Philip M . Morse , Library Effectiveness: A Systems Approach (Cambridge , Mass. : MIT Press , 1968). 3 . Michael Halperin , "Waiting Lin e s ," RQ 16:297-99 (Summer 1977). 4 . John J. Regazzi and Rodn e y Hers berger, "Queues and Reference Service: Some Impli- cations for Staffing, !' College & Research Li- braries 39:293-98 (July 1978). 5. Bookstein, "Congestion ." 6. Morse, Library Effectiveness. 7. A. Alan B. Pritsher, The GASP IV Simulation Language (New York : John Wiley & Sons , 1974).