UUnniivveerrssiittyy ooff TTeennnneesssseeee,, KKnnooxxvviillllee TTRRAACCEE:: TTeennnneesssseeee RReesseeaarrcchh aanndd CCrreeaattiivvee EExxcchhaannggee Doctoral Dissertations Graduate School 8-2007 AApppprrooxxiimmaattiioonn MMeetthhooddss ffoorr tthhee SSttaannddaarrdd DDeevviiaattiioonn ooff FFllooww TTiimmeess iinn tthhee GG//GG//ss QQuueeuuee Xiaofeng Zhao University of Tennessee - Knoxville Follow this and additional works at: https://trace.tennessee.edu/utk_graddiss Part of the Management Sciences and Quantitative Methods Commons RReeccoommmmeennddeedd CCiittaattiioonn Zhao, Xiaofeng, "Approximation Methods for the Standard Deviation of Flow Times in the G/G/s Queue. " PhD diss., University of Tennessee, 2007. https://trace.tennessee.edu/utk_graddiss/187 This Dissertation is brought to you for free and open access by the Graduate School at TRACE: Tennessee Research and Creative Exchange. It has been accepted for inclusion in Doctoral Dissertations by an authorized administrator of TRACE: Tennessee Research and Creative Exchange. For more information, please contact [email protected]. To the Graduate Council: I am submitting herewith a dissertation written by Xiaofeng Zhao entitled "Approximation Methods for the Standard Deviation of Flow Times in the G/G/s Queue." I have examined the final electronic copy of this dissertation for form and content and recommend that it be accepted in partial fulfillment of the requirements for the degree of Doctor of Philosophy, with a major in Management Science. Kenneth C. Gilbert, Major Professor We have read this dissertation and recommend its acceptance: Mandyam M. Srinivasan, Melissa R. Bowers, Funda Sahin Accepted for the Council: Carolyn R. Hodges Vice Provost and Dean of the Graduate School (Original signatures are on file with official student records.) To the Graduate Council: I am submitting herewith a dissertation written by Xiaofeng Zhao entitled “Approximation Methods for the Standard Deviation of Flow Times in the G/G/s Queue”. I have examined the final electronic copy of this dissertation for form and content and recommend that it be accepted in partial fulfillment of the requirements for the degree of Doctor of Philosophy, with a major in Management Science. Kenneth C. Gilbert Major Professor We have read this dissertation and recommend its acceptance: Mandyam M. Srinivasan Melissa R. Bowers Funda Sahin Accepted for the Council: Carolyn R. Hodges Vice Provost and Dean of the Graduate School (Original signatures are on file with official student records.) APPROXIMATION METHODS FOR THE STANDARD DEVIATION OF FLOW TIMES IN THE G/G/s QUEUE A Dissertation Presented for the Doctor of Philosophy Degree The University of Tennessee, Knoxville Xiaofeng Zhao August 2007 Copyright © 2007 by Xiaofeng Zhao All rights reserved ii Dedication To my parents Yurong Zhang and Hongyi Zhao For their unconditional support, encouragement, and love iii Acknowledgement There are many individuals to whom I owe much gratitude. My deepest thanks go to my advisor and dissertation committee chair Dr. Kenneth Gilbert, who has endured copious discussions on how to approach this topic and waded through numerous iterations of this dissertation, aiming for the highest degree of lucidity. He has always been generous with his time, expertise and enthusiasm. He has taught me so much on how to do research. Without his guidance, insight and commitment, completing this dissertation would not have been possible. I would also like to express my appreciation to the other members of my dissertation committee: Dr. Mandyam Srinivasan, Dr. Melissa Bowers, and Dr. Funda Sahin, who give generosity of their time and expertise to help me refine and focus on my research, greatly strengthening it. I will always be grateful for the opportunity to study and work with all faculty, staff and fellow students at the College of Business, who teach me and demonstrate a true commitment to quality education. A special thank you is due to Dr. Frank Guess for his invaluable support and indefatigable positive attitude. He has taught me so much on how to become an excellent scholar. I would also like to thank Dr. Russell Zaretzki for his helpful discussions and comments, Ms. Amber Clay for helping me learn the simulation software. In particular, I would like to thank Ms. Jane Moser, who helps me so much to make my journey at University of Tennessee a pleasant and wonderful one. My wife and son deserve special recognition for encouraging my education. I owe a large debt of gratitude to them for their patience, understanding, and never-ending support. Last but certainly not the least, I deeply thank my parents and my sister’s family. Although this dissertation is still very foreign to them, they are constantly stressing the importance of education and unconditionally supporting my pursuit of higher goals. iv Abstract We provide approximation methods for the standard deviation of flow time in system for a general multi-server queue with infinite waiting capacity (G/G/s). The approximations require only the mean and standard deviation or the coefficient of variation of the inter-arrival and service time distributions, and the number of servers. These approximations are simple enough to be implemented in manual or spreadsheet calculations, but in comparisons to Monte Carlo simulations have proven to give good approximations (within±10%) for cases in which the coefficients of variation for the inter- arrival and service times are between 0 and 1. The approximations also have the desirable properties of being exact for the specific case of Markov queue model M /M /s, as well as some imbedded Markov queuing models (E /M /1andM /E /1). k α The practical significance of this research is that (1) many real world queuing problems involve the G/G/squeuing systems, and (2) predicting the range of variation of the time in the system (rather than just the average) is needed for decision making. For example, one job shop facility with which the authors have worked, guarantees its customers a nine day turnaround time and must determine the minimum number of machines of each type required to achieve nine days as a “worst case” time in the system. In many systems, the “worst case” value of flow time is very relevant because it represents the lead time that can safely be promised to customers. To estimate this we need both the average and standard deviation of the time in system. The usefulness of our results stems from the fact that they are computationally simple and thus provide quick approximations without resorting to complex numerical techniques or Monte Carlo simulations. While many accurate approximations for the G/G/squeue have been proposed previously, they often result in algebraically intractable expressions. This hinders attempts to derive closed-form solutions to the decision variables incorporated in optimization models, and inevitably leads to the use of complex numeric methods. Furthermore, actual application of many of these approximations often requires specification of the actual distributions of the inter-arrival time and the service time. Also, these results have tended to focus on delay probabilities and v average waiting time, and do not provide a means of estimating the standard deviation of the time in the system. We also extend the approximations to computing the standard deviation of flow times of each priority class in the G/G/spriority queues and compare the results to those obtained via Monte Carlo simulations. These simulation experiments reveal good approximations for all priority classes with the exception of the lowest priority class in queuing systems with high utilization. In addition, we use the approximations to estimate the average and the standard deviation of the total flow time through queuing networks and have validated these results via Monte Carlo Simulations. The primary theoretical contributions of this work are the derivations of an original expression for the coefficient of variation of waiting time in the G/G/s queue, which holds exactly for G/M /sand M /G/1 queues. We also do some error sensitivity analysis of the formula and develop interpolation models to calculate the probability of waiting, since we need to estimate the probability of waiting for the G/G/squeue to calculate the coefficient of variation of waiting time. Technically we develop a general queuing system performance predictor, which can be used to estimate all kinds of performances for any steady state, infinite queues. We intend to make available a user friendly predictor for implementing our approximation methods. The advantages of these models are that they make no assumptions about distribution of inter-arrival time and service time. Our techniques generalize the previously developed approximations and can also be used in queuing networks and priority queues. Hopefully our approximation methods will be beneficial to those practitioners who like simple and quick practical answers to their multi-server queuing systems. Key words and Phrases: Queuing System, Standard Deviation, Waiting Time, Stochastic Process, Heuristics,G/G/s, Approximation Methods, Priority Queue, and Queuing Networks. vi Contents 1 Introduction and motivation 1 1.1 Introduction.......................................................................................................................1 1.2 Motivation.........................................................................................................................4 2 Literature review 7 3 Theory basics and assumptions 11 3.1 Queuing system basics....................................................................................................12 3.2 Stochastic process and Markov chains............................................................................15 3.3 Research design and methodology..................................................................................17 4 Exact Methods for Markov queue and some imbedded Markov queues 19 4.1 Formulae for coefficient of variation of waiting time.....................................................19 4.1.1 Exact formula for M /M /1 ,M /M /s queue ................................................19 4.1.2 Exact formula for G/M /s. queue....................................................................31 4.1.3 Exact formula for M /G/1 queue......................................................................36 4.2 Exact formulae for the probability of waiting..................................................................38 5 Heuristic approximation methods for G/G/s queue 41 5.1 Basics and assumptions for G/G/s queue...................................................................41 5.2 Average waiting time for G/G/squeue.......................................................................43 5.3 Coefficien of variation of waiting time for G/G/squeue............................................45 5.4 Interpolation methods for the probability of waiting in G/G/s queue........................50 6 Priority queues and queuing networks for G/G/s queue 55 6.1 Priority queues................................................................................................................55 6.2 Queuing networks...........................................................................................................61 7 Simulations 65 7.1 Test the accuracy of the approximation by simulation....................................................65 7.2 Approach for using simulation........................................................................................66 7.3 Results analysis...............................................................................................................70 8 Summary 76 8.1 Contributions to knowledge............................................................................................76 8.2 Limitations and future directions....................................................................................78 vii