Parameter estimation is a long-lasting topic in queueing systems and has attracted considerable attention from both academia and industry. In this thesis, we design a parameter estimation framework for a tandem queueing system that collects end-to-end measurement data and utilizes the finite mixture model for the maximum likelihood (ML) estimation. The likelihood equations produced by ML are then solved by the iterative expectation-maximization (EM) algorithm, a powerful algorithm for parameter estimation in scenarios involving complicated distributions. We carry out a set of experiments with different parameter settings to test the performance of the proposed framework. Experimental results show that our method performs well for tandem queueing systems, in which the constituent nodes' service time follow distributions governed by exponential family. Under this framework, both the Newton-Raphson (NR) algorithm and the EM algorithm could be applied. The EM algorithm, however, is recommended due to its ease of implementation and lower computational overhead. / Graduate / hangli@uvic.ca

No description available.

We consider the problem of staffing large-scale service centers with multiple customer classes and agent types operating under quality-of-service (QoS) constraints. We introduce formulations for a class of staffing problems, minimizing the cost of staffing while requiring that the long-run average QoS achieves a certain pre-specified level. The queueing models we use to define such service center staffing problems have random inter-arrival times and random service times. The models we study differ with respect to whether the arrival rates are deterministic or stochastic. In the deterministic version of the service center staffing problem, we assume that the customer arrival rates are known deterministically. It is computationally challenging to solve our service center staffing problem with deterministic arrival rates. Thus, we provide an approximation and prove that the solution of our approximation is asymptotically optimal in the sense that the gap between the optimal value of the exact model and the objective function value of the approximate solution shrinks to zero as the size of the system grows large. In our work, we also focus on doubly stochastic service center systems; that is, we focus on solving large-scale service center staffing problems when the arrival rates are uncertain in addition to the inherent randomness of the system's inter-arrival times and service times. This brings the modeling closer to reality. In solving the service center staffing problems with deterministic arrival rates, we provide a solution procedure for solving staffing problems for doubly stochastic service center systems. We consider a decision making scheme in which we must select staffing levels before observing the arrival rates. We assume that the decision maker has distributional information about the arrival rates at the time of decision making. In the presence of arrival-rate uncertainty, the decision maker's goal is to minimize the staffing cost, while ensuring the QoS achieves a given level. We show that as the system scales large in size, there is at most one key scenario under which the probability of waiting converges to a non-trivial value, i.e., a value strictly between 0 and 1. That is, the system is either over- or under-loaded in any other scenario as the size of the system grows to infinity. Exploiting this result, we propose a two-step solution procedure for the staffing problem with random arrival rates. In the first step, we use the desired QoS level to identify the key scenario corresponding to the optimal staffing level. After finding the key scenario, the random arrival-rate model reduces to a deterministic arrival-rate model. In the second step, we solve the resulting model, with deterministic arrival rate, by using the approximation model we point to above. The approximate optimal staffing level obtained in this procedure asymptotically converges to the true optimal staffing level for the random arrival-rate problem. The decision making scheme we sketch above, assumes that the distribution of the random arrival rates is known at the time of decision making. In reality this distribution must be estimated based on historical data and experience, and needs to be updated as new observations arrive. Another important issue that arises in service center management is that in the daily operation in service centers, the daily operational period is split into small decision time periods, for example, hourly periods, and then the staffing decisions need to be made for all such time periods. Thus, to achieve an overall optimal daily staffing policy, one must deal with the interaction among staffing decisions over adjacent time periods. In our work, we also build a model that handles the above two issues. We build a two-stage stochastic model with recourse that provides the staffing decisions over two adjacent decision time periods, i.e., two adjacent decision stages. The model minimizes the first stage staffing cost and the expected second stage staffing cost while satisfying a service quality constraint on the second stage operation. A Bayesian update is used to obtain the second-stage arrival-rate distribution based on the first-stage arrival-rate distribution and the arrival observations in the first stage. The second-stage distribution is used in the constraint on the second stage service quality. After reformulation, we show that our two-stage model can be expressed as a newsvendor model, albeit with a demand that is derived from the first stage decision. We provide an algorithm that can solve the two-stage staffing problem under the most commonly used QoS constraints. This work uses stochastic programming methods to solve problems arising in queueing networks. We hope that the ideas that we put forward in this dissertation lead to other attempts to deal with decision making under uncertainty for queueing systems that combine techniques from stochastic programming and analysis tools from queueing theory. / text

