Doctoral Dissertations

Date of Award

8-2007

Degree Type

Dissertation

Degree Name

Doctor of Philosophy

Major

Management Science

Major Professor

Kenneth C. Gilbert

Committee Members

Mandyam M. Srinivasan, Melissa R. Bowers, Funda Sahin

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 interarrival 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 ( Ek / M / 1 and M / Eα / 1).

The practical significance of this research is that (1) many real world queuing problems involve the G / G / s queuing 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 / s queue 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 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 / s priority 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 / s and 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 / s queue 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.

Download
Files over 3MB may be slow to open. For best results, right-click and select "save as..."

Share

COinS