Thesis (Ph.D.)--Massachusetts Institute of Technology, Alfred P. Sloan School of Management, 1982. / MICROFICHE COPY AVAILABLE IN ARCHIVES AND DEWEY. / Bibliography: leaves 184-189. / by Samuel Shin-Wai Chiu. / Ph.D.

Many systems in services, manufacturing, and technology, feature users or customers sharing a limited number of resources, and which suffer some form of congestion when the number of users exceeds the number of resources. In such settings, queueing models are a common tool for describing the dynamics of the system and quantifying the congestion that results from the aggregated effects of individuals joining and leaving the system. Additionally, the customers themselves may be sensitive to congestion and react to the performance of the system, creating feedback and interaction between individual customer behavior and aggregate system dynamics.This dissertation focuses on the modeling and performance of service systems with congestion-sensitive customers using large-scale asymptotic analyses of queueing models. This work extends the theoretical literature on congestion-sensitive customers in queues in the settings of service differentiation and observational learning and abandonment. Chapter 2 considers the problem of a service provider facing a heterogeneous market of customers who differ based on their value for service and delay sensitivity. The service provider seeks to find the revenue maximizing level of service differentiation (offering different price-delay combinations). We show that the optimal policy places the system in heavy traffic, but at substantially different levels of congestion depending on the degree of service differentiation. Moreover, in a differentiated offering, the level of congestion will vary substantially between service classes. Chapter 3 presents a new model of customer abandonment in which congestion-sensitive customers observe the queue length, but do not know the service rate. Instead, they join the queue and observe their progress in order to estimate their wait times and make abandonment decisions. We show that an overloaded queue with observational learning and abandonment stabilizes at a queue length whose scale depends on the tail of the service time distribution. Methodologically, our asymptotic approach leverages stochastic limit theory to provide simple and intuitive results for optimizing or characterizing system performance. In particular, we use the analysis of deterministic fluid-type queues to provide a first-order characterization of the stochastic system dynamics, which is demonstrated by the convergence of the stochastic system to the fluid model. This also allows us to crisply illustrate and quantify the relative contributions of system or customer characteristics to overall system performance.

This thesis develops techniques to evaluate and to improve the performance of single-server service systems with time-varying arrivals. The performance measures considered are the time-varying expected length of the queue and the expected customer waiting time. Time varying arrival rates are considered because they often occur in service systems. For example, arrival rates often vary significantly over the hours of each day and over the days of each week. Stochastic textbook methods do not apply to models with time-varying arrival rates. Hence new techniques are needed to provide high quality of service when stationary steady-state analysis is not appropriate. In contrast to the extensive recent literature on many-server queues with time-varying arrival rates, we focus on single-server queues with time-varying arrival rates. Single-server queues arise in real applications where there is no flexibility in the number of service facilities (servers). Different analysis techniques are required for single-server queues, because the two kinds of models exhibit very different performance. Many-server models are more tractable because methods for highly tractable infinite-server models can be applied. In contrast, single-server models are more complicated because it takes a long time to respond to a build up of workload when there is only one server. The thesis is divided into two parts: simulation algorithms for performance evaluation and service-rate controls for performance stabilization. The first part of the thesis develops algorithms to efficiently simulate the single-server time-varying queue. For the generality considered, no explicit mathematical formulas are available for calculating performance measures, so simulation experiments are needed to calculate and evaluate system performance. Efficient algorithms for both standard simulation and rare-event simulation are developed. The second part of the thesis develops service-rate controls to stabilize performance in the time-varying single-server queue. The performance stabilization problem aims to minimize fluctuations in mean waiting times for customers coming at different times even though the arrival rate is time-varying. A new service rate control is developed, where the service rate at each time is a function of the arrival rate function. We show that a specific service rate control can be found to stabilize performance. In turn, that service rate control can be used to provide guidance for real applications on optimal changes in staffing, processing speed or machine power status over time. Both the simulation experiments to evaluate performance of alternative service-rate controls and the simulation search algorithm to find the best parameters for a damped time-lag service-rate control are based on efficient performance evaluation algorithms in the first part of the thesis. In Chapter Two, we present an efficient algorithm to simulate a general non-Poisson non-stationary point process. The general point process can be represented as a time transformation of a rate-one base process and by exploiting a table of the inverse cumulative arrival rate function outside of simulation, we can efficiently convert the simulated rate-one process into the simulated general point process. The simulation experiments can be conducted in linear time subject to small error bounds. Then we can apply this efficient algorithm to generate the arrival process, the service process and thus to calculate performance measures for the G_t/G_t/1 queues, which are single-server queues with time-varying arrival rates and service rates. Service models are constructed for this purpose where time-varying service rates are specified separately from the rate-one service requirement process, and service times are determined by equating service requirements with integrals of service rates over a time period equal to the service time. In Chapter Three, we develop rare-event simulation algorithms in periodic GI_t/GI/1 queues and further in GI_t/GI_t/1 queues to estimate probabilities of rare but important events as a sanity check of the system, for example, estimating the probability that the waiting time is very long. Importance sampling, specifically exponential tilting, is required to estimate rare-event probabilities because in standard simulation, the number of experiments may blow up to achieve a targeted relative error and for each experiment, it may take a very long time to determine that the rare event does not happen. To extend the rare-event simulation algorithm to periodic queues, we derive a convenient expression for the periodic steady-state virtual waiting time. We apply this expression to establish bounds between the periodic workload and the steady-state workload in stationary queues, so that we can prove that the exponential tilting algorithm with the same parameter efficient in stationary queues is efficient in the periodic setting as well, which has a bounded relative error. We apply this algorithm to compute the periodic steady-state distribution of reflected periodic Brownian motion with support of a heavy-traffic limit theorem and to calculate the periodic steady-state distribution and moments of the virtual waiting time. This algorithm's advantage in calculating these distributions and moments is that it can directly estimate them at a specific position of the cycle without simulating the whole queueing process until steady state is reached for the whole cycle. In Chapter Four, we conduct simulation experiments to validate performance of four service-rate controls: the rate-matching control, which is directly proportional to the arrival rate, two square-root controls related to the square root staffing formula and the square-root control based on the mean stationary waiting time. Simulations show that the rate-matching control stabilizes the queue length distribution but not the virtual waiting time. This is consistent with established theoretical results, which follow from the observation that with rate-matching control, the queueing process becomes a time transformation of the stationary queueing process with constant arrival rates and service rates. Simulation results also show that the two square-root controls analogous to the server staffing formula are not effective in stabilizing performance. On the other hand, the alternative square-root service rate control based on the mean stationary waiting time approximately stabilizes the virtual waiting time when the cycle is long so that the arrival rate changes slowly enough. In Chapter Five, since we are mostly interested in stabilizing waiting times in more common scenarios when the traffic intensity is not close to one or when the arrival rate does not change slowly, we develop a damped time-lag service-rate control that performs fairly well for this purpose. This control is a modification of the rate-matching control involving a time lag and a damping factor. To find the best parameters for this control, we search over reasonable intervals for the most time-stable performance measures, which are computed by the extended rare-event simulation algorithm in GI_t/GI_t/1 queue. We conduct simulation experiments to validate that this control is effective for stabilizing the expected steady-state virtual waiting time (and its distribution to a large extent). We also establish a heavy-traffic limit with periodicity in the fluid scale to provide theoretical support for this control. We also show that there is a time-varying Little's law in heavy-traffic, which implies that this control cannot stabilize the queue length and the waiting time at the same time.

