PLANNING A N AUTOMATED STORAGE AND RETRIEVAL SYSTEM AT UBC LIBRARY By Ying Liu B.E. in Electronic Engineering, Tianjin University 1992 A THESIS SUBMITTED IN PARTIAL FULFILLMENT OF THE REQUIREMENTS FOR THE DEGREE OF MASTER OF SCIENCE IN BUSINESS ADMINISTRATION in THE FACULTY OF GRADUATE STUDIES SAUDER SCHOOL OF BUSINESS We accept this thesis as conforming to the required standard THE UNIVERSITY OF BRITISH COLUMBIA April, 2004 © Ying Liu, 2004 Library Authorization In presenting this thesis in partial fulfillment of the requirements for an advanced degree at the University of British Columbia, I agree that the Library shall make it freely available for reference and study. I further agree that permission for extensive copying of this thesis for scholarly purposes may be granted by the head of my department or by his or her representatives. It is understood that copying or publication of this thesis for financial gain shall not be allowed without my written permission. Name of Author (please print) Title of Thesis: Degree: Date (dd/mm/yyyy) TlfUiuviAa ^ Master of -A^tOWflct-ecl ^ttrry Qu^Jj &e-tf7-eW $d •e^t Department of SOMA^T SCXOQ [ The University of British Columbia Vancouver, BC Canada ^ Year: Bu$ir^A<> XOO $~ ABSTRACT The university of British Columbia (UBC) Library plans to install an Automated Storage and Retrieval System (ASRS) at its Irving K. Barber Learning Centre. The system is intended to store 1.4 million volumes of materials, 0.8 million of which have already been identified. The Centre for Operations Excellence (COE) was asked to assist in the design of the system, to recommend desired staffing levels at the service desks and to assist in the selection of the remaining 0.6 million volumes of materials that should be stored in the system. In the ASRS, materials are stored in bins, and we have used stratified sampling in order to obtain the desired distribution of bin heights in the system. We have then formulated the overall bin configuration problem as an integer programming problem, and have used branch and bound and local search to find an optimal system configuration. Two discrete-event simulation models were constructed, using Arena 6.0, to gain insight into the operation of the system, and to recommend staffing levels at the circulation and reference desks, which ensure acceptable service levels. Finally we have used staffing levels and service level criteria to identify the remaining 0.6 million volumes of that should be stored in the system. TABLE OF CONTENTS ABSTRACT -. ii TABLE OF CONTENTS '. iii LIST OF TABLES iv LIST OF FIGURES v ACKNOWLEDGEMENT vii 1. INTRODUCTION 1 2.1 Project Background 3 2.2 Introduction to the Automated Storage and Retrieval System 3 2.3 Problem Definition 6 2.4 Job Responsibilities of Library Staff at the Circulation Desk and Reference Desk at Irving K. Barber Learning Centre after the System Is in Operation 7 2.5 Service Time and Customer Processing Time 8 3. LITERATURE REVIEW 9 4. METHODOLOGY 11 4.1 Bin Selection 11 4.2 Staffing Levels and Selection Rule 16 5. RESULTS 20 5.1 Bin Selection 20 5.2 Results from the Simulation Models 21 6. CONCLUSIONS 30 6.1 Bin Recommendations 30 6.2 Staff Scheduling 32 6.3 Selection Rule '. 34 7. REQUIRED STAFFING LEVELS USING QUEUEING THEORY 35 REFERENCE 41 APPENDIX A - PROCESS MAPS 43 APPENDIX B - SAMPLING RESULTS OF MATERIALS' HEIGHTS 45 B.l Materials Excluding Archives and Special Collections and Microforms 45 B.2 Archives and Special Collections 46 B.3 Microforms 49 B. 4 Bin Configurations 50 APPENDIX C- ARRIVAL RATES 60 C. l Circulation Desk 60 C. 2 Archives and Special Collections Reference Desk 69 APPENDIX D SIMULATION MODEL- USER GUIDE 71 D. 1 Introduction 71 D.2 Logic Overview 72 D.3 Animation Screen 73 D.4 Shortcut Keys 74 D.5 Running Result Report 75 D.6 Dynamic On-screen Displays 75 LIST OF TABLES Table 4-1 Table 5-1 Table 5-2 Table 5-3 Table 5-4 Table 5-5 Table 5-6 Table 6-1 Table 6-2 Table 6-3 Table 6-4 Proportion of Each Height Category in a Preliminary Sample 15 Sampling Result 20 Estimated Proportions of Bin Heights' for Different Time Horizons 20 Maximum Waiting Time at the Initial Stage (65s, 120s) 22 Maximum Waiting Time at Final Stage (65s, 120s) 25 Maximum Queue Length in a High Month in High Season (65s, 120s) 28 Maximum Queue Length in a High Month in High Season (40s, 65s) 29 Bin Configuration for a 5-year Horizon 30 Bin Configuration for a 10-year Horizon 31 Bin Configuration for a 15-year Horizon 31 Staff Schedule in January, February, March, October and November (High Season) 32 Table 6-5 Staff Schedule in April and September (Middle Season) 32 Table 6-6 Staff Schedule in May, June, July, August and December (Low Season) 33 Table 6-7 Staff schedule in January, February, March, October, November (High Season).... 33 Table 6-8 Staff Schedule in April and September (Middle Season) 33 Table 6-9 Staff schedule in May, June, July, August and December (Low Season) 34 Table 7-1 System Performance with Dedicated Staff Member 37 Table 7-2 System Performance with Same-task Servers Derived by Simulation 38 Table 7-3 Percentage of Patrons Waiting Less Than 5 Minutes in Peak Hours in a High Month in High Season Based on Queueing Model 39 Table 7-4 Service Levels for ASRS Patrons in Peak Hours in a 39 High Month in High Season Derived from Simulation 39 Table B-1 Heights Proportion of Materials Excluding Archives and Special Collections and Microforms 45 Table B-2 Proportion of Required Bins for Materials Excluding Archives and Special Collections and Microforms 46 Table B-3 Type 1 Box 47 Table B-4 Number of Bins Required 47 Table B-5 Forecast Number of Bins for Different Years Horizons 49 Table B-6 Final Number of Bins Required Considering Future Growth 49 Table B-7 Proportion of Each Height Category 52 Table B-8 Solutions of the Linear Programming Relaxation Problem 54 Table B-9 Number of Tiers in Each Row 55 Table B-10 Different Scenarios for Total Number of Tiers in Each Row 55 Table B-11 Results of Scenario 6 58 Table B-12 Results of Scenario 7 58 Table C-l Seasons and Representatives 62 Table C-2 Daily Arrival Rates at the Circulation Desk 67 Table C-3 Arrival Rates at the Archives and Special Collections Reference Desk 69 Table D-l Shortcut Key List 75 iv LIST OF FIGURES Figure 2.1 The Automated Storage and Retrieval System 4 Figure 2.2 The Layout of ASRS at The Irving K. Barber Learning Centre 5 Figure 2.3 Locations of Materials That Will Be Initially Stored in the ASRS 5 Figure 2.4 Relationship Between Customer Processing Time and Service Time 8 Figure 4.1 Stratified Sampling Plan 12 Figure 4.2 Conversion Between Space Length and Volumes 14 Figure 4.3 Maximum Number of Requests Processed in a Day Using Different Number of Representative Stations 17 Figure 5.1 Maximum Queue Length in Front of Circulation Desk 21 Figure 5.2 Maximum Queue Length in Front of Circulation Desk 22 Figure 5.3 The Impact of Self-checkout to Maximum Queue Length 23 Figure 5.4 Maximum Queue Length in Front of Circulation Desk at Final Stage 24 Figure 5.5 Maximum Queue Length in Front of Archives and Special Collections Reference Desk '. 26 Figure 5.6 Maximum Queue Length in Front of Archives and Special Collections Reference Desk .• 26 Figure 7.1 Required Number of Staff at the Final Stage Given Different Circulation Interval for Added Materials 40 Figure A. 1 Borrowing Process 43 Figure A.2 Return Process...„ 44 Figure B.l Method 1 of Placing Type 1 Box in a Bin 48 Figure B.2 Method 2 of Placing Type 1 Box in a Bin 48 Figure B.3 Percentage of Different Materials Considering a 5-year Growth for Archives and Special Collection 51 Figure B.4 Percentage of Different Materials Considering a 10 -year Growth for Archives and Special Collection 51 Figure B.5 Percentage of Different Materials Considering a 15-year Growth for Archives and Special Collection 51 Figure B.6 Branch Tree to Select Scenarios with Feasible Solutions 57 Figure C. 1 Open shelves and Storage Locations Average Daily Requests and Renewals 60 Figure C.2 Average Daily Requests and Renewals for Materials on Open shelves and in Storage Locations 61 Figure C.3 Daily Arrivals of Open-shelf Patrons in a High Month in High Season 62 Figure C.4 Daily Arrivals of Open-shelf Patrons in a Low Month in High Season 63 Figure C.5 Daily Arrivals of Open-shelf Patrons in Middle Season 63 Figure C.6 Daily Arrivals of Open-shelf Patrons in Low Season 64 Figure C.7 Daily Requests in a High Month in High Season 65 Figure C.8 Daily Requests in a Low Month in High Season 66 Figure C.9 Daily Requests in Middle Season 66 Figure CIO Daily Requests in Low Season 67 Figure C.l 1 Hourly Arrivals' Pattern in a High Month in High Season 68 Figure C. 12 Hourly Arrivals' Pattern in a Low Month in High Season 68 Figure C.l3 Hourly Arrivals' Pattern in Middle Season 68 Figure C.14 Hourly Arrivals' Pattern in Low Season : 68 Figure C.15 Average Daily Requests for Archives and Special Collections Figure D.l Screen Shot of Animation Figure D.2 Screen Shot of Statistic Data 69 74 76 vi ACKNOWLEDGEMENT First, I would like to thank the Centre for Operations Excellence for offering me the extraordinary opportunity and strong support to work on an interesting project. I would like to express my appreciation to my faculty advisor, Professor Daniel Granot, whose guidance and support made the completion of the project and thesis possible. Special thanks go to Aimee Zhou for her sincere advice and assistance to my work. I would also like to thank Professor Martin Puterman and Professor Alexandre Carvalho for giving me key ideas in designing the sampling plan. My thanks also go to Mats Gerschman, the Associate Director of the Center for Operations Excellence, for coordinating and for providing his guidance throughout various stages of the project. I also would like to acknowledge Professor Anming Zhang for his time and input as my thesis committee member. I would like to thank UBC Library for providing the research opportunity. Special thanks go to Darrel Bailie for his time and support and the UBC Library System Division. I sincerely appreciate the valuable information and experiences from Eric Willis and Davis Douglas at the California State University, Northridge, and Daryl Privott at the University of Nevada, Las Vegas. In addition, I acknowledge Todd Hunter from HK Systems for helping me understand the operation of the Automated Storage and Retrieval System. Next, I would like to express my thanks to my classmates. Thanks especially to Junko Fukui Innes, Liping Liang, Michael Chen, and Tom Mojica for their help and encouragement. My thanks also go to Andrew Gray and Dan Beck who have given me key assistance in the project. Finally, I would like to express my gratitude to my family. vii 1. INTRODUCTION Automated Storage and Retrieval Systems (ASRS) have been widely used in the United States and western European industrial settings since the 1960s. In the 1970s, such a system was first introduced for library applications, but turned out to be a failure. In 1988, with the improvement in technology, a modern ASRS was successfully implemented at the library of California State University, Northridge. In the 1990s, three more universities in the United States installed ASRS. To find out more about the evolution and implementation of ASRS in university libraries, see e.g. [19]. In 2003, UBC Library - the second largest academic library in Canada - decided to install an ASRS to store slow moving materials, mainly to solve a space limitation problem. The system was designed to have eight rows of bins, to hold materials of different heights. UBC Library has sought a recommendation, from the Centre for Operations Excellence (COE) at UBC, what should be the bins' heights, and the number of bins of each height. To answer these questions, the COE adopted Stratified Sampling to find out the heights' distribution of slow moving materials which were already designated to be stored in the ASRS. Based on the sampling results and estimation of future growth, the COE has provided recommendations on the selection of bins' heights and corresponding number of bins of each height. Currently, the slow moving materials at the UBC Library are stored in several locations and some of them are not circulated. After the system is in operation, those materials will be consolidated at the Irving K. Barber Learning Centre and will become available for circulation. The slow moving materials are separated into two major categories: Archives and Special Collections and non-Archives and Special Collections. Patrons of the former category will pick up materials from the Archives and Special Collections reference desk. Patrons of the latter category will pick up materials from the circulation desk, and will be referred to as ASRS general patrons in this thesis. Due to volume growth and consolidation, the arrival rates at the reference desk and the circulation desk will increase. Therefore, it is necessary to plan for new staffing levels. Based on the analysis of past record for arrivals, an entire year was divided into high, middle and low seasons and representative months were selected in each season. For each l representative month at the circulation desk, the distribution of daily arrivals was fitted and the 95 percentile point was selected to represent daily arrivals. Hourly arrival rates were then analyzed to obtain the daily arriving pattern in a day to determine the staff scheduling. A similar analysis was done for the reference desk. Two simulation models were developed to represent the system's operation and the borrowing process. The service levels for different customer processing times and different number of staff members were estimated and recommendations on staff scheduling in the different seasons were provided. Finally, according to UBC Library's plan, an additional 0.6 million volumes of materials should be identified to be put in the ASRS, in addition to the 0.8 million volumes of materials which were already identified to be stored in the system. A selection rule for the additional 0.6 million volumes of material should be determined. In this project, these additional materials were identified by examining their effects on service level. More specifically, we have evaluated the service level of the system as a function of the circulation intervals of the additional materials. Based on our findings, it was recommended that the circulation interval of the additional materials should be longer than 13 years. 2 2. BACKGROUND 2.1 Project Background The UBC Library is the second largest research library in Canada. It consists of 21 branches and divisions at UBC campus and at other locations. Its collection includes 4 million books and journals, 4.9 million microforms, over 1.5 million maps, videos and other multimedia materials, as well as over 33,500 subscriptions by the end of year 2002. With the growth of library collections, the lack of library space could not be ignored any more. However, there are about one million of materials on shelves that are not circulated for several years. To solve the issue of space limitation, UBC Library plans to install an Automated Storage and Retrieval System (ASRS) at the Irving K. Barber Learning Centre (currently called Main Library, a branch of UBC Library) to store slow moving materials. 2.2 Introduction to the Automated Storage and Retrieval System Automated storage and retrieval technology has been used in the industrial world since the 1960s [19]. From the 1990s, it has become an option for libraries to solve storage problems [19]. In an ASRS, a storage unit is either a bin or a shelf, depending on the supplier of the system and the customer's requirement. UBC has selected the bin as the storage unit (Figure 2.1). Bins are contained in frames. The frames are separated into bays by a vertical division and into tiers by a horizontal division. Two rows of frames share one crane. The crane moves back and forth along the aisle between the two rows of frames to retrieve the requested bin and put it onto the designated workstation. When the retrieved bin is no longer needed, it will be returned to its original location by the crane. In ASRS, materials can be either randomly stored or stored in fixed bins, while the location of each bin is fixed. Items and bins are linked by barcode. When an item is put into a bin, both the item's barcode and the bin's barcode are scanned and the computer set up a link between the item and the bin. Next time when the item is requested, the crane will be instructed to pick up the 3 right bin. When an item is removed from a bin, both barcodes will be scanned as well to remove the link. The ASRS that will be installed at the Irving K. Barber Learning Centre will consist of four aisles, where each aisle consists of two rows. Therefore, there will be eight rows in total. In the original plan, two rows will have 59 bays and the other six rows will have 62 bays. Archives and Special Collections will be stored in the bottom three rows shown in Figure 2.2. In this paper, the bottom row is named Row 1 and the uppermost row in the figure is named Row 8. The system will hold 0.8 million volumes of materials at the initial stage and is expected to hold 1.4 million volumes of materials at the final stage. The sources of the 0.8 million volumes of materials are shown in Figure 2.3. When the system is in operation, patrons will request materials in the system through online catalogue. The requests will initiate the system and the right cranes will be instructed to complete the requests. Crane Bays Figure 2.1 Rows The Automated Storage and Retrieval System 4 | -J |.J I I -r- Aisle S3? , Figure 2 . 2 \_f\''' 11 111 The Layout of ASRS at The Irving K. Barber Learning Centre 0.8 million volumes of materials Archives and Special Collections Microforms Other slow moving materials Storage Location MN7 Figure 2 . 3 Open shelves MNA&MNB& MNK Locations of Materials That Will Be Initially Stored in the ASRS 2.3 Problem Definition 2.3.1 Bin Selection Materials will be stored in bins in the ASRS. The length and width of each bin are fixed at 4' x 2', while the heights of the bins can be different. The height of the space for installing the system has been predetermined. Therefore, the more high bins are selected, the fewer tiers the space is able to hold; Thus, the system will have a lower capacity. UBC Library has set the lowest bins to be of a six-inch height, which will be used for storing microforms, and the highest bins are set to be of a sixteen-inch height. The Library needs advice on the selection of one or two additional heights of bins and the number of bins for each height. 2.3.2 Staffing Levels Slow moving materials include microforms, Archives and Special Collections, journals, inactive serials, and so forth, and are currently stored on several floors at the Main Library. Patrons for Archives and Special Collections are served at the Archives and Special Collections reference desk. If a patron needs an item, s/he fills in a slip and submits to a staff member at the reference desk. Then the staff member figures out where the item is located and goes to the right shelf to fetch it. No patrons are allowed to access the shelves. After the ASRS is installed, requested materials will be sent by a crane to a designated workstation close to the reference desk. Therefore, it will save staffs time. On the other hand, the number of volumes for Archives and Special Collections is increasing each year, which implies a possible increase in the number of patrons requesting service. Thus, it is necessary to estimate the required number of staff members that should be operating at the reference desk after the system is in operation. Some of the slow moving materials are only browsed in the library and not allowed in circulation. Others are only accessible by library staff, as is the case for the Archives and Special Collections. After the ASRS is installed, those materials will be consolidated into the system and cannot be browsed any more. Therefore, there will be far more patrons coming to the circulation desk and the staffing levels will have to increase. In this project, a year was divided into high, middle and 6 low seasons based on past arrivals data, and optimal staff scheduling is determined for each season. The actual job assignment in the UBC Library, which will result with the recommended staffing levels at the circulation desk, is beyond the scope of the project. 2.3.3 Selection Rule Recall that of the 1.4 million volumes of materials that will be stored in the ASRS at UBC Library, about 0.6 million volumes of materials have yet to be identified. Different criteria can be used to decide upon the additional materials that should be added, and we used the staff requirement criterion. Naturally, the more frequently items are used, i.e., the shorter are their circulation intervals, the more staff members are required to achieve the same service level. Thus, in this project, we examined the relationship between the circulation intervals of the 0.6 millions of additional materials and staffing levels to achieve a given service level, in order to set a lower limit for the circulation interval of these materials. 2.4 Job Responsibilities of Library Staff at the Circulation Desk and Reference Desk at Irving K. Barber Learning Centre after the System Is in Operation 2.4.1 Circulation desk Patrons arriving at the circulation desk may request different services. For example, patrons coming from open shelves are provided by checkout service from the library staff. The service provided to patrons requesting items in the ASRS will be different, as displayed in Figure 2.4. There may also be patrons requesting information, to pay fines, to renew borrowed materials, and so forth. In this project, only services for open-shelf patrons, including renewal, and ASRS patrons are considered. 2.4.2 Archives and Special Collections Reference Desk Staff members at the reference desk provide different types of services as well. If a patron requests an item from the compact shelves, a staff member will go to the right shelf to fetch the 7 item. If a patron requests an item from the ASRS, the staff will provide the same service as the circulation staff does for ASRS general patrons. The staff members are also responsible for questions asked over the phone, email or in person. In this project, only services provided for compact-shelf patrons and ASRS patrons are included. 2.5 Service Time and Customer Processing Time The service provided to ASRS patrons could be different based on the situation. Figure 2.4 describes the services that could be provided for ASRS patrons as well as displaying the relationship between the service time and customer processing time under different conditions. Customer processing time The stall'member finds the item on the shelf. Checkout The patron leaves. Figure 2.4 Relationship Between Customer Processing Time and Service Time 8 3. LITERATURE REVIEW As previously mentioned, one of the objective of the project carried out by the COE for UBC Library is to find the optimal new staffing levels at the circulation desk after the ASRS has been installed. Such a staffing problem, wherein we seek the optimal, time dependent, number of staff to serve customers, is often refereed to as the operator staffing problem, and has many applications. Below, we briefly report on several applications of this problem and approaches used to analyze it. Kolesar et al. (1975) studied the problem of scheduling police patrol cars to meet specified service standards at each hour of the day in New York City. In this paper, the patrol environment was viewed as a complicated multiple-server queueing system and an M/M/s queueing model was solved numerically with time-dependent parameters. The authors showed that one specific measure of service performance was quantitatively related to the number of cars fielded and how this relation could be used to generate estimates of the number of cars required at each hour of the day to obtain desired police performance levels. Buffa et al. (1976) proposed a stepwise approach to employee scheduling, in which the demand rates were forecasted period-by-period, and then the forecasted demands were converted to period-by-period minimum employee requirements. This approach was later referred to as the stationary independent period by period (SIPP) approach and led to extensive further studies on queueing effects in dynamic (control) models. Agnihothri and Taylor (1991) followed this approach to find the optimal staffing levels to handle daily call arrivals in Lourdes Hospital. The authors grouped consecutive intervals into different periods, where intervals in the same period had similar arrival rates. Thus arrivals can be viewed as stationary. An M/M/s model was used in each period to find the minimum number of staff members to meet the service target. Green et al. (1991) pointed out that a stationary approximation underestimated delays even when the arrival rate was only modestly non-stationary. They proposed an approximation for long-run average performance measures called the pointwise stationary approximation (PSA) for queues 9 with non-stationary arrivals to measure long-run average performance. Such approximation works very well when the arrival rate changes sufficiently slowly relative to the service time. Mason et al. (1998) used a simulation system, embedded within a heuristic search, to determine minimum staffing levels for arrival and departure work areas at the Auckland International Airport. Finally, we note that the Centre for Operations Excellence (COE) studied the staff scheduling problem at UBC Library (Guo, 2003). In this study, an M/M/s model was employed to find the minimum required number of staff to meet a certain service level. In our project, since staff members provide different service to different patrons, simulation turns out to be a more convenient tool to tackle the scheduling problem. 10 4. METHODOLOGY For the bin selection problem, a statistical. sampling method is used to find out the heights' distribution of slow moving materials. Then, an integer programming methodology, coupled with a rudimentary local search is used to get a good solution for the system's bin configuration. To obtain the staffing levels and selection rule for the storage of the additional 0.6 million volumes of materials, simulation seems to be a natural tool for the following reasons: first, when ASRS patrons arrive at the desks, it is difficult to know whether the items requested are available. Therefore, it is hard to estimate the service time for those patrons. In the simulation model, there is an imbedded clock and the software has time record function. Thus, the time each patron reaches a desk and the time each patron leaves can be recorded and the service time for each patron can be derived; second, the customer processing time and arrival rates are not available as the system has not been in operation. It is convenient to use a simulation model, wherein different scenarios can be easily investigated, by changing parameter values, in order to gain an insight into the performance of the whole system. 4.1 Bin Selection In order to select the bins' heights, the proportions of materials of different heights are required. We assume that the 0.8 million volumes of materials selected by UBC Library at the initial stage are good representatives of the total 1.4 million volumes of materials for deciding upon such proportions. The 0.8 million volumes of materials are first separated into three groups (refer to Figure 2.3): Group 1: Microforms Group 2: Archives and special collections Group 3: Other materials including books, journals, inactive serials, etc. 4.1.1 Sampling Design Since the materials are divided into three groups and located in different locations, Stratified ll Sampling turns out to be the most suitable method in this situation. 4.1.1.1 Review of Stratified Sampling In Stratified Sampling, the entire population is divided into several strata. The sum of the population of all the strata equals to the entire population. The simplest way of sampling is to select samples independently from each stratum (Figure 4.1). Figure 4.1 Stratified Sampling Plan Suppose the population of N is divided into H "layers" and N i + N2 + ... + N H = N, and samples are independently selected from each stratum to find out the proportion of a specified height category /, then the proportion of the total stratified samples, pj, is equal to the weighted sum of the proportion of the samples, p ', in each stratum (4-1), and the variance of the total h stratified samples is equal to the weighted sum of the variance of the sample proportion in each stratum (4-2). 12 ^0.')=t(^) (l-^-)^ f ' , ft : ^ (l ^\ where (1- — ) ( — N„ (4-2) i ^—) is the variance of the sample proportion in the h th stratum, and n -\ h N h - the population in stratum h, 1% - the sample size in stratum h, and N - the entire population. 4.1.1.2 Sample Size Formula (4-3), shown below, implies that sample size is determined by half-width of the confidence interval (p - Z ^Var(p') l a/2 , P' + Z ^ ^ ( ^ ) ) on the true proportion p for l a / 2 height category / at confidence level (1-a). e=Z a / 2 V 1 - 1 PQ-P) N \ n-l t (4-3) H where n is the sample size, N is the entire population, and ^Var(p') = Il - — N \ \ P \ \ - P ' ) n-l Therefore, once the desired width of the confidence interval is set, the sample size can be determined. In this case, however, we should decide the sample size in each stratum instead of that in the entire population. Since the width of the confidence interval is determined by ZQ/2 and the variance of sampled proportion p', if the width of the confidence interval on the true proportion in each stratum is the same and the confidence level (1-a) is set at the same value, the variance of the sample proportion in each stratum will be the same. Then, from ( 4 - 2 ) , the variance of the total stratified 13 samples will be smaller and we will definitely meet the requirement on the width of the confidence interval on the true proportion in the entire population. Therefore, we set the width of the confidence interval on the proportion in each stratum to be equal to the width of the confidence interval on the proportion of the entire population, which allows us to choose the sample size in each stratum independently. 4.1.2 Method of Measurement There are different types of materials at UBC Library. For example, there are books, journals, serials, as well as manuscripts, videotapes, pictures, slides, etc, all stored at different locations. It is necessary to give a standard "volume" definition for all materials. For example, if one book is considered as one volume, due to the difference in thickness, biased results will be generated. UBC Library provides a general rule for calculating "volumes" which is 10.3 volumes / foot when books are arranged as shown in Figure 4.2. \ 1 foot Figure 4.2 Conversion Between Space Length and Volumes Through the above conversion, each location can be further divided into sub-strata. Each shelf is considered as a sub-stratum and shelves are randomly selected to measure the length that each height category occupies. 4.1.3 Heights' Categories Bin's height is restricted to be integer. Six inches and sixteen inches high bins have been pre- 14 selected as the lowest and highest bins, respectively. Additional bins' heights need to be determined. Table 4.1 below, which shows height distribution in a small sample we have done, suggests six height categories. Table 4-1 Proportion of Each Height Category in a Preliminary Sample Height category H < 8 " 3.93% 8"< H < 9 " 9 " < H < Proportion 5.66% 10" 23.68% 10"<H< 11" 30.68% 11"<H< 12" 15.34% 1 2 " < H < 13" 10.86% 1 3 " < H < 16" 7.87% H> 16" 1.97% 4.1.4 Bonferroni Correction The heights are divided into six categories. It means that there will be five proportions that should simultaneously have the width of their confidence intervals set by Formula (4-3). Formula (4-3) is suitable for getting the width of confidence intervals one-at-a-time. Therefore we need to modify the Formula (4-3) by Bonferroni correction: e=Z a/2r JlTZ V Afy [I'V-P'), n-1 (4-4) where r is the number of simultaneously established confidence intervals. 15 4.2 Staffing Levels and Selection Rule 4.2.1 Process Mapping Information is gathered from the system's supplier and other universities that have already installed ASRS. Our understanding of the future operation is reflected in the process maps. There are two process maps. One describes the borrowing process, while the other describes the returning process. They are shown, respectively, in Appendix A. 4.2.2 Data Collection The data required to run the simulation models are: • Arrival rate. • Customer processing time: The time spent at the circulation desk to serve a patron. • Crane processing time: The time for a crane to retrieve a bin and place it on a designated workstation. • Material processing time: The time for a staff to locate and pick up a requested item from ASRS. Data for estimating arrival rate are collected from the records of the past five years. Technical specification for selected type of crane is gathered from the supplier. Materials processing time is set based on information obtained from other universities that have already installed the system. The customer processing time is deemed as a variable in the model. 4.2.3 Model Development 4.2.3.1 Simulation Software: Arena 6.0 4.2.3.2 Essential Elements of the Simulation Simulation models are event driven. Library staff members are considered as transporters instead of resources (servers), since they are required to go back and forth between the circulation 16 (reference) desk and workstations. Distance unit is foot and time unit is second. 4.2.3.3 Number of Stations There are either 62 bays or 59 bays in each aisle. In the real system, the crane is able to go to any of the bays. In the simulation model, if we establish 62(or 59) stations for all the 62 (or 59) bays, it will be very time consuming. (The time for building stations in the model increases by 2 , k where k is the number of stations that are added). So we experimented with different number of stations and checked the number of requests that a crane was able to process in one hour. From Figure 4.3, we noticed that the number of processed requests did not increase much when more than 4 stations were used to represent the 62 bays. Therefore, we divided equally each aisle into four zones and each station represents one zone. Since a crane in ASRS has simultaneous vertical and horizontal movements, tiers in an aisle are also equally divided into four zones. Productivity of a crane 9 5 0 7 0 0 "I 1 1 1 2 r = = - 1 4 8 16 N u m b e r of stations Figure 4.3 Maximum Number of Requests Processed in a Day Using Different Number of Representative Stations 1 7 4.2.3.4 Relationship Between the Number of Requests and the Number of Patrons Based on the analysis of available data for slow moving materials it was found that, on average, one person borrows 1.6 items (note: not applicable to open shelf patrons). Therefore, we assume that one person requests a single item (a conservative assumption). After a request enters the model, it initiates the corresponding crane to pick up the bin. At the same time, the request is duplicated to create a patron who will go to the circulation desk (or reference desk) to pick up the requested item. After the crane has completed the request, the request is converted to a single item, waiting for a staff member to pick up. 4.2.4 Assumptions • Staff members at the same desk have identical job responsibilities. • Whenever there is no patron at the desk and there are items waiting at the workstation to be picked up, a staff member will go to the workstation to pick up the items. • Patrons will go to the circulation desk (or reference desk) immediately after they make requests on UBC Library website. • When a patron reaches the desk and the requested item has not been processed by the crane, the staff will prioritize the request. • Return process is ignored in the simulation model for the following reasons: After a requested item has been removed from the bin, the staff member will be asked if there are any items waiting to be put back in the system, prior to storing the bin. The staff member could then begin scanning and putting back the items that meet the criteria for the bin at the workstation. Therefore, the time for the return process is quite short and can be ignored. Furthermore, the arrival rate in the first two hours in the morning and in the evening after 8:00 pm is very low, so the staff members could utilize these periods to put back items. • Service discipline is first come first serve. 4.2.5 Models Two models have been developed. One is for a single staff member at the circulation desk and a 18 single staff member at the Archives and Special Collections reference desk. The second model is for multiple staff members at the circulation desk and multiple staff members at the Archives and Special Collections reference desk. The need to have two models is that it is difficult to represent the real operation in the simulation model when there are multiple staff members. Thus, when there are multiple staff members at the desks, we have to simplify the simulation model. 4.2.6 Model Validation Since the new system has not been in operation, we have only verified the model's logic. 4.2.7 Criteria for Determining the Staffing Levels UBC library would like to have a table which displays the service performance for different number of staff members. Thus, we have evaluated the maximum queue length with different staffing levels. Once the maximum queue length was decreased to the critical value, chosen to be ten and acceptable by UBC Library, we stopped increasing the number of staff members. 4.2.8 Scenario Analysis Since the customer processing time is unknown, we input different processing times to examine the maximum queue length at different staffing levels. 19 5. RESULTS 5.1 Bin Selection 5.1.1 Sampling Result Aside for the six-inch and sixteen-inch high bins selected by UBC Library, two additional sizes of bins, ten-inch and twelve-inch, are recommended based on sampling results (Appendix B). Table 5-1 provides the proportion of bins heights derived from our sampling analysis. Table 5-1 Sampling Result Bin height Proportion 6" 10" 12" 16" 1% 33% 61% 5% 5.1.2 Estimated Proportions for Different Time Horizons The volumes of Archives and Special Collections increase with time. Based on the current volumes and growth rate, we have come up with different proportions for different time horizons. Detailed information is provided in Appendix B. Table 5-2 Estimated Proportions of Bin Heights' for Different Time Horizons 6" 5-year horizon 1.09% 10-year horizon 1.09% 15-year horizon 1.09% 10" 36.16% 35.05% 33.94% 12" 57.80% 59.06% 60.32% 16" 4.95% 4.81% 4.66% Bin height 20 5.2 Results from the Simulation Models There are two major semesters in each year at UBC. One is the Winter Semester, the other is the Spring Semester. A winter Semester starts from early September and ends in December. A spring Semester starts from early January and ends in April. As a result, the number of patrons at UBC Library displays a seasonal pattern. Therefore, we divided the twelve months into three different seasons, high, middle and low, at the circulation desk and reference desk, according to the number of daily arrivals (Appendix C). The following provides the simulation results for different scenarios. The maximum values shown in the various displays are the average of maximum values in 30 replications. 5.2.1 Circulation Desk 5.2.1.1 Initial Stage (0.8 Million Volumes) One Staff u « 120.0 W 3 •g « 100.0 80.0 60.0 S 20.0 40.0 I °" 5" a x 5 ' *-•"' ^\ > - \ -- -=<» 0.0 40 52 65 Highest month in high season 40 52 65 40 Lowest month in high season | 52 65 Middle season 40 | 52 65 Low season Average customer processing time f o r open shelves patrons(seconds) - 65s Figure 5.1 90s - 120s Maximum Queue Length in Front of Circulation Desk 21 Two staff i- V <D 3 .Q 0) 16 E = 12 I 4 1 E 2 5 to 8 & — ~z$t— \ 0 40 52 40 65 Highest month in high s e a s o n 52 65 40 Lowest month in high s e a s o n j 52 | 65 Middle s e a s o n Average customer processing time for open shelves patrons(seconds) -65 Figure 5.2 -90 •120 Maximum Queue Length in Front of Circulation Desk From the results above, we conclude that three staff members are required in the worst case. In the middle and low seasons, two staff members are enough to keep the maximum queue length relatively short (less than ten). Besides the queue length, we examine the maximum waiting time as well. Table 5-3 gives the maximum waiting time for the longest average customer processing time. We observe that the maximum waiting time is short enough as well (less than ten minutes). Table 5-3 Maximum Waiting Time at the Initial Stage (65s, 120s) Number of staff Maximum waiting time (minutes) High season 3 6 Middle season 2 7 Low season 2 5 N o t e : ( 6 5 s , 1 2 0 s ) m e a n s that the a v e r a g e c u s t o m e r p r o c e s s i n g t i m e f o r o p e n - s h e l f p a t r o n s is 6 5 s e c o n d s , a n d t h e a v e r a g e c u s t o m e r p r o c e s s i n g t i m e f o r A S R S g e n e r a l p a t r o n s is 1 2 0 s e c o n d s . 22 Figures 5.1 and 5.2 are based on the assumption that all open-shelf patrons will go to the circulation desk to check out material. However, there are self-check out machines in the library. In Figure 5.3, we display the maximum queue length if some of the open-shelf patrons make self-check out. It demonstrates that if UBC Library educates patrons to use self-checkout machine, the maximum queue length will significantly decrease. As a result, fewer staff members will be required. One staff in high month in high season (65s,120s) >_ is 140 120 100 80 60 V 40 20 0 50% 75% 100% Percentage of self-checkout Figure 5.3 The Impact of Self-checkout to Maximum Queue Length 5.2.1.2 Final Stage (1.4 Million Volumes) The previous results are for the initial stage when 0.8 million volumes of materials are stored in the system. Next, we will estimate staffing levels required when the ASRS is full i.e., having 1.4 million volumes. From the data collection for materials' heights, we know that the volumes for materials excluding Archives and Special Collections and microforms will almost doubled. We assume 23 that the arrival rate increases in the same proportion as the increase of volumes. Therefore, the arrival rate will double at the circulation desk. Figure 5.4 displays the maximum queue length in the final stage in the worst case if there are three staff members at the circulation desk. It shows that three staff members are enough to keep the queue length relatively short. In the high season, three or four staff members are required, depending on the maximum queue length that the library wants to achieve. Suppose four staff members are assigned in high season, and three staff members are assigned in middle and low seasons. Table 5-4 shows the corresponding maximum waiting time for the staffing levels. It demonstrates that the staffing levels not only ensure short queue but also ensure short waiting time. Three staff (65s, 120s) 16 12 - 8 Is * a. 3 ra High month in high season Low month in high season Middle season Low s e a s o n Season Figure 5.4 Maximum Queue Length in Front of Circulation Desk at Final Stage 24 Table 5-4 Maximum Waiting Time at Final Stage (65s, 120s) Number of staff H i g h season Middle Low season season Maximum waiting time (minutes) 4 5 3 6 3 5 5.2.2 Archives and Special Collections Reference Desk The volumes of Archives and Special Collections will increase by 20% at the final stagefromthe initial stage. We considered scenarios wherein the arrival rate at the Archives and Special Collections reference desk increases by 25%, 50% and 100%. Figure 5.5 shows the maximum queue length in different scenarios when there is only one staff member at the reference desk. In the term (600s, 600s) in Figure 5.5, the first (resp., second) 600s denotes the average customer processing time in seconds for compact-shelf patrons (resp., ASRS patrons). Figure 5.5 suggests that one staff member is enough in the middle season to keep the queue length short at the initial stage. In the final stage, two staff members are required in the worst case (arrival rate doubled) to keep the maximum queue length short. Figure 5.6 displays the maximum queue length in the worst scenario in the high season when there are two staff members at the reference desk. In the high season at the initial stage, two staff members can achieve a relatively short maximum queue length. At the final stage, an additional staff member may be required if the arrival rate is doubled. 25 O n e staff E = 50 3 ^ a a 40 | S 30.§ I 2 0 'B es M ft S «g in 1 ~>~~*~~~~'—"""" ' ^ U ^f^^^^^ ZZZZ'~~~Z-——Mr'""'""' "~ — ——— o 1.25 1 1.50 2 R a t i o o f final s t a g e v e r s u s initial stage arrival rates —•— High season (600s, 600s) » -*— Middle season (600s, 600s) — High season (300s, 300s) Middle season (300s, 300s) Figure 5 . 5 Maximum Queue Length in Front of Archives and Special Collections Reference Desk Two staff members in high season (600s,600s) •2 ®25 9 s a ™ 9 | 20 15 10 5 1.25 1.5 R a t i o o f final s t a g e v e r s u s initial stage arrival rates Figure 5 . 6 Maximum Queue Length in Front of Archives and Special Collections Reference Desk ..— 5.2.3 Selection Rule Since the initial volumes of materials will be 0.8 million and the targeted final volumes will be 1.4 million, 0.6 million volumes of materials will be gradually added to the system. The current volumes of Archives and Special Collections are 0.2 million, and are estimated to grow by 25% in 15 years. Hence, the volumes of the additional materials that will be served at the circulation desk will almost be doubled. The pattern of circulation frequency for the additional 0.6 million volumes of materials is unknown. To simplify the problem, we assume that the circulation interval is the same for all of those additional items. For instance, if the circulation interval is 20 years, it means that any of the additional items will be requested once per 20 years. We further assume that the chance to request any of the items is the same and that the 0.6 million volumes will represent 0.6 million items. Therefore, we are able to derive the annual arrival rate for the additional materials. For example, suppose that the circulation interval is 20 years, then the number of annual requests for the additional materials is 600,000/20 = 30,000. Since we maintain the assumption that each patron requests a single item, the 30,000 annual requests will imply that 30,000 additional patrons arrive at the circulation desk in one year. In order to estimate the daily arrival rates, we make three additional assumptions: • Pattern of the monthly arrival rate in the future follows the same as that in the initial stage. • Pattern of hourly arrival rate in the future follows the same as that in the initial stage. • Daily arrivals are constant in each month. Based on the above three assumptions, we are able to calculate the average hourly arrival rates in, e.g., the high month in high season. Inputting the new data of arrivals to the simulation model, we get the results shown in Tables 5-5 and 5-6, which should be understood as follows: In Table 5-5, the average customer processing time for open shelves' patrons is 65 seconds and the average customer processing time for the ASRS general patrons is 120 seconds. Then, based on the above three assumptions, for any circulation interval of items of the additional 0.6 million 27 volumes, we are able to get the hourly arrival rates in a high month in high season for those items. Adding the arrival rates obtained to that of the 0.8 million volumes of materials (initial stage) results with the total arrival rates. Thus, for example, if the circulation interval for the additional 0.6 million volumes is 20 years, and there are three staff members at the circulation desk, the maximum number of patrons in queue will be thirteen. Tables 5-5 and 5-6 provide the relationship between the number of staff members, the circulation interval of additional materials and the maximum queue length. We can conclude from these two tables that if, for example, the maximum number of staff members that the UBC Library is able to assign to the circulation desk is four and the maximum accepted queue length is ten, then only materials that are requested once per 13 years or less can be stored in the system. Table 5-5 Maximum Queue Length in a High Month in High Season (65s, 120s) Circulation interval of Daily arrivals of additional materials A S R S general (years) patrons 20 288 13 6 15 334 18 9 14 346 23 9 13 361 23 10 12 379 34 11 6 11 399 41 13 7 10 424 55 16 10 9 454 68 16 11 8 491 22 12 8 7 540 37 14 10 6 604 20 12 9 5 695 40 16 11 3 staff 4 staff 5 staff 6 staff 7 staff 7 Note: ( 6 5 s , 120s) m e a n s that the a v e r a g e c u s t o m e r p r o c e s s i n g t i m e f o r o p e n s h e l v e s ' patrons is 6 5 s e c o n d s , a n d t h e a v e r a g e c u s t o m e r p r o c e s s i n g t i m e f o r A S R S p a t r o n s a r r i v i n g at the c i r c u l a t i o n d e s k is 1 2 0 s e c o n d s . 28 Table 5-6 Maximum Queue Length in a High Month in High Season (40s, 65s) Circulation interval of Daily arrivals of additional materials A S R S general (years) patrons 20 3 staff 4 staff 288 8 6 15 334 11 7 10 424 14 8 9 454 15 8 8 491 18 9 7 540 27 11 8 6 604 43 14 9 5 695 20 14 10 4 853. 19 13 5 staff 6 staff 7 staff 11 Note: ( 4 0 s , 6 5 s ) m e a n s that the a v e r a g e c u s t o m e r p r o c e s s i n g t i m e f o r o p e n s h e l v e s ' patrons is 4 0 s e c o n d s , the a v e r a g e c u s t o m e r p r o c e s s i n g t i m e f o r A S R S p a t r o n s a r r i v i n g at t h e c i r c u l a t i o n d e s k i s 6 5 s e c o n d s . In Tables 5-5 and 5-6, for every circulation interval of the additional 0.6 million volumes, we find the number of staff requirements in the circulation desk so as to reduce the maximum queue length below the critical number of 10 patrons. Thus, for example, in Table 5-5, for a circulation interval of 10 years, three staff members would result with a maximum queue length of 34, four staff members would result with a maximum queue length of 11, and five staff members will reduce the maximum queue length to six. Since for five staff members the maximum queue length is reduced below the critical value of ten, it is not necessary, in this case, to calculate the maximum queue length for a higher level of staffing. 29 6. CONCLUSIONS 6.1 Bin Recommendations As Table 5-2 shows, when different horizons are considered for the growth of Archives and Special Collections, the derived proportion for each height of bins is different. Therefore, the bins' configuration will be different for different horizons. Aside for the proportion requirements, there are other factors to consider for determining the bin configuration. In the ASRS, the crane must be "mapped" so that it can repeatedly position itself at the proper location in the rack. Thus, having rows with the same configuration would have been the most efficient option for installing the system. However, the Archives and Special Collections, which are only stored in the first three rows, require many more high bins than other materials, which makes it more difficult to have all rows with the same configuration. So we have to relax this requirement. Thus, we have just required that every two rows sharing the same crane have the same configuration except for the third and fourth rows. Furthermore, we have tried to have as many rows as possible of the same height. We used two methods to derive the recommended configurations. One is by trial and error, and the other is by using integer programming and rudimental search (Appendix B.4). The two methods happened to provide the same results. Table 6-1 Bins 1 st row 2 n d row 3 r d row Bin Configuration for a 5-year Horizon 4 t h row 5 , h row 6 row 7 row , h 8 t h row Number Actual Target of bins proportion proportion 6" 0 0 0 1 0 0 1 1 183 1% 10" 9 9 9 19 9 16 19 19 6674 35% 36% . 1% 12" 27 27 27 18 27 21 18 18 11211 59% 58% 16" 2 2 2 2 2 2 2 2 980 5% 5% T o t a l tiers 38 38 38 40 38 39 40 40 Space left 0 0 0 0 0 1 0 0 Total bins 19048 30 Table 6-2 Bins ,sl 1 row 2 n d row 3 r d row Bin Configuration for a 10-year Horizon 4 , h row 5 row 6 row 7 , h row 8 l h row Number Actual Target o f bins proportion proportion 6" 0 0 1 0 0 0 1 1 186 1% 1% 10" 9 9 6 14 16 16 19 19 6606 35% 35% 12" 27 27 29 24 21 21 18 18 11335 59% 59% 16" 2 2 2 1 2 2 2 2 921 5% 5% T o t a l tiers 38 38 38 39 39 39 40 40 Space left 0 0 0 1" 1" 1" 0 0 Total bins 19048 Table 6-3 Bin Configuration for a 15-year Horizon Bins l " row 2 n d row 3 r d row 4 , h row -th 5 row 6 t h row 7 row 8 , h row Number Actual Target of bins proportion proportion 6" 1 1 1 0 0 0 0 0 186 1% 1% 10" 6 6 6 20 9 9 22 22 6113 32% 34% 12" 29 29 29 19 27 27 16 16 11766 62% 60% 16" 2 2 2 1 2 2 2 2 921 5% 5% T o t a l tiers 38 38 38 40 38 38 40 40 S p a c e left 0 0 0 0 0 0 0 0 Total bins 18986 31 6.2 Staff Scheduling 6.2.1 Circulation Desk At the circulation desk, the hourly arrival rates are not stationary. Generally, the hourly arrival rates are increasing before noon and decreasing after 4:00pm (Appendix C.1.3). Therefore, it is not necessary to keep the number of staff at the same level. By ensuring the maximum queue length in each period less than ten, we come up with the following schedules for each season. 6.2.1.1 The staff Schedules at the Initial Stage Table 6-4 Staff Schedule in January, February, March, October and November (High Season) Time 8:00-11:00 11:00-12:00 12:00- 17:00 17:00-18:00 18:00-Close Table 6-5 Number of staff 1 2 3 2 1 Staff Schedule in April and September (Middle Season) Time 8:00-12:00 12:00- 17:00 17:00-Close Number of staff 1 2 1 32 Table 6-6 Staff Schedule in May, June, July, August and December (Low Season) Time 8:00- 14:00 14:00- 17:00 17:00-Close Number of staff 1 2 1 6.2.1.2 The Staff Schedules at the Final Stage (Assuming the Arrival Rate is Doubled) Table 6-7 Staff schedule in January, February, March, October, November (High Season) Table 6-8 Time Number of staff 8:00-10:00 1 10:00-11:00 2 11:00- 12:00 3 12:00- 17:00 4 17:00-18:00 3 18:00-19:00 2 19:00-Close 1 Staff Schedule in April and September (Middle Season) Time 8:00-10:00 10:00-11:00 Number of staff 1 2 11:00- 18:00 3 18:00- 19:00 19:00-Close 2 1 Table 6-9 Staff schedule in May, June, July, August and December (Low Season) Time Number of staff 8:00-10:00 1 10:00- 12:00 2 12:00- 17:00 3 17:00- 18:00 2 18:00-Close 1 6.2.2 Archives and Special Collections Reference Desk Since the hourly arrival rates for the Archives and Special Collections do not vary a lot during a day, the number of staff members at the Archives and Special Collections reference desk will remain constant during the day. The required number is recommended to be either two or three. 6.3 Selection Rule According to the simulation results, assuming a maximum of four staff members at the circulation desk, materials with circulation intervals longer than 13 years are recommended to be put into the system to avoid a maximum queue length exceeding ten. 34 7. REQUIRED STAFFING LEVELS USING QUEUEING THEORY In the simulation model, all the staff members are assumed to have the same responsibilities. In this section, further analysis, using queueing theory methodology, is carried out under the assumption that staff members at the circulation desk are dedicated to different tasks. The staff members at the circulation desk have three major tasks: • Serve open-shelf patrons • Serve ASRS general patrons • Pick up requested items in ASRS and deliver them to the circulation desk Therefore, we separate the staff members into three categories according to the three different tasks. It normally takes, on average, less than one minute to complete the third task according to information provided by library staff at other universities that have the ASRS in operation. Therefore, we assign one minute to the third task for each requested item. It implies that additional staff member is required for this task for each marginal increase of sixty in the hourly arrival rates. We further assume that any requested item by an ASRS patron is available when he/she reaches the circulation desk. Thus each type of patrons, either open-shelf or ASRS, can be analyzed separately by queueing model. Queueing theory methodology can be used to derive the values of various system performance indicators. For example, it can be used to derive the average queue length, average waiting time, the distribution of queue length, the distribution of waiting time and the probability that a certain number of patrons are in the queue. The service level requiring the probability that a patron should wait less than 5 minutes is greater than 80%, is adopted in this section to determine the minimum number of staff members required. For each type of patrons, the inter-arrival time and the service time are assumed to have exponential distribution and that there are s staff members serving each type of patrons. Different types of patrons have different queues. Then the queueing system for each type of patrons can be modelled as an M/M/s system, and we can use, e.g., Gross and Harris (1998), to obtain various 35 measures for system performance, including, e.g., the cumulative distribution function of the waiting time in queue, which is presented below. (t=0) s\(s-Xlfi) (7-1) w (t) = q ) (s-l)l(s-Af //) 71 o + W (0) (t>0) q where we denote by W (t) - Probability (time in queue ^ t) q X - the arrival rate [i - the service rate k - number of patrons in the system s - number of staff members in the system, and 7io - probability that there are no patrons in the queue in steady state, where } -i A/sjU < 1 The probability that there are k patrons in queue is: r for k= 1,2,...,s The mean number of patrons in the system, Lo, waiting for service is: U> -{.—) SI /J. ( " ) ~———77 (l-A/SjU) 7 3 and the mean waiting time, Wo, in queue is: W =^ (7-4) 0 A The analysis is carried out for peak hours in a high month in high season and the average service time for ASRS general patrons is 120 seconds and the average time for open-shelf patrons is 65s. At the initial stage, according to our previous assumption, one staff member is dedicated to open shelves' patrons, one is dedicated to ASRS general patrons and the third one is responsible'for picking up requested items from the ASRS and sending them to the circulation desk. Then, using the above formula, we are able to derive the various indicators representing system performance (Table 7-1). Table 7-1 System Performance with Dedicated Staff Member 7t P(N> 10) Lo W (minutes) W (0) W (2) W (5) Open-shelf patrons 0.37 0.03 1.7 2.9 0.37 0.68 0.88 ASRS general patrons 0.40 0.01 1.5 5.0 0.40 0.60 0.78 0 0 q q q Note: N is the number of patrons in queue It follows from Table 7-1 that one staff member is able to meet the service level for open shelves' patrons. However, for ASRS general patrons, the probability that patrons wait for less than 5 minutes is a little lower than 0.8, even though the probability that more than ten patrons are in the queue is very low. But the probability of no patrons in queue is 0.4 (7i0). It implies that staff utilization is low. Furthermore, a maximum of eighteen ASRS general patrons arrive at the desk in the peak hours. Thus, the utilization of the staff member who is responsible for fetching 37 requested items is only about 0.3. This low utilization of staff members implies that system performance can be improved without adding staff. To verify this point, simulation analysis is used to derive the system performance when all the staff members do all tasks and there is only one queue for both types of patrons. The simulation results are presented in Table 7-2. Table 7-2 System Performance with Same-task Servers Derived by Simulation TC System performance 0 0.66 Lo 0.5 W (minutes) W (0) W (2) W (5) 0.54 0.66 0.90 0.99 0 q q q By comparing the result in Table 7-2 and Table 7-1, it is obvious that the service level is much better when each staff member does all tasks. The above results are for the initial stage. When more materials are added into the system, the number of patrons at the circulation desk is increasing. Table 7-3 displays the required number of staff for ASRS patrons that ensure 80% of patrons wait less than 5 minutes in the peak hour based on the M/M/s queueing model. Table 7-4 presents the percentage of ASRS patrons waiting less than 5 minutes based on the simulation results. 38 Table 7 - 3 Percentage of Patrons Waiting Less Than 5 Minutes in Peak Hours in a High Month in High Season Based on Queueing Model Circulation interval of additional materials(years) Hourly arrivals Number of staff members for Total required A S R S general patrons number of staff 2 3 members 4 20 34 95% 4 15 40 90% 4 14 41 89% 4 13 43 85% 4 12 45 82% 11 48 77% 10 4 99% 5 50 99% 5 9 54 98% 5 8 59 97% 5 7 66 93% 6 6 74 82% 6 5 85 41% 98% 7 N o t e : W h e n the n u m b e r o f requested i t e m is greater than 60(each i t e m represents a patron), t w o staff m e m b e r s are r e q u i r e d to p i c k u p r e q u e s t e d items (one m i n u t e f o r e a c h item). Table 7-4 Service Levels for ASRS Patrons in Peak Hours in a High Month in High Season Derived from Simulation Circulation interval Hourly of additional arrivals materials(years) 20 34 Total required number of staff 3 4 5 6 82% 15 40 98% 14 41 97% 13 43 97% 12 45 94% 11 48 93% 10 50 87% 9 54 86% 8 59 68% 7 66 93% 6 74 86% 5 85 97% 92% 39 Required number of staff 20 15 14 13 12 11 10 9 8 7 6 5 C i r c u l a t i o n interval of additioan materials (years) F i g u r e 7.1 • Q u e u e i n g m o d e l service level 1 * Simulation model service level 1 • S i m u l a t i o n model service level 2 R e q u i r e d N u m b e r o f S t a f f at t h e F i n a l S t a g e G i v e n Different Circulation Interval for A d d e d Materials Note: S e r v i c e L e v e l 1: 8 0 % p a t r o n s w a i t l e s s t h a n 5 m i n u t e s . S e r v i c e L e v e l 2 : the m a x i m u m q u e u e l e n g t h is ten. Figure 7.1 methods displays for the different total required service number levels. W h e n of staff based on Service Level the 1 is u s e d queueing for and determining simulation the l e v e l s , the p o l i c y that all staff m e m b e r s d o all tasks w i l l require o n e less m e m b e r than the staff policy t h a t s t a f f m e m b e r s a r e a s s i g n e d t o d e d i c a t e d t a s k s . It i m p l i e s t h a t h a v i n g a l l s t a f f d o i n g a l l t a s k s is a better Service policy. Level 2 requires no less staff than service level 1. It d e r i v e d b a s e d o n S e r v i c e L e v e l 2 ensure that S e r v i c e L e v e l 1 is implies that the staffing levels met. 40 REFERENCE Agnihothri, S.R., Taylor, P.F., 1991. Staffing a Centralized Appointment Scheduling Department in Lourdes Hospital. Interfaces, Sep/Oct, 1-11. Buffa, E.S., Cosgrove, M.J., & Luce, B.J., 1976. An Integrated Work Shift Scheduling System. Decision Science, 7 (4), 620 - 630. Crabill,. T.B., Gross, D., Magazine, M.J., 1977. A Classified Bibliography of Research on Optimal Design and Control of Queues. Operations Research, 25 (2), 219-232. Green L., Kolesar, P., 1991. The Pointwise Stationary Approximation for Queues with Nonstationary Arrivals. Management Science, 37 0), 84-97 Green L., Kolesar P., Svoronos, A., 1991. Some Effects of Nonstationarity on Multiserver Markovian Quueing Systems. Operations Research, 39, 502-511. Gross, D., Harris, CM. 1998. Fundamentals of Queueing Theory. 2 ed. John Wiley & Sons. nd Guo, I., 2003. Staff Scheduling and Workstation Allocation at UBC Libraries. M.Sc. Thesis, The University of British Columbia. Ingolfsson, A., Haque, M.A., Umnikov, A., 2002. Accounting for Time-varying Queueing Effects in Workforce Scheduling. European Journal of Operational Research, 139, 585-597. Jennings, O.B., Mandelbaum, A., Massey, W.A., Whitt, W., 1996. Server Staffing to Meet Timevarying Demand. Management Science, 42 (10), 1383-1394. Kirsch, S.E. Automated Storage and Retrieval - The Next Generation: How Northridge's Success Is Spurring A Revolution in Library Storage and Circulation. A C R L ninth national conference http://www.als.org/ala/acrl/acrlevents/kirsch99.pdf 41 Kolesar, P.J., Rider, K.L., Crabill, T.B., Walker W.E., 1975. A Queueing-linear Programming Approach to Scheduling Police Patrol Cars. Operations Research, 23 (6), 1045-1062. Mason, A.J., Ryan D.M., Panton, D.M., 1998. Integrated Simulation, Heuristic and Optimisation Approaches to Staff Scheduling. Operations Research, 46(2), 161-175 Montgomery, D.C., 2001. Design and Analysis of Experiments. 5 ed. John Wiley & Sons. th Shaler Stidham Jr. (2002). Analysis, Design, and Control of Queueing Systems. Operations Research, 50, 197-216 Sharon L.Lohr, 1998. Sampling: Design and Analysis. Brooks Cole. Wolsey, L.A., 1998. Integer Programming. Wiley. Zhou, A. 2003. Simulation Modeling as a Decision Analysis Support Tool at the Vancouver Container Terminal. M.Sc. Thesis, The University of British Columbia. Automated Storage & Retrieval System, http://library.csun.edu/asrs.html ASRS (Automated Storage and Retrieval System) in Academic Libraries. http://w\v^.slais.ubc.ca courses/libr50()/()l-02-wtl/vv^vw/J Loo/history.htm / 42 APPENDIX A - PROCESS MAPS Irving K. Barber Learning Centre Automated Storage and Retrieval System (ASRS) Process Map Figure A.l Borrowing Process Irving K. Barber Learning Centre Automated Storage and Retrieval System (ASRS) Process Map Figure A . 2 Return Process 44 APPENDIX B - SAMPLING RESULTS OF MATERIALS' HEIGHTS Information about the heights of some materials is available in the UBC Library database. The reason that information for those materials has been entered into the system and information for other materials is not in the system is unknown. It was suggested that we should physically verify the height of materials for the ASRS. B.l Materials Excluding Archives and Special Collections and Microforms At the time we started to make the measurement, the materials in MN2 and MN7 have been removed and stored out of campus. In these two locations, the shelves' heights varied with the materials' heights. Therefore, all shelves' heights were measured and used as an approximation for materials' height in these two locations. Table B-1 presents the sampling results for the materials in Main Storage, Library Processing Centre and Open shelves' inactive serials (all the materials excluding Archives and Special Collections and microforms). Table B-1 Heights Proportion of Materials Excluding Archives and Special Collections and Microforms Proportion based on data collected for all three locations Proportion based on data collected from open shelf, L P C , M N A & B & K and data from database for MN2 & MN7 Proportion based on data from database for all three locations 19.01% 20.14% 25.71% 9 " < H < 10" 31.09% 32.12% 34.16% 10"<H< 11" 28.47% 27.83% 11.29% 11"<H< 12" 13.75% 13.47% 25.84% 1 2 " < H < 16" 6.81% 5.72% 2.88% 0.87% 0.71% 0.12% Height Category H < H > 9" 16" 45 The results suggest ten-inch and twelve-inch bins are best choices. Materials higher than sixteen inches will be put flat in the ten-inch bins, resulting with a new proportion distribution as shown in Table B-2. Table B-2 shows that the proportions for twelve-inch bins and sixteen-inch bins derived from the physical measurement are higher than that derived partly or completely from the database. Thus, the configuration of bins based on physical measurement results is safer. Indeed, if the number of low bins is underestimated, we can put low heights materials into high bins. But, it is impossible to put high materials into low bins. Therefore, the proportions based on measured data is used to estimate the number of bins of each height. Table B-2 Proportion of Required Bins for Materials Excluding Archives and Special Collections and Microforms Height Category Proportions based on data collected for all three locations Proportions based on data collected from Open shelf, L P C , M N A & B & K and data from database for M N 2 & M N 7 Proportions based on data from database for all three locations 10" 50.96% 52.98% 59.99% 12" 42.22% 41.29% 37.13% 16" 6.81% 5.72% 2.88% B.2 Archives and Special Collections All materials for Archives and Special Collections will be put into boxes before being placed into bins. There are more than 20 types of boxes but the heights of most boxes are between 10.5" and 12". By measuring boxes dimensions, we found that the number of bins for Type 1 box (dimensions shown in Table B-3) should be determined by the number of Type 1 boxes. Each bin is able to hold 2 or 3 of Type 1 box depending on how the boxes are placed in the bins. Figures B.l and B.2 present two such methods. By considering the space left, storing two Type 1 46 Boxes in each bin is a better choice. In Method 1, the width of space left on the right is 7.25" (24"-16.75"). The width is shorter than the widths of many types of materials in the library. In Method 2, the width of space left on the right is 10.75" (24" - 13.25"). It has fewer constraints on materials' dimension than Method 1. For other types of boxes, the number of bins required can be estimated based on the number of shelves they occupy. Table B-3 L (inch) Typel Type 1 Box W (inch) 16.75 Quantity Bins required 5078 2539 13.25 Table B-4 Number of Bins Required Bin height Bins required by type 1 box 12" 2539 1841 4380 16" 0 20 20 Bins required by other boxes Quantity of bins Each year the volumes added to Archives and Special Collections occupy up to 149 Type 1 Boxes, which is equivalent to 74.5 bins. Table B-5 gives the number of additional bins needed in the next 5, 10 and 15 years. Table B-6 provides the total number of bins required by Archives and Special Collections for these different horizons. 4 7 16.75*13.25 16.75 *13.25 16.75 " 12.75 24 Figure B . l Method inches 1 of Placing Type 7.675M2.5 1 B o x in a B i n 7.675M5.5 7.675-15.5 Figure B.2 Method 2 of Placing Type 1 B o x in a B i n 48 Table B-5 Forecast Number of Bins for Different Years Horizons Additional bins for a Additional bins for a 10- Additional bins for a 5- year growth year growth 15- year growth 373 745 1118 Quantity Table B-6 Final Number of Bins Required Considering Future Growth Current volumes + 5 years forecast Bin Number Equivalent Height of bins Tiers Percentage of 1.4 million Current volumes + 10 years forecast Number Equivalent of bins Tiers Percentage of 1.4 million Current volumes + 15 years forecast Number of Equivalent bins Tiers Percentage of 1.4 million 12" 4753 77 27.84% 5125 83 30.02% 5498 89 32.20% 16" 20 1 0.12% 20 1 0.12% 20 1 0.12% N o t e : E a c h b i n holds 82 volumes o f materials. B.3 Microforms Microforms will also be placed in boxes before being stored in bins. There are four types of boxes. The fewest number of boxes that one bin will be able to hold is nine. After counting the number of boxes, we concluded that 93 six-inch bins would be required in the worst case scenario. The targeted capacity (1.4 million volumes) is 1.7 times of the current volume (0.8 million). This ratio is applied to microforms and is used to estimate the number of six-inch bins required in total. As a result, 158 six-inch bins will be required, that is 3 tiers, which is equivalent to 1.09% of 1.4 million volumes. 49 B.4 Bin Configurations Based on the results from data collection, the amount of additional space given to Archives and Special Collections determines the total percentage of materials from the Open shelf inactive serials, LPC and Main Storage (Figures B.3, B.4 & B.5). Therefore, the percentages for ten-inch, twelve-inch and sixteen-inch bins are different in different scenarios (Table B-7). In calculating the percentage of different bins in each scenario, the following approach is followed. First the space is reserved for microforms and the Archives and Special Collections for the 5, 10 and 15 years projections. Then the remaining space is used to calculate the percentage of different height bins using the data collected from the open shelves, LPC and Main Storage. For example, consider the 36.16% figure in Table B-7 below which estimates the percentage of 10" bins and a 5-year growth for Archives and Special Collections. This figure is calculated as follows: Microforms occupy 1.09%, and Archives and Special Collections occupy 27.96%. Then, 70.95% space is left for the materials from open shelves, LPC and Main Storage according to Table B-2, 50.96% of materials from these locations require 10" bins. Thus the final percentage for 10" bins is 50.96%*70.95% = 36.16%, as shown in Table B-7. 50 Percentage Percentage 1% • Microforms O Microforms B Archives and Special Collections ( 5 more years) • Archives and Special Collections ( 10 more years) • Open Shelf Inactive Series, I P C & Storage D Open Shelf Inactive Seres, LPC & Storage Figure B.3 Percentage of Different Figure B.4 Percentage of Different Materials Considering a 5-year Growth Materials Considering a 10 -year Growth for Archives and Special Collection for Archives and Special Collection Percentage 1% 0 Microforms B Archives and Special Collections ( 15 more years) • Open Shelf Inactive Series, LPC & Storage Figure B.5 Percentage of Different Materials Considering a 15-year Growth for Archives and Special Collection 51 Table B-7 Proportion of Each Height Category Proportion (given a 5-year Proportion (given a 10- Proportion (given a 15- growth of Archives and year growth of Archives year growth of Archives Special collections) and Special Collections) and Special Collections) 6" 1.09% 1.09% 1.09% 10" 36.16% 35.05% 33.94% 12" 57.80% 59.06% 60.32% 16" 4.95% 4.81% Bin height 4.66% Based on the proportions shown in Table B-7 and other constraints, we have formulated the bin configuration problem as an integer program model. We present below the analysis of the 15year horizon problem as an example to illustrate the method. We denote by x the number of tiers whose bins in row i are of height j; j=l stands for sixtj inch bins, 7=2 stands for ten-inch bins, j=3 stands for twelve-inch bins, and y"=4 stands for sixteen-inch bins. One inch height of clearance should be given between every two tiers. Therefore the heights used in the integer program model are bins' heights plus one. For example, for a six-inch bin, the actual height used is seven inches. Furthermore, two and a half inches of additional height should be given for every 5 tiers. Since initially we did not know the total number of tiers in each row, we have approximated this height requirement by the term 2 - 5 » ( * n + * « + * » + * , - 4 ) = 0 - * 5 { X n + ^ + + X h ) . The total space height is 500.5", which determines the space constraint (b-1). • Space constraint: 7 * x n + 11 * x i2 + 13 * x i3 + 17 * x i4 + 0.5* (x n + x i2 + x for i= 1,2 i3 + x )< i4 8 502 , (b-1) The left-hand-side of (b-1) can be viewed as if 1.5 inches' clearance is given between any two 52 tiers. However, such clearance is not needed for the top tier bins. Therefore, an extra 1.5 inches are added to the right-hand-side whose value becomes 502 (500.5 + 1.5). (b-2) to (b-5) are implied by the proportion constraints. Since feasible solutions were not obtained when the proportion of each bin height is forced to be equal to the number shown in Table 8-1, and it is better to overestimate the high bins than the low bins, we assign less than or equal sign to the constraints for six-inch and ten-inch bins, and greater or equal sign to the constraints for twelve-inch bins and sixteen-inch bins. Thus, we obtain: • Modified proportion constraints: 5>„ 0>- ) < 0.0109 * 2 1=1 y'=l i=l 5>„ < 0.3394 * X2>* 8 5>, =1 (b-4) 1=1 7=1 5>, i=i 4 > 0.6032 * 3 1 (b-3) 1=1 7=1 i=i 4 8 4 i=l 7=1 > 0.0466 *XZ^7 (b-5) Recall that rows 1, 2 and 3 store Archives and Special Collections. In these three rows, the total number of twelve-inch bins should not be less than 5498 and the total number of sixteen-inch bins should not be less than twenty. Because bins in the same tier in the same row should have the same height and there are 62 bays in each of the first three rows, we obtain the following constraints: • Archives and Special Collections constraints: 5>,. >5518 3 (b-6) i=i 53 (b-7) I>,4>62 1=1 • Any two rows sharing the same crane shall have the same configuration except for rows 3 and 4 (refer to 6.1) x,.= x j , for i=l,5,7; j= 1,2,3,4 M (b-8) Xy is non-negative and an integer The objective function is to maximize the total number of bins: 8 4 z= ^ ^ x. Maximize (b-9) tj <=i y=i We have used linear programming (LP) relaxation, and branch method to solve the above integer programming problem. Recall that the LP relaxation of an integer program max {cx: x e P D Z "} has a constraint set P = { x e R": Ax<b} and an optimal value z = max {cx: x e P }. L P One important property of the relaxed problem is that the value of its objective function is always better or equal to that of the Integer Program. The relaxed problem can be used to find a good solution to our bin configuration problem. The solution for the LP relaxation problem is shown in Table B-8. Table B-8 Solutions of the Linear Programming Relaxation Problem 8 8 8 8 1=1 1=1 (=1 i'=l 108.2 195.2 z 19747 3.5 15.6 54 T h e n u m b e r o f tiers c o r r e s p o n d i n g to table B - 8 is s h o w n i n T a b l e B - 9 . Table B - 9 1 row 2 st 41.6 The row nd 3 41.6 rd row N u m b e r o f Tiers in Each R o w 4 38.3 t h row 5 34.1 th 6 row 38.6 th 7 row th row 38.6 8 44.8 th row 44.8 total n u m b e r o f tiers i n each r o w is b e t w e e n 3 0 a n d 4 5 , a n d T a b l e B - 1 0 presents eight different scenarios f o r the n u m b e r o f tiers i n each r o w . T h e r e f o r e , a b r a n c h a n d b o u n d m e t h o d is applied to find out scenarios h a v i n g feasible solutions (Figure B . 6 ) . Table B - 1 0 Different Scenarios for Total N u m b e r o f Tiers in Each R o w Scenario Total number of tiers N 1 row 2 st nd row 3 rd row 4 t h row 5 th row 6 th 7 row th row 8 th row 1 N>40 N>40 35<N<40 N<35 35<N<40 35<N<40 N>40 N>40 2 35<N<40 35<N<40 35<N<40 N<35 35<N<40 35<N<40 N>40 N>40 3. 35<N<40 35<N<40 35<N<40 35<N<40 35<N<40 35<N<40 N>40 N>40 4 N>40 N>40 35<N<40 35<N<40 35<N<40 35<N<40 N>40 N>40 5 N>40 N>40 35<N<40 N<35 35<N<40 35<N<40 35<N<40 35<N<40 6 35<N<40 35<N<40 35<N<40 N<35 35<N<40 35<N<40 35<N<40 35<N<40 7 35<N<40 35<N<40 35<N<40 35<N<40 35<N<40 35<N<40 35<N<40 35<N<40 8 N>40 N>40 35<N<40 35<N<40 35<N<40 35<N<40 35<N<40 35<N<40 N o t e : T h e ( b - 1 ) to ( b - 8 ) constraints a n d the o b j e c t i v e f u n c t i o n e n s u r e that the total n u m b e r o f tiers i n e a c h r o w w i l l n e v e r b e greater than 4 5 o r less than 3 0 . For each Therefore, scenario, w e can determine the space constraint the number o f extra 2 . 5 i n c h e s that should be c a n be accurately represented. Furthermore, since added. there are constraints f o r the total n u m b e r o f tiers i n each r o w , such constraints s h o u l d b e added. H e r e w e 55 take Scenario 1 as an example to explain how to revise the space constraints and add new constraints for each row. In Scenario 1, the total number of tiers in any of the rows 1,2,7 and 8 is more than 40 but less than 45, which suggests that an extra 20 (2.5*8) inches should be added. Therefore, there is only 480.5 (500.5-20) inches left for accommodating bins and the required one inch clearance between every two tiers (b-12). Notice that one extra inch is given on the left-hand-side because top tier bins do not need such clearance, the right-hand-side changes to 481.5 (480.5 + 1). Repeat the calculation for the other rows and we get the revised space constraints which replace (b-1): 7 * x,., + 11 * x i4 ^ 484 for i- 3,5,6 (6-10) 1 * x + 11 * x + 13 * x +17* x i4 ^ 486.5 for i- 4 (6-11) 7 * x + 11 * x i4 ^ 481.5 for i- 1,2,7,8 (6-12) l2 n j2 i2 n + 13 * x i3 + 17 * x i3 + 13 * x i3 + 17 * x The newly added constraints for the total number of tiers are: 4 ^40 forz = 3,5,6 (6-13) ^35 for i = 3,5,6 (6-14) fbri = 4 (6-15) 7=1 4 7=1 J>,^35 7=1 4 5^2*40 7=1 fori = 1,2,7,8 (6-16) We solve the new relaxed problem corresponding to each scenario to obtain the results shown in Figure B.6. Then the requirement for variables to be integer is added step by step, starting from the type of bins having the smallest value, to check under which scenario a feasible solution exists. After imposing the integer requirement to six-inch bins and sixteen-inch bins, feasible solutions are obtained in scenarios 1 2, 6 and 7. In all scenarios, the total number of tiers for six- 56 inch bins is less than four and the number for sixteen-inch bins is less than 16 (results of Step 3). Before we move on to add integer requirement to other variables, we first add two constraints for*,., and* : /4 x n e {0,1} for i= 1,2,...,8 (b-17) for i = 1,2,...,8 (b-18) The constraints are added because it is better to evenly allocate each type of bins to each row. Then we solve the new model and keep on moving by adding integer requirement for x j2 and x !3 After Step 6, feasible solutions are obtained in scenarios 6 and 7. Figure B.6 Branch Tree to Select Scenarios with Feasible Solutions Note: /= 1,2,...,8 57 The constraints for evenly allocating ten-inch bins and twelve-inch bins in the system are not reasonable because Archives and Special Collections require much more twelve-inch bins than other materials. Therefore, the process of finding feasible solutions using Integer Programming model is stopped when Step 6 is finished. The derived solutions for the number of bins in each row are shown in Table B - 1 1 and Table B - 1 2 . Table B - 1 1 Results of Scenario 6 Bins row 1 2 row 3 row 4 row 5 row 6 row 7 row 8 row 6" 1 1 1 0 0 0 0 0 10" 6 6 4 0 22 22 22 22 12" 29 29 32 33 16 16 16 16 16" 2 2 1 2 2 2 2 T o t a l tiers 38 38 38 35 40 40 40 40 heights 500.5 500.5 500.5 477 500.5 500.5 500.5 500.5 left(inches) 0 0 0 23.5 0 0 0 0 Total Space • 2 Table B-12 Results of Scenario 7 Bins , St 1 row -«n<i 2 row 3 row 4 row -th 5 ^th row 6 row 7 row oth 8 row 6" 1 1 1 0 0 0 0 0 10" 6 6 4 26 23 23 9 9 12" 29 29 32 12 15 15 27 27 16" 2 2 1 2 2 2 2 2 T o t a l tiers 38 38 38 40 40 40 38 38 height 500.5 500.5 500.5 492.5 498.5 498.5 500.5 500.5 left(inches) 0 0 0 8 2 2 0 0 Total Space There is a space waste in Both Scenario 6 and Scenario 7 , which suggests a further exploration. Scenario 6 and Scenario 7 have the same configuration for rows 1 and 2 , in which no space is 58 wasted. Rows 5 to 8 in Scenario 6 and rows 7 and 8 in Scenario 7 suggest two possible configurations with no space waste. Therefore, those configurations are kept initially and new configurations for Row 3 and Row 4 are further sought by rudimentary search. The final configuration is shown in Table 6-3. The solution sacrifices 104 twelve-inch bins in Row 1 to Row 3 to prevent a space waste. Such a sacrifice is acceptable by UBC Library. 59 APPENDIX C- ARRIVAL RATES C.l Circulation Desk There are two types of patrons at the circulation desk. The first type of patrons is the ones coming from open shelves, while the other is those requesting materials other than Archives and Special Collections in ASRS. Average Daily Requests and Renewals > 700 2 6 0 0 re 5 500 | <u I tt/\ 400 17 J\1 l 300 | 200 CD §• 100 CD * 0 1111111 O ) O O O ) cn C N oo cn O ) I C cn cn cn I I I C OD C cn cn cn cn cn cn I I I 5 C cn cn cn I I I N C o o o C M I I I O I I C O O O C M cnO o o o C M C M o o o C M o o C M • i i n i i n C O ) O C r~ N C O C N O o O O O O O C M C M O C N C N Date Figure C.l Open shelves and Storage Locations Average Daily Requests and Renewals There is neither an increasing nor a decreasing trend for the average daily requests and renewals in each month during the past five years. Therefore, we assume that the number of requests and renewals in the future will remain at the same level and historical data are used to determine the high, middle and low seasons. In the high season, two months are selected. One has the highest arrival rate and the other has the lowest arrival rate. These two months are selected in order to examine whether the same staffing 60 levels are required during high season. In the middle and low seasons, the month with the highest arrivals are selected. The staffing level determined by those representative months will meet the service requirements in other months of the same seasons. January, February, March, October, November } April, September May, June, July, August, December Figure C.2 Average Daily Requests and Renewals for Materials on Open shelves and in Storage Locations Based on Figure C.2 and detailed data analysis, the months in different seasons and the representative months are shown in Table C-l for the circulation desk. 61 Table C-l Season High Middle Low Seasons and Representatives Months January,February, M a r c h , October, April, May, November September June, July, August, December Representatives March, January September December In each of the selected months, we fitted the distribution of the daily arrivals and selected the 9 5 percentile values as the estimated daily arrivals for further analysis. C.l.l Histogram of Daily Arrivals of Open-shelf Patrons Figure C.3 Daily Arrivals of Open-shelf Patrons in a High Month in High Season 62 Figure C.4 Daily Arrivals of Open-shelf Patrons in a Low Month in High Season Figure C.5 Daily Arrivals of Open-shelf Patrons in Middle Season Histogram Estimated 20% distribution: N o r m a l (84, 36) S 10% 0% 95 percentile: 4 o 143 p a t r o n s / d a y OO OO o o OO O • OO Daily arrival Figure C.6 Daily Arrivals of Open-shelf Patrons in Low Season C.1.2 Daily Arrivals of ASRS General Patrons UBC Library has records of requests for materials in Storage Location. Inactive serials are currently not circulated and records for Library Processing Centre are not available. The volumes in these three locations are almost the same. We assume that the number of requests has the same linear relationship with the volumes in those three locations. Therefore, the total number of requests for all those materials will be three times the number of requests in the Storage Location. For the Storage Locations, we have two sources of data. One is from the original slips which patrons filled in to request materials and the other is the Library annual summary. We notice that the statistical summary for the number of requests is around 3 times the number of requests counted from slips. To be conservative, we assume that the annual summary figures are correct and the number of daily requests is three times the number of requests we counted from slips. There are two methods of fitting the distribution and finding the value of the 9 5 t h percentile. The first method is multiplying the original data by three, fitting the distribution and finding the 95th percentile value. The second method is fitting the distribution with the original data we have counted from slips, finding the 95th percentile value, then multiplying the value by three. We 64 i have tried both methods and found that the second method comes up with a slightly higher value. To be conservative, we have selected the second method. Therefore, the final daily arrival rate for slow moving materials excluding Archives and Special Collections and microforms is around 9 times the 95th percentile value of the distribution fitted by the data from original slips. The ratio of the number of requests over the number of patrons is 1.6. So each request is deemed as a patron. Thus, we fit distributions for daily requests to get daily arriving rates. Histogram Estimated distribution based on slips: 40% -0.5 + Gamma (7.17+1.42) 10% -J 95 percentile: 0% o n n <N 17 patrons/day OO D a i l y requests Figure C.7 Daily Requests in a High Month in High Season Library statistical record for the month is 3 times the sum of available slips record. Therefore daily arrivals are estimated to be 3*3* 17 =153. 65 Histogram Estimated distribution based on slips: -0.5 + Gamma (2.68, 2.44) 50% 40% 30% 95 percentile: 20% 14 patrons/day 10% 0% 0 1-5 6-10 11-15 16-20 21-25 Daily requests Figure C.8 Daily Requests in a Low Month in High Season Library statistical record for the month is 3.4 times the sum of available slips record. Therefore the estimated daily arrivals are 3.4*3* 14=141. Histogram Estimated distribution based on slips: 40% -0.5 + Gamma(4.12, 1.44) 30% 20% 95 percentile: 10% 11 patrons/day 0% Daily reqeusts Figure C.9 Daily Requests in Middle Season Library statistical record is 2.84 times the sum of available slips record. Therefore the estimated daily arrivals are 2.84*3* 11=93. 66 Histogram Estimated distribution based o n slips: 60% -0.5 + G a m m a (3.48,1.36) 50% 40% 30% 20% - 95 percentile: 10% - 9 patrons/day 0% Daily requests Figure CIO Daily Requests in Low Season Library statistical record is 3 times of the sum of available slips record. Therefore the estimated daily arrivals are 3*3*9=81. The summary of the daily arrival rates for estimating staffing levels at the circulation desk is shown in Table C-2. Table C-2 Daily Arrival Rates at the Circulation Desk Number of patrons / Day March January September December O p e n shelves 276 226 205 130 ASRS 153 141 93 81 C.l.3 Hourly Arrival Patterns in Different Seasons On each day, the arrival rate is not constant. We estimate the pattern of hourly arrivals based on the transaction records in the database for the number of patrons processed in each hour at the circulation desk in the representative months (Figure C.l 1 - Figure C.14). 67 January 14% 12% D) 10% 3C o 0. 8% 6% 4% 2% 0% 8 10 12 14 16 18 20 22 Hour Figure C.l 1 Hourly Arrivals' Pattern in a High Month in High Season Figure C.l2 Hourly Arrivals' Pattern in a Low Month in High Season September December 14% O) ac o a) a. 16% 14% « 12% J 1 10% . A . 12% 10% 8% c 6% 0) a a. 4% 2% 0% 8 10 12 14 16 18 20 22 Hour Figure C.l3 Hourly Arrivals' Pattern in Middle Season 7^ 8% 6% 4% 2% 0% 8 10 12 14 16 18 20 22 Hour Figure C . l 4 Hourly Arrivals'Pattern in Low Season 68 C.2 Archives and Special Collections Reference Desk The detailed arrivals' data at the reference desk are not available. UBC Library has statistical summary of total requests in each month. To be conservative, we still assume that each request represents one patron. Since detailed data are not available, we use the average daily requests in the selected month to represent the number of arrivals (Table C-3). The average of daily requests is obtained by dividing the monthly request over the number of working days. Since the requests for Archives and Special Collections are very low, the low season is negligible for analysis. A v e r a g e Daily R e q u e s t s March 70 UJ 60 t (A i 50 (2 40 t f f\ */ A /V jf cr /' / ° 30 ffi I 3 Z t / f il • * * * V] \H » October J \ 10 C c O n C o O p m C 3 ) c n c Q . ( ! ) J = C C 0 D 5 - 5 U 0 n ) a 0 ) 5 c p m O o c O p O q ) O t ' ^ - ) - c ^ p T c p - e ^ ^ Q . 6 ^ : C a . O S : C Q . O 5 D 5 - J C 0 Q S - 5 C 0 Q Month Figure C.l5 Average Daily Requests for Archives and Special Collections Table C-3 Arrival Rates at the Archives and Special Collections Reference Desk Archives Books March 37 27 October 25 20 69 The requests for microforms are ignored in the analysis because those that will be put into the system are seldom requested and their circulation data are unavailable. APPENDIX D SIMULATION MODEL- USER GUIDE D.l Introduction The UBC Irving Barber Learning Center ASRS simulation model(ASRSSIM), developed by the Centre for Operations Excellence, is a visual replication and analysis tool developed for borrowing process at the UBC Irving Barber Learning Centre after the ASRS is installed. This version of the ASRSSBM has been created using Arena 6.0 software. To help visualize the future borrowing process, the ASRSSTM animates the ASRS operations: Cranes and librarians are either busy or idle and patrons are either waiting in queue or doing checkout through the system. The visual representation allows users to see how the system would behave when system parameters such as staffing levels and customer processing time vary. The modeling tool requires four Creates in order to operate. Two schedules, Schedule Openshelf and Compactshelf, drive the creation of patrons arriving at the circulation desk and the reference desk. The other two schedules, Schedule ASRS and Schedule Archives, drive the creation of requests sent to the ASRS, those requests are duplicated as patrons in the models. Those schedules can be copied from excel file. In addition to providing visualization of the operations of ASRS and librarians, the simulation provides statistics output in real time over the duration of a simulation run. Final statistics are also generated at the end of each simulation run. Output statistics displayed during a run include: Cranes' utilization, Librarians' utilization, Queue length, average waiting time, maximum waiting time, etc. Generated output statistics include: Maximum number of patrons in queue at the circulation desk, Maximum waiting time in queue at the circulation desk, Maximum number of patrons in queue at the reference desk. The ASRSSIM has been modified into two separate versions. The two versions are slightly different in Librarian operation logic because it is too hard to depict the actual operations when 71 there are multiple librarians. The logic for Librarian operations is simplified but has little impact on the parameters of interest. D.2 Logic Overview The logical framework is the motor that drives request and patron entities through the simulated borrowing process. This framework is contained in one main logic section and 24 sub-models. 4 sub-models represent the operations of four cranes. 16 sub-models represent the process in which the librarians fetch requested items from workstation. 2 sub-models represent the check out process at the circulation desk. 2 sub-models represent the borrowing process at the reference desk. Modeling is initiated with the creation of patron (open shelves and compact shelves) or request (ASRS) entities. Attributes are assigned to requests to record the ID number and the type of requested item (Archives and special collections or Non Archives and Special Collections). Then the requests will initiate the corresponding cranes to move. At the same time, the requests are duplicated as patrons who will show up at the circulation desk or reference desk. Cranes Pick up and Return Bins Each crane has two simultaneous movements: horizontal and vertical. Variables are assigned to control the movement of a crane to make sure it moves correctly. After a bin is picked up by a crane, it will be dropped onto an empty workstation, waiting for a librarian to pick up the requested item(s). Each workstation can only hold one bin. Each aisle has two workstations. In an urgent case, the crane is instructed to pick up a bin and hold the bin at the front of the aisle until a librarian arrives to pick up the requested item(s). After the librarian picks up the item(s), the crane is instructed to put back the bin. The sub-models under each crane model simulate the returning process. 72 Items Picked up Process When an item is ready to be picked up, a librarian will come over to the workstation and pick it up from the bin. Then the librarian will check if someone is waiting at the desk. If yes, s/he will go back to the desk with the item. Otherwise s/he will check if there is any item waiting to be picked up. If yes, s/he will go to the corresponding workstation to pick up the item(s). Otherwise s/he will go back to the desk. Checking out Process Checking out process for ASRS patrons is more complicated than the checkout process for open shelves patrons or compact shelves patrons. When an ASRS patron reaches the desk, the librarian first checks if the requested item is ready on the shelf at the desk. If it is, the librarian will find the item and perform a checkout for the patron. Otherwise, the librarian will check the processing status of the requested item. If it is ready at the workstation, the librarian will go and pick up the item, then come back to do the checkout. If the request has not been processed by the crane, the librarian will prioritize the request, pick up the item when it is ready at the workstation, and does the checkout for the patron. The sub-models in this process are used to check the status of the request. D.3 Animation Screen The graphical animation screen that accompanies the simulation allows users to assess the current state of the model and determine how well the system is operating. The ASRS, librarians and associated queues are animated. A screen shot of the animations can be seen in Figure D . l . The top of the animation screen shows the vertical movements of the cranes. The L-shape illustrates the horizontal movements of the cranes. The queue line in front of librarian in the middle of the screen shows the number of patrons waiting for service. 73 The status of cranes and librarians are animated using different colors. Blue means idle and red means busy. The patrons in green are those who requested items belonging to ASRS. Figure D. 1 D.4 Shortcut Screen Shot of Animation Keys There are many screens in the simulation models that are accessible with shortcut keys. The user can simply press a key on the keyboard to gain the best view of certain simulation screen. Most useful shortcut keys are listed in Table D-l. 74 Table D-1 Shortcut Key List Shortcut key Description a Archives and Special Collections reference desk screen (large) c Circulation desk screen (large) g Graphs for status of cranes and librarians and queue length s A view for statistics D.5 Running Result Report After the user click the stop button when any of the simulation model finishes running, a window will appear to ask if the user would like to see the result. If the user selects Yes, a text file will automatically pops up. The common results shown in the file are the maximum number of patrons waiting in queue at the circulation desk, maximum waiting time in queue at the circulation desk, maximum number of patrons waiting in queue at the Archives and Special Collections reference desk. The text file from the simulation model with one librarian at each desk will provide the following information as well: Percentage of patrons with service time less than 2 minutes Percentage of patrons with service time less than 3 minutes Percentage of patrons with service time less than 4 minutes Percentage of patrons with service time less than 5 minutes D.6 Dynamic On-screen Displays In addition to being shown on the post-run reports, some model outputs have been animated and updated as the simulation run progresses. These outputs are shown when the shortcut key "s" is pressed. A screen shot of the information display is shown in Figure D.2. 75 Circulation Desk ArthrveS R e f e r e n c e Desk 1 Av*r.ftafcWi"rtinu T i m * ; { WimuteS) MAjt'tmurai Wd'nVirag Tim*{r*inutes; 1 11. II i .1 I.I L i 1. 1) i. i 1, J i, i g r e a t e r t f i f i n 2 m i r w t e s (*.'c) 0.0 1.« Pr^pOrtori of P i t r G n S v r h o S e S e r v i c e time a. a renter t h a n 5 nrimiteS(<yijj 0.1 L i L i i, ( Maximum Serving T i m * ( Minutes) Averi-weServirau T i m e {Minutes) Prvpurfuniof Patrons vrboSe S e r v k A time s AveNSoe T i m e in t h e S y t e m o f A S R S PitruraS ( M i n u t e s ) M a x i m u m T i m e in t h e Sy i t e m of A S R S Pitronci {Minutes) ASRS Throughput RJte { H u m her o f P a t r o n s } h o u r ) 0. 0 i Miiri Circulation Desk Librarian i A v e r a g e Utirczation{«ft) A i n r v t s R e f e r e n c e O e S k LibrArtAn A v e r a g e Ufirrafltiori{ yjj ( Figure D.2 i Screen Shot of Statistic Data
- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- UBC Theses and Dissertations /
- Planning an automated storage and retrieval system...
Open Collections
UBC Theses and Dissertations
Featured Collection
UBC Theses and Dissertations
Planning an automated storage and retrieval system at UBC Library Liu, Ying 2004
pdf
Page Metadata
Item Metadata
Title | Planning an automated storage and retrieval system at UBC Library |
Creator |
Liu, Ying |
Date Issued | 2004 |
Description | The university of British Columbia (UBC) Library plans to install an Automated Storage and Retrieval System (ASRS) at its Irving K. Barber Learning Centre. The system is intended to store 1.4 million volumes of materials, 0.8 million of which have already been identified. The Centre for Operations Excellence (COE) was asked to assist in the design of the system, to recommend desired staffing levels at the service desks and to assist in the selection of the remaining 0.6 million volumes of materials that should be stored in the system. In the ASRS, materials are stored in bins, and we have used stratified sampling in order to obtain the desired distribution of bin heights in the system. We have then formulated the overall bin configuration problem as an integer programming problem, and have used branch and bound and local search to find an optimal system configuration. Two discrete-event simulation models were constructed, using Arena 6.0, to gain insight into the operation of the system, and to recommend staffing levels at the circulation and reference desks, which ensure acceptable service levels. Finally we have used staffing levels and service level criteria to identify the remaining 0.6 million volumes of that should be stored in the system. |
Extent | 5935481 bytes |
Genre |
Thesis/Dissertation |
Type |
Text |
File Format | application/pdf |
Language | eng |
Date Available | 2009-11-18 |
Provider | Vancouver : University of British Columbia Library |
Rights | For non-commercial purposes only, such as research, private study and education. Additional conditions apply, see Terms of Use https://open.library.ubc.ca/terms_of_use. |
DOI | 10.14288/1.0091572 |
URI | http://hdl.handle.net/2429/15272 |
Degree |
Master of Science in Business - MScB |
Program |
Business Administration |
Affiliation |
Business, Sauder School of |
Degree Grantor | University of British Columbia |
Graduation Date | 2004-05 |
Campus |
UBCV |
Scholarly Level | Graduate |
Aggregated Source Repository | DSpace |
Download
- Media
- 831-ubc_2004-0259.pdf [ 5.66MB ]
- Metadata
- JSON: 831-1.0091572.json
- JSON-LD: 831-1.0091572-ld.json
- RDF/XML (Pretty): 831-1.0091572-rdf.xml
- RDF/JSON: 831-1.0091572-rdf.json
- Turtle: 831-1.0091572-turtle.txt
- N-Triples: 831-1.0091572-rdf-ntriples.txt
- Original Record: 831-1.0091572-source.json
- Full Text
- 831-1.0091572-fulltext.txt
- Citation
- 831-1.0091572.ris
Full Text
Cite
Citation Scheme:
Usage Statistics
Share
Embed
Customize your widget with the following options, then copy and paste the code below into the HTML
of your page to embed this item in your website.
<div id="ubcOpenCollectionsWidgetDisplay">
<script id="ubcOpenCollectionsWidget"
src="{[{embed.src}]}"
data-item="{[{embed.item}]}"
data-collection="{[{embed.collection}]}"
data-metadata="{[{embed.showMetadata}]}"
data-width="{[{embed.width}]}"
async >
</script>
</div>
Our image viewer uses the IIIF 2.0 standard.
To load this item in other compatible viewers, use this url:
http://iiif.library.ubc.ca/presentation/dsp.831.1-0091572/manifest