

small (250x250 max)
medium (500x500 max)
Large
Extra Large
large ( > 500x500)
Full Resolution


INTEGRATED ANALYTICAL PERFORMANCE EVALUATION MODELS OF WAREHOUSES By KARTHIK AYODHIRAMANUJAN Bachelor of Engineering (Mechanical) S. V. National Institute of Technology Surat, Gujarat, India 1998 Master of Science (Mechanical Engineering) Oklahoma State University Stillwater, Oklahoma, USA 2001 Submitted to the Faculty of the Graduate College of Oklahoma State University in partial fulfillment of the requirements for the Degree of DOCTOR OF PHILOSOPHY July, 2009 COPYRIGHT c By KARTHIK AYODHIRAMANUJAN July, 2009 INTEGRATED ANALYTICAL PERFORMANCE EVALUATION MODELS OF WAREHOUSES Dissertation Approved: Dr. Manjunath Kamath Dissertation Advisor Dr. Ricki G. Ingalls Dr. David B. Pratt Dr. Dursun Delen Dr. Gordon Emslie Dean of the Graduate College iii Acknowledgments There is an Indian adage about one’s spiritual evolution, “Maata, Pitha, Guru, Deivam”; Maata (mother) identifies the child to its Pitha (father), who shows the child to the Guru (teacher), who leads one to the path to Deivam (God). First and foremost, I wish to dedicate my work to my father (Late) Mr. Ayodhiramanujan and mother, Mrs. Ganapriya Ayodhiramanujan. There are no words that can express my gratitude to my advisor, Dr. Manjunath Kamath, who is not only my teacher but also my mentor, for providing me with valuable guidance and immense support at all times. I would like to thank my wife, Janani Murali, who by just being there for me gave me great strength in the last three years. Special thanks go to my committee members, Dr. Ricki Ingalls, Dr. David Pratt and Dr. Dursun Delen for their suggestions in simulation modeling, many aspects of warehouse processes and in general sharing their experiences with me, thereby bolstering my interest and confidence. I would like to take this opportunity to thank my friends and colleagues at the Center for Computer Integrated Manufacturing enterprises who made the research center, a home away from home. I would like to thank Sandeep Srivathsan for his tremendous help especially during my work from Dallas. Finally, I would like to acknowledge the financial support provided by Center for Engineering Logistics and Distribution, and Department of Biosystems Engineering at Oklahoma State University. As always, “Sarvam Krishnarpanam”, everything at the lotus feet of Lord Krishna. 4 Contents 1 Introduction 1 1.1 Warehousing Systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.2 Warehouse Activity Description . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.3 Performance Evaluation of Warehouses . . . . . . . . . . . . . . . . . . . . . 6 1.4 Motivation for the Current Research . . . . . . . . . . . . . . . . . . . . . . 7 1.4.1 The Problem Statement . . . . . . . . . . . . . . . . . . . . . . . . . 8 1.5 Overview of the Document . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 2 Literature Review 10 2.1 Review of Warehouse Performance Evaluation Models . . . . . . . . . . . . 10 2.1.1 Throughput Capacity Models . . . . . . . . . . . . . . . . . . . . . . 11 2.1.2 Storage Capacity Models . . . . . . . . . . . . . . . . . . . . . . . . 16 2.1.3 Integrated Design Methods . . . . . . . . . . . . . . . . . . . . . . . 18 2.2 Review of ProductionInventory Models . . . . . . . . . . . . . . . . . . . . 20 2.3 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 3 Statement of Research 25 3.1 Research Objectives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 3.2 Research Scope and Limitations . . . . . . . . . . . . . . . . . . . . . . . . 28 4 SharedServer System 29 4.1 SharedServer System Development . . . . . . . . . . . . . . . . . . . . . . . 29 4.1.1 Description of the SharedServer System . . . . . . . . . . . . . . . . 30 4.1.2 Assumptions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 4.2 CTMC Model and Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 4.2.1 Numerical Experiments . . . . . . . . . . . . . . . . . . . . . . . . . 36 4.3 Queueing Network Model of the SharedServer . . . . . . . . . . . . . . . . 39 4.3.1 Characterization of the Synchronization Station . . . . . . . . . . . 43 4.3.2 Characterization of the Processing Station . . . . . . . . . . . . . . . 45 4.3.3 Linking the Stations . . . . . . . . . . . . . . . . . . . . . . . . . . . 49 4.3.4 Solution Approach . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52 4.3.5 Computational Effort and Convergence . . . . . . . . . . . . . . . . 56 4.3.6 Performance Measures and Model Accuracy . . . . . . . . . . . . . . 56 4.3.7 Accuracy of the SharedServer Model . . . . . . . . . . . . . . . . . 58 4.3.8 Departure Process from the Retrieval Processing Station . . . . . . . 89 4.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96 i 5 SharedServer System: Multiserver case 98 5.1 Modifications to the Service Time . . . . . . . . . . . . . . . . . . . . . . . 98 5.2 Characterization of the Storage Processing Station . . . . . . . . . . . . . . 100 5.3 Accuracy of the MultiServer Model . . . . . . . . . . . . . . . . . . . . . . 102 5.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103 6 OrderPicking System 112 6.1 Description of the OrderPicking Model . . . . . . . . . . . . . . . . . . . . 113 6.2 Single Stage QI model with Batch Processing . . . . . . . . . . . . . . . . . 114 6.2.1 SingleServer Processing Station . . . . . . . . . . . . . . . . . . . . 116 6.2.2 MultiServer Processing Station . . . . . . . . . . . . . . . . . . . . . 122 6.3 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127 7 Integrated Warehouse Model 128 7.1 Warehouse Description . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 128 7.2 QueueingNetwork Description . . . . . . . . . . . . . . . . . . . . . . . . . 129 7.3 Analysis of the Integrated Model . . . . . . . . . . . . . . . . . . . . . . . . 130 7.3.1 Integrated Model : SingleServer Case . . . . . . . . . . . . . . . . . 131 7.3.2 Integrated Model : MultiServer Case . . . . . . . . . . . . . . . . . 141 7.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 142 8 Summary, Conclusions and Future Research 146 8.1 Research Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 146 8.2 Research Contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 148 8.3 Future Directions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 149 8.3.1 Research related to the sharedserver system . . . . . . . . . . . . . 149 8.3.2 Research related to warehouse system . . . . . . . . . . . . . . . . . 150 Bibliography 151 A Appendix 156 A.1 Stationary Equations  SharedServer System . . . . . . . . . . . . . . . . . 156 A.2 Simulation Study of the SharedServer System . . . . . . . . . . . . . . . . 160 ii List of Figures 1.1 Functional areas and product flow in a typical warehouse . . . . . . . . . . 4 1.2 A typical warehouse with forwardreserve inventory . . . . . . . . . . . . . . 5 2.1 EndofAisle System with (a) dedicated and (b) multiple aisles per picker . 13 2.2 An example Order Accumulation and Sortation System (Johnson and Meller, 2002) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 2.3 A simple highlevel queueing network model of a warehouse . . . . . . . . . 19 2.4 Mstage ProductionInventory model . . . . . . . . . . . . . . . . . . . . . . 21 3.1 A sharedserver system . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 3.2 An orderpicking system . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 4.1 Process and resource centric views of warehouse operations . . . . . . . . . 30 4.2 ProductionInventory (PI) models of (a) manufacturing system (b) warehouse rack storage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 4.3 Example statetransitions for the CTMC model of the sharedserver system 34 4.4 A single stage kanban system (Krishnamurthy, 2002) . . . . . . . . . . . . . 39 4.5 Queueing network model of a shared server . . . . . . . . . . . . . . . . . . 40 4.6 Overview of parametricdecomposition approach for the queueing network model of the sharedserver . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42 4.7 Characterization of storage synchronization station (JS) . . . . . . . . . . . 44 4.8 Characterization of the Storage Processing station (SP) . . . . . . . . . . . 46 4.9 Linking storage synchronization and storage processing stations . . . . . . . 50 4.10 Linking storage processing and retrieval synchronization stations . . . . . . 50 4.11 Retrieval throughput as a function of system variability in a balanced system 67 4.12 Utilization as a function of system variability in a balanced system . . . . . 69 4.13 Mean queue length (storage requests) as a function of system variability in a balanced system . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71 4.14 Retrieval throughput from a unbalanced sharedserver system at 90% expected utilization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88 4.15 Mean queue length of storage requests in an unbalanced sharedserver system at 90% expected utilization . . . . . . . . . . . . . . . . . . . . . . . . . . . 90 4.16 Mean queue length of retrieval requests in an unbalanced sharedserver system at 90% expected utilization . . . . . . . . . . . . . . . . . . . . . . . . . 92 4.17 Average inventory in rack in an unbalanced sharedserver system at 90% expected utilization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94 4.18 Sharedserver model with a downstream loading operation . . . . . . . . . . 96 iii 5.1 Multiple aisles (S/R machines) in the warehouse and sharedserver system with multiple servers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99 5.2 The multiserver storage processing station . . . . . . . . . . . . . . . . . . 100 5.3 Retrieval throughput as a function of system variability in a balanced sharedserver system with multiple servers . . . . . . . . . . . . . . . . . . . . . . . 108 5.4 Mean queue length (storage requests) as a function of system variability in a balanced sharedserver system with multiple servers . . . . . . . . . . . . . 110 6.1 Changing unitload configuration . . . . . . . . . . . . . . . . . . . . . . . . 112 6.2 A queueinginventory model that illustrates changing unitload configuration 113 6.3 Single stage QI model with batch processing . . . . . . . . . . . . . . . . . . 114 6.4 Average inventory level and average backorders at the rack at 80% utilization (singleserver processing station) . . . . . . . . . . . . . . . . . . . . . . . . 120 6.5 Average inventory level and average backorders at the rack at 90% utilization (singleserver processing station) . . . . . . . . . . . . . . . . . . . . . . . . 121 6.6 Average inventory level and average backorders at the rack at 80% utilization (multiserver processing station) . . . . . . . . . . . . . . . . . . . . . . . . 125 6.7 Average inventory level and average backorders at the rack at 90% utilization (multiserver processing station) . . . . . . . . . . . . . . . . . . . . . . . . 126 7.1 Iconic model of the warehouse . . . . . . . . . . . . . . . . . . . . . . . . . . 128 7.2 Queueing  Inventory model of the warehouse . . . . . . . . . . . . . . . . . 129 7.3 Input to and output from the Sharedserver stage . . . . . . . . . . . . . . . 131 7.4 Input to and output from InternalReplenishment stage . . . . . . . . . . . 132 7.5 Superposition of upstream and downstream arrivals to the orderpicking queue133 7.6 Input to and output from OrderPicking stage . . . . . . . . . . . . . . . . . 134 A.1 Plot of batch means of time in system for retrieval requests . . . . . . . . . 161 A.2 Plot of batch means of time in system for retrieval requests . . . . . . . . . 162 iv List of Tables 4.1 Design of experiments for shared server system (Markovian case) . . . . . . 35 4.2 Results for the sharedserver CTMC model (BS = BR = Z) = 0.8 and S = R = 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 4.3 Results for the sharedserver CTMC model (BS = BR > Z) = 0.8 and S = R = 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 4.4 Design of experiments for sharedserver system: single server case . . . . . . 58 4.5 Comparison of mean queue lengths (storage and retrieval requests) and average inventory level in the rack for S = R = 1 and 70% expected utilization (A: Analytical, S: Simulation) . . . . . . . . . . . . . . . . . . . . . . . . . . 60 4.6 Comparison of utilization and throughput of the shared server for S = R = 1 and 70% expected utilization (A: Analytical, S: Simulation) . . . . . . . . 61 4.7 Comparison of mean queue lengths (storage and retrieval requests) and average inventory level in the rack for S = R = 1 and 80% expected utilization (A: Analytical, S: Simulation) . . . . . . . . . . . . . . . . . . . . . . . . . . 62 4.8 Comparison of utilization and throughput of the shared server for S = R = 1 and 80% expected utilization (A: Analytical, S: Simulation) . . . . . . . . 63 4.9 Comparison of mean queue lengths (storage and retrieval requests) and average inventory level in the rack for S = R = 1 and 90% expected utilization (A: Analytical, S: Simulation) . . . . . . . . . . . . . . . . . . . . . . . . . . 64 4.10 Comparison of utilization and throughput of the shared server for S = R = 1 and 90% expected utilization (A: Analytical, S: Simulation) . . . . . . . . 65 4.11 Comparison of mean queue length (storage and retrieval requests) and average inventory in the rack at 70% expected utilization in an unbalanced system (A: Analytical, S: Simulation) . . . . . . . . . . . . . . . . . . . . . 73 4.12 Comparison of actual utilization and retrieval throughput at 70% expected utilization in an unbalanced system (A: Analytical, S: Simulation) . . . . . 76 4.13 Comparison of mean queue length (storage and retrieval requests) and average inventory in the rack at 80% expected utilization in an unbalanced system (A: Analytical, S: Simulation) . . . . . . . . . . . . . . . . . . . . . 78 4.14 Comparison of actual utilization and retrieval throughput at 80% expected utilization in an unbalanced system (A: Analytical, S: Simulation) . . . . . 81 4.15 Comparison of mean queue length (storage and retrieval requests) and average inventory in the rack at 90% expected utilization in an unbalanced system (A: Analytical, S: Simulation) . . . . . . . . . . . . . . . . . . . . . 83 4.16 Comparison of actual utilization and retrieval throughput at 90% expected utilization in an unbalanced system (A: Analytical, S: Simulation) . . . . . 86 4.17 Verification of SCV of the departure process of the retrieval requests from the sharedserver system at 90% expected utilization . . . . . . . . . . . . . 97 v 5.1 Experimental design for the sharedserver system: multi server case . . . . . 102 5.2 Comparison of mean queue lengths (storage and retrieval requests) and average inventory level in the rack for S = R = 1 and 80% expected utilization (A: Analytical, S: Simulation) . . . . . . . . . . . . . . . . . . . . . . . . . . 104 5.3 Comparison of utilization and throughput of the multi  shared server for S = R = 1 and 80% expected utilization (A: Analytical, S: Simulation) . 105 5.4 Comparison of mean queue lengths (storage and retrieval requests) and average inventory level in the rack for S = R = 1 and 90% expected utilization (A: Analytical, S: Simulation) . . . . . . . . . . . . . . . . . . . . . . . . . . 106 5.5 Comparison of utilization and throughput of the shared server for S = R = 1 and 90% expected utilization (A: Analytical, S: Simulation) . . . . . . . . 107 6.1 Experimental setup for single stage QI system with batching . . . . . . . . 118 6.2 Average inventory and average backorder at 80% utilization and batch size of 2 (singleserver processing station) . . . . . . . . . . . . . . . . . . . . . . 118 6.3 Average inventory and average backorder at 90% utilization and batch size of 2 (singleserver processing station) . . . . . . . . . . . . . . . . . . . . . . 119 6.4 Average inventory and average backorder at 80% utilization and batch size of 4 (singleserver processing station) . . . . . . . . . . . . . . . . . . . . . . 119 6.5 Average inventory and average backorder at 90% utilization and batch size of 4 (singleserver processing station) . . . . . . . . . . . . . . . . . . . . . . 119 6.6 Average inventory and average backorder at 80% utilization and batch size of 2 (multiserver processing station) . . . . . . . . . . . . . . . . . . . . . . 123 6.7 Average inventory and average backorder at 90% utilization and batch size of 2 (multiserver processing station) . . . . . . . . . . . . . . . . . . . . . . 124 6.8 Average inventory and average backorder at 80% utilization and batch size of 4 (multiserver processing station) . . . . . . . . . . . . . . . . . . . . . . 124 6.9 Average inventory and average backorder at 90% utilization and batch size of 4 (multiserver processing station) . . . . . . . . . . . . . . . . . . . . . . 124 7.1 Experimental design to evaluate the integrated model . . . . . . . . . . . . 136 7.2 Complete set of experiments to evaluate the integrated model (single server case) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 136 7.3 Analytical estimates of the performance measures when C2S = C2C = C2i = 0.5 (singleserver) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 138 7.4 Simulation estimates of the performance measures when C2S = C2C = C2i = 0.5 (singleserver) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 138 7.5 Error estimates of the performance measures when C2S = C2C = C2i = 0.5 (singleserver) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 138 7.6 Analytical estimates of the performance measures when C2S = C2C = C2i = 1 (singleserver) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 139 7.7 Simulation estimates of the performance measures when C2S = C2C = C2i = 1 (singleserver) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 139 7.8 Error estimates of the performance measures when C2S = C2C = C2i = 1 (singleserver) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 139 7.9 Analytical estimates of the performance measures when C2S = C2C = C2i = 2 (singleserver) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 140 vi 7.10 Simulation estimates of the performance measures when C2S = C2C = C2i = 2 (singleserver) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 140 7.11 Error estimates of the performance measures when C2S = C2C = C2i = 2 (singleserver) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 140 7.12 Complete set of experiment to evaluate the integrated model (multi server) 141 7.13 Analytical estimates of the performance measures when C2S = C2C = C2i = 0.5 (multiserver) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143 7.14 Simulation estimates of the performance measures when C2S = C2C = C2i = 0.5 (multiserver) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143 7.15 Error estimates of the performance measures when C2S = C2C = C2i = 0.5 (multiserver) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143 7.16 Analytical estimates of the performance measures when C2S = C2C = C2i = 1 (multiserver) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 144 7.17 Simulation estimates of the performance measures when C2S = C2C = C2i = 1 (multiserver) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 144 7.18 Error estimates of the performance measures when C2S = C2C = C2i = 1 (multiserver) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 144 7.19 Analytical estimates of the performance measures when C2S = C2C = C2i= 2 (multiserver) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 145 7.20 Simulation estimates of the performance measures when C2S = C2C= C2i = 2 (multiserver) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 145 7.21 Error estimates of the performance measures when C2S = C2C = C2i = 2 (multiserver) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 145 vii Chapter 1 Introduction With rapidly changing business scenarios, the role of warehouses is becoming increasingly critical in the efficient management and success of supply chains. With respect to their position in a supply chain, Frazelle (2001) classified the warehouses as • Production warehouses • Finished goods warehouses and fulfillment centers • Distribution warehouses • Contract warehouses Production warehouses hold raw materials or workinprocess inventory for use by manufacturing facilities. Finished goods warehouses store finished products, typically in pallet loads that serve as a buffer against uncertainties in customer demand. With the proliferation of ecommerce, fulfillment centers are shipping small quantities or individual items to end customers directly. Distribution warehouses accumulate and consolidate products from multiple manufacturing facilities for multiple customers. Contract warehouses are operated by a third party organization for one or more customers. Two major factors that have caused a change in the focus of warehousing systems are the evolution of manufacturing concepts like JustInTime and the evolution of information systems and technology. Mass customization and global competition are requiring supply 1 chain partners to be more flexible with respect to product demand and product mix. Frequent delivery in low volumes for a wide range of products is the focus of current supply chains, thus moving many small, but important valueadded services closer to the customer. With the renewed emphasis on customer satisfaction and integrated supply chain management, warehouses are not the traditional storage locations they once used to be. Today’s warehouses are responsive to customer demands by providing valueadded services such as last minute customization, small assembly, labeling, kitting, and special packaging. Hence, warehouse operations are not only more productive but also more complicated than ever before. Modern information systems have enabled the traditional warehouses plan their operations more effectively. Concepts such as crossdocking have received more attention; the results include the reduction of the time a product spends at a warehouse and the elimination of some storage and doublehandling of products. With customer demandpatterns evolving continuously, the drive to reduce cost and extreme competition have forced warehouses to devote a lot of effort to constantly improving their methods and systems. In such a dynamic environment, modeling and analysis of the underlying warehouse systems and continuous improvement of their operations becomes critical for their effective and efficient design and control. 1.1 Warehousing Systems Warehousing systems are one of the most researched components of a supply chain. Many authors have provided excellent reviews of warehousing systems, see for example, Berg (1999), Berg & Zijm (1999), Yoon & Sharp (1996), and Tompkins et al. (2003). Depending on the position of the warehouse in the supply chain, the activities within the warehouse and the form of material handled are determined. The typical activities in a warehouse are summarized in Figure 1.1. Receiving is the collection of all the activities related to the orderly receipt of goods, inspection (for quantity and quality) and disbursing to storage or crossdocking for immediate shipping. 2 Repackaging is the process of splitting the products that are ordered in bulk quantities and repacking to customer specifications (single or carton/case), or assembling to form kits with other parts of a customer shipment. Some part of the load might also be held in storage for future shipment. This function is also called breakbulk operation. Putaway is the process of placing the merchandise in either longterm storage (reserve) or shortterm storage (forward). Orderpicking is the process of retrieving items from the storage area to meet a specific demand. Many classifications of warehousing systems exist based on the type of order picking which is the most cost intensive process in the warehouse. Sortation is the process of sorting the accumulated batch picks into individual orders. Crossdocking is the process of staging the inbound goods directly to shipping without sending it to storage. Replenishment is the process of refilling the primary and secondary picking areas from longterm storage. Shipping includes all the activities related to checking the order for completeness and appropriate packaging; determining shipping charges; accumulating orders by outbound trailer; and loading the trailers. 1.2 Warehouse Activity Description The basic functions common to all the warehouses are receiving, putaway or storage, picking, and shipping. A typical warehouse with reserve and forward storage areas, together with the material flow is shown in Figure 1.2. In this section, we will describe the configuration of warehouses with particular attention to storage and retrieval operations. A typical material flow in a warehouse starts with the incoming trucks arriving into the yard. The trucks either deliver the trailers directly to the dock or wait in a queue till a dock door is available. Once the trailer occupies a dock door, a worker crew (strippers) is assigned 3 Figure 1.1: Functional areas and product flow in a typical warehouse to unload the trailer. In this dissertation, we assume that trailers contain pallet loads. The workers unload all the contents of the trailer and place the items in the receiving/staging area for further processing (e.g. inspection). The dock door is then scheduled to unload the next waiting trailer. The stripper or another employee verifies the contents of the trailer for quality in the receiving/staging area. The stripper may place the items for crossdocking or longterm storage. Discrete or continuous material handling devices may be used to move the items from the receiving area. The items meant for longterm storage usually do not alter their unitload configuration. Workers/fork lifts move the pallets into the reserve storage area. This process is automated in some warehouses using Automated Guided Vehicles (AGVs). The reserve storage may be as simple as a rack storage system or an Automated Storage and Retrieval System (AS/RS). In the case of AS/RS, the storage into the racks and retrievals from the racks are performed by Storage/Retrieval (S/R) machines. A warehouse dealing with lessthanpalletloads may have two different storage areas – reserve or long term storage for pallets and forward or short term storage for cases. The presence of forward and reserve areas necessitates an internal replenishment policy. There 4 Figure 1.2: A typical warehouse with forwardreserve inventory is a break bulk operation, i.e. pallets from the reserve storage are broken into individual cases. Typically the order pickers picking from the forward area pick individual cases from the replenished pallet loads. Some warehouses may deal with individual items. In such scenarios, there is another break bulk like operation called the splitcase operation. The order pickers may pick individual items from the cases; sort and assemble an order before shipping. Each order is defined by number of unique line items and related quantities. Once an order is received for an item, orders are picked either from the forward or reserve storage. Items are accumulated in a shipping/staging area to be loaded on to the trailers. The orders are verified to ensure quality and items are loaded by a worker crew (stackers). The items are assembled to form a tight packing and order integrity is preferred, i.e., items in the same order are shipped together. Some of the factors that influence the retrieval of items include: • Order picking method – single, dual or multiple command • Material handling equipment properties – capacity of the carts, fork lifts or pallet jacks 5 • Layout of the terminals – multiple cross aisles • Storage assignment policies – random, dedicated, or class based • Clustering of items in storage • Order batching and hence, associated sortation process if necessary • Presence of forwardreserve storage areas In some warehouses, palletization may be an additional process to build unit load pallets that could consist of similar items or a mixed load. 1.3 Performance Evaluation of Warehouses Suri et al. (1993) defined performance evaluation (PE) as "a methodology (including techniques and tools) for determining the performance measures that can be expected to result from a given set of decisions." Performance evaluation usually employs simulation models or analytical models. Simulation models are dynamic in nature and model the evolution of the system over time. These are detailed models and model development takes considerable effort. Analytical models, also called as aggregate dynamic models, account for some uncertainties and interactions in the system using mathematical or symbolic relationships. These models can be used for rapid analysis of many design configurations albeit at an aggregate level. Analytical models based on stochastic Petri nets, Markov chains, and queueing theory provide rapid analysis capability and can provide insights into the behavior of the system. As with any performance evaluation model, there is a tradeoff between model detail and tractability. Some of the performance measures of interest in a warehouse environment are throughput, average response time, fill rate, and utilization of space, equipment, and human resources, in addition to financial metrics. Schefczyk (1990) provides a comprehensive list of performance measures related to warehouses. Many authors have developed performance evaluation models for warehousing systems. A detailed review is provided in the following chapter. To a great extent, these models 6 focus on a particular system or class of systems within a bigger facility, for example Endof Aisle order picking systems (Bozer & White (1990)), AS/RS (Abdelkrim et al. (2003), and Lee (1997)), and sortation systems (Bozer et al. (1988) and Johnson and Meller (2002)), which are important subsystems of a warehouse. Some of the models focus on limited and welldefined isolated problems like routing and sequencing of order pickers or dwell point determination, neglecting the interaction amongst system components. 1.4 Motivation for the Current Research Warehouse system design is a complex process with numerous alternatives at all design levels for the designer to consider and evaluate. For example, a warehouse might deal with more than one product configuration (pallet, case, or item), choice of storage systems (AS/RS, carousels, or bin shelves), and storage policies (random, classbased or dedicated). Warehouse design decisions typically focus on three important aspects; the throughput capacity, the size of the inventory to be stored and the material handling equipment requirements. Enumerating all feasible solutions that satisfy the throughput and storage capacity requirements and finding an optimal solution is not practical. Until now, the decisionmakers have relied on experience and descriptive, systematic procedures to select a set of feasible candidates of warehouse design. The literature on integrated models focuses either on descriptive design methodologies (e.g., Ashayeri & Goetschalckx (1988)) or sequential solution approaches. In addition, the warehouse managers have limited readymade tools to evaluate the warehouse performance or resource requirement if a new operation is to be incorporated into the material flow, for example, repackaging. Simulation is the preferred tool for evaluating the designs. Building a warehouse simulation model takes considerable time and effort, though computing power is no longer a constraint. Analytical models for performance evaluation, on the other hand may be approximate but enable quick evaluation and offer insight into the system behavior. Analytical models can help in examining a larger set of alternatives initially, thereby reducing the number of candidates for detailed simulation analysis. A useful tool in the design pro 7 cess or in the evaluation of current warehousing systems would be an integrated model that can capture the interactions among material handling and storage processes that span receiving, inspection, storage/putaway, picking, shipping and valueadded services. Isolated analysis of warehouse subsystems, though valuable and important, is not sufficient at the overall system design stage. Rouwenhorst et al. (2000) point out that the design decisions at the strategic and tactical levels are interrelated. For example, a decision to have separate forward and reserve areas (strategic) leads to an inventory replenishment policy between the storage areas (tactical). Also, the inventory decisions (size of the warehouse) are made independently from the individual subsystems such as AS/RS. But the performance of the subsystems is affected by the storage size. Such interrelated decisions need to be modeled jointly. To support decision making for the new generations of warehouses, there is a need to include a larger set of issues such as inventory and capacity/congestion, within a single analytical model, so that their impact on the total system performance can be evaluated. 1.4.1 The Problem Statement With the changing role of warehouses, the ability to model multiple decisions simultaneously, especially inventory and throughput decisions, will complement the warehouse design process and aid in analyzing existing operations. Queues and queueing networks have been applied in the performance evaluation of warehouses, but the focus has been more on isolated systems like AS/RS and its related decisions like throughput and storage size estimation, separately. Productioninventory networks, i.e., queueing network models that address both capacity/ congestion and planned inventory issues have been successfully applied in manufacturing and supply chain systems. But very limited literature is available on their application in the warehouse domain. This dissertation is the first step towards addressing this gap. Hence, the problem statement can be described as “developing analytical models of queueinginventory systems that address capacity/congestion and inventory issues simultaneously in the context of a warehouse system.” To this end, the dissertation first focuses on the development of performance evaluation 8 models of subcomponents that are representative of AS/RS type systems (e.g., a server that stores and retrieves material from the same storage area) and orderpicking systems where unitload configurations vary between two successive material movements. These models address both material handling and material storage operations in a manner similar to the productioninventory models. The dissertation also demonstrates the applicability of these individual models in building comprehensive endtoend warehouse performance evaluation models. 1.5 Overview of the Document In this chapter, we introduced warehousing systems in general, and commented on the current status of performance evaluation of such systems. We described some of the characteristics of warehousing systems and provided the motivation for the research effort. Chapter 2 gives an overview of the warehouse performance evaluation models and a review of the literature on productioninventory networks. The research objectives, general assumptions and research limitations are summarized in Chapter 3. In Chapter 4, we focus on the development and analysis of the sharedserver system, a key building block in the performance evaluation of warehouses. We extend the sharedserver model to the multiserver case in Chapter 5. We then focus on the development and analysis of models that accommodate changing unitload configuration (single and multiserver cases) in Chapter 6. Chapter 7 illustrates the development of a proofofconcept endtoend model for warehouses. Finally, we conclude the dissertation with a prospectus for future research with respect to warehouse performance evaluation models. 9 Chapter 2 Literature Review In this chapter, we focus on the review of literature pertinent to warehouse performance evaluation and productioninventory models. The analytical models in this review tend to focus more on the application of queueing or queueing network models. 2.1 Review of Warehouse Performance Evaluation Models The major sources of randomness in a warehouse are the demand for the items to be retrieved from storage, the arrival of the items to be stored, the material handling times and the inherent reliability of the servers (human and machine). Sophisticated simulation models that address some of these sources of randomness have been developed and can evaluate the performance of different configurations of warehouses (see for example, Linn & Wysk (1984), Berg & Gademann (2000) among others). The analytical performance evaluation models of warehouses can be classified as throughput capacity models, storage capacity models, and warehouse design models (Cormier & Gunn (1992)). Throughput capacity models are mostly tactical and operational models that evaluate the throughput of the warehouse, where throughput is defined as the number of storage/retrieval operations per unit time. The storage capacity models, which are usually strategic models, focus on the determination of the size of the warehouse to satisfy a minimum service level commitment. The warehouse design models focus on the overall design involving decisions related to space allocation among storage systems, crossdocking, 10 and other valueadded services. 2.1.1 Throughput Capacity Models Throughput capacity issues have received considerable attention in the warehouse literature, mainly because the orderpicking costs constitute a major portion of the total operational costs (Tompkins et al. (2003)). In this section, we will summarize the modeling approach and the decisions considered in the throughput models for two important subsystems, namely Automated Storage and Retrieval Systems (AS/RS) and Order Accumulation and Sortation Systems (OASS). AS/RS performance evaluation models have focused on the development of traveltime models for both unitload AS/RS and miniload AS/RS. For a detailed literature survey on stochastic modeling of AS/RS and travel time models, the reader is referred to Johnson and Brandeau (1996) and Sarker & Babu (1995) respectively. Lee (1997) presented the first stochastic analysis of a unitload AS/RS by using a singleserver queueing model. He assumed aisle captive S/R machines and modeled each aisle as a single server with two queues: a storage queue for incoming unit loads and a retrieval queue. Both the queues have finite capacity. The storage and retrieval arrivals are lost when the queues are full. The S/R machine always returned to the I/O point and the FIFO policy was followed for the queues, except when both the queues had transactions waiting. In the later case, a dual command cycle is performed. The proposed model could be viewed in part as an assemblylike queue and in part as a polling queue. Lee (1997) further assumed independent Poisson arrivals for storage and retrieval queues, and exponential service times for single and dual command cycles. Using a Continuous Time Markov Chain (CTMC) to represent the queue, Lee derived many useful performance measures including system throughput, turn around time for the requests and S/R machine utilization. The limited queue capacity and high variance assumption in the previous model underestimated the throughput and the S/R machine utilization. Lee (1997) had also assumed equal arrival rates for storage and retrieval. Hur et al. (2004) relaxed some these assumptions and modeled the S/R machine as a M/G/1 queuing system with separate queues for storage and retrieval requests. There was 11 no capacity limit on the queues and the arrivals were independent with different arrival rates. They assumed that the S/R machine could start and end the single command (SC) and dual command (DC) cycles at the I/O point or at the rack. Because of this assumption, they also assumed that the travel time for the SC and DC followed the same distribution with a single service rate. They also proposed a state space for the S/R machine by defining the state as (i, j) where i, j are the number of requests in the storage and retrieval queues, respectively, after a service completion. The resulting CTMC was solved to derive system performance measures. They compared their solution with that of Lee (1997) and found it to outperform Lee’s in many instances. Bozer & Cho (2005) assumed separate travel times for SC and DC cycles. They assumed the dwell point as the last known storage location of the S/R machine. The S/R machine always tried to perform a DC violating the FIFO policy for storage or retrieval request arrivals. They still assumed independent Poisson arrivals. For random storage assignment and different configurations of the rack, they derived closed form equations to determine whether the AS/RS meets the required throughput. They compared the S/R machine utilization for balanced and unbalanced systems (when storage requests exceeded retrieval requests or vice versa, which is possible in a warehouse) with simulation. Their results are also valid for other storage assignment policies and I/O point locations as long as the mean interleaving time (time between dropoff and pickup) in a DC cycle is smaller than mean SC cycle time. Hur & Nam (2006) extended the models of Hur et al. (2004) by considering separate service times for single and dual command cycles for the S/R machine with Poisson arrivals for service requests. They assumed finite queue capacity only for storage requests. The state space of the system is defined as the number of requests in the queues at the completion of a service request or the start of a busy period, similar to the earlier model. A Semi Markov Process (SMP) is generated from the Markov Chain to obtain the timeaverage probabilities, which is later used to obtain the system performance measures, including the probability that an arbitrary arrival is lost. All the above models for AS/RS performance evaluation considered unitload systems with equal sized storage spaces. Lee et al. (1999) presented models for AS/RS with unequal sized cells, i.e. cells within 12 Figure 2.1: EndofAisle System with (a) dedicated and (b) multiple aisles per picker a zone have the same size but differ in size between zones. They derived travel time models for SC and DC cycles, including interleaving time between different zones. An example of endofaisle order picking systems is a miniload AS/RS. In such systems, stored material is delivered by the S/R machine to the order picker located at the end of the aisle. While the order picker picks from the storage container, the S/R machine returns the previous container and retrieves the next order. These systems operate predominantly DC cycles. There are at least two pick positions at the end of each aisle. Bozer & White (1990) presented a design algorithm for such endofaisle order picking systems. They modeled each aisle as a closed queueing network with two nodes, the S/R machine and the order picker, as shown in Figure 2.1(a). The number of pick locations was the number of customers in the system. They assumed random storage policy with dedicated pickers for each aisle. They presented an iterative algorithm to find the minimum number of aisles necessary to meet the storage and throughput requirements. The throughput constraints were based on the picker utilization and the S/R machine utilization was only an additional measurement. Using simulation, they obtained an approximation for the standard deviation of the DC cycle travel time and approximated the DC cycle time with a uniform distribution. Their model confirmed that as the rack became more nonsquareintime, the number of aisles increased to meet the required throughput. Bozer & White (1996) extended their work to model multiple pick positions per aisle. 13 They relaxed their assumptions about aislerestricted orderpicker. The more general closed queueing network model is shown in Figure 2.1(b). Using diffusion approximations, they derived the expected utilization of the S/R machine and the order picker. They modified their design algorithm to include the expressions for utilization. They further experimented with sequencing of the retrieval requests. Only when the variance of pick time is low, significant improvements to throughput were achieved. Park (1999) used a similar closed queueing network model to study the impact of buffer sizes (number of pick locations per aisle for storage and retrieval queues) on the throughput of the system. They found that the maximum throughput obtainable by increasing the queue capacity is less than or equal to twice the throughput with a single space for storage and retrieval. They also analyzed the conditions under which the S/R machine can be blocked (“production blocking”) because of limited queue capacity. The literature on performance evaluation of AS/RS also considers operational details such as dwell point and order batching, and operating characteristics such as acceleration and deceleration of the S/R machines. Order Accumulation and Sortation Systems (OASS) find applications in both manufacturing and warehousing systems. The basic components in an OASS are the input conveyors; induction, spacing, and merge units; sortation mainline; and diverter modules. An example OASS is given in Figure 2.2 with one induction point, a recirculating conveyor, and multiple accumulation lanes (Johnson and Meller (2002)). In distribution centers, when orders are picked at the case and item level, orders are dispatched to the conveyor that sorts the items to different chutes assigned to a particular order or outbound truck. Throughput of the OASS is an important performance measure and it depends on many factors including the speed of the conveyors, induction process, sorting strategies, the upstream order picking process and downstream stacking/palletizing process amongst others. For wave picking (each wave consists of many orders and each order consists of many line items) and recirculating sortation conveyors, Johnson (1998) developed analytical models that study the impact of sorting strategies on the throughput of the system. He developed expressions for the expected time to sort a wave with and without blocking at the accumulation conveyors for Fixed Priority Rule (FPR) (smallest order first and largest order first) 14 Figure 2.2: An example Order Accumulation and Sortation System (Johnson and Meller, 2002) and Next Available Rules (NAR) for sorting. In the NAR, the orders are sorted based on the order in which the boxes pass through the scanner that initiates the sorting process. Eldemir (2003) developed another strategy based on the earliest completion time of an order, which reduced the wave sortation time. Johnson and Meller (2002) developed analytical models of an OASS with multiple induction points in the main conveyor. They assumed no recirculation of orders. When there is no blocking at the accumulation conveyors and the number of orders is less than the number of accumulation conveyors, the OASS performance is dependent only on the induction process. The authors analyze systems with sidebyside induction points and split induction points. In the sidebyside induction systems, the inductors compete for the same scanner thereby creating interference like phenomenon that tends to reduce the system throughput. The authors also address the impact of presorting orders on the OASS system performance. Eldemir (2003) proposed an open queueing network model for the design of OASS. The network consists of three processes (induction, sortation, and shipping) with corresponding queues (induction lane, main conveyor, and accumulation line). He derived expressions for the blocking probability and the lengths of the main sortation and accumulation conveyors by approximating each queue as an M/G/n/N queue. Russell & Meller (2003) developed descriptive and prescriptive design models for order fulfillment systems that are integrated order picking and ordersortation systems. They developed throughput simulation models 15 to compare the different configurations of wave picking and manual and automated OASS systems. Apart from these studies on OASS, there is a huge body of literature on conveyor theory, see for example, Bastani (1988); Arantes et al. (1998) and Bozer & Hsieh (2005) amongst others. 2.1.2 Storage Capacity Models The purpose of storage capacity models is to determine the number of warehouses, the size of each warehouse and any additional space that could be leased by minimizing the total discounted costs and/or to achieve predetermined service level. Cormier & Gunn (1992) categorized the models as static and dynamic models. In static models, the demand is assumed stationary and a warehouse size is determined. In dynamic models, the demand is assumed to be nonstationary and the warehouse is allowed to expand and contract i.e. size of the warehouse at different periods is determined. The authors also review models related to performance evaluation and maximization of space utilization through unitization & block stacking methods. Roll & Rosenblatt (1983) compared the effect of random and grouped storage policies on the warehouse capacity. In general, the random storage policy offers higher space utilization (assumption that the demand for each pallet is independent and all storage spaces are equally likely to be occupied) compared to grouped storage policy. In addition, the authors clearly noted that grouped storage policies offered operational and administrative advantages over the random storage policy. The authors defined Nominal Capacity Requirements (NCR) as the product of average throughput and the average storage time for each pallet. It is the lower bound on the required warehouse capacity and is the average size necessary subject to random throughput factors. Because of the stochastic nature of the arrivals of order and number of items per order, the warehouse may not be able to store the entire shipment and has to lease space outside. The effects of number of items and their characteristics, and operational issues (travel distances, orderpicking policies) were not considered. Rosenblatt & Roll (1988) later studied the factors that influence the storage capacity of the warehouse; a) number of items stored, b) demand characteristics of the items 16 (distribution of orders and items in an order) c) replenishment policy (order quantity and order point) for the item. They performed simulation experiments assuming a (r, Q) replenishment policy and random storage policy. They derived an approximate multiplicative expression using regression analysis for the deviation from the NCR for 95% service level as follows: Y95 = 34 Q0.16D0.22 1 N0.62r0.06D0.02 2 (2.1) where, Q is the order quantity, r is the reorder point, D1 is the average demand (orders/ day), D2 is the percentage deviation from D1, and N is the number of items. We can see that reorder point and the variance of the demand have very little effect on capacity. They tested the demand for different distributions (uniform, normal and exponential) and found that the maximum deviation was around 10% of the NCR capacity. They assumed the same inventory policy for all items and that the items have similar physical and economical characteristics. They also claimed that changes in the above have little effect on the storage capacity. Roll et al. (1989) found a suitable size of a warehouse container and used simulation to find the optimal combination of warehouse capacity and container size. Sung & Han (1992) extended the queuing model of Schwarz et al. (1978) to determine the size of AS/RS for single and multiple item storage scenarios. In the case of single item storage, the AS/RS is treated as an M/M/m/m or M/G/m/m model. For multiple item storage, a single class closed queueing network model is developed to determine the storage size. Both the models were extended to include blocking (when an arriving item does not find a storage space in the rack) and batch arrivals. The important assumption is that the items spend a known but random amount of time at the racks. Cormier & Gunn (1992) formulated the warehouse sizing problem as a cost minimization problem considering inventory policy costs, warehouse construction/operating costs and the cost of leasing for constant product demand (static conditions) for a single period, assuming a continuous review policy without the possibility of backorders. Rao & Rao (1998) presented a modified formulation for warehouse sizing under static and dynamic conditions. They provided three extensions to the static conditions involving 17 varying cost over time, economies of scale in capital expenditure and/or operating cost and stochastic version. The dynamic version of the problem with stochastic demand was shown to be a network flow problem and its concave cost version could be solved efficiently using dynamic programming methods. Huang et al. (2003) simultaneously selected distribution centers and their capacities by solving a 2stage distribution network. They modeled the distribution center as an M/G/c queue where each storage space represents a server. They consider the case of discrete and continuous racks. They also studied the difference between a stepwise approach (site selection and space determination) and the integrated approach. 2.1.3 Integrated Design Methods The warehouse design procedure is a complex process because the number of available design alternatives is large and hence, the choice of a particular design depends on the experience of the designers. Ashayeri & Goetschalckx (1988) presented a systematic planning and designing procedure for orderpicking systems. Their stepwise design procedure consists of nine steps starting with external strategic planning considering market information to selecting operational policies for the order picking system. Gray et al. (1992) proposed a multistage hierarchical decision approach. The approach consists of three levels; facility design and technology selection, item allocation, and operating policy decisions. Each level has a set of mathematical models that evaluates the major tradeoffs to obtain a set of feasible design alternatives. The authors suggest the use of simulation to fine tune the design and operating policies. They applied the methodology successfully to design a spare parts distribution center. Yoon & Sharp (1995, 1996) present a cognitive design procedure for an order picking system (OPS). They present a general framework for the OPS design and analysis that consists of a general structure of the OPS and a conceptual design procedure. The general structure illustrates all the functional areas and material flows (pallets, cases, and items) in an OPS. The conceptual design procedure consists of input, selection and evaluation stages. An alternative design methodology was proposed by McGinnis et al. (2000) based on a functional flow network. The activities are represented as nodes and flows are represented 18 Figure 2.3: A simple highlevel queueing network model of a warehouse as arcs. Once a flow network for a particular configuration of the warehouse is established, the functions are assigned to spaces in the warehouse. Goetschalckx et al. (2002) applied this methodology for a small parts warehousing system. Bodner et al. (2002) developed a process model to assist in the development of computational tools for warehouse design. Many researchers have used simulation to analyze tactical and operational decisions simultaneously. Petersen & Aase (2004) compared picking, storage and routing policies on warehouse throughput. Manzini et al. (2005) used simulation to develop an expert system by performing a comprehensive set of designed experiments. Berg & Gademann (2000) compared control policies like storage location assignment and sequencing together using simulation. Eldemir (2003) suggested two approaches for modeling an integrated system based on queuing network and material flow diagrams. Material flow diagrams are graphical representations of the movement of materials used in a process. They are a useful aid in identifying the source, stages and sink including the quantities and losses at each stage/process. Using a set of standard procedures at the process and routing probabilities after the process, system throughput, and subsystem throughput can be calculated. This approach cannot capture the stochastic nature of the processes in the system. The second approach is modeling the system as a network of queues. The author had modeled individual systems (palletizer, AS/RS, and sortation) with buffer capacities. Eldemir (2003) suggested the use of Jackson network type models or Queueing Network Analyzer (QNA) based models proposed by Whitt (1983). An example of such a system model is presented in Figure 2.3. 19 Jackson network assumes exponential service times and Poisson arrivals. In addition, the extensions for multiple classes assume that the service time is the same for all the classes, which severely restricts the model use. QNA provides a more flexible framework for modeling such a system. Our approach is based on the parametricdecomposition approach presented by Whitt (1983). In the queueing network approach suggested by Eldemir (2003), the storage rack configuration is modeled implicitly in the service time of the S/R machines operating in a single or dual command mode. Other authors who explicitly consider the rack and the storage process, assume that each rack space/bay as a server (Huang et al. (2003)) or the rack as a queue space. The disadvantage of the first approach is that the service time of the racks is not known or can only be assumed. Some retail warehouses are very large with thousands of bays effectively modifying the rack to be an infinite server. In the case where rack is treated as a queue space, the potentially large queue space will tend to behave like an infinite queue. 2.2 Review of ProductionInventory Models General queueing network models are readily applicable for maketoorder systems, where the only inventory is the workinprocess due to the parts waiting to be processed. In maketostock systems, finished goods and intermediate items are produced and stored in anticipation of customer demand. The demand is satisfied immediately reducing the overall waiting time of the customer. Such holding of both finished goods and intermediate parts in anticipation of demand is called planned inventory. In addition to providing better customer service, the planned inventories act as a buffer against uncertainties like machine failure. Some of the relevant literature in productioninventory networks includes Buzacott & Shantikumar (1993), Lee and Zipkin (1992), Sivaramakrishnan & Kamath (1997), Sivaramakrishnan (1998) and Zipkin (1995). A review of the relevant work is presented in the following paragraphs. Consider an Mstage productioninventory model as shown in Figure 2.4. Each stage is represented by a queueserveroutput store. Each stage operates under a basestock 20 Figure 2.4: Mstage ProductionInventory model policy. The base stock level is the maximum planned inventory at the output a stage. The demand process, occurring at the Mth stage is assumed to be a renewal process and for one unit at any given time. If a finished item is available, the order is fulfilled immediately and a replenishment order is placed at stage M − 1. Such a policy is called a oneforone replenishment policy. If the item is not available, the demand is backordered. The inventory is replenished until the base stock level is reached. The replenishment order at stage M − 1 looks at the output store of that stage. If a part is available, it immediately moves to the processing queue of stage M and an upstream replenishment order is placed else it is backordered. In the first stage, orders join the processing queue immediately. Unlimited supply of raw material is assumed at stage 1. In all the stages, a backorder is fulfilled first before the planned inventory is replenished. In the oneforone replenishment policy, the demand arrivals are reflected at all the stages of the network. Hybrids of maketoorder and maketostock systems can be analyzed by constraining some of the basestock levels to be zero. Lee and Zipkin (1992) modeled such a tandem production line with Poisson arrivals and exponential service times. They modeled each stage as an M/M/1 queue and applied the approximations of Svoronos & Zipkin (1991) for a multiechelon inventory system. Zipkin (1995) extended these results to tandem queues with feedback. Single stage maketostock systems were studied extensively by Buzacott & Shantikumar (1993). They modeled such systems using the ProductionAuthorization (PA) card concept. When each item in the manufacturing facility is produced, a tag is associated with the item. When the demand consumes an item in the output store, the tag is removed and is converted into a ProductionAuthorization card. They vary the rules governing the transmission of 21 PA cards to authorize production. The variations are a) immediate transmittal of PA cards into the facility as soon as it is generated, b) fixed batch of PA cards, say q, when at least q PA cards are accumulated, and c) all the PA cards when at least q PA cards are accumulated. These variations represent the oneforone replenishment base stock policy, reorder point/order quantity and reorder point/order up to inventory policies, respectively. Buzacott & Shantikumar (1993) modeled single stage systems with unit demand, bulk demand, and interruptible demand, backlogging and lost sales, yield loses and multiple classes of customers. Sivaramakrishnan & Kamath (1997) analyzed multistage tandem maketostock systems using a node decomposition approach. Each stage in the model had a delay node that captured the effects of backorder delay. A processed item at each stage would satisfy any backorders in that stage or replenish the inventory. The output store in each stage was controlled by a base stock policy with oneforone replenishment. Using the parametricdecomposition approach (Whitt, 1983), Sivaramakrishnan (1998) extended the results to include general arrivals and service times, multiple servers, batch service, limited raw material supply, multiple classes, service interruptions and feedback. Feed forward networks were also considered. Liu et al. (2004) modeled a similar tandem network with a basestock policy and onefor one replenishment. The difference with the Liu et al. (2004) is in modeling the departure process from the output store of a stage. In each stage, the input buffer consists of two queues; material queue (orders for which material was available at the output store of the previous stage) and backorder queue (orders for which material was not available at the output store). In general, some of the performance measures considered were expected inventory levels at the finished goods stores, average workinprocess, fill rate and average number of backorders. Dong & Chen (2005) developed an approximate model for a (q, S) inventory policy for a single stage system. They adopted the target level PA cards mechanism with fixed lot size model in Buzacott & Shantikumar (1993). They used the GIX/G/1 model, where X is the fixed batch size q. They transform the bulk arrival queue into an equivalent GI/G/1 queue by modifying the service time to obtain performance measures similar to Buzacott 22 & Shantikumar (1993). Srivathsan (2005) developed productioninventory models of supply chain networks. He developed models for convergent (two suppliers, supplying a manufacturer) and divergent (one manufacturer supplying two retailers) aspects of a supply chain. He modeled the lead time/transit time using a delay node and analyzed a larger network with multiple suppliers, manufacturers and retailers. 2.3 Summary In this chapter, we have provided a detailed literature review of the status of performance evaluation models for warehouses and general productioninventory systems. In this context, we note that • Majority of performance evaluation models for warehouses are specific and analyze specific warehouse systems in isolation. A majority of the studies focused on aislebased automated warehouses, while literature on carousel systems and Autonomous Vehicle Storage Retrieval Systems (AVS/RS) are emerging (Fukunari, 2003). One of the main assumptions in the performance evaluation of these systems is that there is always space available for the waiting storage requests and similarly, a customer demand can always be satisfied. Hence, the performance measures and improvements focus more on improving the material handling aspects of the storage and retrieval systems. • New approaches for systems design and evaluation have started emerging such as those based on process modeling techniques but lack the analytical evaluation capability. The current systematic procedures for warehouse design are mostly descriptive with some prescriptive steps where specific optimization models can be applied for evaluating economic tradeoffs. • In the limited applications of queueing or queueing network models to warehouse performance evaluation, only the congestion effects in the warehouse storage systems have been analyzed. In addition, many models assume that the service provided by 23 the storage system is known and can be approximated by the exponential distribution, which in fact may not be realistic. • In general, the models developed do not provide an analysis framework to include valueadded services in the warehouse. In the next chapter, we will discuss the research goals and objectives and the contribution made by this dissertation. 24 Chapter 3 Statement of Research The overall goal of this research was to develop analytical models for warehouse performance evaluation that can simultaneously deal with inventory and capacity/congestion issues. In a warehouse system, the primary storage function of the warehouse and the inbound/ outbound configuration of the unitloads give rise to two important configurations; the sharedserver system and the orderpicking system. The first two objectives in this dissertation can be thought of as focusing on queueinginventory models of these two configurations which are seen as key building blocks of a warehouse system. The final research objective focuses on building a proofofconcept endtoend warehouse system model using these building blocks. 3.1 Research Objectives Research objectives 1 and 2 focus on the development of the sharedserver and orderpicking system respectively while research objective 3 focuses on the development of endtoend models. Objective 1: To develop and investigate the accuracy of an approximate analytical model of the sharedserver system i.e., an inventory store with a server performing both storage and retrieval operations (hence the name, sharedserver). The storage operation increases the inventory level and the retrieval operation decreases the inventory level. The analytical model explicitly considers the presence or absence of items in the inventory store 25 Figure 3.1: A sharedserver system and its size. In this objective, we study the system independent of the rest of the operations in the warehouse and we make the following assumptions. • We assume independent arrivals for the storage/retrieval requests. • The configuration of the unitload is maintained during storage/retrieval operation and the system operates under FCFS discipline. • The server operates in a singlecommand mode and the storage/retrieval operations have identical service time distributions. • The storage request or retrieval request is for a single item. A typical configuration of such a system is illustrated in Figure 3.1. Subobjective 1.1 : The sharedserver is studied under Markovian assumptions – Poisson arrivals for storage/retrieval requests and exponential service times for the S/R machine. Subobjective 1.2 : The Markovian assumption is relaxed and the sharedserver system is modeled under general arrival and service time distributions. Subobjective 1.3 : This objective extends the general model to account for parallel aisles in the storage system with dedicated S/R servers. Warehouses that deal with different unitload configurations (pallets and cases) will have separate storage areas allocated to a particular configuration; reserve storage for pallets 26 Figure 3.2: An orderpicking system and forward storage for cases, in general. Whenever the inventory in the forward area is depleted because of orderpicking, an internal replenishment occurs from the reserve area. In objective 2, our focus is on this forward storage area, where the replenishment orders are in pallet loads and orderpicking is in case loads. Objective 2: To develop and analyze an approximate analytical model for an orderpicking system; a single storage area with a server picking in lessthanunitload quantities (cases) and a separate server replenishing the inventory in unitloads (pallets). A tandem model representing such an orderpicking operation is illustrated in Figure 3.2. We assume unit orderpicking quantity and unit replenishment–order quantity. We also assume that the orderpicker and replenishment server have unit capacity. Subobjective 2.1 : The orderpicking system is studied under general arrivals and general service time distributions for the single server case. Subobjective 2.2 : The model is extended to include multiserver cases. Objective 3: To demonstrate the applicability of the models developed in objectives 1 and 2 as building blocks to develop comprehensive endtoend models of the warehouse system. The proofofconcept system includes a reserve storage area, a forward storage area and a downstream shipping operation. The reserve storage area is modeled using the sharedserver system and the forward storage area is modeled using the orderpicking system. Hence, this objective demonstrates the applicability of models developed in previous objectives in building endtoend warehouse models. 27 3.2 Research Scope and Limitations The scope of this research was limited by the following assumptions. • The analytical models developed are for a single class of customers and the customer demand for storage and retrieval are for unit orderquantity. Also, the servers are assumed to be reliable. • Design characteristics of the storage area such as warehouse layout, zoning (assigning workers to particular sets of aisles), slotting (assigning products to individual bays), and operational characteristics such as order scheduling and order sequencing are not modeled. Orders are mostly satisfied on a FCFS basis. The storage rack is treated as a single inventory location for modeling purposes. • This framework does not model the inventory staggering decisions that have proven to reduce the maximum inventory levels in the warehouse (Hariga & Jackson, 1996). We assume that the capacity of the inventory store is given as the inventory sizing decisions are now made during the design of distribution network itself, which is outside the scope of this research. • Travel time models for the storage systems are abundant and they consider the physical characteristics of the storage racks (squareintime and nonsquareintime) and storage assignment policies. We do not consider such decisions and policies explicitly in this study. In the next chapter, we focus on the development of the sharedserver system in detail. 28 Chapter 4 SharedServer System In this chapter, we focus on the development of an analytical model of a sharedserver system, a key building block for developing endtoend performance evaluation models of a warehouse. We described the activities and the material flow within a typical warehouse in chapter 1. Here, we focus on the sharedserver system, describe our modeling assumptions, and develop an approximate analytical model of the sharedserver. We perform a detailed evaluation of the sharedserver model by comparing its results with equivalent simulation results. We conclude the chapter by discussing how the sharedserver model can be part of an endtoend warehouse model. 4.1 SharedServer System Development A queueinginventory model of a warehouse illustrating a subset of warehouse operations with respect to a single storage area is illustrated in Figure 4.1. From the perspective of process flow, the warehouse operations follow a sequential flow. But from a resource centric view, the queueinginventory model of the same is not necessarily tandem. The distinction comes from the fact that resources are shared between activities/operations. In a traditional productioninventory model of manufacturing system, such as the one shown in Figure 4.2(a), each resource/processing unit has its own output store. When a demand consumes an inventory at the output store of stage 2, it triggers a replenishment order immediately. This order then looks for a part at the output store of stage 1, and if available 29 (a) Processcentric view of warehouse operations (b) Resourcecentric view of warehouse operations Figure 4.1: Process and resource centric views of warehouse operations goes and waits for processing at stage 2. Parts after processing move to the output store. This process is repeated at each stage. Hence, at each inventory store, parts are put into the store by an upstream machine and parts are retrieved for processing by a downstream machine. In warehouses, material handling resources such as cranes and S/R machines that are assigned to a particular storage area perform both storage and retrieval operations. Hence, the pallets that need to be stored (similar to upstream operation) and the orders that need to be retrieved (similar to downstream operation) share the same resources. We call this resource/server that is shared between storage and retrieval operations as the SharedServer. This chapter of the dissertation focuses on the performance evaluation of the sharedserver system for the single server case and how it can be used as a building block in a comprehensive endtoend model of the warehouse. 4.1.1 Description of the SharedServer System A typical AS/RS consists of multiple parallel aisles, one or more S/R machines that can travel simultaneously in horizontal and vertical directions, and an input/output station. The S/R machine can operate in a single command mode (either storage or retrieval operation in a single cycle) or in a dual command mode (a storage operation and a retrieval operation in the same cycle). There is a buffer in front of the AS/RS where the requests wait in 30 (a) PI model of a tandem manufacturing system (b) PI model of a warehouse rack storage Figure 4.2: ProductionInventory (PI) models of (a) manufacturing system (b) warehouse rack storage a queue to be serviced. It is a physical queue in case of storage requests and a (virtual) information queue, in case of retrieval requests. A sharedserver is representative of AS/RS type of systems. The model consists of a server (S/R machine), separate queues for storage and retrieval requests, and physical inventory store (rack). The following assumptions are made about the sharedserver system. 4.1.2 Assumptions • Storage and retrieval requests arrive independently of each other and join separate queues. The storage requests are say, pallets waiting to be stored and hence, the storage queue has a physical limit because of limited warehouse space. The retrieval requests are information, and hence, the maximum backlog is limited by design decisions. In this dissertation, we assume that both the physical queue and the information queue are finite and are equal in capacity. Similarly, the rack has a finite capacity. Requests that arrive when the storage (request) queue is full will be lost. • The shared server is assumed to operate in a single command mode and follow a first 31 come first served service discipline as long as the request can be serviced. Because of the limited capacity of the rack, the FCFS discipline may be violated. When a storage request arrives before a retrieval request and there is no space in the rack, the request is blocked (storage blocking). The blockage is resolved when the retrieval request is serviced before the storage request. Similar blockage occurs when a retrieval request arrives before a storage request, and there is no item to retrieve (retrieval blocking). • Each request (storage or retrieval) is for a unitload item only and the server can handle only one unitload at a time. The following notation is used in this chapter. −1 S ,C2S  mean and SCV of the interarrival times of storage requests −1 R ,C2R  mean and SCV of the interarrival times of retreival requests μ−1 SC,C2S C  mean and SCV of the service times BS,BR  Queue capacities for storage and retrieval requests respectively Z  Rack size LQ(S),LQ(R)  mean queue length of storage and retrieval requests respectively L(RACK)  average inventory level in the rack −1 dR,C2 dR  mean and SCV of the interdeparture times of retrieval requests The squared coefficient of variation (SCV) of a random variable (rv) is defined as the variance of the rv divided by the square of its mean. We believe that this dissertation effort is the first analytical model of the shared server system where the inventory store or the rack size is explicitly modeled. As is customary with any new performance modeling research, we first model the sharedserver system under the Markovian assumption. 4.2 CTMC Model and Analysis Modeling queues using Continuous Time Markov Chains (CTMC) is a widely used performance evaluation technique because it provides us with an exact method of analysis under exponential assumptions. Algorithms exists to solve the CTMC model and to compute 32 performance measures that can be used to understand system behavior. In our case, we also use the CTMC model to verify the simulation model that is used to evaluate the more general model of the sharedserver system which is the subject of section 4.3. We assume that the single command service time follows an exponential distribution with the service rate (μS = μR) for storage and retrieval requests. The arrivals of storage and retrieval requests are independent of each other and are Poisson processes with mean arrival rates of S and R, respectively. We also assume limits, namely, BS and BR on the capacities of storage and retrieval request queues, respectively. Storage and retrieval arrivals are lost when the queues are full. The state of the system at time t is then defined as, X(t) = {m, i, j, k} where m represents the current mode of the server (0 idle, S serving a storage request, R serving a retrieval request); i, j, k are nonnegative integers representing the number of storage requests waiting in queue, number of retrieval requests waiting in queue and the inventory level in the rack, respectively; 0 i BS, 0 j BR and 0 k Z . The server becomes idle when both the request queues are empty (i = 0, j = 0). The server is blocked when i = 0, j > 0 and k = 0 (retrieval blocking) and when i > 0, j = 0 and k = Z (storage blocking). Figure 4.3 provides examples of system states together with their transitions. In the CTMC model, when the server is capable of servicing either request, as in Figure 4.3(c) we assumed that with a probability pS (= S/( S + R)), the server satisfies a storage request and with a probability pR (= 1−pS), the server satisfies a retrieval request. Using the memoryless property of the exponential distribution, the behavior of the queueing model can be represented as a Continuous Time Markov Chain. The stationary equations are presented in Appendix A.1. The stationary equations were solved numerically using XpressMP (Heipcke, 2000) and compared against simulation estimates. The experimental setup to verify the analytical model is presented in Table 4.1. The arrival rates ( S = R) were set at 1 / time unit and the service times are set such that the utilization 33 (a) state illustrating storage blocking (b) state illustrating retrieval blocking (c) state illustrating a storage operation Figure 4.3: Example statetransitions for the CTMC model of the sharedserver system 34 Parameter Levels (values) Service Times 1 (corresponding to 80% utilization level) Rack Size (Z) 10 (1  10) Buffer Size (BS = BR) BS = BR = Z and BS = BR > Z Number of Servers 1 Table 4.1: Design of experiments for shared server system (Markovian case) of the sharedserver is 0.8. While our model can handle any limit on the queue capacity, in our experiment we present two scenarios; one where the queue capacity is equal to the rack size, and the other where the queue capacity is greater than the rack size. Let Pm,i,j,k be the steadystate probability that CTMC will be in state (m, i, j, k) which we can obtain by solving the balance equations given in Appendix A.1. With the solution of Pm,i,j,k, we can derive some useful performance measures, such as: 1. Utilization of the server P(S/R) = 1 − X k>=0 P0,0,0,k (4.1) 2. Probability of storage blocking P(Storage Blocking) = X i>0 P0,i,0,Z (4.2) 3. Probability of retrieval blocking P(Retrieval Blocking) = X j>0 P0,0,j,0 (4.3) 4. Effective throughput of the server (can be less than the total arrival rate because of lost arrivals and blocking) eff = μSC 0 @1 − 0 @ X k 0 P0,0,0,k + X i>0 P0,i,0,Z + X j>0 P0,0,j,0 1 A 1 A (4.4) 5. Expected number of retrieval requests waiting to be serviced LQ(R) = X j 0 j.Pm,i,j,k (4.5) 35 6. Expected number of storage requests waiting to be serviced LQ(S) = X i 0 i.Pm,i,j,k (4.6) 4.2.1 Numerical Experiments In order to verify the results of the CTMC model, we compare the output of the CTMC model to the performance measure estimates obtained by simulating the sharedserver. In the case of utilization and queue length performance measures, the relative percentage difference is defined as Rel.Diff% = Analytical − Simulation Simulation 100 We present the absolute difference when the quantities involved are small (typically less than 1) (Whitt, 1983). Tables 4.2 and 4.3 summarize the results when the buffer size is equal to the rack size and greater than the rack size, respectively. From the tables, we see that the CTMC model tracks the simulation model closely. The maximum relative percentage difference on the storage (retrieval) queue is 4.84% (4.97%) in the first scenario and 2.53% (2.68%) in the second scenario. In the case of utilization and average inventory level in the rack, the differences are very small, and only absolute differences are reported. The difference between the analytical and simulation model can be explained by the following assumption in the CTMC model. In the CTMC model, when the server is capable of servicing either request, as in Figure 4.3(c) we have assumed that with a probability pS (= S/( S + R), the server satisfies a storage request and with a probability pR (= 1 − pS), the server satisfies a retrieval request. But in the simulation model we enforce the FCFS discipline strictly and the sharedserver services the request that arrived first into the system. The results indicate that the utilization is an increasing function of the rack size and it is less than the expected utilization level of 80%, because of 1) the blocking of requests when the rack is full or empty and 2) the loss of requests, when the storage or retrieval queues are full. The average number of items in the rack was maintained close to half of 36 the rack size, since the arrival rates were same for the storage and retrieval requests. We note that the average inventory level in the rack is the same in both cases, namely, “buffer size = rack size” and “buffer size > rack size”. The above analysis also provides confidence in the simulation model that will be used for evaluation of the approximate analytical model developed in the next section. As the rack size or the queue capacities increase, the CTMC state space grows rapidly and the numerical solution to the balance equations becomes challenging. If both queues have no capacity limits, then we also need to investigate the conditions under which the CTMC will have a steady state. 37 Utilization Storage Queue Retrieval Queue Rack Rack Size (Z) Buffer Size (BS = BR) A S %Diff A S %Diff A S %Diff A S %Diff 1 1 0.500 0.500 0.000 0.374 0.374 0.000 0.374 0.374 0.000 0.500 0.500 0.000 2 2 0.614 0.615 0.001 0.731 0.737 0.006 0.731 0.738 0.007 1.000 1.000 0.000 3 3 0.670 0.671 0.001 1.070 1.093 2.10% 1.070 1.095 2.28% 1.500 1.497 0.003 4 4 0.702 0.704 0.002 1.386 1.430 3.08% 1.386 1.432 3.21% 2.000 1.999 0.001 5 5 0.723 0.725 0.002 1.680 1.746 3.78% 1.680 1.750 4.00% 2.500 2.495 0.005 6 6 0.738 0.740 0.002 1.955 2.040 4.17% 1.955 2.046 4.45% 3.000 2.994 0.006 7 7 0.748 0.750 0.002 2.213 2.317 4.49% 2.213 2.320 4.61% 3.500 3.497 0.003 8 8 0.756 0.757 0.001 2.457 2.573 4.51% 2.457 2.580 4.77% 4.000 3.989 0.011 9 9 0.762 0.763 0.001 2.688 2.821 4.71% 2.688 2.828 4.95% 4.500 4.488 0.012 10 10 0.767 0.767 0.000 2.908 3.056 4.84% 2.908 3.060 4.97% 5.000 4.985 0.015 Table 4.2: Results for the sharedserver CTMC model (BS = BR = Z) = 0.8 and S = R = 1 Utilization Storage Queue Retrieval Queue Rack Rack Size (Z) Buffer Size (BS = BR) A S %Diff A S %Diff A S %Diff A S %Diff 1 2 0.543 0.543 0.000 0.501 0.501 0.000 0.501 0.501 0.000 0.500 0.500 0.000 2 4 0.651 0.650 0.001 0.972 0.965 0.007 0.972 0.966 0.006 1.000 0.999 0.001 3 6 0.698 0.696 0.002 1.388 1.365 1.68% 1.388 1.367 1.54% 1.500 1.499 0.001 4 8 0.724 0.722 0.002 1.753 1.713 2.34% 1.753 1.715 2.22% 2.000 1.999 0.001 5 10 0.740 0.738 0.002 2.078 2.025 2.62% 2.078 2.029 2.41% 2.500 2.497 0.003 6 12 0.751 0.749 0.002 2.369 2.305 2.78% 2.369 2.308 2.64% 3.000 2.999 0.001 7 14 0.759 0.757 0.002 2.634 2.561 2.85% 2.634 2.561 2.85% 3.500 3.501 0.001 8 16 0.764 0.762 0.002 2.880 2.801 2.82% 2.880 2.800 2.86% 4.000 3.996 0.004 9 18 0.769 0.767 0.002 3.110 3.025 2.81% 3.110 3.026 2.78% 4.500 4.489 0.011 10 20 0.772 0.770 0.002 3.328 3.246 2.53% 3.328 3.241 2.68% 5.000 4.993 0.007 Table 4.3: Results for the sharedserver CTMC model (BS = BR > Z) = 0.8 and S = R = 1 38 Figure 4.4: A single stage kanban system (Krishnamurthy, 2002) 4.3 Queueing Network Model of the SharedServer In this section, we present an approximate analytical model of the general sharedserver system. Our modeling and solution approach uses previous work on the parametricdecomposition method (Whitt, 1983) and the modeling of synchronization operations (Krishnamurthy, 2002). The need for modeling synchronization operations can be explained by the observation that for a storage (retrieval) operation to begin a storage (retrieval) request must be waiting and an empty space (item) must be present in the rack. The analytical model presented here is based on the material control model developed for a single stage kanban system by Krishnamurthy (2002). In a kanban controlled production system, kanbans (cards) are used to control material flow and trigger production. In a multi stage production system, each stage has a fixed number of kanbans. A part can be processed at given stage i, if the corresponding stage i kanban is attached to the part. Upon completion of the process, both the finished part and the kanban wait at the output buffer of stage i. The part is transferred to the next stage, stage i+1, as soon as a kanban from stage i+1 is available. The stage i kanban is then returned to the input buffer of stage i enabling new parts to enter stage i. Such a kanban system can be represented as a queueing model using fork/join synchronization stations and is shown in Figure 4.4. A similar material control modeling approach is followed in the development of the approximate analytical model of the sharedserver system. 39 Figure 4.5: Queueing network model of a shared server Figure 4.5 represents a queueing network model of a single class, single sharedserver system. The sharedserver is represented as two independent servers, serving the storage and retrieval requests, at the storage processing (SP) and retrieval processing (RP) stations, respectively. The synchronization stations JS and JR model the material control mechanism at the processing stations. A closed loop system is formed by the sync stations JS and JR and processing stations SP and RP as shown. Associated with this closed loop are Z kanbans which represent the number of rack spaces in the system. Hence, this part of the queueing network model can be viewed as a closed queueing network where the kanbans act as customers, circulating in the network formed by queues EK, SP, RACK and RP. The arrival processes of storage and retrieval requests are external processes that need to be synchronized with the internal flow of the kanbans in the closed loop. The sync station JS models the synchronization of the storage requests (that arrive from the upstream or external processes) with that of kanbans that represent the empty spaces in the rack. JS has two input queues, the storage request queue (BS) and the empty space/kanban queue (EK). The sync station JR models the synchronization of the retrieval requests (that arrive from downstream or external processes) with that of kanbans that represent items in the rack. JR has two input queues, the retrieval request queue (BR) and the rack queue (RACK). The material control model works as follows. Unitload items wait in the queue, RACK, 40 to be retrieved and satisfy a retrieval request. These items in the RACK have a kanban attached to it. As soon as a retrieval request arrives in queue BR, an item from the RACK and the request is joined together and released from the sync station to join the retrieval processing queue. Upon completion of the service (the item was successfully retrieved from the rack), the kanban is returned to the queue EK, that represents the empty spaces in the rack. The queue EK is a part of the storage synchronization station (JS). At this station, when a storage request arrives at the queue BS, it is immediately joined with the kanban in queue EK and sent to the storage processing station (SP) to be stored in the rack. As we can see from the operating mechanism, the kanban cards are either in one of the four queues or at the servers; EK representing empty spaces, SP representing unitloads waiting to be stored and in process, RACK representing unitloads in the rack and RP representing unitloads waiting to be retrieved and in process. Hence, these four queues and the two servers can have a maximum of Z kanbans/customers at any time. The arrival processes at the synchronization stations and service processes at the processing stations are assumed to be general and hence, the queueing network model is a nonproduct form. Therefore, approximation techniques must be used for performance analysis. The solution approach to solving the queueing network consists of four steps and is based on the parametricdecomposition approach (Whitt (1983, 1994); Krishnamurthy (2002)). The two main features of this approach are that the departure and arrival processes within the network are approximated as renewal processes and such a renewal process is described by its first two moments, mean and squared coefficient of variation. In reality, the successive departures or arrivals in the closed queueing network are not independent, and hence not a renewal process. Earlier works on open and closed queueing network models (Kuehn (1979); Whitt (1983); Kamath (1989); Krishnamurthy (2002)) have shown that such an approximation is effective and yields reliable estimates of the desired performance measures without much computational effort. In this solution approach, we extend the application of this technique to solve the sharedserver system model. The approach consists of four steps: Decomposition, Characterization, Linkage, and Solution. An overview of these steps is given below and illustrated in Figure 4.6. 41 Figure 4.6: Overview of parametricdecomposition approach for the queueing network model of the sharedserver 42 • Decomposition: The queueing network representation of the shared server system is decomposed into individual components; storage and retrieval synchronization stations (JS and JR), and storage and retrieval processing stations (SP and RP). • Characterization: Each component/station (JS, SP, JR and RP) obtained from the decomposition step is analyzed in isolation. We assume that the arrival process and the service process (if any) are known and are renewal processes. We also assume that the renewal process is adequately quantified by two parameters; the mean and squared coefficient of variation (SCV) of the interrenewal times. In this queueing network, we know the external arrival processes for storage and retrieval requests, and the single command service process but we do not know the internal departure processes from each of the components. By analyzing the components/stations independent of the rest of the network, we obtain the mean and SCV of the departure process and estimate the performance measures of each of the components. The details of this characterization step, especially the storage and retrieval processing stations are described in detail in the following sections. • Linkage: In this step, the traffic equations from the individual stations are linked together in the closed loop part of the queueing network. We make use of the expressions derived in Krishnamurthy & Suri (2006) that link the traffic processes at the stations (JS and SP, SP and JR, JR and RP, and RP and JS). The resulting sets of nonlinear equations are then solved numerically to obtain the parameters of the internal traffic processes. • Solution: The system of nonlinear equations, linking the traffic processes of the individual components is iteratively solved to determine the internal traffic parameters. Once those parameters are determined, the network performance measures as well as the station performance measures can be obtained easily. 4.3.1 Characterization of the Synchronization Station The decomposition step presents two synchronization stations, storage and retrieval synchronization stations. The storage sync station (JS) consists of two input queues, one for 43 Figure 4.7: Characterization of storage synchronization station (JS) the storage requests that come from upstream stages (BS) and the other for kanbans representing empty storage spaces (EK). The subnetwork SN in Figure 4.7 represents the downstream stages where the Z kanbans circulate. In the queue EK, kanbans representing empty storage spaces wait for the storage requests. Each storage request is then attached with the kanban and they proceed together to be processed, i.e., the storage request and the kanban are routed together in the subnetwork SN. Because the rack has a finite capacity represented by the Z kanbans, the sum of kanbans in queue EK and subnetwork SN will always be equal to Z. Additionally, the arrival process to the queue BS will shutoff as soon as its capacity is reached, which is set at BS. In line with two moment approximations, we assume that the arrival processes to queues EK and BS are renewal processes characterized by the mean and SCV of the interarrival times; −1 S , C2 aS to the queue BS and −1 S,j−1, C2 s,j−1 to the queue EK. There are only Z kanbans circulating in the subnetwork and queue EK, the arrivals to the queue EK shuts off once all the kanbans are in the queue EK. Hence, we really assume that the traffic process conditioned on the event that it is not shutdown is a renewal process. Thus, the synchronization station JS is characterized by the 6tuple ( −1 S ,C2 as,BS, −1 s,j−1,C2 s,j−1,Z). The characterization of JS will be complete when the parameters for the departure process are specified, which were derived by Krishnamurthy (2002). Let r = S/ S,j−1r 1 and C2 = 0.5(C2 aS + C2 s,j−1). The rate of the departure process is given by 44 S,j = 8>< >: S h 1−rZ+BS 1−rZ+BS+1 i h 1 − 0.5(C2 − 1) (1−r)rZ+BS 1−r2(Z+BS)+1 i r < 1 S Z+BS Z+BS+1 1 − 0.5(C2−1) 2(Z+BS)+1 r = 1 (4.7) As we can see from the above expression, for finite values of Z and BS, the rate of the departure process is always less than min( S, S,j−1). The SCV of the departure process is given by (Krishnamurthy, 2002) C2 S,j = " 5 S 5 S + 5 S,j−1 ! C2 S,j−1 + 5 S,j−1 5 S + 5 S,j−1 ! C2 aS # 1 − 1 (Z + BS + 1) − 1 (Z + BS + 1)2 (4.8) The expressions for queue length parameters are (Krishnamurthy, 2002) LBS = 8>< >: S h 1−rZ+BS 1−rZ+BS+1 i h 1 − 0.5(C2 − 1) (1−r)rZ+BS 1−r2(Z+BS)+1 i r < 1 BS 2 BS+1 Z+BS+1 r = 1 (4.9) LEK = 8>< >: S h 1−rZ+BS 1−rZ+BS+1 i h 1 − 0.5(C2 − 1) (1−r)rZ+BS 1−r2(Z+BS)+1 i r < 1 Z2 Z+1 Z+BS+1 r = 1 (4.10) The characterization of the retrieval synchronization station (JR) is very similar to that of storage synchronization station. The station JR is characterized by two queues, the retrieval request queue (BR) and the queue representing the items in storage (RACK). 4.3.2 Characterization of the Processing Station Figure 4.8 shows the storage processing station obtained by the decomposition of the queueing network. The processing station can be any configuration, and in this section we assume a single server storage processing station operating under a FCFS discipline. The subnetwork SN represents the rest of the queueing network in which the Z kanbans circulate. The arrivals to the SP station are the storage requests with kanbans, i.e., each storage request will have a space reserved for it when it joins the queue. Upon completion of the storage processing operation, the kanbans are routed back to the subnetwork SN where they are subject to random delays. In the subnetwork, the kanban stays in the RACK 45 Figure 4.8: Characterization of the Storage Processing station (SP) until it is matched to a retrieval request and the completion of the retrieval operation will release the kanban to the queue EK. Matching a storage request with a kanban in queue EK results in the kanban revisiting the storage processing station. The number of kanbans at the SP station and subnetwork will always be equal to Z and consequently, the arrival process to the SP station shuts off when all the kanbans are in the SP station. The arrival process to the SP station can be fairly complex. Hence, in line with the twomoment approximations, we assume that the arrival process to the SP station is a renewal process conditioned on the event that the arrival shuts off when all the customers are in the station. The arrival process is characterized by the mean and SCV of the interarrival times ( −1 aS,j ,C2 aS,j ). Together with the parameters describing the service process, the SP station can be represented by the 5tuple ( −1 aS,j ,C2 aS,j , μ−1 mSC,C2 mSC,Z). The service times are modified single command cycle times since the SP station and RP station are both serviced by a single shared server. The details of the modification are presented in the next subsection. Meanwhile, we assume that the service times are i.i.d with mean (μ−1 mSC) and SCV (C2 mSC). The characterization of the SP station will be complete with the description of the departure process and the performance measure of interest, namely the mean queue length. By flow conservation principle, the mean of the interdeparture time is given by −1 ds = −1 aS,j (4.11) 46 The estimation of the SCV of the interdeparture times is based on the approximation by Whitt (1983) for a GI/G/1 queue. Let S = S,j/μmSCbe the utilization of the shared server to account for servicing the storage requests. Then, the SCV (C2 ds) is given by C2 dS = (1 − 2 S)C2 aS,j + 2 SC2 mSC (4.12) To obtain the expression for mean queue length of the SP station, we first obtain the expression for mean waiting time (Wq,SP ). Following the approach by Kamath et al. (1988), the approximate mean waiting time is given by Cf Wq(GI/G/1), where Cf is a correction factor and Wq(GI/G/1) is the waiting time in a GI/G/1 queue. Based on the work of Kuehn (1979) and Whitt (1983), the mean waiting time in a GI/G/1 queue is given by Wq = g( S,C2 aS,j ,C2 mSC) C2 aS,j + C2 mSC 2 ! S 1 − S μ−1 mSC (4.13) The above equation assumes that the customers to the queue arrive from an infinite population. The correction factor (Cf) accounts for the finite population of Z kanbans in the closed loop part of the queueing network, and has been derived by Kamath et al. (1988) as, Cf = Z − 1 Z 0 B@1 1 + Wq Z μ−1 mSC 1 CA (4.14) Then, using Little’s law (Little, 1961), we obtain the mean queue length at the storage processing station as Lq,SP = S,j Cf Wq (4.15) Modifying the Single Command Service Time In the characterization of the SP station, we had mentioned that the single command service time was modified. The reason behind this modification is to account for a single server that is shared by the storage processing station (SP) and the retrieval processing station (RP). We model this shared server as two independent servers and then account for the time spent on each other’s activities. The service time spent by the sharedserver in performing the 47 storage activity accounts for the time it spends in performing any retrieval activity before the next storage activity and vice versa. This is similar to the approach used by Segal & Whitt (1989) to model the service interruptions within the QNA framework (Whitt, 1983). To modify the service time for the storage processing station, we assume that the down time is the time spent on performing retrieval operations between two storage operations. Let S and R be arrival rates for storage and retrieval requests, and SC(= 1/μSC) be the mean single command service time for storage/retrieval requests. Let S0 be the random variable representing the modified service time, which is given by S0 = S + X NR R (4.16) where S(R) is the random variable representing original storage (retrieval) time and NR is the random variable representing the number of retrieval operations performed until the next storage operation. The number of retrieval requests completed before servicing another storage request is a modified geometric random variable, whose parameter is the probability of that the next request is a storage request and is given by pS = S/( R + S). P NR R is a random sum of identical random variables R. The mean of the modified single command storage service time is given by E[S0] = E[S] + E[NR] E[R] E[NR] = pS 1−pS E[S] = E[R] = μ−1 SC = SC E[S0] = mSC = SC 1−pS (4.17) The variance of the modified single command storage service time is given by V ar[S0] = V ar[S] + V ar[P NR R] V ar[S0] = V ar[S] + V ar[NR] (E[R])2 + E[NR] V ar[R] V ar[R] = C2S C 2 SC V ar[NR] = pS (1−pS)2 C2 mSC = V ar[S0] 2 mSC (4.18) 48 Since, we assume that the arrival rates for storage and retrieval requests are equal ( S = R), the expressions 4.17 and 4.18 will also apply for modifying the service time for the retrieval requests. We also note that the two independent servers can be ‘active’ at the same time in the queueing network model. The specification of the traffic processes for each of the components/stations and the performance measures of interest complete the characterization step. In the following section, we link the traffic processes of the decomposed components. 4.3.3 Linking the Stations In the characterization step, the parameters describing the input processes to the processing stations and the synchronization stations are assumed to be given, which in fact need to be determined. In this section, we will determine the relationship between the interdeparture times from a station and the interarrival times to a downstream station, thereby explicitly incorporating the effects of shut downs in the arrival process in the closed part of the queueing network. We need to determine the following four linkages (see Figure 4.6). 1. Linking the departure processes of the storage synchronization station (JS) at the arrival process of the storage processing station (SP) 2. Linking the departure process of the storage processing station (SP) with the retrieval synchronization station (JR) 3. Linking the departure processes of the retrieval synchronization station (JR) at the arrival process of the retrieval processing station (RP) 4. Linking the departure process of the retrieval processing station (RP) with the storage synchronization station (JS). Linking the Departure Process from JS to Arrival Process at SP We now describe the procedure to link the mean and SCV of the departure process of the station JS ( −1 S,j and C2 s,j) to the mean and SCV of the arrival process at the SP ( −1 aS,j and C2 as,j) (see Figure 4.9). We note that the parameters of the arrival process to queue 49 Figure 4.9: Linking storage synchronization and storage processing stations Figure 4.10: Linking storage processing and retrieval synchronization stations BS correspond to external demand and hence, the −1 aS , C2 aS and BS are user inputs. The parameters of the interarrival process at SP, mean ( −1 aS,j) and SCV (C2 aS,j) can be equated directly to the parameters of the interdeparture process from JS. In the characterization step, the correction factor incorporates the finite population nature of the closed part of the queueing network and hence, we do not have to modify the parameters of the interarrival process at SP. Then, using flow conservation principle, aS,j = S,j C2 aS,j = C2 S,j (4.19) We can provide a similar argument to link the departure process from the retrieval synchronization station (JR) to the arrival process to the retrieval processing station (RP). 50 Linking the Departure Process from SP to Arrival Process at JR We now describe the procedure to link the mean and SCV of the departure process of the station SP ( −1 ds and C2 ds) to the mean and SCV of the arrival process at the JR ( −1 R,j−1 and C2R ,j−1) (see Figure 4.10). We note that the parameters of the arrival process to queue BR could correspond to external retrieval request arrival process and hence, −1 aR, C2 aR and BR are user inputs to this model. In the characterization step of the synchronization station, the parameters of the arrival process to the queue RACK ( −1 R,j−1 and C2R ,j−1) are not conditioned on the event that the arrival process is shutdown when all the kanbans are in RACK. Hence, we need to incorporate this fact when we link these two stations. Krishnamurthy & Suri (2006) developed a procedure to develop the linkage equations analyzing the arrival point process to the queue RACK. We will describe the procedure next. Let RACK denote the long run proportion of time that arrivals to RACK are shut down. Then, R,j−1 = dS 1− RACK C2R ,j−1 = C2 dS (1− RACK)2 − RACK (1− RACK)2 dS aR 2C2 aR 1+C2 aR (4.20) By the principle of flow conservation, we have −1 R,j = −1 dS . Together, the three equations provide the necessary stochastic transformation required to relate the traffic processes of the stations SP and JR. We assume that parameters of the departure process from the station SP ( −1 dS ,C2 dS) are given and proceed to develop a numerical procedure to find the arrival process to the station JR. We know that the arrival parameters and the size of the queue BR ( −1 aR,C2 aR,BR) are the user inputs. The iterative numerical procedure, based on the bisection search method is given in Algorithm 4.3.1. 51 Algorithm 4.3.1: LinkProcToSync( dS,C2 dS,Z, aR,C2 aR,BR) comment: Links the storage processing station and retrieval synchronization station Initialize: low = 0, high = 1, " while   > " do 8>>>>>>>>>>>>>>>>>>>>>>>< >>>>>>>>>>>>>>>>>>>>>>>: Step1: Set (k) RACK = (low + high)/2 Step2: Compute R,j−1 and C2R ,j−1 Step3: Compute R,j using synchronization characterization equations Step4: Compute = (k) R,j − dS if < −" then low = (k) RACK else if > " then high = (k) RACK In the algorithm 4.3.1, (k) RACK represents the estimate for RACK in the kth iteration. In each iteration, we compute the difference between the estimated throughput ( R,j) and the required throughput ( dS). If the estimated throughput is lower than the required throughput, then we update the interval of the bisection search to increase the value of RACK in the next iteration, and viceversa. The algorithm terminates when the estimate of RACK meets the required tolerance level (") in the throughput. Convergence property of the algorithm is discussed in a later section. Using a similar argument, we can develop a numerical procedure to solve the linkage equations connecting the retrieval processing station (RP) and the storage synchronization station (JS). 4.3.4 Solution Approach The solution step involves solving the set of nonlinear equations linking the traffic process of the individual stations in the closed part of the queueing network. We increase the user input (Z) by one kanban to account for the fact that the two independent servers can be active at the same time in the queueing network model. We initialize the algorithm by first modifying the single command storage (retrieval) processing time using equations 4.16  4.18. Then, we proceed with an initial estimate of 52 parameters for the departure process of one of the four component stations, in our case it is the storage processing station SP. The algorithm then iteratively estimates the internal traffic process parameters, updating the initial estimates until they are consistent with the user inputs. The solution procedure is described in Algorithm 4.3.2. After computing the modified service time parameters for the processing stations, we obtain initial estimates of dS, and C2 dS in step 1 of loop1. As the initial estimates may be inconsistent with each other, we update the value of C2 dS in loop2 for given value of dS. To update C2 dS, we make use of the characterization and linking equations derived in earlier sections, and solve for the traffic parameters for each of the stations sequentially (steps 2.1 to 2.8). Upon solving the SP, we obtain a new value for C2 dS . We repeat this procedure until the difference between the new and old estimates of C2 dS are within the set tolerance limit ("). In step 3, algorithm verifies if these values of dS and C2 dS are consistent with the user input values for the number of kanbans. To do so, we calculate the difference between the user input value (increased by one) and sum of the kanbans at each of the stations including the servers. We update dS using a bisection search approach in step 4, until the difference between current and previous estimates are within a predefined tolerance limit. If the sum of mean queue lengths is more than the number of kanbans, then the current estimate of ds is too high; the bisection search algorithm accordingly updates the interval for the next iteration. At the end of loop1, we would have obtained dS and C2 dS that are consistent with each other, and consistent with user input & modified service times. As a last step, we update the modified service time based on the effective internal arrival process to the processing stations. We repeat the entire procedure starting with step 1, until the difference between the current and previous estimate of the modified service times are within the specified tolerance limits. Once, the algorithm converges, we can obtain the performance measures of interest such as the throughput and mean queue lengths at the various processing and synchronization stations. The average inventory at the rack is the sum of the mean queue lengths of RACK, and mean number of customers at the retrieval processing station. The average number of 53 storage requests waiting to be serviced is the sum of the mean queue length of BS and mean queue length at the storage processing station. The average number of retrieval requests waiting to be serviced is the sum of the mean queue length of BR and mean queue length at the retrieval processing station. 54 Algorithm 4.3.2: SuperSolve( S,C2 aS,BS, R,C2 aR,BR, μSC,C2S C,Z) Modify: No of kanbans Z0 = Z + 1 Compute: Modified single command service time at SP and RP (μmSC,C2 mSC) Initialize: Low = 0,High = min( S, R, μmSC) while  1 > " do 8>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>< >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>: Step1: Let (k) ds = (Low + High)/2, C 2(k) ds = 1.0(say) while  2 > " do 8>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>< >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>: Step2.1: Solve RACK, R,j−1, and C2R ,j−1 using Algorithm 4.3.1 setting dS = (k) dS and C2 dS = C 2(k) dS Step2.2: Calculate R,j ,C2R ,j and Lq,BR and Lq,RACK using the characterization equations Step2.3: Compute input parameters to the retrieval processing station Step2.4: Calculate dR,C2 dR and Lq,RP using the RP characterization equations Step2.5: Solve EK, S,j−1, and C2 S,j−1 using Algorithm 4.3.1 Step2.6: Calculate S,j ,C2 S,j and Lq,BS and Lq,EK using the characterization equations Step2.7: Compute input parameters to the storage processing station Step2.8: Calculate dS,C2 dS and Lq,SP using the SP characterization equations Step2.9: Compute 2 = C 2(k) dS − C2 dS;C 2(k) dS = C2 dS Step3: Compute 1 = Lq,RACK + Lq,RP + R + Lq,EK + Lq,SP + S − Z0 Step4: if 1 < −" then Low = (k) dS else if 1 > " then High = (k) dS 55 4.3.5 Computational Effort and Convergence We note that the number of unknown parameters in this analysis is independent of the number of customers in the closed part of the queueing network model. Both numerical algorithms are based on the bisection search procedure, and it is assumed that the solution lies within the specified intervals. In the Algorithm 4.3.1, bisection search is used to estimate the probability of the shut downs, ( RACK) to the queue RACK and ( EK) to the queue EK. Hence, the interval [0, 1] is sufficient to search for the probabilities. In the case of Algorithm 4.3.2, the bisection search is used to obtain the throughput of the storage processing station consistent with the user input values. We note that the throughput of the system, then must lie within the interval [0, min( aS, aR, μmSC)] where the μmSC is the modified single command service rate at the storage or retrieval processing station. We cannot guarantee a unique solution within this interval or provide a bound on the number of iterations necessary for the model to converge. In all our experiments, the algorithm converged to a solution within a reasonable number of iterations (<20). 4.3.6 Performance Measures and Model Accuracy The performance measures of interest for the shared server model are related to throughput, inventory, and warehouse resources. The performance measures related to the throughput are the throughputs for storage and retrieval requests. Throughput is defined as the number of requests served per unit time. Other measures of interest are the waiting time and average number of storage and retrieval requests in the system. With respect to inventory, average number of items in storage is a measure of interest. With respect to resources, utilization is the major performance measure. In the following sections, we summarize the results for the throughput for retrieval requests, utilization of the shared server, the mean queue length of the storage & retrieval queues, and the average inventory level in the rack. The accuracy of the models is tested by comparing the analytical results with simulation estimates. The simulation models were developed for the sharedserver component using the Arena simulation software (Kelton et al., 2002). The steady state estimate of a performance 56 measure was obtained by averaging over appropriate number of replications after accounting for warmup periods. The warmup period was estimated using Welch’s method (Welch, 1983) and set at 400,000 entities. The statistics were collected for 600,000 entities (retreival requests) and the performance measures were averaged for 10 replications. The relative percentage error (RE), a common measure to test the accuracy of analytical models, was used in the case of throughput ( dR) and utilization ( SC). When the magnitude of the performance measures is small (typically less than 1), absolute error is considered better than RE (Whitt, 1983). RE( dR) = 100 (Analytical) dR − (Simulation) dR (Simulation) dR In the case of mean queue lengths and average inventory in the rack, normalized error is measured rather than relative percentage error. The normalized error is measured as the difference between the analytical and simulation model as a percentage of the rack size. Since the shared server system is modeled as a queueing network, the normalized error (NE) is measured as NE(LQ(S)) = 100 LQ(S)(Analytical) − LQ(S)(Simulation) Rack Size NE(LQ(R)) = 100 LQ(R)(Analytical) − LQ(R)(Simulation) Rack Size NE(L(RACK)) = 100 L(RACK)(Analytical) − L(RACK)(Simulation) Rack Size The normalized error is used for measuring queue length accuracy in order to avoid the small queue length effect. Robustness of the analytical models will be tested by varying the parameters of the interarrival time distributions for storage/retrieval requests, service time distribution, and rack size. The performance measures will be examined under low (SCV = 0.5), medium (SCV = 1) and high variability (SCV = 2) conditions. An experimental design is provided in Table 4.4 for the sharedserver model. The arrival rates for the storage and retrieval requests are fixed at one, and the mean service times are 57 Parameter Levels (values) Service Times 3 (corresponding to 70%, 80% and 90% utilization levels) SCV of service time distribution 3 (0.5, 1.0 and 2.0) SCV of interarrival time distribution 3 (0.5, 1.0 and 2.0) Rack Size 3 (5, 25 and 125) Number of servers 1 Table 4.4: Design of experiments for sharedserver system: single server case set such that the expected utilization of the shared server is 70%, 80% and 90%. 4.3.7 Accuracy of the SharedServer Model The input parameters to the queueing model are the arrival parameters of the storage and retrieval requests, the service parameters of the single command service time, the queue capacities and the rack size. The output parameters, namely the performance measures of interest are the mean queue lengths of the storage and retrieval requests, the throughput (which is the departure rate of the retrieval requests) and average inventory in the rack. In the case of the sharedserver system, we are also interested in measuring the parameters of the departure process of the retrieval requests as they will become the inputs to the downstream stations in an endtoend comprehensive model of the warehouse. In all our experiments in this section, the sharedserver is a single server operating under a FCFS discipline. We also study the sharedserver system when the variability in the arrival processes is the same (balanced case) and when the variability is different (unbalanced case). Balanced Case In the balanced case, the storage and retrieval processes have the same arrival rate and variability. The estimates of mean queue length (storage and retrieval requests) and the average inventory level in the rack at 70%, 80% and 90% expected utilization for the balanced case are given in Tables 4.5, 4.7, and 4.9 respectively. The estimates of throughput and utilization of the sharedserver are reported in Tables 4.6, 4.8, and 4.10 for the three expected utilization levels. The results from Tables 4.5, 4.7, and 4.9 indicate that the maximum absolute error for the mean queue length of storage (retrieval) request is 5.84% (5.83%). 58 The maximum absolute error for the average inventory in the rack is 3.95%. We note that the above errors are found at the 90% expected utilization levels. In the case of throughput and actual utilization, the maximum absolute error is 13.84% for 90% utilization levels. The observed error percentages are in the range of good to acceptable for queueing models based on two moment approximations as noted in many previous studies (e.g. Whitt, 1983 and Suri et al., 1993). Next, we develop insights into the behavior of the sharedserver model for the balanced system. 59 Storage Queue Retrieval Queue Average Inventory C2 aS = C2 aR C2S C Rack Size A S %E A S %E A S %E 0.5 0.5 5 0.526 0.387 2.79% 0.527 0.387 2.79% 2.416 2.499 1.65% 0.5 0.5 25 1.220 0.781 1.76% 1.220 0.786 1.74% 12.317 12.474 0.63% 0.5 0.5 125 2.438 2.296 0.11% 2.438 2.252 0.15% 62.300 62.915 0.49% 0.5 1 5 0.595 0.471 2.48% 0.595 0.472 2.47% 2.423 2.499 1.53% 0.5 1 25 1.414 0.928 1.95% 1.414 0.932 1.93% 12.318 12.481 0.65% 0.5 1 125 2.682 2.451 0.18% 2.682 2.402 0.22% 62.293 62.894 0.48% 0.5 2 5 0.713 0.581 2.64% 0.713 0.581 2.65% 2.434 2.499 1.31% 0.5 2 25 1.786 1.217 2.28% 1.787 1.218 2.27% 12.321 12.497 0.70% 0.5 2 125 3.166 2.717 0.36% 3.166 2.691 0.38% 62.298 62.870 0.46% 1 0.5 5 0.547 0.475 1.45% 0.548 0.475 1.45% 2.424 2.497 1.46% 1 0.5 25 1.340 1.030 1.24% 1.340 1.030 1.24% 12.319 12.472 0.61% 1 0.5 125 2.600 2.606 0.00% 2.600 2.676 0.06% 62.291 62.631 0.27% 1 1 5 0.611 0.534 1.53% 0.611 0.535 1.52% 2.430 2.498 1.36% 1 1 25 1.888 1.178 2.84% 1.888 1.178 2.84% 12.321 12.469 0.59% 1 1 125 2.841 2.776 0.05% 2.841 2.833 0.01% 62.296 62.646 0.28% 1 2 5 0.721 0.611 2.20% 0.721 0.612 2.18% 2.440 2.497 1.14% 1 2 25 1.888 1.457 1.72% 1.888 1.457 1.72% 12.321 12.474 0.61% 1 2 125 3.321 3.091 0.18% 3.321 3.137 0.15% 62.298 62.569 0.22% 2 0.5 5 0.580 0.560 0.40% 0.580 0.560 0.41% 2.439 2.498 1.18% 2 0.5 25 1.559 1.354 0.82% 1.560 1.357 0.81% 12.325 12.496 0.68% 2 0.5 125 2.909 2.993 0.07% 2.909 2.999 0.07% 62.318 62.883 0.45% 2 1 5 0.635 0.602 0.66% 0.635 0.603 0.65% 2.444 2.498 1.08% 2 1 25 1.740 1.506 0.94% 1.740 1.508 0.93% 12.324 12.491 0.67% 2 1 125 3.153 3.182 0.02% 3.153 3.179 0.02% 62.299 62.906 0.49% 2 2 5 0.733 0.655 1.55% 0.733 0.654 1.57% 2.453 2.502 0.99% 2 2 25 2.083 1.776 1.23% 2.083 1.761 1.29% 12.327 12.614 1.15% 2 2 125 3.633 3.596 0.03% 3.633 3.481 0.12% 62.302 63.030 0.58% Table 4.5: Comparison of mean queue lengths (storage and retrieval requests) and average inventory level in the rack for S = R = 1 and 70% expected utilization (A: Analytical, S: Simulation) 60 Utilization Throughput SCV C2 aS = C2 aR C2S C Rack Size A S %E A S %E A 0.5 0.5 5 0.584 0.647 9.72% 0.835 0.924 9.71% 0.452 0.5 0.5 25 0.683 0.689 0.87% 0.976 0.985 0.97% 0.543 0.5 0.5 125 0.697 0.697 0.06% 0.996 0.997 0.07% 0.556 0.5 1 5 0.578 0.642 10.00% 0.826 0.917 10.02% 0.567 0.5 1 25 0.682 0.689 1.03% 0.974 0.985 1.13% 0.686 0.5 1 125 0.697 0.697 0.04% 0.996 0.997 0.09% 0.704 0.5 2 5 0.567 0.629 9.94% 0.890 0.899 1.00% 0.793 0.5 2 25 0.680 0.689 1.36% 0.971 0.984 1.36% 0.971 0.5 2 125 0.697 0.698 0.14% 0.996 0.997 0.12% 1.007 1 0.5 5 0.576 0.602 4.25% 0.823 0.860 4.24% 0.544 1 0.5 25 0.681 0.679 0.28% 0.973 0.971 0.19% 0.654 1 0.5 125 0.697 0.695 0.29% 0.996 0.994 0.18% 0.667 1 1 5 0.571 0.597 4.42% 0.815 0.853 4.39% 0.656 1 1 25 0.678 0.679 0.22% 0.968 0.971 0.31% 1.080 1 1 125 0.697 0.695 0.27% 0.996 0.994 0.16% 0.815 1 2 5 0.560 0.585 4.26% 0.800 0.838 4.47% 0.878 1 2 25 0.678 0.678 0.07% 0.968 0.969 0.11% 1.080 1 2 125 0.697 0.696 0.10% 0.995 0.994 0.13% 1.111 2 0.5 5 0.562 0.541 3.79% 0.802 0.773 3.71% 0.739 2 0.5 25 0.677 0.662 2.22% 0.967 0.946 2.18% 0.884 2 0.5 125 0.696 0.692 0.64% 0.995 0.989 0.57% 0.890 2 1 5 0.557 0.536 3.82% 0.795 0.766 3.83% 0.847 2 1 25 0.676 0.661 2.19% 0.965 0.945 2.11% 1.024 2 1 125 0.696 0.692 0.61% 0.995 0.989 0.55% 1.038 2 2 5 0.547 0.526 4.05% 0.782 0.751 4.07% 1.060 2 2 25 0.673 0.658 2.33% 0.962 0.941 2.25% 1.307 2 2 125 0.696 0.692 0.58% 0.994 0.988 0.62% 1.334 Table 4.6: Comparison of utilization and throughput of the shared server for S = R = 1 and 70% expected utilization (A: Analytical, S: Simulation) 61 Storage Queue Retrieval Queue Average Inventory C2 aS = C2 aR C2S C Rack Size A S %E A S %E A S %E 0.5 0.5 5 0.688 0.550 2.76% 0.688 0.550 2.77% 2.354 2.499 2.90% 0.5 0.5 25 1.907 1.122 3.14% 1.907 1.126 3.12% 12.223 12.474 1.00% 0.5 0.5 125 3.373 2.683 0.55% 3.373 2.639 0.59% 62.190 62.921 0.59% 0.5 1 5 0.775 0.655 2.41% 0.776 0.655 2.41% 2.363 2.499 2.72% 0
Click tabs to swap between content that is broken into logical sections.
Rating  
Title  Integrated Analytical Performance Evaluation Models of Warehouses 
Date  20090701 
Author  Ayodhiramanujan, Karthik 
Department  Industrial Engineering & Management 
Document Type  
Full Text Type  Open Access 
Abstract  Warehouse design process is a complex process with numerous alternatives at all design stages, with focus on throughput capacity, inventory size and material handling equipment requirements. Enumerating all feasible solutions that satisfy the throughput and storage capacity requirements is not practical. Analytical models play a key role in the preliminary design stages in identifying several good initial warehouse configurations. This research effort pertains to the development of integrated analytical models that address capacity/congestion and inventory issues simultaneously in warehouse systems. The first part of the dissertation focuses on the development of a queueing network model of the "sharedserver system" which is an inventory store with a server performing both storage and retrieval operations. First, we modeled the sharedserver system using Continuous Time Markov Chains (CTMC) under exponential assumptions. We then developed an approximate queueing network model for general arrivals and general service time distribution, and designed a solution procedure based on the parametricdecomposition method. Later, we extended these models to include multiserver cases. The second part of the dissertation focuses on the development of a queueinginventory (QI) model of an orderpicking system. The configuration of the unitload that is stored (pallets) is different from that which is retrieved (cases). We developed a single stage QI model with batch processing to represent the material movement in and out of the forward inventory store. We then extended these models to include multiserver cases. The last part of the dissertation focuses on the development of an integrated model that demonstrates the applicability of these key building blocks (the sharedserver system and the orderpicking system) in developing an endtoend model of the warehouse system. Extensive numerical experiments indicate that the proposed analytical models can be solved in a computationally efficient manner and are accurate for a wide range of parameter values when compared with simulation estimates. 
Note  Dissertation 
Rights  © Oklahoma Agricultural and Mechanical Board of Regents 
Transcript  INTEGRATED ANALYTICAL PERFORMANCE EVALUATION MODELS OF WAREHOUSES By KARTHIK AYODHIRAMANUJAN Bachelor of Engineering (Mechanical) S. V. National Institute of Technology Surat, Gujarat, India 1998 Master of Science (Mechanical Engineering) Oklahoma State University Stillwater, Oklahoma, USA 2001 Submitted to the Faculty of the Graduate College of Oklahoma State University in partial fulfillment of the requirements for the Degree of DOCTOR OF PHILOSOPHY July, 2009 COPYRIGHT c By KARTHIK AYODHIRAMANUJAN July, 2009 INTEGRATED ANALYTICAL PERFORMANCE EVALUATION MODELS OF WAREHOUSES Dissertation Approved: Dr. Manjunath Kamath Dissertation Advisor Dr. Ricki G. Ingalls Dr. David B. Pratt Dr. Dursun Delen Dr. Gordon Emslie Dean of the Graduate College iii Acknowledgments There is an Indian adage about one’s spiritual evolution, “Maata, Pitha, Guru, Deivam”; Maata (mother) identifies the child to its Pitha (father), who shows the child to the Guru (teacher), who leads one to the path to Deivam (God). First and foremost, I wish to dedicate my work to my father (Late) Mr. Ayodhiramanujan and mother, Mrs. Ganapriya Ayodhiramanujan. There are no words that can express my gratitude to my advisor, Dr. Manjunath Kamath, who is not only my teacher but also my mentor, for providing me with valuable guidance and immense support at all times. I would like to thank my wife, Janani Murali, who by just being there for me gave me great strength in the last three years. Special thanks go to my committee members, Dr. Ricki Ingalls, Dr. David Pratt and Dr. Dursun Delen for their suggestions in simulation modeling, many aspects of warehouse processes and in general sharing their experiences with me, thereby bolstering my interest and confidence. I would like to take this opportunity to thank my friends and colleagues at the Center for Computer Integrated Manufacturing enterprises who made the research center, a home away from home. I would like to thank Sandeep Srivathsan for his tremendous help especially during my work from Dallas. Finally, I would like to acknowledge the financial support provided by Center for Engineering Logistics and Distribution, and Department of Biosystems Engineering at Oklahoma State University. As always, “Sarvam Krishnarpanam”, everything at the lotus feet of Lord Krishna. 4 Contents 1 Introduction 1 1.1 Warehousing Systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.2 Warehouse Activity Description . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.3 Performance Evaluation of Warehouses . . . . . . . . . . . . . . . . . . . . . 6 1.4 Motivation for the Current Research . . . . . . . . . . . . . . . . . . . . . . 7 1.4.1 The Problem Statement . . . . . . . . . . . . . . . . . . . . . . . . . 8 1.5 Overview of the Document . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 2 Literature Review 10 2.1 Review of Warehouse Performance Evaluation Models . . . . . . . . . . . . 10 2.1.1 Throughput Capacity Models . . . . . . . . . . . . . . . . . . . . . . 11 2.1.2 Storage Capacity Models . . . . . . . . . . . . . . . . . . . . . . . . 16 2.1.3 Integrated Design Methods . . . . . . . . . . . . . . . . . . . . . . . 18 2.2 Review of ProductionInventory Models . . . . . . . . . . . . . . . . . . . . 20 2.3 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 3 Statement of Research 25 3.1 Research Objectives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 3.2 Research Scope and Limitations . . . . . . . . . . . . . . . . . . . . . . . . 28 4 SharedServer System 29 4.1 SharedServer System Development . . . . . . . . . . . . . . . . . . . . . . . 29 4.1.1 Description of the SharedServer System . . . . . . . . . . . . . . . . 30 4.1.2 Assumptions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 4.2 CTMC Model and Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 4.2.1 Numerical Experiments . . . . . . . . . . . . . . . . . . . . . . . . . 36 4.3 Queueing Network Model of the SharedServer . . . . . . . . . . . . . . . . 39 4.3.1 Characterization of the Synchronization Station . . . . . . . . . . . 43 4.3.2 Characterization of the Processing Station . . . . . . . . . . . . . . . 45 4.3.3 Linking the Stations . . . . . . . . . . . . . . . . . . . . . . . . . . . 49 4.3.4 Solution Approach . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52 4.3.5 Computational Effort and Convergence . . . . . . . . . . . . . . . . 56 4.3.6 Performance Measures and Model Accuracy . . . . . . . . . . . . . . 56 4.3.7 Accuracy of the SharedServer Model . . . . . . . . . . . . . . . . . 58 4.3.8 Departure Process from the Retrieval Processing Station . . . . . . . 89 4.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96 i 5 SharedServer System: Multiserver case 98 5.1 Modifications to the Service Time . . . . . . . . . . . . . . . . . . . . . . . 98 5.2 Characterization of the Storage Processing Station . . . . . . . . . . . . . . 100 5.3 Accuracy of the MultiServer Model . . . . . . . . . . . . . . . . . . . . . . 102 5.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103 6 OrderPicking System 112 6.1 Description of the OrderPicking Model . . . . . . . . . . . . . . . . . . . . 113 6.2 Single Stage QI model with Batch Processing . . . . . . . . . . . . . . . . . 114 6.2.1 SingleServer Processing Station . . . . . . . . . . . . . . . . . . . . 116 6.2.2 MultiServer Processing Station . . . . . . . . . . . . . . . . . . . . . 122 6.3 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127 7 Integrated Warehouse Model 128 7.1 Warehouse Description . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 128 7.2 QueueingNetwork Description . . . . . . . . . . . . . . . . . . . . . . . . . 129 7.3 Analysis of the Integrated Model . . . . . . . . . . . . . . . . . . . . . . . . 130 7.3.1 Integrated Model : SingleServer Case . . . . . . . . . . . . . . . . . 131 7.3.2 Integrated Model : MultiServer Case . . . . . . . . . . . . . . . . . 141 7.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 142 8 Summary, Conclusions and Future Research 146 8.1 Research Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 146 8.2 Research Contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 148 8.3 Future Directions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 149 8.3.1 Research related to the sharedserver system . . . . . . . . . . . . . 149 8.3.2 Research related to warehouse system . . . . . . . . . . . . . . . . . 150 Bibliography 151 A Appendix 156 A.1 Stationary Equations  SharedServer System . . . . . . . . . . . . . . . . . 156 A.2 Simulation Study of the SharedServer System . . . . . . . . . . . . . . . . 160 ii List of Figures 1.1 Functional areas and product flow in a typical warehouse . . . . . . . . . . 4 1.2 A typical warehouse with forwardreserve inventory . . . . . . . . . . . . . . 5 2.1 EndofAisle System with (a) dedicated and (b) multiple aisles per picker . 13 2.2 An example Order Accumulation and Sortation System (Johnson and Meller, 2002) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 2.3 A simple highlevel queueing network model of a warehouse . . . . . . . . . 19 2.4 Mstage ProductionInventory model . . . . . . . . . . . . . . . . . . . . . . 21 3.1 A sharedserver system . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 3.2 An orderpicking system . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 4.1 Process and resource centric views of warehouse operations . . . . . . . . . 30 4.2 ProductionInventory (PI) models of (a) manufacturing system (b) warehouse rack storage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 4.3 Example statetransitions for the CTMC model of the sharedserver system 34 4.4 A single stage kanban system (Krishnamurthy, 2002) . . . . . . . . . . . . . 39 4.5 Queueing network model of a shared server . . . . . . . . . . . . . . . . . . 40 4.6 Overview of parametricdecomposition approach for the queueing network model of the sharedserver . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42 4.7 Characterization of storage synchronization station (JS) . . . . . . . . . . . 44 4.8 Characterization of the Storage Processing station (SP) . . . . . . . . . . . 46 4.9 Linking storage synchronization and storage processing stations . . . . . . . 50 4.10 Linking storage processing and retrieval synchronization stations . . . . . . 50 4.11 Retrieval throughput as a function of system variability in a balanced system 67 4.12 Utilization as a function of system variability in a balanced system . . . . . 69 4.13 Mean queue length (storage requests) as a function of system variability in a balanced system . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71 4.14 Retrieval throughput from a unbalanced sharedserver system at 90% expected utilization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88 4.15 Mean queue length of storage requests in an unbalanced sharedserver system at 90% expected utilization . . . . . . . . . . . . . . . . . . . . . . . . . . . 90 4.16 Mean queue length of retrieval requests in an unbalanced sharedserver system at 90% expected utilization . . . . . . . . . . . . . . . . . . . . . . . . . 92 4.17 Average inventory in rack in an unbalanced sharedserver system at 90% expected utilization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94 4.18 Sharedserver model with a downstream loading operation . . . . . . . . . . 96 iii 5.1 Multiple aisles (S/R machines) in the warehouse and sharedserver system with multiple servers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99 5.2 The multiserver storage processing station . . . . . . . . . . . . . . . . . . 100 5.3 Retrieval throughput as a function of system variability in a balanced sharedserver system with multiple servers . . . . . . . . . . . . . . . . . . . . . . . 108 5.4 Mean queue length (storage requests) as a function of system variability in a balanced sharedserver system with multiple servers . . . . . . . . . . . . . 110 6.1 Changing unitload configuration . . . . . . . . . . . . . . . . . . . . . . . . 112 6.2 A queueinginventory model that illustrates changing unitload configuration 113 6.3 Single stage QI model with batch processing . . . . . . . . . . . . . . . . . . 114 6.4 Average inventory level and average backorders at the rack at 80% utilization (singleserver processing station) . . . . . . . . . . . . . . . . . . . . . . . . 120 6.5 Average inventory level and average backorders at the rack at 90% utilization (singleserver processing station) . . . . . . . . . . . . . . . . . . . . . . . . 121 6.6 Average inventory level and average backorders at the rack at 80% utilization (multiserver processing station) . . . . . . . . . . . . . . . . . . . . . . . . 125 6.7 Average inventory level and average backorders at the rack at 90% utilization (multiserver processing station) . . . . . . . . . . . . . . . . . . . . . . . . 126 7.1 Iconic model of the warehouse . . . . . . . . . . . . . . . . . . . . . . . . . . 128 7.2 Queueing  Inventory model of the warehouse . . . . . . . . . . . . . . . . . 129 7.3 Input to and output from the Sharedserver stage . . . . . . . . . . . . . . . 131 7.4 Input to and output from InternalReplenishment stage . . . . . . . . . . . 132 7.5 Superposition of upstream and downstream arrivals to the orderpicking queue133 7.6 Input to and output from OrderPicking stage . . . . . . . . . . . . . . . . . 134 A.1 Plot of batch means of time in system for retrieval requests . . . . . . . . . 161 A.2 Plot of batch means of time in system for retrieval requests . . . . . . . . . 162 iv List of Tables 4.1 Design of experiments for shared server system (Markovian case) . . . . . . 35 4.2 Results for the sharedserver CTMC model (BS = BR = Z) = 0.8 and S = R = 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 4.3 Results for the sharedserver CTMC model (BS = BR > Z) = 0.8 and S = R = 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 4.4 Design of experiments for sharedserver system: single server case . . . . . . 58 4.5 Comparison of mean queue lengths (storage and retrieval requests) and average inventory level in the rack for S = R = 1 and 70% expected utilization (A: Analytical, S: Simulation) . . . . . . . . . . . . . . . . . . . . . . . . . . 60 4.6 Comparison of utilization and throughput of the shared server for S = R = 1 and 70% expected utilization (A: Analytical, S: Simulation) . . . . . . . . 61 4.7 Comparison of mean queue lengths (storage and retrieval requests) and average inventory level in the rack for S = R = 1 and 80% expected utilization (A: Analytical, S: Simulation) . . . . . . . . . . . . . . . . . . . . . . . . . . 62 4.8 Comparison of utilization and throughput of the shared server for S = R = 1 and 80% expected utilization (A: Analytical, S: Simulation) . . . . . . . . 63 4.9 Comparison of mean queue lengths (storage and retrieval requests) and average inventory level in the rack for S = R = 1 and 90% expected utilization (A: Analytical, S: Simulation) . . . . . . . . . . . . . . . . . . . . . . . . . . 64 4.10 Comparison of utilization and throughput of the shared server for S = R = 1 and 90% expected utilization (A: Analytical, S: Simulation) . . . . . . . . 65 4.11 Comparison of mean queue length (storage and retrieval requests) and average inventory in the rack at 70% expected utilization in an unbalanced system (A: Analytical, S: Simulation) . . . . . . . . . . . . . . . . . . . . . 73 4.12 Comparison of actual utilization and retrieval throughput at 70% expected utilization in an unbalanced system (A: Analytical, S: Simulation) . . . . . 76 4.13 Comparison of mean queue length (storage and retrieval requests) and average inventory in the rack at 80% expected utilization in an unbalanced system (A: Analytical, S: Simulation) . . . . . . . . . . . . . . . . . . . . . 78 4.14 Comparison of actual utilization and retrieval throughput at 80% expected utilization in an unbalanced system (A: Analytical, S: Simulation) . . . . . 81 4.15 Comparison of mean queue length (storage and retrieval requests) and average inventory in the rack at 90% expected utilization in an unbalanced system (A: Analytical, S: Simulation) . . . . . . . . . . . . . . . . . . . . . 83 4.16 Comparison of actual utilization and retrieval throughput at 90% expected utilization in an unbalanced system (A: Analytical, S: Simulation) . . . . . 86 4.17 Verification of SCV of the departure process of the retrieval requests from the sharedserver system at 90% expected utilization . . . . . . . . . . . . . 97 v 5.1 Experimental design for the sharedserver system: multi server case . . . . . 102 5.2 Comparison of mean queue lengths (storage and retrieval requests) and average inventory level in the rack for S = R = 1 and 80% expected utilization (A: Analytical, S: Simulation) . . . . . . . . . . . . . . . . . . . . . . . . . . 104 5.3 Comparison of utilization and throughput of the multi  shared server for S = R = 1 and 80% expected utilization (A: Analytical, S: Simulation) . 105 5.4 Comparison of mean queue lengths (storage and retrieval requests) and average inventory level in the rack for S = R = 1 and 90% expected utilization (A: Analytical, S: Simulation) . . . . . . . . . . . . . . . . . . . . . . . . . . 106 5.5 Comparison of utilization and throughput of the shared server for S = R = 1 and 90% expected utilization (A: Analytical, S: Simulation) . . . . . . . . 107 6.1 Experimental setup for single stage QI system with batching . . . . . . . . 118 6.2 Average inventory and average backorder at 80% utilization and batch size of 2 (singleserver processing station) . . . . . . . . . . . . . . . . . . . . . . 118 6.3 Average inventory and average backorder at 90% utilization and batch size of 2 (singleserver processing station) . . . . . . . . . . . . . . . . . . . . . . 119 6.4 Average inventory and average backorder at 80% utilization and batch size of 4 (singleserver processing station) . . . . . . . . . . . . . . . . . . . . . . 119 6.5 Average inventory and average backorder at 90% utilization and batch size of 4 (singleserver processing station) . . . . . . . . . . . . . . . . . . . . . . 119 6.6 Average inventory and average backorder at 80% utilization and batch size of 2 (multiserver processing station) . . . . . . . . . . . . . . . . . . . . . . 123 6.7 Average inventory and average backorder at 90% utilization and batch size of 2 (multiserver processing station) . . . . . . . . . . . . . . . . . . . . . . 124 6.8 Average inventory and average backorder at 80% utilization and batch size of 4 (multiserver processing station) . . . . . . . . . . . . . . . . . . . . . . 124 6.9 Average inventory and average backorder at 90% utilization and batch size of 4 (multiserver processing station) . . . . . . . . . . . . . . . . . . . . . . 124 7.1 Experimental design to evaluate the integrated model . . . . . . . . . . . . 136 7.2 Complete set of experiments to evaluate the integrated model (single server case) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 136 7.3 Analytical estimates of the performance measures when C2S = C2C = C2i = 0.5 (singleserver) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 138 7.4 Simulation estimates of the performance measures when C2S = C2C = C2i = 0.5 (singleserver) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 138 7.5 Error estimates of the performance measures when C2S = C2C = C2i = 0.5 (singleserver) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 138 7.6 Analytical estimates of the performance measures when C2S = C2C = C2i = 1 (singleserver) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 139 7.7 Simulation estimates of the performance measures when C2S = C2C = C2i = 1 (singleserver) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 139 7.8 Error estimates of the performance measures when C2S = C2C = C2i = 1 (singleserver) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 139 7.9 Analytical estimates of the performance measures when C2S = C2C = C2i = 2 (singleserver) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 140 vi 7.10 Simulation estimates of the performance measures when C2S = C2C = C2i = 2 (singleserver) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 140 7.11 Error estimates of the performance measures when C2S = C2C = C2i = 2 (singleserver) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 140 7.12 Complete set of experiment to evaluate the integrated model (multi server) 141 7.13 Analytical estimates of the performance measures when C2S = C2C = C2i = 0.5 (multiserver) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143 7.14 Simulation estimates of the performance measures when C2S = C2C = C2i = 0.5 (multiserver) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143 7.15 Error estimates of the performance measures when C2S = C2C = C2i = 0.5 (multiserver) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143 7.16 Analytical estimates of the performance measures when C2S = C2C = C2i = 1 (multiserver) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 144 7.17 Simulation estimates of the performance measures when C2S = C2C = C2i = 1 (multiserver) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 144 7.18 Error estimates of the performance measures when C2S = C2C = C2i = 1 (multiserver) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 144 7.19 Analytical estimates of the performance measures when C2S = C2C = C2i= 2 (multiserver) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 145 7.20 Simulation estimates of the performance measures when C2S = C2C= C2i = 2 (multiserver) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 145 7.21 Error estimates of the performance measures when C2S = C2C = C2i = 2 (multiserver) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 145 vii Chapter 1 Introduction With rapidly changing business scenarios, the role of warehouses is becoming increasingly critical in the efficient management and success of supply chains. With respect to their position in a supply chain, Frazelle (2001) classified the warehouses as • Production warehouses • Finished goods warehouses and fulfillment centers • Distribution warehouses • Contract warehouses Production warehouses hold raw materials or workinprocess inventory for use by manufacturing facilities. Finished goods warehouses store finished products, typically in pallet loads that serve as a buffer against uncertainties in customer demand. With the proliferation of ecommerce, fulfillment centers are shipping small quantities or individual items to end customers directly. Distribution warehouses accumulate and consolidate products from multiple manufacturing facilities for multiple customers. Contract warehouses are operated by a third party organization for one or more customers. Two major factors that have caused a change in the focus of warehousing systems are the evolution of manufacturing concepts like JustInTime and the evolution of information systems and technology. Mass customization and global competition are requiring supply 1 chain partners to be more flexible with respect to product demand and product mix. Frequent delivery in low volumes for a wide range of products is the focus of current supply chains, thus moving many small, but important valueadded services closer to the customer. With the renewed emphasis on customer satisfaction and integrated supply chain management, warehouses are not the traditional storage locations they once used to be. Today’s warehouses are responsive to customer demands by providing valueadded services such as last minute customization, small assembly, labeling, kitting, and special packaging. Hence, warehouse operations are not only more productive but also more complicated than ever before. Modern information systems have enabled the traditional warehouses plan their operations more effectively. Concepts such as crossdocking have received more attention; the results include the reduction of the time a product spends at a warehouse and the elimination of some storage and doublehandling of products. With customer demandpatterns evolving continuously, the drive to reduce cost and extreme competition have forced warehouses to devote a lot of effort to constantly improving their methods and systems. In such a dynamic environment, modeling and analysis of the underlying warehouse systems and continuous improvement of their operations becomes critical for their effective and efficient design and control. 1.1 Warehousing Systems Warehousing systems are one of the most researched components of a supply chain. Many authors have provided excellent reviews of warehousing systems, see for example, Berg (1999), Berg & Zijm (1999), Yoon & Sharp (1996), and Tompkins et al. (2003). Depending on the position of the warehouse in the supply chain, the activities within the warehouse and the form of material handled are determined. The typical activities in a warehouse are summarized in Figure 1.1. Receiving is the collection of all the activities related to the orderly receipt of goods, inspection (for quantity and quality) and disbursing to storage or crossdocking for immediate shipping. 2 Repackaging is the process of splitting the products that are ordered in bulk quantities and repacking to customer specifications (single or carton/case), or assembling to form kits with other parts of a customer shipment. Some part of the load might also be held in storage for future shipment. This function is also called breakbulk operation. Putaway is the process of placing the merchandise in either longterm storage (reserve) or shortterm storage (forward). Orderpicking is the process of retrieving items from the storage area to meet a specific demand. Many classifications of warehousing systems exist based on the type of order picking which is the most cost intensive process in the warehouse. Sortation is the process of sorting the accumulated batch picks into individual orders. Crossdocking is the process of staging the inbound goods directly to shipping without sending it to storage. Replenishment is the process of refilling the primary and secondary picking areas from longterm storage. Shipping includes all the activities related to checking the order for completeness and appropriate packaging; determining shipping charges; accumulating orders by outbound trailer; and loading the trailers. 1.2 Warehouse Activity Description The basic functions common to all the warehouses are receiving, putaway or storage, picking, and shipping. A typical warehouse with reserve and forward storage areas, together with the material flow is shown in Figure 1.2. In this section, we will describe the configuration of warehouses with particular attention to storage and retrieval operations. A typical material flow in a warehouse starts with the incoming trucks arriving into the yard. The trucks either deliver the trailers directly to the dock or wait in a queue till a dock door is available. Once the trailer occupies a dock door, a worker crew (strippers) is assigned 3 Figure 1.1: Functional areas and product flow in a typical warehouse to unload the trailer. In this dissertation, we assume that trailers contain pallet loads. The workers unload all the contents of the trailer and place the items in the receiving/staging area for further processing (e.g. inspection). The dock door is then scheduled to unload the next waiting trailer. The stripper or another employee verifies the contents of the trailer for quality in the receiving/staging area. The stripper may place the items for crossdocking or longterm storage. Discrete or continuous material handling devices may be used to move the items from the receiving area. The items meant for longterm storage usually do not alter their unitload configuration. Workers/fork lifts move the pallets into the reserve storage area. This process is automated in some warehouses using Automated Guided Vehicles (AGVs). The reserve storage may be as simple as a rack storage system or an Automated Storage and Retrieval System (AS/RS). In the case of AS/RS, the storage into the racks and retrievals from the racks are performed by Storage/Retrieval (S/R) machines. A warehouse dealing with lessthanpalletloads may have two different storage areas – reserve or long term storage for pallets and forward or short term storage for cases. The presence of forward and reserve areas necessitates an internal replenishment policy. There 4 Figure 1.2: A typical warehouse with forwardreserve inventory is a break bulk operation, i.e. pallets from the reserve storage are broken into individual cases. Typically the order pickers picking from the forward area pick individual cases from the replenished pallet loads. Some warehouses may deal with individual items. In such scenarios, there is another break bulk like operation called the splitcase operation. The order pickers may pick individual items from the cases; sort and assemble an order before shipping. Each order is defined by number of unique line items and related quantities. Once an order is received for an item, orders are picked either from the forward or reserve storage. Items are accumulated in a shipping/staging area to be loaded on to the trailers. The orders are verified to ensure quality and items are loaded by a worker crew (stackers). The items are assembled to form a tight packing and order integrity is preferred, i.e., items in the same order are shipped together. Some of the factors that influence the retrieval of items include: • Order picking method – single, dual or multiple command • Material handling equipment properties – capacity of the carts, fork lifts or pallet jacks 5 • Layout of the terminals – multiple cross aisles • Storage assignment policies – random, dedicated, or class based • Clustering of items in storage • Order batching and hence, associated sortation process if necessary • Presence of forwardreserve storage areas In some warehouses, palletization may be an additional process to build unit load pallets that could consist of similar items or a mixed load. 1.3 Performance Evaluation of Warehouses Suri et al. (1993) defined performance evaluation (PE) as "a methodology (including techniques and tools) for determining the performance measures that can be expected to result from a given set of decisions." Performance evaluation usually employs simulation models or analytical models. Simulation models are dynamic in nature and model the evolution of the system over time. These are detailed models and model development takes considerable effort. Analytical models, also called as aggregate dynamic models, account for some uncertainties and interactions in the system using mathematical or symbolic relationships. These models can be used for rapid analysis of many design configurations albeit at an aggregate level. Analytical models based on stochastic Petri nets, Markov chains, and queueing theory provide rapid analysis capability and can provide insights into the behavior of the system. As with any performance evaluation model, there is a tradeoff between model detail and tractability. Some of the performance measures of interest in a warehouse environment are throughput, average response time, fill rate, and utilization of space, equipment, and human resources, in addition to financial metrics. Schefczyk (1990) provides a comprehensive list of performance measures related to warehouses. Many authors have developed performance evaluation models for warehousing systems. A detailed review is provided in the following chapter. To a great extent, these models 6 focus on a particular system or class of systems within a bigger facility, for example Endof Aisle order picking systems (Bozer & White (1990)), AS/RS (Abdelkrim et al. (2003), and Lee (1997)), and sortation systems (Bozer et al. (1988) and Johnson and Meller (2002)), which are important subsystems of a warehouse. Some of the models focus on limited and welldefined isolated problems like routing and sequencing of order pickers or dwell point determination, neglecting the interaction amongst system components. 1.4 Motivation for the Current Research Warehouse system design is a complex process with numerous alternatives at all design levels for the designer to consider and evaluate. For example, a warehouse might deal with more than one product configuration (pallet, case, or item), choice of storage systems (AS/RS, carousels, or bin shelves), and storage policies (random, classbased or dedicated). Warehouse design decisions typically focus on three important aspects; the throughput capacity, the size of the inventory to be stored and the material handling equipment requirements. Enumerating all feasible solutions that satisfy the throughput and storage capacity requirements and finding an optimal solution is not practical. Until now, the decisionmakers have relied on experience and descriptive, systematic procedures to select a set of feasible candidates of warehouse design. The literature on integrated models focuses either on descriptive design methodologies (e.g., Ashayeri & Goetschalckx (1988)) or sequential solution approaches. In addition, the warehouse managers have limited readymade tools to evaluate the warehouse performance or resource requirement if a new operation is to be incorporated into the material flow, for example, repackaging. Simulation is the preferred tool for evaluating the designs. Building a warehouse simulation model takes considerable time and effort, though computing power is no longer a constraint. Analytical models for performance evaluation, on the other hand may be approximate but enable quick evaluation and offer insight into the system behavior. Analytical models can help in examining a larger set of alternatives initially, thereby reducing the number of candidates for detailed simulation analysis. A useful tool in the design pro 7 cess or in the evaluation of current warehousing systems would be an integrated model that can capture the interactions among material handling and storage processes that span receiving, inspection, storage/putaway, picking, shipping and valueadded services. Isolated analysis of warehouse subsystems, though valuable and important, is not sufficient at the overall system design stage. Rouwenhorst et al. (2000) point out that the design decisions at the strategic and tactical levels are interrelated. For example, a decision to have separate forward and reserve areas (strategic) leads to an inventory replenishment policy between the storage areas (tactical). Also, the inventory decisions (size of the warehouse) are made independently from the individual subsystems such as AS/RS. But the performance of the subsystems is affected by the storage size. Such interrelated decisions need to be modeled jointly. To support decision making for the new generations of warehouses, there is a need to include a larger set of issues such as inventory and capacity/congestion, within a single analytical model, so that their impact on the total system performance can be evaluated. 1.4.1 The Problem Statement With the changing role of warehouses, the ability to model multiple decisions simultaneously, especially inventory and throughput decisions, will complement the warehouse design process and aid in analyzing existing operations. Queues and queueing networks have been applied in the performance evaluation of warehouses, but the focus has been more on isolated systems like AS/RS and its related decisions like throughput and storage size estimation, separately. Productioninventory networks, i.e., queueing network models that address both capacity/ congestion and planned inventory issues have been successfully applied in manufacturing and supply chain systems. But very limited literature is available on their application in the warehouse domain. This dissertation is the first step towards addressing this gap. Hence, the problem statement can be described as “developing analytical models of queueinginventory systems that address capacity/congestion and inventory issues simultaneously in the context of a warehouse system.” To this end, the dissertation first focuses on the development of performance evaluation 8 models of subcomponents that are representative of AS/RS type systems (e.g., a server that stores and retrieves material from the same storage area) and orderpicking systems where unitload configurations vary between two successive material movements. These models address both material handling and material storage operations in a manner similar to the productioninventory models. The dissertation also demonstrates the applicability of these individual models in building comprehensive endtoend warehouse performance evaluation models. 1.5 Overview of the Document In this chapter, we introduced warehousing systems in general, and commented on the current status of performance evaluation of such systems. We described some of the characteristics of warehousing systems and provided the motivation for the research effort. Chapter 2 gives an overview of the warehouse performance evaluation models and a review of the literature on productioninventory networks. The research objectives, general assumptions and research limitations are summarized in Chapter 3. In Chapter 4, we focus on the development and analysis of the sharedserver system, a key building block in the performance evaluation of warehouses. We extend the sharedserver model to the multiserver case in Chapter 5. We then focus on the development and analysis of models that accommodate changing unitload configuration (single and multiserver cases) in Chapter 6. Chapter 7 illustrates the development of a proofofconcept endtoend model for warehouses. Finally, we conclude the dissertation with a prospectus for future research with respect to warehouse performance evaluation models. 9 Chapter 2 Literature Review In this chapter, we focus on the review of literature pertinent to warehouse performance evaluation and productioninventory models. The analytical models in this review tend to focus more on the application of queueing or queueing network models. 2.1 Review of Warehouse Performance Evaluation Models The major sources of randomness in a warehouse are the demand for the items to be retrieved from storage, the arrival of the items to be stored, the material handling times and the inherent reliability of the servers (human and machine). Sophisticated simulation models that address some of these sources of randomness have been developed and can evaluate the performance of different configurations of warehouses (see for example, Linn & Wysk (1984), Berg & Gademann (2000) among others). The analytical performance evaluation models of warehouses can be classified as throughput capacity models, storage capacity models, and warehouse design models (Cormier & Gunn (1992)). Throughput capacity models are mostly tactical and operational models that evaluate the throughput of the warehouse, where throughput is defined as the number of storage/retrieval operations per unit time. The storage capacity models, which are usually strategic models, focus on the determination of the size of the warehouse to satisfy a minimum service level commitment. The warehouse design models focus on the overall design involving decisions related to space allocation among storage systems, crossdocking, 10 and other valueadded services. 2.1.1 Throughput Capacity Models Throughput capacity issues have received considerable attention in the warehouse literature, mainly because the orderpicking costs constitute a major portion of the total operational costs (Tompkins et al. (2003)). In this section, we will summarize the modeling approach and the decisions considered in the throughput models for two important subsystems, namely Automated Storage and Retrieval Systems (AS/RS) and Order Accumulation and Sortation Systems (OASS). AS/RS performance evaluation models have focused on the development of traveltime models for both unitload AS/RS and miniload AS/RS. For a detailed literature survey on stochastic modeling of AS/RS and travel time models, the reader is referred to Johnson and Brandeau (1996) and Sarker & Babu (1995) respectively. Lee (1997) presented the first stochastic analysis of a unitload AS/RS by using a singleserver queueing model. He assumed aisle captive S/R machines and modeled each aisle as a single server with two queues: a storage queue for incoming unit loads and a retrieval queue. Both the queues have finite capacity. The storage and retrieval arrivals are lost when the queues are full. The S/R machine always returned to the I/O point and the FIFO policy was followed for the queues, except when both the queues had transactions waiting. In the later case, a dual command cycle is performed. The proposed model could be viewed in part as an assemblylike queue and in part as a polling queue. Lee (1997) further assumed independent Poisson arrivals for storage and retrieval queues, and exponential service times for single and dual command cycles. Using a Continuous Time Markov Chain (CTMC) to represent the queue, Lee derived many useful performance measures including system throughput, turn around time for the requests and S/R machine utilization. The limited queue capacity and high variance assumption in the previous model underestimated the throughput and the S/R machine utilization. Lee (1997) had also assumed equal arrival rates for storage and retrieval. Hur et al. (2004) relaxed some these assumptions and modeled the S/R machine as a M/G/1 queuing system with separate queues for storage and retrieval requests. There was 11 no capacity limit on the queues and the arrivals were independent with different arrival rates. They assumed that the S/R machine could start and end the single command (SC) and dual command (DC) cycles at the I/O point or at the rack. Because of this assumption, they also assumed that the travel time for the SC and DC followed the same distribution with a single service rate. They also proposed a state space for the S/R machine by defining the state as (i, j) where i, j are the number of requests in the storage and retrieval queues, respectively, after a service completion. The resulting CTMC was solved to derive system performance measures. They compared their solution with that of Lee (1997) and found it to outperform Lee’s in many instances. Bozer & Cho (2005) assumed separate travel times for SC and DC cycles. They assumed the dwell point as the last known storage location of the S/R machine. The S/R machine always tried to perform a DC violating the FIFO policy for storage or retrieval request arrivals. They still assumed independent Poisson arrivals. For random storage assignment and different configurations of the rack, they derived closed form equations to determine whether the AS/RS meets the required throughput. They compared the S/R machine utilization for balanced and unbalanced systems (when storage requests exceeded retrieval requests or vice versa, which is possible in a warehouse) with simulation. Their results are also valid for other storage assignment policies and I/O point locations as long as the mean interleaving time (time between dropoff and pickup) in a DC cycle is smaller than mean SC cycle time. Hur & Nam (2006) extended the models of Hur et al. (2004) by considering separate service times for single and dual command cycles for the S/R machine with Poisson arrivals for service requests. They assumed finite queue capacity only for storage requests. The state space of the system is defined as the number of requests in the queues at the completion of a service request or the start of a busy period, similar to the earlier model. A Semi Markov Process (SMP) is generated from the Markov Chain to obtain the timeaverage probabilities, which is later used to obtain the system performance measures, including the probability that an arbitrary arrival is lost. All the above models for AS/RS performance evaluation considered unitload systems with equal sized storage spaces. Lee et al. (1999) presented models for AS/RS with unequal sized cells, i.e. cells within 12 Figure 2.1: EndofAisle System with (a) dedicated and (b) multiple aisles per picker a zone have the same size but differ in size between zones. They derived travel time models for SC and DC cycles, including interleaving time between different zones. An example of endofaisle order picking systems is a miniload AS/RS. In such systems, stored material is delivered by the S/R machine to the order picker located at the end of the aisle. While the order picker picks from the storage container, the S/R machine returns the previous container and retrieves the next order. These systems operate predominantly DC cycles. There are at least two pick positions at the end of each aisle. Bozer & White (1990) presented a design algorithm for such endofaisle order picking systems. They modeled each aisle as a closed queueing network with two nodes, the S/R machine and the order picker, as shown in Figure 2.1(a). The number of pick locations was the number of customers in the system. They assumed random storage policy with dedicated pickers for each aisle. They presented an iterative algorithm to find the minimum number of aisles necessary to meet the storage and throughput requirements. The throughput constraints were based on the picker utilization and the S/R machine utilization was only an additional measurement. Using simulation, they obtained an approximation for the standard deviation of the DC cycle travel time and approximated the DC cycle time with a uniform distribution. Their model confirmed that as the rack became more nonsquareintime, the number of aisles increased to meet the required throughput. Bozer & White (1996) extended their work to model multiple pick positions per aisle. 13 They relaxed their assumptions about aislerestricted orderpicker. The more general closed queueing network model is shown in Figure 2.1(b). Using diffusion approximations, they derived the expected utilization of the S/R machine and the order picker. They modified their design algorithm to include the expressions for utilization. They further experimented with sequencing of the retrieval requests. Only when the variance of pick time is low, significant improvements to throughput were achieved. Park (1999) used a similar closed queueing network model to study the impact of buffer sizes (number of pick locations per aisle for storage and retrieval queues) on the throughput of the system. They found that the maximum throughput obtainable by increasing the queue capacity is less than or equal to twice the throughput with a single space for storage and retrieval. They also analyzed the conditions under which the S/R machine can be blocked (“production blocking”) because of limited queue capacity. The literature on performance evaluation of AS/RS also considers operational details such as dwell point and order batching, and operating characteristics such as acceleration and deceleration of the S/R machines. Order Accumulation and Sortation Systems (OASS) find applications in both manufacturing and warehousing systems. The basic components in an OASS are the input conveyors; induction, spacing, and merge units; sortation mainline; and diverter modules. An example OASS is given in Figure 2.2 with one induction point, a recirculating conveyor, and multiple accumulation lanes (Johnson and Meller (2002)). In distribution centers, when orders are picked at the case and item level, orders are dispatched to the conveyor that sorts the items to different chutes assigned to a particular order or outbound truck. Throughput of the OASS is an important performance measure and it depends on many factors including the speed of the conveyors, induction process, sorting strategies, the upstream order picking process and downstream stacking/palletizing process amongst others. For wave picking (each wave consists of many orders and each order consists of many line items) and recirculating sortation conveyors, Johnson (1998) developed analytical models that study the impact of sorting strategies on the throughput of the system. He developed expressions for the expected time to sort a wave with and without blocking at the accumulation conveyors for Fixed Priority Rule (FPR) (smallest order first and largest order first) 14 Figure 2.2: An example Order Accumulation and Sortation System (Johnson and Meller, 2002) and Next Available Rules (NAR) for sorting. In the NAR, the orders are sorted based on the order in which the boxes pass through the scanner that initiates the sorting process. Eldemir (2003) developed another strategy based on the earliest completion time of an order, which reduced the wave sortation time. Johnson and Meller (2002) developed analytical models of an OASS with multiple induction points in the main conveyor. They assumed no recirculation of orders. When there is no blocking at the accumulation conveyors and the number of orders is less than the number of accumulation conveyors, the OASS performance is dependent only on the induction process. The authors analyze systems with sidebyside induction points and split induction points. In the sidebyside induction systems, the inductors compete for the same scanner thereby creating interference like phenomenon that tends to reduce the system throughput. The authors also address the impact of presorting orders on the OASS system performance. Eldemir (2003) proposed an open queueing network model for the design of OASS. The network consists of three processes (induction, sortation, and shipping) with corresponding queues (induction lane, main conveyor, and accumulation line). He derived expressions for the blocking probability and the lengths of the main sortation and accumulation conveyors by approximating each queue as an M/G/n/N queue. Russell & Meller (2003) developed descriptive and prescriptive design models for order fulfillment systems that are integrated order picking and ordersortation systems. They developed throughput simulation models 15 to compare the different configurations of wave picking and manual and automated OASS systems. Apart from these studies on OASS, there is a huge body of literature on conveyor theory, see for example, Bastani (1988); Arantes et al. (1998) and Bozer & Hsieh (2005) amongst others. 2.1.2 Storage Capacity Models The purpose of storage capacity models is to determine the number of warehouses, the size of each warehouse and any additional space that could be leased by minimizing the total discounted costs and/or to achieve predetermined service level. Cormier & Gunn (1992) categorized the models as static and dynamic models. In static models, the demand is assumed stationary and a warehouse size is determined. In dynamic models, the demand is assumed to be nonstationary and the warehouse is allowed to expand and contract i.e. size of the warehouse at different periods is determined. The authors also review models related to performance evaluation and maximization of space utilization through unitization & block stacking methods. Roll & Rosenblatt (1983) compared the effect of random and grouped storage policies on the warehouse capacity. In general, the random storage policy offers higher space utilization (assumption that the demand for each pallet is independent and all storage spaces are equally likely to be occupied) compared to grouped storage policy. In addition, the authors clearly noted that grouped storage policies offered operational and administrative advantages over the random storage policy. The authors defined Nominal Capacity Requirements (NCR) as the product of average throughput and the average storage time for each pallet. It is the lower bound on the required warehouse capacity and is the average size necessary subject to random throughput factors. Because of the stochastic nature of the arrivals of order and number of items per order, the warehouse may not be able to store the entire shipment and has to lease space outside. The effects of number of items and their characteristics, and operational issues (travel distances, orderpicking policies) were not considered. Rosenblatt & Roll (1988) later studied the factors that influence the storage capacity of the warehouse; a) number of items stored, b) demand characteristics of the items 16 (distribution of orders and items in an order) c) replenishment policy (order quantity and order point) for the item. They performed simulation experiments assuming a (r, Q) replenishment policy and random storage policy. They derived an approximate multiplicative expression using regression analysis for the deviation from the NCR for 95% service level as follows: Y95 = 34 Q0.16D0.22 1 N0.62r0.06D0.02 2 (2.1) where, Q is the order quantity, r is the reorder point, D1 is the average demand (orders/ day), D2 is the percentage deviation from D1, and N is the number of items. We can see that reorder point and the variance of the demand have very little effect on capacity. They tested the demand for different distributions (uniform, normal and exponential) and found that the maximum deviation was around 10% of the NCR capacity. They assumed the same inventory policy for all items and that the items have similar physical and economical characteristics. They also claimed that changes in the above have little effect on the storage capacity. Roll et al. (1989) found a suitable size of a warehouse container and used simulation to find the optimal combination of warehouse capacity and container size. Sung & Han (1992) extended the queuing model of Schwarz et al. (1978) to determine the size of AS/RS for single and multiple item storage scenarios. In the case of single item storage, the AS/RS is treated as an M/M/m/m or M/G/m/m model. For multiple item storage, a single class closed queueing network model is developed to determine the storage size. Both the models were extended to include blocking (when an arriving item does not find a storage space in the rack) and batch arrivals. The important assumption is that the items spend a known but random amount of time at the racks. Cormier & Gunn (1992) formulated the warehouse sizing problem as a cost minimization problem considering inventory policy costs, warehouse construction/operating costs and the cost of leasing for constant product demand (static conditions) for a single period, assuming a continuous review policy without the possibility of backorders. Rao & Rao (1998) presented a modified formulation for warehouse sizing under static and dynamic conditions. They provided three extensions to the static conditions involving 17 varying cost over time, economies of scale in capital expenditure and/or operating cost and stochastic version. The dynamic version of the problem with stochastic demand was shown to be a network flow problem and its concave cost version could be solved efficiently using dynamic programming methods. Huang et al. (2003) simultaneously selected distribution centers and their capacities by solving a 2stage distribution network. They modeled the distribution center as an M/G/c queue where each storage space represents a server. They consider the case of discrete and continuous racks. They also studied the difference between a stepwise approach (site selection and space determination) and the integrated approach. 2.1.3 Integrated Design Methods The warehouse design procedure is a complex process because the number of available design alternatives is large and hence, the choice of a particular design depends on the experience of the designers. Ashayeri & Goetschalckx (1988) presented a systematic planning and designing procedure for orderpicking systems. Their stepwise design procedure consists of nine steps starting with external strategic planning considering market information to selecting operational policies for the order picking system. Gray et al. (1992) proposed a multistage hierarchical decision approach. The approach consists of three levels; facility design and technology selection, item allocation, and operating policy decisions. Each level has a set of mathematical models that evaluates the major tradeoffs to obtain a set of feasible design alternatives. The authors suggest the use of simulation to fine tune the design and operating policies. They applied the methodology successfully to design a spare parts distribution center. Yoon & Sharp (1995, 1996) present a cognitive design procedure for an order picking system (OPS). They present a general framework for the OPS design and analysis that consists of a general structure of the OPS and a conceptual design procedure. The general structure illustrates all the functional areas and material flows (pallets, cases, and items) in an OPS. The conceptual design procedure consists of input, selection and evaluation stages. An alternative design methodology was proposed by McGinnis et al. (2000) based on a functional flow network. The activities are represented as nodes and flows are represented 18 Figure 2.3: A simple highlevel queueing network model of a warehouse as arcs. Once a flow network for a particular configuration of the warehouse is established, the functions are assigned to spaces in the warehouse. Goetschalckx et al. (2002) applied this methodology for a small parts warehousing system. Bodner et al. (2002) developed a process model to assist in the development of computational tools for warehouse design. Many researchers have used simulation to analyze tactical and operational decisions simultaneously. Petersen & Aase (2004) compared picking, storage and routing policies on warehouse throughput. Manzini et al. (2005) used simulation to develop an expert system by performing a comprehensive set of designed experiments. Berg & Gademann (2000) compared control policies like storage location assignment and sequencing together using simulation. Eldemir (2003) suggested two approaches for modeling an integrated system based on queuing network and material flow diagrams. Material flow diagrams are graphical representations of the movement of materials used in a process. They are a useful aid in identifying the source, stages and sink including the quantities and losses at each stage/process. Using a set of standard procedures at the process and routing probabilities after the process, system throughput, and subsystem throughput can be calculated. This approach cannot capture the stochastic nature of the processes in the system. The second approach is modeling the system as a network of queues. The author had modeled individual systems (palletizer, AS/RS, and sortation) with buffer capacities. Eldemir (2003) suggested the use of Jackson network type models or Queueing Network Analyzer (QNA) based models proposed by Whitt (1983). An example of such a system model is presented in Figure 2.3. 19 Jackson network assumes exponential service times and Poisson arrivals. In addition, the extensions for multiple classes assume that the service time is the same for all the classes, which severely restricts the model use. QNA provides a more flexible framework for modeling such a system. Our approach is based on the parametricdecomposition approach presented by Whitt (1983). In the queueing network approach suggested by Eldemir (2003), the storage rack configuration is modeled implicitly in the service time of the S/R machines operating in a single or dual command mode. Other authors who explicitly consider the rack and the storage process, assume that each rack space/bay as a server (Huang et al. (2003)) or the rack as a queue space. The disadvantage of the first approach is that the service time of the racks is not known or can only be assumed. Some retail warehouses are very large with thousands of bays effectively modifying the rack to be an infinite server. In the case where rack is treated as a queue space, the potentially large queue space will tend to behave like an infinite queue. 2.2 Review of ProductionInventory Models General queueing network models are readily applicable for maketoorder systems, where the only inventory is the workinprocess due to the parts waiting to be processed. In maketostock systems, finished goods and intermediate items are produced and stored in anticipation of customer demand. The demand is satisfied immediately reducing the overall waiting time of the customer. Such holding of both finished goods and intermediate parts in anticipation of demand is called planned inventory. In addition to providing better customer service, the planned inventories act as a buffer against uncertainties like machine failure. Some of the relevant literature in productioninventory networks includes Buzacott & Shantikumar (1993), Lee and Zipkin (1992), Sivaramakrishnan & Kamath (1997), Sivaramakrishnan (1998) and Zipkin (1995). A review of the relevant work is presented in the following paragraphs. Consider an Mstage productioninventory model as shown in Figure 2.4. Each stage is represented by a queueserveroutput store. Each stage operates under a basestock 20 Figure 2.4: Mstage ProductionInventory model policy. The base stock level is the maximum planned inventory at the output a stage. The demand process, occurring at the Mth stage is assumed to be a renewal process and for one unit at any given time. If a finished item is available, the order is fulfilled immediately and a replenishment order is placed at stage M − 1. Such a policy is called a oneforone replenishment policy. If the item is not available, the demand is backordered. The inventory is replenished until the base stock level is reached. The replenishment order at stage M − 1 looks at the output store of that stage. If a part is available, it immediately moves to the processing queue of stage M and an upstream replenishment order is placed else it is backordered. In the first stage, orders join the processing queue immediately. Unlimited supply of raw material is assumed at stage 1. In all the stages, a backorder is fulfilled first before the planned inventory is replenished. In the oneforone replenishment policy, the demand arrivals are reflected at all the stages of the network. Hybrids of maketoorder and maketostock systems can be analyzed by constraining some of the basestock levels to be zero. Lee and Zipkin (1992) modeled such a tandem production line with Poisson arrivals and exponential service times. They modeled each stage as an M/M/1 queue and applied the approximations of Svoronos & Zipkin (1991) for a multiechelon inventory system. Zipkin (1995) extended these results to tandem queues with feedback. Single stage maketostock systems were studied extensively by Buzacott & Shantikumar (1993). They modeled such systems using the ProductionAuthorization (PA) card concept. When each item in the manufacturing facility is produced, a tag is associated with the item. When the demand consumes an item in the output store, the tag is removed and is converted into a ProductionAuthorization card. They vary the rules governing the transmission of 21 PA cards to authorize production. The variations are a) immediate transmittal of PA cards into the facility as soon as it is generated, b) fixed batch of PA cards, say q, when at least q PA cards are accumulated, and c) all the PA cards when at least q PA cards are accumulated. These variations represent the oneforone replenishment base stock policy, reorder point/order quantity and reorder point/order up to inventory policies, respectively. Buzacott & Shantikumar (1993) modeled single stage systems with unit demand, bulk demand, and interruptible demand, backlogging and lost sales, yield loses and multiple classes of customers. Sivaramakrishnan & Kamath (1997) analyzed multistage tandem maketostock systems using a node decomposition approach. Each stage in the model had a delay node that captured the effects of backorder delay. A processed item at each stage would satisfy any backorders in that stage or replenish the inventory. The output store in each stage was controlled by a base stock policy with oneforone replenishment. Using the parametricdecomposition approach (Whitt, 1983), Sivaramakrishnan (1998) extended the results to include general arrivals and service times, multiple servers, batch service, limited raw material supply, multiple classes, service interruptions and feedback. Feed forward networks were also considered. Liu et al. (2004) modeled a similar tandem network with a basestock policy and onefor one replenishment. The difference with the Liu et al. (2004) is in modeling the departure process from the output store of a stage. In each stage, the input buffer consists of two queues; material queue (orders for which material was available at the output store of the previous stage) and backorder queue (orders for which material was not available at the output store). In general, some of the performance measures considered were expected inventory levels at the finished goods stores, average workinprocess, fill rate and average number of backorders. Dong & Chen (2005) developed an approximate model for a (q, S) inventory policy for a single stage system. They adopted the target level PA cards mechanism with fixed lot size model in Buzacott & Shantikumar (1993). They used the GIX/G/1 model, where X is the fixed batch size q. They transform the bulk arrival queue into an equivalent GI/G/1 queue by modifying the service time to obtain performance measures similar to Buzacott 22 & Shantikumar (1993). Srivathsan (2005) developed productioninventory models of supply chain networks. He developed models for convergent (two suppliers, supplying a manufacturer) and divergent (one manufacturer supplying two retailers) aspects of a supply chain. He modeled the lead time/transit time using a delay node and analyzed a larger network with multiple suppliers, manufacturers and retailers. 2.3 Summary In this chapter, we have provided a detailed literature review of the status of performance evaluation models for warehouses and general productioninventory systems. In this context, we note that • Majority of performance evaluation models for warehouses are specific and analyze specific warehouse systems in isolation. A majority of the studies focused on aislebased automated warehouses, while literature on carousel systems and Autonomous Vehicle Storage Retrieval Systems (AVS/RS) are emerging (Fukunari, 2003). One of the main assumptions in the performance evaluation of these systems is that there is always space available for the waiting storage requests and similarly, a customer demand can always be satisfied. Hence, the performance measures and improvements focus more on improving the material handling aspects of the storage and retrieval systems. • New approaches for systems design and evaluation have started emerging such as those based on process modeling techniques but lack the analytical evaluation capability. The current systematic procedures for warehouse design are mostly descriptive with some prescriptive steps where specific optimization models can be applied for evaluating economic tradeoffs. • In the limited applications of queueing or queueing network models to warehouse performance evaluation, only the congestion effects in the warehouse storage systems have been analyzed. In addition, many models assume that the service provided by 23 the storage system is known and can be approximated by the exponential distribution, which in fact may not be realistic. • In general, the models developed do not provide an analysis framework to include valueadded services in the warehouse. In the next chapter, we will discuss the research goals and objectives and the contribution made by this dissertation. 24 Chapter 3 Statement of Research The overall goal of this research was to develop analytical models for warehouse performance evaluation that can simultaneously deal with inventory and capacity/congestion issues. In a warehouse system, the primary storage function of the warehouse and the inbound/ outbound configuration of the unitloads give rise to two important configurations; the sharedserver system and the orderpicking system. The first two objectives in this dissertation can be thought of as focusing on queueinginventory models of these two configurations which are seen as key building blocks of a warehouse system. The final research objective focuses on building a proofofconcept endtoend warehouse system model using these building blocks. 3.1 Research Objectives Research objectives 1 and 2 focus on the development of the sharedserver and orderpicking system respectively while research objective 3 focuses on the development of endtoend models. Objective 1: To develop and investigate the accuracy of an approximate analytical model of the sharedserver system i.e., an inventory store with a server performing both storage and retrieval operations (hence the name, sharedserver). The storage operation increases the inventory level and the retrieval operation decreases the inventory level. The analytical model explicitly considers the presence or absence of items in the inventory store 25 Figure 3.1: A sharedserver system and its size. In this objective, we study the system independent of the rest of the operations in the warehouse and we make the following assumptions. • We assume independent arrivals for the storage/retrieval requests. • The configuration of the unitload is maintained during storage/retrieval operation and the system operates under FCFS discipline. • The server operates in a singlecommand mode and the storage/retrieval operations have identical service time distributions. • The storage request or retrieval request is for a single item. A typical configuration of such a system is illustrated in Figure 3.1. Subobjective 1.1 : The sharedserver is studied under Markovian assumptions – Poisson arrivals for storage/retrieval requests and exponential service times for the S/R machine. Subobjective 1.2 : The Markovian assumption is relaxed and the sharedserver system is modeled under general arrival and service time distributions. Subobjective 1.3 : This objective extends the general model to account for parallel aisles in the storage system with dedicated S/R servers. Warehouses that deal with different unitload configurations (pallets and cases) will have separate storage areas allocated to a particular configuration; reserve storage for pallets 26 Figure 3.2: An orderpicking system and forward storage for cases, in general. Whenever the inventory in the forward area is depleted because of orderpicking, an internal replenishment occurs from the reserve area. In objective 2, our focus is on this forward storage area, where the replenishment orders are in pallet loads and orderpicking is in case loads. Objective 2: To develop and analyze an approximate analytical model for an orderpicking system; a single storage area with a server picking in lessthanunitload quantities (cases) and a separate server replenishing the inventory in unitloads (pallets). A tandem model representing such an orderpicking operation is illustrated in Figure 3.2. We assume unit orderpicking quantity and unit replenishment–order quantity. We also assume that the orderpicker and replenishment server have unit capacity. Subobjective 2.1 : The orderpicking system is studied under general arrivals and general service time distributions for the single server case. Subobjective 2.2 : The model is extended to include multiserver cases. Objective 3: To demonstrate the applicability of the models developed in objectives 1 and 2 as building blocks to develop comprehensive endtoend models of the warehouse system. The proofofconcept system includes a reserve storage area, a forward storage area and a downstream shipping operation. The reserve storage area is modeled using the sharedserver system and the forward storage area is modeled using the orderpicking system. Hence, this objective demonstrates the applicability of models developed in previous objectives in building endtoend warehouse models. 27 3.2 Research Scope and Limitations The scope of this research was limited by the following assumptions. • The analytical models developed are for a single class of customers and the customer demand for storage and retrieval are for unit orderquantity. Also, the servers are assumed to be reliable. • Design characteristics of the storage area such as warehouse layout, zoning (assigning workers to particular sets of aisles), slotting (assigning products to individual bays), and operational characteristics such as order scheduling and order sequencing are not modeled. Orders are mostly satisfied on a FCFS basis. The storage rack is treated as a single inventory location for modeling purposes. • This framework does not model the inventory staggering decisions that have proven to reduce the maximum inventory levels in the warehouse (Hariga & Jackson, 1996). We assume that the capacity of the inventory store is given as the inventory sizing decisions are now made during the design of distribution network itself, which is outside the scope of this research. • Travel time models for the storage systems are abundant and they consider the physical characteristics of the storage racks (squareintime and nonsquareintime) and storage assignment policies. We do not consider such decisions and policies explicitly in this study. In the next chapter, we focus on the development of the sharedserver system in detail. 28 Chapter 4 SharedServer System In this chapter, we focus on the development of an analytical model of a sharedserver system, a key building block for developing endtoend performance evaluation models of a warehouse. We described the activities and the material flow within a typical warehouse in chapter 1. Here, we focus on the sharedserver system, describe our modeling assumptions, and develop an approximate analytical model of the sharedserver. We perform a detailed evaluation of the sharedserver model by comparing its results with equivalent simulation results. We conclude the chapter by discussing how the sharedserver model can be part of an endtoend warehouse model. 4.1 SharedServer System Development A queueinginventory model of a warehouse illustrating a subset of warehouse operations with respect to a single storage area is illustrated in Figure 4.1. From the perspective of process flow, the warehouse operations follow a sequential flow. But from a resource centric view, the queueinginventory model of the same is not necessarily tandem. The distinction comes from the fact that resources are shared between activities/operations. In a traditional productioninventory model of manufacturing system, such as the one shown in Figure 4.2(a), each resource/processing unit has its own output store. When a demand consumes an inventory at the output store of stage 2, it triggers a replenishment order immediately. This order then looks for a part at the output store of stage 1, and if available 29 (a) Processcentric view of warehouse operations (b) Resourcecentric view of warehouse operations Figure 4.1: Process and resource centric views of warehouse operations goes and waits for processing at stage 2. Parts after processing move to the output store. This process is repeated at each stage. Hence, at each inventory store, parts are put into the store by an upstream machine and parts are retrieved for processing by a downstream machine. In warehouses, material handling resources such as cranes and S/R machines that are assigned to a particular storage area perform both storage and retrieval operations. Hence, the pallets that need to be stored (similar to upstream operation) and the orders that need to be retrieved (similar to downstream operation) share the same resources. We call this resource/server that is shared between storage and retrieval operations as the SharedServer. This chapter of the dissertation focuses on the performance evaluation of the sharedserver system for the single server case and how it can be used as a building block in a comprehensive endtoend model of the warehouse. 4.1.1 Description of the SharedServer System A typical AS/RS consists of multiple parallel aisles, one or more S/R machines that can travel simultaneously in horizontal and vertical directions, and an input/output station. The S/R machine can operate in a single command mode (either storage or retrieval operation in a single cycle) or in a dual command mode (a storage operation and a retrieval operation in the same cycle). There is a buffer in front of the AS/RS where the requests wait in 30 (a) PI model of a tandem manufacturing system (b) PI model of a warehouse rack storage Figure 4.2: ProductionInventory (PI) models of (a) manufacturing system (b) warehouse rack storage a queue to be serviced. It is a physical queue in case of storage requests and a (virtual) information queue, in case of retrieval requests. A sharedserver is representative of AS/RS type of systems. The model consists of a server (S/R machine), separate queues for storage and retrieval requests, and physical inventory store (rack). The following assumptions are made about the sharedserver system. 4.1.2 Assumptions • Storage and retrieval requests arrive independently of each other and join separate queues. The storage requests are say, pallets waiting to be stored and hence, the storage queue has a physical limit because of limited warehouse space. The retrieval requests are information, and hence, the maximum backlog is limited by design decisions. In this dissertation, we assume that both the physical queue and the information queue are finite and are equal in capacity. Similarly, the rack has a finite capacity. Requests that arrive when the storage (request) queue is full will be lost. • The shared server is assumed to operate in a single command mode and follow a first 31 come first served service discipline as long as the request can be serviced. Because of the limited capacity of the rack, the FCFS discipline may be violated. When a storage request arrives before a retrieval request and there is no space in the rack, the request is blocked (storage blocking). The blockage is resolved when the retrieval request is serviced before the storage request. Similar blockage occurs when a retrieval request arrives before a storage request, and there is no item to retrieve (retrieval blocking). • Each request (storage or retrieval) is for a unitload item only and the server can handle only one unitload at a time. The following notation is used in this chapter. −1 S ,C2S  mean and SCV of the interarrival times of storage requests −1 R ,C2R  mean and SCV of the interarrival times of retreival requests μ−1 SC,C2S C  mean and SCV of the service times BS,BR  Queue capacities for storage and retrieval requests respectively Z  Rack size LQ(S),LQ(R)  mean queue length of storage and retrieval requests respectively L(RACK)  average inventory level in the rack −1 dR,C2 dR  mean and SCV of the interdeparture times of retrieval requests The squared coefficient of variation (SCV) of a random variable (rv) is defined as the variance of the rv divided by the square of its mean. We believe that this dissertation effort is the first analytical model of the shared server system where the inventory store or the rack size is explicitly modeled. As is customary with any new performance modeling research, we first model the sharedserver system under the Markovian assumption. 4.2 CTMC Model and Analysis Modeling queues using Continuous Time Markov Chains (CTMC) is a widely used performance evaluation technique because it provides us with an exact method of analysis under exponential assumptions. Algorithms exists to solve the CTMC model and to compute 32 performance measures that can be used to understand system behavior. In our case, we also use the CTMC model to verify the simulation model that is used to evaluate the more general model of the sharedserver system which is the subject of section 4.3. We assume that the single command service time follows an exponential distribution with the service rate (μS = μR) for storage and retrieval requests. The arrivals of storage and retrieval requests are independent of each other and are Poisson processes with mean arrival rates of S and R, respectively. We also assume limits, namely, BS and BR on the capacities of storage and retrieval request queues, respectively. Storage and retrieval arrivals are lost when the queues are full. The state of the system at time t is then defined as, X(t) = {m, i, j, k} where m represents the current mode of the server (0 idle, S serving a storage request, R serving a retrieval request); i, j, k are nonnegative integers representing the number of storage requests waiting in queue, number of retrieval requests waiting in queue and the inventory level in the rack, respectively; 0 i BS, 0 j BR and 0 k Z . The server becomes idle when both the request queues are empty (i = 0, j = 0). The server is blocked when i = 0, j > 0 and k = 0 (retrieval blocking) and when i > 0, j = 0 and k = Z (storage blocking). Figure 4.3 provides examples of system states together with their transitions. In the CTMC model, when the server is capable of servicing either request, as in Figure 4.3(c) we assumed that with a probability pS (= S/( S + R)), the server satisfies a storage request and with a probability pR (= 1−pS), the server satisfies a retrieval request. Using the memoryless property of the exponential distribution, the behavior of the queueing model can be represented as a Continuous Time Markov Chain. The stationary equations are presented in Appendix A.1. The stationary equations were solved numerically using XpressMP (Heipcke, 2000) and compared against simulation estimates. The experimental setup to verify the analytical model is presented in Table 4.1. The arrival rates ( S = R) were set at 1 / time unit and the service times are set such that the utilization 33 (a) state illustrating storage blocking (b) state illustrating retrieval blocking (c) state illustrating a storage operation Figure 4.3: Example statetransitions for the CTMC model of the sharedserver system 34 Parameter Levels (values) Service Times 1 (corresponding to 80% utilization level) Rack Size (Z) 10 (1  10) Buffer Size (BS = BR) BS = BR = Z and BS = BR > Z Number of Servers 1 Table 4.1: Design of experiments for shared server system (Markovian case) of the sharedserver is 0.8. While our model can handle any limit on the queue capacity, in our experiment we present two scenarios; one where the queue capacity is equal to the rack size, and the other where the queue capacity is greater than the rack size. Let Pm,i,j,k be the steadystate probability that CTMC will be in state (m, i, j, k) which we can obtain by solving the balance equations given in Appendix A.1. With the solution of Pm,i,j,k, we can derive some useful performance measures, such as: 1. Utilization of the server P(S/R) = 1 − X k>=0 P0,0,0,k (4.1) 2. Probability of storage blocking P(Storage Blocking) = X i>0 P0,i,0,Z (4.2) 3. Probability of retrieval blocking P(Retrieval Blocking) = X j>0 P0,0,j,0 (4.3) 4. Effective throughput of the server (can be less than the total arrival rate because of lost arrivals and blocking) eff = μSC 0 @1 − 0 @ X k 0 P0,0,0,k + X i>0 P0,i,0,Z + X j>0 P0,0,j,0 1 A 1 A (4.4) 5. Expected number of retrieval requests waiting to be serviced LQ(R) = X j 0 j.Pm,i,j,k (4.5) 35 6. Expected number of storage requests waiting to be serviced LQ(S) = X i 0 i.Pm,i,j,k (4.6) 4.2.1 Numerical Experiments In order to verify the results of the CTMC model, we compare the output of the CTMC model to the performance measure estimates obtained by simulating the sharedserver. In the case of utilization and queue length performance measures, the relative percentage difference is defined as Rel.Diff% = Analytical − Simulation Simulation 100 We present the absolute difference when the quantities involved are small (typically less than 1) (Whitt, 1983). Tables 4.2 and 4.3 summarize the results when the buffer size is equal to the rack size and greater than the rack size, respectively. From the tables, we see that the CTMC model tracks the simulation model closely. The maximum relative percentage difference on the storage (retrieval) queue is 4.84% (4.97%) in the first scenario and 2.53% (2.68%) in the second scenario. In the case of utilization and average inventory level in the rack, the differences are very small, and only absolute differences are reported. The difference between the analytical and simulation model can be explained by the following assumption in the CTMC model. In the CTMC model, when the server is capable of servicing either request, as in Figure 4.3(c) we have assumed that with a probability pS (= S/( S + R), the server satisfies a storage request and with a probability pR (= 1 − pS), the server satisfies a retrieval request. But in the simulation model we enforce the FCFS discipline strictly and the sharedserver services the request that arrived first into the system. The results indicate that the utilization is an increasing function of the rack size and it is less than the expected utilization level of 80%, because of 1) the blocking of requests when the rack is full or empty and 2) the loss of requests, when the storage or retrieval queues are full. The average number of items in the rack was maintained close to half of 36 the rack size, since the arrival rates were same for the storage and retrieval requests. We note that the average inventory level in the rack is the same in both cases, namely, “buffer size = rack size” and “buffer size > rack size”. The above analysis also provides confidence in the simulation model that will be used for evaluation of the approximate analytical model developed in the next section. As the rack size or the queue capacities increase, the CTMC state space grows rapidly and the numerical solution to the balance equations becomes challenging. If both queues have no capacity limits, then we also need to investigate the conditions under which the CTMC will have a steady state. 37 Utilization Storage Queue Retrieval Queue Rack Rack Size (Z) Buffer Size (BS = BR) A S %Diff A S %Diff A S %Diff A S %Diff 1 1 0.500 0.500 0.000 0.374 0.374 0.000 0.374 0.374 0.000 0.500 0.500 0.000 2 2 0.614 0.615 0.001 0.731 0.737 0.006 0.731 0.738 0.007 1.000 1.000 0.000 3 3 0.670 0.671 0.001 1.070 1.093 2.10% 1.070 1.095 2.28% 1.500 1.497 0.003 4 4 0.702 0.704 0.002 1.386 1.430 3.08% 1.386 1.432 3.21% 2.000 1.999 0.001 5 5 0.723 0.725 0.002 1.680 1.746 3.78% 1.680 1.750 4.00% 2.500 2.495 0.005 6 6 0.738 0.740 0.002 1.955 2.040 4.17% 1.955 2.046 4.45% 3.000 2.994 0.006 7 7 0.748 0.750 0.002 2.213 2.317 4.49% 2.213 2.320 4.61% 3.500 3.497 0.003 8 8 0.756 0.757 0.001 2.457 2.573 4.51% 2.457 2.580 4.77% 4.000 3.989 0.011 9 9 0.762 0.763 0.001 2.688 2.821 4.71% 2.688 2.828 4.95% 4.500 4.488 0.012 10 10 0.767 0.767 0.000 2.908 3.056 4.84% 2.908 3.060 4.97% 5.000 4.985 0.015 Table 4.2: Results for the sharedserver CTMC model (BS = BR = Z) = 0.8 and S = R = 1 Utilization Storage Queue Retrieval Queue Rack Rack Size (Z) Buffer Size (BS = BR) A S %Diff A S %Diff A S %Diff A S %Diff 1 2 0.543 0.543 0.000 0.501 0.501 0.000 0.501 0.501 0.000 0.500 0.500 0.000 2 4 0.651 0.650 0.001 0.972 0.965 0.007 0.972 0.966 0.006 1.000 0.999 0.001 3 6 0.698 0.696 0.002 1.388 1.365 1.68% 1.388 1.367 1.54% 1.500 1.499 0.001 4 8 0.724 0.722 0.002 1.753 1.713 2.34% 1.753 1.715 2.22% 2.000 1.999 0.001 5 10 0.740 0.738 0.002 2.078 2.025 2.62% 2.078 2.029 2.41% 2.500 2.497 0.003 6 12 0.751 0.749 0.002 2.369 2.305 2.78% 2.369 2.308 2.64% 3.000 2.999 0.001 7 14 0.759 0.757 0.002 2.634 2.561 2.85% 2.634 2.561 2.85% 3.500 3.501 0.001 8 16 0.764 0.762 0.002 2.880 2.801 2.82% 2.880 2.800 2.86% 4.000 3.996 0.004 9 18 0.769 0.767 0.002 3.110 3.025 2.81% 3.110 3.026 2.78% 4.500 4.489 0.011 10 20 0.772 0.770 0.002 3.328 3.246 2.53% 3.328 3.241 2.68% 5.000 4.993 0.007 Table 4.3: Results for the sharedserver CTMC model (BS = BR > Z) = 0.8 and S = R = 1 38 Figure 4.4: A single stage kanban system (Krishnamurthy, 2002) 4.3 Queueing Network Model of the SharedServer In this section, we present an approximate analytical model of the general sharedserver system. Our modeling and solution approach uses previous work on the parametricdecomposition method (Whitt, 1983) and the modeling of synchronization operations (Krishnamurthy, 2002). The need for modeling synchronization operations can be explained by the observation that for a storage (retrieval) operation to begin a storage (retrieval) request must be waiting and an empty space (item) must be present in the rack. The analytical model presented here is based on the material control model developed for a single stage kanban system by Krishnamurthy (2002). In a kanban controlled production system, kanbans (cards) are used to control material flow and trigger production. In a multi stage production system, each stage has a fixed number of kanbans. A part can be processed at given stage i, if the corresponding stage i kanban is attached to the part. Upon completion of the process, both the finished part and the kanban wait at the output buffer of stage i. The part is transferred to the next stage, stage i+1, as soon as a kanban from stage i+1 is available. The stage i kanban is then returned to the input buffer of stage i enabling new parts to enter stage i. Such a kanban system can be represented as a queueing model using fork/join synchronization stations and is shown in Figure 4.4. A similar material control modeling approach is followed in the development of the approximate analytical model of the sharedserver system. 39 Figure 4.5: Queueing network model of a shared server Figure 4.5 represents a queueing network model of a single class, single sharedserver system. The sharedserver is represented as two independent servers, serving the storage and retrieval requests, at the storage processing (SP) and retrieval processing (RP) stations, respectively. The synchronization stations JS and JR model the material control mechanism at the processing stations. A closed loop system is formed by the sync stations JS and JR and processing stations SP and RP as shown. Associated with this closed loop are Z kanbans which represent the number of rack spaces in the system. Hence, this part of the queueing network model can be viewed as a closed queueing network where the kanbans act as customers, circulating in the network formed by queues EK, SP, RACK and RP. The arrival processes of storage and retrieval requests are external processes that need to be synchronized with the internal flow of the kanbans in the closed loop. The sync station JS models the synchronization of the storage requests (that arrive from the upstream or external processes) with that of kanbans that represent the empty spaces in the rack. JS has two input queues, the storage request queue (BS) and the empty space/kanban queue (EK). The sync station JR models the synchronization of the retrieval requests (that arrive from downstream or external processes) with that of kanbans that represent items in the rack. JR has two input queues, the retrieval request queue (BR) and the rack queue (RACK). The material control model works as follows. Unitload items wait in the queue, RACK, 40 to be retrieved and satisfy a retrieval request. These items in the RACK have a kanban attached to it. As soon as a retrieval request arrives in queue BR, an item from the RACK and the request is joined together and released from the sync station to join the retrieval processing queue. Upon completion of the service (the item was successfully retrieved from the rack), the kanban is returned to the queue EK, that represents the empty spaces in the rack. The queue EK is a part of the storage synchronization station (JS). At this station, when a storage request arrives at the queue BS, it is immediately joined with the kanban in queue EK and sent to the storage processing station (SP) to be stored in the rack. As we can see from the operating mechanism, the kanban cards are either in one of the four queues or at the servers; EK representing empty spaces, SP representing unitloads waiting to be stored and in process, RACK representing unitloads in the rack and RP representing unitloads waiting to be retrieved and in process. Hence, these four queues and the two servers can have a maximum of Z kanbans/customers at any time. The arrival processes at the synchronization stations and service processes at the processing stations are assumed to be general and hence, the queueing network model is a nonproduct form. Therefore, approximation techniques must be used for performance analysis. The solution approach to solving the queueing network consists of four steps and is based on the parametricdecomposition approach (Whitt (1983, 1994); Krishnamurthy (2002)). The two main features of this approach are that the departure and arrival processes within the network are approximated as renewal processes and such a renewal process is described by its first two moments, mean and squared coefficient of variation. In reality, the successive departures or arrivals in the closed queueing network are not independent, and hence not a renewal process. Earlier works on open and closed queueing network models (Kuehn (1979); Whitt (1983); Kamath (1989); Krishnamurthy (2002)) have shown that such an approximation is effective and yields reliable estimates of the desired performance measures without much computational effort. In this solution approach, we extend the application of this technique to solve the sharedserver system model. The approach consists of four steps: Decomposition, Characterization, Linkage, and Solution. An overview of these steps is given below and illustrated in Figure 4.6. 41 Figure 4.6: Overview of parametricdecomposition approach for the queueing network model of the sharedserver 42 • Decomposition: The queueing network representation of the shared server system is decomposed into individual components; storage and retrieval synchronization stations (JS and JR), and storage and retrieval processing stations (SP and RP). • Characterization: Each component/station (JS, SP, JR and RP) obtained from the decomposition step is analyzed in isolation. We assume that the arrival process and the service process (if any) are known and are renewal processes. We also assume that the renewal process is adequately quantified by two parameters; the mean and squared coefficient of variation (SCV) of the interrenewal times. In this queueing network, we know the external arrival processes for storage and retrieval requests, and the single command service process but we do not know the internal departure processes from each of the components. By analyzing the components/stations independent of the rest of the network, we obtain the mean and SCV of the departure process and estimate the performance measures of each of the components. The details of this characterization step, especially the storage and retrieval processing stations are described in detail in the following sections. • Linkage: In this step, the traffic equations from the individual stations are linked together in the closed loop part of the queueing network. We make use of the expressions derived in Krishnamurthy & Suri (2006) that link the traffic processes at the stations (JS and SP, SP and JR, JR and RP, and RP and JS). The resulting sets of nonlinear equations are then solved numerically to obtain the parameters of the internal traffic processes. • Solution: The system of nonlinear equations, linking the traffic processes of the individual components is iteratively solved to determine the internal traffic parameters. Once those parameters are determined, the network performance measures as well as the station performance measures can be obtained easily. 4.3.1 Characterization of the Synchronization Station The decomposition step presents two synchronization stations, storage and retrieval synchronization stations. The storage sync station (JS) consists of two input queues, one for 43 Figure 4.7: Characterization of storage synchronization station (JS) the storage requests that come from upstream stages (BS) and the other for kanbans representing empty storage spaces (EK). The subnetwork SN in Figure 4.7 represents the downstream stages where the Z kanbans circulate. In the queue EK, kanbans representing empty storage spaces wait for the storage requests. Each storage request is then attached with the kanban and they proceed together to be processed, i.e., the storage request and the kanban are routed together in the subnetwork SN. Because the rack has a finite capacity represented by the Z kanbans, the sum of kanbans in queue EK and subnetwork SN will always be equal to Z. Additionally, the arrival process to the queue BS will shutoff as soon as its capacity is reached, which is set at BS. In line with two moment approximations, we assume that the arrival processes to queues EK and BS are renewal processes characterized by the mean and SCV of the interarrival times; −1 S , C2 aS to the queue BS and −1 S,j−1, C2 s,j−1 to the queue EK. There are only Z kanbans circulating in the subnetwork and queue EK, the arrivals to the queue EK shuts off once all the kanbans are in the queue EK. Hence, we really assume that the traffic process conditioned on the event that it is not shutdown is a renewal process. Thus, the synchronization station JS is characterized by the 6tuple ( −1 S ,C2 as,BS, −1 s,j−1,C2 s,j−1,Z). The characterization of JS will be complete when the parameters for the departure process are specified, which were derived by Krishnamurthy (2002). Let r = S/ S,j−1r 1 and C2 = 0.5(C2 aS + C2 s,j−1). The rate of the departure process is given by 44 S,j = 8>< >: S h 1−rZ+BS 1−rZ+BS+1 i h 1 − 0.5(C2 − 1) (1−r)rZ+BS 1−r2(Z+BS)+1 i r < 1 S Z+BS Z+BS+1 1 − 0.5(C2−1) 2(Z+BS)+1 r = 1 (4.7) As we can see from the above expression, for finite values of Z and BS, the rate of the departure process is always less than min( S, S,j−1). The SCV of the departure process is given by (Krishnamurthy, 2002) C2 S,j = " 5 S 5 S + 5 S,j−1 ! C2 S,j−1 + 5 S,j−1 5 S + 5 S,j−1 ! C2 aS # 1 − 1 (Z + BS + 1) − 1 (Z + BS + 1)2 (4.8) The expressions for queue length parameters are (Krishnamurthy, 2002) LBS = 8>< >: S h 1−rZ+BS 1−rZ+BS+1 i h 1 − 0.5(C2 − 1) (1−r)rZ+BS 1−r2(Z+BS)+1 i r < 1 BS 2 BS+1 Z+BS+1 r = 1 (4.9) LEK = 8>< >: S h 1−rZ+BS 1−rZ+BS+1 i h 1 − 0.5(C2 − 1) (1−r)rZ+BS 1−r2(Z+BS)+1 i r < 1 Z2 Z+1 Z+BS+1 r = 1 (4.10) The characterization of the retrieval synchronization station (JR) is very similar to that of storage synchronization station. The station JR is characterized by two queues, the retrieval request queue (BR) and the queue representing the items in storage (RACK). 4.3.2 Characterization of the Processing Station Figure 4.8 shows the storage processing station obtained by the decomposition of the queueing network. The processing station can be any configuration, and in this section we assume a single server storage processing station operating under a FCFS discipline. The subnetwork SN represents the rest of the queueing network in which the Z kanbans circulate. The arrivals to the SP station are the storage requests with kanbans, i.e., each storage request will have a space reserved for it when it joins the queue. Upon completion of the storage processing operation, the kanbans are routed back to the subnetwork SN where they are subject to random delays. In the subnetwork, the kanban stays in the RACK 45 Figure 4.8: Characterization of the Storage Processing station (SP) until it is matched to a retrieval request and the completion of the retrieval operation will release the kanban to the queue EK. Matching a storage request with a kanban in queue EK results in the kanban revisiting the storage processing station. The number of kanbans at the SP station and subnetwork will always be equal to Z and consequently, the arrival process to the SP station shuts off when all the kanbans are in the SP station. The arrival process to the SP station can be fairly complex. Hence, in line with the twomoment approximations, we assume that the arrival process to the SP station is a renewal process conditioned on the event that the arrival shuts off when all the customers are in the station. The arrival process is characterized by the mean and SCV of the interarrival times ( −1 aS,j ,C2 aS,j ). Together with the parameters describing the service process, the SP station can be represented by the 5tuple ( −1 aS,j ,C2 aS,j , μ−1 mSC,C2 mSC,Z). The service times are modified single command cycle times since the SP station and RP station are both serviced by a single shared server. The details of the modification are presented in the next subsection. Meanwhile, we assume that the service times are i.i.d with mean (μ−1 mSC) and SCV (C2 mSC). The characterization of the SP station will be complete with the description of the departure process and the performance measure of interest, namely the mean queue length. By flow conservation principle, the mean of the interdeparture time is given by −1 ds = −1 aS,j (4.11) 46 The estimation of the SCV of the interdeparture times is based on the approximation by Whitt (1983) for a GI/G/1 queue. Let S = S,j/μmSCbe the utilization of the shared server to account for servicing the storage requests. Then, the SCV (C2 ds) is given by C2 dS = (1 − 2 S)C2 aS,j + 2 SC2 mSC (4.12) To obtain the expression for mean queue length of the SP station, we first obtain the expression for mean waiting time (Wq,SP ). Following the approach by Kamath et al. (1988), the approximate mean waiting time is given by Cf Wq(GI/G/1), where Cf is a correction factor and Wq(GI/G/1) is the waiting time in a GI/G/1 queue. Based on the work of Kuehn (1979) and Whitt (1983), the mean waiting time in a GI/G/1 queue is given by Wq = g( S,C2 aS,j ,C2 mSC) C2 aS,j + C2 mSC 2 ! S 1 − S μ−1 mSC (4.13) The above equation assumes that the customers to the queue arrive from an infinite population. The correction factor (Cf) accounts for the finite population of Z kanbans in the closed loop part of the queueing network, and has been derived by Kamath et al. (1988) as, Cf = Z − 1 Z 0 B@1 1 + Wq Z μ−1 mSC 1 CA (4.14) Then, using Little’s law (Little, 1961), we obtain the mean queue length at the storage processing station as Lq,SP = S,j Cf Wq (4.15) Modifying the Single Command Service Time In the characterization of the SP station, we had mentioned that the single command service time was modified. The reason behind this modification is to account for a single server that is shared by the storage processing station (SP) and the retrieval processing station (RP). We model this shared server as two independent servers and then account for the time spent on each other’s activities. The service time spent by the sharedserver in performing the 47 storage activity accounts for the time it spends in performing any retrieval activity before the next storage activity and vice versa. This is similar to the approach used by Segal & Whitt (1989) to model the service interruptions within the QNA framework (Whitt, 1983). To modify the service time for the storage processing station, we assume that the down time is the time spent on performing retrieval operations between two storage operations. Let S and R be arrival rates for storage and retrieval requests, and SC(= 1/μSC) be the mean single command service time for storage/retrieval requests. Let S0 be the random variable representing the modified service time, which is given by S0 = S + X NR R (4.16) where S(R) is the random variable representing original storage (retrieval) time and NR is the random variable representing the number of retrieval operations performed until the next storage operation. The number of retrieval requests completed before servicing another storage request is a modified geometric random variable, whose parameter is the probability of that the next request is a storage request and is given by pS = S/( R + S). P NR R is a random sum of identical random variables R. The mean of the modified single command storage service time is given by E[S0] = E[S] + E[NR] E[R] E[NR] = pS 1−pS E[S] = E[R] = μ−1 SC = SC E[S0] = mSC = SC 1−pS (4.17) The variance of the modified single command storage service time is given by V ar[S0] = V ar[S] + V ar[P NR R] V ar[S0] = V ar[S] + V ar[NR] (E[R])2 + E[NR] V ar[R] V ar[R] = C2S C 2 SC V ar[NR] = pS (1−pS)2 C2 mSC = V ar[S0] 2 mSC (4.18) 48 Since, we assume that the arrival rates for storage and retrieval requests are equal ( S = R), the expressions 4.17 and 4.18 will also apply for modifying the service time for the retrieval requests. We also note that the two independent servers can be ‘active’ at the same time in the queueing network model. The specification of the traffic processes for each of the components/stations and the performance measures of interest complete the characterization step. In the following section, we link the traffic processes of the decomposed components. 4.3.3 Linking the Stations In the characterization step, the parameters describing the input processes to the processing stations and the synchronization stations are assumed to be given, which in fact need to be determined. In this section, we will determine the relationship between the interdeparture times from a station and the interarrival times to a downstream station, thereby explicitly incorporating the effects of shut downs in the arrival process in the closed part of the queueing network. We need to determine the following four linkages (see Figure 4.6). 1. Linking the departure processes of the storage synchronization station (JS) at the arrival process of the storage processing station (SP) 2. Linking the departure process of the storage processing station (SP) with the retrieval synchronization station (JR) 3. Linking the departure processes of the retrieval synchronization station (JR) at the arrival process of the retrieval processing station (RP) 4. Linking the departure process of the retrieval processing station (RP) with the storage synchronization station (JS). Linking the Departure Process from JS to Arrival Process at SP We now describe the procedure to link the mean and SCV of the departure process of the station JS ( −1 S,j and C2 s,j) to the mean and SCV of the arrival process at the SP ( −1 aS,j and C2 as,j) (see Figure 4.9). We note that the parameters of the arrival process to queue 49 Figure 4.9: Linking storage synchronization and storage processing stations Figure 4.10: Linking storage processing and retrieval synchronization stations BS correspond to external demand and hence, the −1 aS , C2 aS and BS are user inputs. The parameters of the interarrival process at SP, mean ( −1 aS,j) and SCV (C2 aS,j) can be equated directly to the parameters of the interdeparture process from JS. In the characterization step, the correction factor incorporates the finite population nature of the closed part of the queueing network and hence, we do not have to modify the parameters of the interarrival process at SP. Then, using flow conservation principle, aS,j = S,j C2 aS,j = C2 S,j (4.19) We can provide a similar argument to link the departure process from the retrieval synchronization station (JR) to the arrival process to the retrieval processing station (RP). 50 Linking the Departure Process from SP to Arrival Process at JR We now describe the procedure to link the mean and SCV of the departure process of the station SP ( −1 ds and C2 ds) to the mean and SCV of the arrival process at the JR ( −1 R,j−1 and C2R ,j−1) (see Figure 4.10). We note that the parameters of the arrival process to queue BR could correspond to external retrieval request arrival process and hence, −1 aR, C2 aR and BR are user inputs to this model. In the characterization step of the synchronization station, the parameters of the arrival process to the queue RACK ( −1 R,j−1 and C2R ,j−1) are not conditioned on the event that the arrival process is shutdown when all the kanbans are in RACK. Hence, we need to incorporate this fact when we link these two stations. Krishnamurthy & Suri (2006) developed a procedure to develop the linkage equations analyzing the arrival point process to the queue RACK. We will describe the procedure next. Let RACK denote the long run proportion of time that arrivals to RACK are shut down. Then, R,j−1 = dS 1− RACK C2R ,j−1 = C2 dS (1− RACK)2 − RACK (1− RACK)2 dS aR 2C2 aR 1+C2 aR (4.20) By the principle of flow conservation, we have −1 R,j = −1 dS . Together, the three equations provide the necessary stochastic transformation required to relate the traffic processes of the stations SP and JR. We assume that parameters of the departure process from the station SP ( −1 dS ,C2 dS) are given and proceed to develop a numerical procedure to find the arrival process to the station JR. We know that the arrival parameters and the size of the queue BR ( −1 aR,C2 aR,BR) are the user inputs. The iterative numerical procedure, based on the bisection search method is given in Algorithm 4.3.1. 51 Algorithm 4.3.1: LinkProcToSync( dS,C2 dS,Z, aR,C2 aR,BR) comment: Links the storage processing station and retrieval synchronization station Initialize: low = 0, high = 1, " while   > " do 8>>>>>>>>>>>>>>>>>>>>>>>< >>>>>>>>>>>>>>>>>>>>>>>: Step1: Set (k) RACK = (low + high)/2 Step2: Compute R,j−1 and C2R ,j−1 Step3: Compute R,j using synchronization characterization equations Step4: Compute = (k) R,j − dS if < −" then low = (k) RACK else if > " then high = (k) RACK In the algorithm 4.3.1, (k) RACK represents the estimate for RACK in the kth iteration. In each iteration, we compute the difference between the estimated throughput ( R,j) and the required throughput ( dS). If the estimated throughput is lower than the required throughput, then we update the interval of the bisection search to increase the value of RACK in the next iteration, and viceversa. The algorithm terminates when the estimate of RACK meets the required tolerance level (") in the throughput. Convergence property of the algorithm is discussed in a later section. Using a similar argument, we can develop a numerical procedure to solve the linkage equations connecting the retrieval processing station (RP) and the storage synchronization station (JS). 4.3.4 Solution Approach The solution step involves solving the set of nonlinear equations linking the traffic process of the individual stations in the closed part of the queueing network. We increase the user input (Z) by one kanban to account for the fact that the two independent servers can be active at the same time in the queueing network model. We initialize the algorithm by first modifying the single command storage (retrieval) processing time using equations 4.16  4.18. Then, we proceed with an initial estimate of 52 parameters for the departure process of one of the four component stations, in our case it is the storage processing station SP. The algorithm then iteratively estimates the internal traffic process parameters, updating the initial estimates until they are consistent with the user inputs. The solution procedure is described in Algorithm 4.3.2. After computing the modified service time parameters for the processing stations, we obtain initial estimates of dS, and C2 dS in step 1 of loop1. As the initial estimates may be inconsistent with each other, we update the value of C2 dS in loop2 for given value of dS. To update C2 dS, we make use of the characterization and linking equations derived in earlier sections, and solve for the traffic parameters for each of the stations sequentially (steps 2.1 to 2.8). Upon solving the SP, we obtain a new value for C2 dS . We repeat this procedure until the difference between the new and old estimates of C2 dS are within the set tolerance limit ("). In step 3, algorithm verifies if these values of dS and C2 dS are consistent with the user input values for the number of kanbans. To do so, we calculate the difference between the user input value (increased by one) and sum of the kanbans at each of the stations including the servers. We update dS using a bisection search approach in step 4, until the difference between current and previous estimates are within a predefined tolerance limit. If the sum of mean queue lengths is more than the number of kanbans, then the current estimate of ds is too high; the bisection search algorithm accordingly updates the interval for the next iteration. At the end of loop1, we would have obtained dS and C2 dS that are consistent with each other, and consistent with user input & modified service times. As a last step, we update the modified service time based on the effective internal arrival process to the processing stations. We repeat the entire procedure starting with step 1, until the difference between the current and previous estimate of the modified service times are within the specified tolerance limits. Once, the algorithm converges, we can obtain the performance measures of interest such as the throughput and mean queue lengths at the various processing and synchronization stations. The average inventory at the rack is the sum of the mean queue lengths of RACK, and mean number of customers at the retrieval processing station. The average number of 53 storage requests waiting to be serviced is the sum of the mean queue length of BS and mean queue length at the storage processing station. The average number of retrieval requests waiting to be serviced is the sum of the mean queue length of BR and mean queue length at the retrieval processing station. 54 Algorithm 4.3.2: SuperSolve( S,C2 aS,BS, R,C2 aR,BR, μSC,C2S C,Z) Modify: No of kanbans Z0 = Z + 1 Compute: Modified single command service time at SP and RP (μmSC,C2 mSC) Initialize: Low = 0,High = min( S, R, μmSC) while  1 > " do 8>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>< >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>: Step1: Let (k) ds = (Low + High)/2, C 2(k) ds = 1.0(say) while  2 > " do 8>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>< >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>: Step2.1: Solve RACK, R,j−1, and C2R ,j−1 using Algorithm 4.3.1 setting dS = (k) dS and C2 dS = C 2(k) dS Step2.2: Calculate R,j ,C2R ,j and Lq,BR and Lq,RACK using the characterization equations Step2.3: Compute input parameters to the retrieval processing station Step2.4: Calculate dR,C2 dR and Lq,RP using the RP characterization equations Step2.5: Solve EK, S,j−1, and C2 S,j−1 using Algorithm 4.3.1 Step2.6: Calculate S,j ,C2 S,j and Lq,BS and Lq,EK using the characterization equations Step2.7: Compute input parameters to the storage processing station Step2.8: Calculate dS,C2 dS and Lq,SP using the SP characterization equations Step2.9: Compute 2 = C 2(k) dS − C2 dS;C 2(k) dS = C2 dS Step3: Compute 1 = Lq,RACK + Lq,RP + R + Lq,EK + Lq,SP + S − Z0 Step4: if 1 < −" then Low = (k) dS else if 1 > " then High = (k) dS 55 4.3.5 Computational Effort and Convergence We note that the number of unknown parameters in this analysis is independent of the number of customers in the closed part of the queueing network model. Both numerical algorithms are based on the bisection search procedure, and it is assumed that the solution lies within the specified intervals. In the Algorithm 4.3.1, bisection search is used to estimate the probability of the shut downs, ( RACK) to the queue RACK and ( EK) to the queue EK. Hence, the interval [0, 1] is sufficient to search for the probabilities. In the case of Algorithm 4.3.2, the bisection search is used to obtain the throughput of the storage processing station consistent with the user input values. We note that the throughput of the system, then must lie within the interval [0, min( aS, aR, μmSC)] where the μmSC is the modified single command service rate at the storage or retrieval processing station. We cannot guarantee a unique solution within this interval or provide a bound on the number of iterations necessary for the model to converge. In all our experiments, the algorithm converged to a solution within a reasonable number of iterations (<20). 4.3.6 Performance Measures and Model Accuracy The performance measures of interest for the shared server model are related to throughput, inventory, and warehouse resources. The performance measures related to the throughput are the throughputs for storage and retrieval requests. Throughput is defined as the number of requests served per unit time. Other measures of interest are the waiting time and average number of storage and retrieval requests in the system. With respect to inventory, average number of items in storage is a measure of interest. With respect to resources, utilization is the major performance measure. In the following sections, we summarize the results for the throughput for retrieval requests, utilization of the shared server, the mean queue length of the storage & retrieval queues, and the average inventory level in the rack. The accuracy of the models is tested by comparing the analytical results with simulation estimates. The simulation models were developed for the sharedserver component using the Arena simulation software (Kelton et al., 2002). The steady state estimate of a performance 56 measure was obtained by averaging over appropriate number of replications after accounting for warmup periods. The warmup period was estimated using Welch’s method (Welch, 1983) and set at 400,000 entities. The statistics were collected for 600,000 entities (retreival requests) and the performance measures were averaged for 10 replications. The relative percentage error (RE), a common measure to test the accuracy of analytical models, was used in the case of throughput ( dR) and utilization ( SC). When the magnitude of the performance measures is small (typically less than 1), absolute error is considered better than RE (Whitt, 1983). RE( dR) = 100 (Analytical) dR − (Simulation) dR (Simulation) dR In the case of mean queue lengths and average inventory in the rack, normalized error is measured rather than relative percentage error. The normalized error is measured as the difference between the analytical and simulation model as a percentage of the rack size. Since the shared server system is modeled as a queueing network, the normalized error (NE) is measured as NE(LQ(S)) = 100 LQ(S)(Analytical) − LQ(S)(Simulation) Rack Size NE(LQ(R)) = 100 LQ(R)(Analytical) − LQ(R)(Simulation) Rack Size NE(L(RACK)) = 100 L(RACK)(Analytical) − L(RACK)(Simulation) Rack Size The normalized error is used for measuring queue length accuracy in order to avoid the small queue length effect. Robustness of the analytical models will be tested by varying the parameters of the interarrival time distributions for storage/retrieval requests, service time distribution, and rack size. The performance measures will be examined under low (SCV = 0.5), medium (SCV = 1) and high variability (SCV = 2) conditions. An experimental design is provided in Table 4.4 for the sharedserver model. The arrival rates for the storage and retrieval requests are fixed at one, and the mean service times are 57 Parameter Levels (values) Service Times 3 (corresponding to 70%, 80% and 90% utilization levels) SCV of service time distribution 3 (0.5, 1.0 and 2.0) SCV of interarrival time distribution 3 (0.5, 1.0 and 2.0) Rack Size 3 (5, 25 and 125) Number of servers 1 Table 4.4: Design of experiments for sharedserver system: single server case set such that the expected utilization of the shared server is 70%, 80% and 90%. 4.3.7 Accuracy of the SharedServer Model The input parameters to the queueing model are the arrival parameters of the storage and retrieval requests, the service parameters of the single command service time, the queue capacities and the rack size. The output parameters, namely the performance measures of interest are the mean queue lengths of the storage and retrieval requests, the throughput (which is the departure rate of the retrieval requests) and average inventory in the rack. In the case of the sharedserver system, we are also interested in measuring the parameters of the departure process of the retrieval requests as they will become the inputs to the downstream stations in an endtoend comprehensive model of the warehouse. In all our experiments in this section, the sharedserver is a single server operating under a FCFS discipline. We also study the sharedserver system when the variability in the arrival processes is the same (balanced case) and when the variability is different (unbalanced case). Balanced Case In the balanced case, the storage and retrieval processes have the same arrival rate and variability. The estimates of mean queue length (storage and retrieval requests) and the average inventory level in the rack at 70%, 80% and 90% expected utilization for the balanced case are given in Tables 4.5, 4.7, and 4.9 respectively. The estimates of throughput and utilization of the sharedserver are reported in Tables 4.6, 4.8, and 4.10 for the three expected utilization levels. The results from Tables 4.5, 4.7, and 4.9 indicate that the maximum absolute error for the mean queue length of storage (retrieval) request is 5.84% (5.83%). 58 The maximum absolute error for the average inventory in the rack is 3.95%. We note that the above errors are found at the 90% expected utilization levels. In the case of throughput and actual utilization, the maximum absolute error is 13.84% for 90% utilization levels. The observed error percentages are in the range of good to acceptable for queueing models based on two moment approximations as noted in many previous studies (e.g. Whitt, 1983 and Suri et al., 1993). Next, we develop insights into the behavior of the sharedserver model for the balanced system. 59 Storage Queue Retrieval Queue Average Inventory C2 aS = C2 aR C2S C Rack Size A S %E A S %E A S %E 0.5 0.5 5 0.526 0.387 2.79% 0.527 0.387 2.79% 2.416 2.499 1.65% 0.5 0.5 25 1.220 0.781 1.76% 1.220 0.786 1.74% 12.317 12.474 0.63% 0.5 0.5 125 2.438 2.296 0.11% 2.438 2.252 0.15% 62.300 62.915 0.49% 0.5 1 5 0.595 0.471 2.48% 0.595 0.472 2.47% 2.423 2.499 1.53% 0.5 1 25 1.414 0.928 1.95% 1.414 0.932 1.93% 12.318 12.481 0.65% 0.5 1 125 2.682 2.451 0.18% 2.682 2.402 0.22% 62.293 62.894 0.48% 0.5 2 5 0.713 0.581 2.64% 0.713 0.581 2.65% 2.434 2.499 1.31% 0.5 2 25 1.786 1.217 2.28% 1.787 1.218 2.27% 12.321 12.497 0.70% 0.5 2 125 3.166 2.717 0.36% 3.166 2.691 0.38% 62.298 62.870 0.46% 1 0.5 5 0.547 0.475 1.45% 0.548 0.475 1.45% 2.424 2.497 1.46% 1 0.5 25 1.340 1.030 1.24% 1.340 1.030 1.24% 12.319 12.472 0.61% 1 0.5 125 2.600 2.606 0.00% 2.600 2.676 0.06% 62.291 62.631 0.27% 1 1 5 0.611 0.534 1.53% 0.611 0.535 1.52% 2.430 2.498 1.36% 1 1 25 1.888 1.178 2.84% 1.888 1.178 2.84% 12.321 12.469 0.59% 1 1 125 2.841 2.776 0.05% 2.841 2.833 0.01% 62.296 62.646 0.28% 1 2 5 0.721 0.611 2.20% 0.721 0.612 2.18% 2.440 2.497 1.14% 1 2 25 1.888 1.457 1.72% 1.888 1.457 1.72% 12.321 12.474 0.61% 1 2 125 3.321 3.091 0.18% 3.321 3.137 0.15% 62.298 62.569 0.22% 2 0.5 5 0.580 0.560 0.40% 0.580 0.560 0.41% 2.439 2.498 1.18% 2 0.5 25 1.559 1.354 0.82% 1.560 1.357 0.81% 12.325 12.496 0.68% 2 0.5 125 2.909 2.993 0.07% 2.909 2.999 0.07% 62.318 62.883 0.45% 2 1 5 0.635 0.602 0.66% 0.635 0.603 0.65% 2.444 2.498 1.08% 2 1 25 1.740 1.506 0.94% 1.740 1.508 0.93% 12.324 12.491 0.67% 2 1 125 3.153 3.182 0.02% 3.153 3.179 0.02% 62.299 62.906 0.49% 2 2 5 0.733 0.655 1.55% 0.733 0.654 1.57% 2.453 2.502 0.99% 2 2 25 2.083 1.776 1.23% 2.083 1.761 1.29% 12.327 12.614 1.15% 2 2 125 3.633 3.596 0.03% 3.633 3.481 0.12% 62.302 63.030 0.58% Table 4.5: Comparison of mean queue lengths (storage and retrieval requests) and average inventory level in the rack for S = R = 1 and 70% expected utilization (A: Analytical, S: Simulation) 60 Utilization Throughput SCV C2 aS = C2 aR C2S C Rack Size A S %E A S %E A 0.5 0.5 5 0.584 0.647 9.72% 0.835 0.924 9.71% 0.452 0.5 0.5 25 0.683 0.689 0.87% 0.976 0.985 0.97% 0.543 0.5 0.5 125 0.697 0.697 0.06% 0.996 0.997 0.07% 0.556 0.5 1 5 0.578 0.642 10.00% 0.826 0.917 10.02% 0.567 0.5 1 25 0.682 0.689 1.03% 0.974 0.985 1.13% 0.686 0.5 1 125 0.697 0.697 0.04% 0.996 0.997 0.09% 0.704 0.5 2 5 0.567 0.629 9.94% 0.890 0.899 1.00% 0.793 0.5 2 25 0.680 0.689 1.36% 0.971 0.984 1.36% 0.971 0.5 2 125 0.697 0.698 0.14% 0.996 0.997 0.12% 1.007 1 0.5 5 0.576 0.602 4.25% 0.823 0.860 4.24% 0.544 1 0.5 25 0.681 0.679 0.28% 0.973 0.971 0.19% 0.654 1 0.5 125 0.697 0.695 0.29% 0.996 0.994 0.18% 0.667 1 1 5 0.571 0.597 4.42% 0.815 0.853 4.39% 0.656 1 1 25 0.678 0.679 0.22% 0.968 0.971 0.31% 1.080 1 1 125 0.697 0.695 0.27% 0.996 0.994 0.16% 0.815 1 2 5 0.560 0.585 4.26% 0.800 0.838 4.47% 0.878 1 2 25 0.678 0.678 0.07% 0.968 0.969 0.11% 1.080 1 2 125 0.697 0.696 0.10% 0.995 0.994 0.13% 1.111 2 0.5 5 0.562 0.541 3.79% 0.802 0.773 3.71% 0.739 2 0.5 25 0.677 0.662 2.22% 0.967 0.946 2.18% 0.884 2 0.5 125 0.696 0.692 0.64% 0.995 0.989 0.57% 0.890 2 1 5 0.557 0.536 3.82% 0.795 0.766 3.83% 0.847 2 1 25 0.676 0.661 2.19% 0.965 0.945 2.11% 1.024 2 1 125 0.696 0.692 0.61% 0.995 0.989 0.55% 1.038 2 2 5 0.547 0.526 4.05% 0.782 0.751 4.07% 1.060 2 2 25 0.673 0.658 2.33% 0.962 0.941 2.25% 1.307 2 2 125 0.696 0.692 0.58% 0.994 0.988 0.62% 1.334 Table 4.6: Comparison of utilization and throughput of the shared server for S = R = 1 and 70% expected utilization (A: Analytical, S: Simulation) 61 Storage Queue Retrieval Queue Average Inventory C2 aS = C2 aR C2S C Rack Size A S %E A S %E A S %E 0.5 0.5 5 0.688 0.550 2.76% 0.688 0.550 2.77% 2.354 2.499 2.90% 0.5 0.5 25 1.907 1.122 3.14% 1.907 1.126 3.12% 12.223 12.474 1.00% 0.5 0.5 125 3.373 2.683 0.55% 3.373 2.639 0.59% 62.190 62.921 0.59% 0.5 1 5 0.775 0.655 2.41% 0.776 0.655 2.41% 2.363 2.499 2.72% 0 



A 

B 

C 

D 

E 

F 

I 

J 

K 

L 

O 

P 

R 

S 

T 

U 

V 

W 