Baigiamojo darbo tikslas – sukurti masinio aptarnavimo sistemų modeliavimo programinę įrangą ir sumodeliuoti bei ištirti įvairias masinio aptarnavimo kompiuterines sistemas. Modeliavimo programinė įranga buvo parašyta C# programavimo kalba. Programos branduolys – Delsi 2.0 masinio aptarnavimo sistemų modeliavimo biblioteka. Sukurta programa buvo sumodeliuota ir ištirta keletas masinio aptarnavimo sistemų: sistemos su apribotu paraiškų eilės ilgiu, sistemos su apribotu paraiškų laukimo eilėje laiku, mišrios sistemos, vieno ir daugelio aptarnavimo kanalų sistemos. Taip pat buvo sumodeliuotas vidutinio dydžio kompiuterių tinklo komutatoriaus darbas ir ištirtos jo pagrindinės charakteristikos. Nustatyta optimali komutatoriaus paketų aptarnavimo sparta ir optimalus paketų buferio dydis. Darbo apimtis – 51 p. teksto be priedų, 14 iliustracijų, 6 lentelės, 16 bibliografinių šaltinių. / Master thesis objective – to create universal modeling software for queueing systems and with its help to conduct simulation experiments, investigating several various queueing systems. The software was written with the help of C# programming language. The core of the created software is Delsi. 2.0 simulation library. Using created software several different queueing systems were modeled and investigated: systems with the restricted queue length, systems with the restricted transaction waiting time in a queue, combined systems, semi- and multichannel systems. Also there was modeled the operation of a middle-sized computer network switch and its main characteristics were investigated. The optimal packet serving rate and packet buffer size of the switch were found. Thesis consists of: 51 p. of text without extras, 14 illustrations, 6 tables, 16 bibliographical entries.

No description available.

This thesis provides a discrete-event simulation framework that can be used to analyze  and  dimension  computing  systems.  The  simulation  framework  can define  and  parametrize  the  flexible  queueing  system.  We  use  the  simulation framework to explore the data collected from the real-world system. We analyze the metrics, including waiting time and server utilization of single-server and multi-server  queueing  systems.  In  particular,  we  study  the  impact  of  the number of servers on waiting time and server utilization. The experiments show it  is  possible  to  increase  server  utilization  and  decrease  the  server  number without  significantly  increasing  waiting  time,  and  flexible  architectures  canlead to significant gains. / Detta  examensarbete  tillhandahåller  ett  ramverk  som  kan  användas  för  att analysera och dimensionera dator-system. Simuleringsramverket kan definera och parameterisera ett flexibelt kösystem baserat på data från ett system i drift. Vi använder simuleringsramverket för att undersöka datat insamlat från skarpa system.  Vi  analyserar  prestandatal,  såsom  väntetid  och  utnyttjandegrad  för system  med  en  och  flera  betjänare.  Framför  allt  undersöker  vi  hur  antalet betjänare  påverkar  väntetid  och  utnyttjandegrad.   Försöken  visar  att  det  är möjligt  att  öka  uttnyttjandegraden  och  minska  antalet  betjänare  utan  att märkbart öka väntetiden, och att en flexibel arkitektur kan leda till märkbaraförbättringar. / <p>Industrial Advisors: Olga Grinchtein and Johan Karlsson </p>

The thesis investigates how Agent-Based Modeling and Simulation (ABMS) and Queueing Theory (QT) techniques help manage mass gathering (MG) crowds. The techniques are applied to Hajj MG, which is one of the most complex annual MG, with a focus on its challenging Tawaf ritual. The objective is to develop a Tawaf Decision Support System (DSS) to better understand Tawaf crowd dynamics and discover decisions that lead to superior performance. TawafSIM is an ABMS model in the DSS, which simulates macro-level Tawaf crowd dynamics through micro-level pilgrim modeling to explore the impact of crowd characteristics, facility layout, and management preferences on emergent crowd behaviours with respect to throughput, satisfaction, health, and safety. Whereas, TawafQT is a QT model in the DSS to explore the impact of pilgrim arrival rate and Tawaf throughput on expected arrival, departure, and waiting times along with average queue length in the Tawaf waiting area. The thesis provides several contributions, including the following. First, it is the only Tawaf research to use a hybrid ABMS and QT approach. Second, TawafSIM is a comprehensive Tawaf simulator. It incorporates features for pilgrim characteristics, facility design, and management preferences. It calculates eight metrics for Tawaf performance, which includes one for throughput, three for satisfaction, one for health, and three for safety. It is the only Tawaf simulator to estimate satisfaction and spread of infectious disease. It conducts 42 simulation experiments in 12 categories. It generates observations for emergent, tipping point, expected, and counter intuitive behaviours. It recommends a default scenario as the best decision along with a small subset of alternative scenarios, which provide above average Tawaf performance. It generates a Tawaf Crowd Management Guide to better understand Tawaf crowd dynamics and how to pursue above average Tawaf performance under different conditions. Third, TawafQT is the only study of the Tawaf waiting area. It uses an accurate queueing model with finite source, single service, and PH type distribution, which is not only applicable to the Tawaf and other Hajj related queueing systems but also to any queueing system, which has finite population and single service characteristics.