by Ma Ka Chun. / Thesis (M.Phil.)--Chinese University of Hong Kong, 2004. / Includes bibliographical references (leaves 50-52). / Abstracts in English and Chinese. / Chapter 1 --- Introduction --- p.7 / Chapter 2 --- Queueing Networks --- p.9 / Chapter 2.1 --- One-queue Networks --- p.9 / Chapter 2.2 --- Two-queue Free Networks --- p.12 / Chapter 2.3 --- Two-queue Overflow Networks --- p.13 / Chapter 2.4 --- Networks with Batch Arrivals --- p.14 / Chapter 3 --- ODE Solvers --- p.16 / Chapter 3.1 --- The Initial Value Methods --- p.16 / Chapter 3.1.1 --- The Linear System of Ordinary Differential Equations --- p.16 / Chapter 3.1.2 --- Euler's Method --- p.17 / Chapter 3.1.3 --- Runge-Kutta Methods --- p.17 / Chapter 3.1.4 --- The Stability of the IVMs --- p.19 / Chapter 3.1.5 --- Applications in Queueing Networks --- p.20 / Chapter 3.2 --- The Boundary Value Methods --- p.20 / Chapter 3.2.1 --- The Generalized Backward Differentiation For- mulae --- p.21 / Chapter 3.2.2 --- An example --- p.24 / Chapter 4 --- The Linear Equation Solver --- p.26 / Chapter 4.1 --- Iterative Methods --- p.26 / Chapter 4.1.1 --- The Jacobi method --- p.27 / Chapter 4.1.2 --- The Gauss-Seidel Method --- p.28 / Chapter 4.1.3 --- Other Iterative Methods --- p.29 / Chapter 4.1.4 --- Preconditioning --- p.29 / Chapter 4.2 --- The Multigrid Method --- p.30 / Chapter 4.2.1 --- Iterative Refinement --- p.30 / Chapter 4.2.2 --- Restriction and Prolongation --- p.30 / Chapter 4.2.3 --- The Geometric Multigrid Method --- p.33 / Chapter 4.2.4 --- The Algebraic Multigrid Method --- p.38 / Chapter 4.2.5 --- Higher Dimensional Cases --- p.38 / Chapter 4.2.6 --- Applications in Queueing Networks --- p.38 / Chapter 5 --- Numerical Experiments --- p.41 / Chapter 6 --- Concluding Remarks --- p.49 / Bibliography --- p.50

Bibliography: leaves 171-175. / ix, 175 leaves ; 30 cm. / Title page, contents and abstract only. The complete thesis in print form is available from the University Library. / Thesis (Ph.D.)--University of Adelaide, Dept. of Applied Mathematics, 1994

M. Sidi and A. Segall. / Bibliography: p. 14. / "June, 1981." / U.S. Department of Defense contract No. N00014-75-C-1183

Thesis (Ph. D.)--School of Industrial and Systems Engineering, Georgia Institute of Technology, 2004. Directed by Robert D. Foley. / Vita. Includes bibliographical references (leaves 85-86).

No description available.

No description available.

No description available.