The thesis investigates how Agent-Based Modeling and Simulation (ABMS) and Queueing Theory (QT) techniques help manage mass gathering (MG) crowds. The techniques are applied to Hajj MG, which is one of the most complex annual MG, with a focus on its challenging Tawaf ritual. The objective is to develop a Tawaf Decision Support System (DSS) to better understand Tawaf crowd dynamics and discover decisions that lead to superior performance. TawafSIM is an ABMS model in the DSS, which simulates macro-level Tawaf crowd dynamics through micro-level pilgrim modeling to explore the impact of crowd characteristics, facility layout, and management preferences on emergent crowd behaviours with respect to throughput, satisfaction, health, and safety. Whereas, TawafQT is a QT model in the DSS to explore the impact of pilgrim arrival rate and Tawaf throughput on expected arrival, departure, and waiting times along with average queue length in the Tawaf waiting area. The thesis provides several contributions, including the following. First, it is the only Tawaf research to use a hybrid ABMS and QT approach. Second, TawafSIM is a comprehensive Tawaf simulator. It incorporates features for pilgrim characteristics, facility design, and management preferences. It calculates eight metrics for Tawaf performance, which includes one for throughput, three for satisfaction, one for health, and three for safety. It is the only Tawaf simulator to estimate satisfaction and spread of infectious disease. It conducts 42 simulation experiments in 12 categories. It generates observations for emergent, tipping point, expected, and counter intuitive behaviours. It recommends a default scenario as the best decision along with a small subset of alternative scenarios, which provide above average Tawaf performance. It generates a Tawaf Crowd Management Guide to better understand Tawaf crowd dynamics and how to pursue above average Tawaf performance under different conditions. Third, TawafQT is the only study of the Tawaf waiting area. It uses an accurate queueing model with finite source, single service, and PH type distribution, which is not only applicable to the Tawaf and other Hajj related queueing systems but also to any queueing system, which has finite population and single service characteristics.

No description available.

Queueing theory is the mathematical study of queues or waiting lines, which are formed whenever demand for service exceeds the capacity to provide service. A queueing system is composed of customers, packets or calls that need some kind of service. These entities arrive at queueing system, join a queue if service is not immediately available and leave system after receiving service. There are also cases when customers, packets or calls leave system without joining queue or drop out without receiving service even after waiting for some time. Queueing network models with finite capacity have facilitated the analysis of discrete flow systems, such as computer systems, transportation networks, manufacturing systems and telecommunication networks, by providing powerful and realistic tools for performance evaluation and prediction. In wireless cellular systems mobility is the most important feature and continuous service is achieved by supporting handoff from one cell to another. Hand off is the process of changing channel associated with the current connection while a call is in progress. A handoff is required when a mobile terminal moves from one cell to another or the signal quality deteriorates in current cell. Since neighbouring cells use disjoint subset of frequency bands therefore negotiation must take place between mobile terminal, the current base station and next potential base station. A poorly designed handoff scheme significantly decreases quality of service (QOS). Different schemes have been devised and in these schemes handoff calls are prioritize. Also most of the performance evaluation techniques consider the case where the arrival process is poisson and service is exponential i.e. there is single arrival and single departure. Whereas in practice there is burstiness in cellular traffic i.e. there can be bulk arrivals and bulk departures. Other issue is that, assumptions made by stochastic process models are not satisfied. Most of the effort is concentrated on providing different interpretations of M/M queues rather than attempting to provide a new methodology. In this thesis performance evaluation of multi traffic cellular models i.e. non priority, priority and hand off calling scheme for bursty traffic are devised. Moreover extensions are carried out towards the analysis of a multi-traffic M/M queueing system and state probabilities are calculated analytically.