<p>Queueing models have been used extensively in the design of call centres. In particular, a queueing model will be used to describe a help desk which is a form of a call centre. The design of the queueing model involves modelling the arrival an service processes of the system.</p><p>Conventionally, the arrival process is assumed to be Poisson and service times are assumed to be exponentially distributed. But it has been proposed that practically these are seldom the case. Past research reveals that the log-normal distribution can be used to model the service times in call centres. Also, services may involve stages/tasks before completion. This motivates the use of a phase-type distribution to model the underlying stages of service.</p><p>This research work focuses on developing statistical models for the overall service times and the service times by job types in a particular help desk. The assumption of exponential service times was investigated and a log-normal distribution was fitted to service times of this help desk. Each stage of the service in this help desk was modelled as a phase in the phase-type distribution.</p><p>Results from the analysis carried out in this work confirmed the irrelevance of the assumption of exponential service times to this help desk and it was apparent that log-normal distributions provided a reasonable fit to the service times. A phase-type distribution with three phases fitted the overall service times and the service times of administrative and miscellaneous jobs very well. For the service times of e-mail and network jobs, a phase-type distribution with two phases served as a good model.</p><p>Finally, log-normal models of service times in this help desk were approximated using an order three phase-type distribution.</p>

<p>Queueing models have been used extensively in the design of call centres. In particular, a queueing model will be used to describe a help desk which is a form of a call centre. The design of the queueing model involves modelling the arrival an service processes of the system.</p><p>Conventionally, the arrival process is assumed to be Poisson and service times are assumed to be exponentially distributed. But it has been proposed that practically these are seldom the case. Past research reveals that the log-normal distribution can be used to model the service times in call centres. Also, services may involve stages/tasks before completion. This motivates the use of a phase-type distribution to model the underlying stages of service.</p><p>This research work focuses on developing statistical models for the overall service times and the service times by job types in a particular help desk. The assumption of exponential service times was investigated and a log-normal distribution was fitted to service times of this help desk. Each stage of the service in this help desk was modelled as a phase in the phase-type distribution.</p><p>Results from the analysis carried out in this work confirmed the irrelevance of the assumption of exponential service times to this help desk and it was apparent that log-normal distributions provided a reasonable fit to the service times. A phase-type distribution with three phases fitted the overall service times and the service times of administrative and miscellaneous jobs very well. For the service times of e-mail and network jobs, a phase-type distribution with two phases served as a good model.</p><p>Finally, log-normal models of service times in this help desk were approximated using an order three phase-type distribution.</p>

Developing equations to compute congestion measures for the general G/G/s/c queueing model and networks of such nodes has always been a challenge. One approach to analyzing such systems is to approximate the model-specified general input processes and distributions by processes and distributions from the more computationally friendly family of phase-type processes and distributions. We develop numerical approximation methods for analysis of general time-dependent queueing nodes by introducing new approximations for the time-dependent first two moments of the number-in-system and departure-count processes. / Ph. D.

Time-dependent queueing models are important since most of real-life problems are time-dependent. We develop a numerical approximation algorithm for the mean, variance and higher-order moments of the number of entities in the system at time t for the Ph(t)/Ph(t)/s/c queueing model. This model can be thought as a reparameterization to the G(t)/GI(t)/s. Our approach is to partition the state space into known and identifiable structures, such as the M(t)/M(t)/s/c or M(t)/M(t)/1 queueing models. We then use the Polya-Eggenberger distribution to approximate certain unknown probabilities via a two-moment matching algorithm. We describe the necessary steps to validate the approximation and measure the accuracy of the model. / Master of Science

A deterministic change to a time-varying queueing model is described as either changing the number of entities, the queue capacity, or the number of servers in the system at selected times. We use a surrogate distribution for N(t), the number of entities in the system at time t, to approximate deterministic changes to the Ph(t)/Ph(t)/1/c and the Ph(t)/M(t)/s/c queueing models. We develop a solution technique to minimize the number of state probabilities to be approximated. / Master of Science

Sequential data are encountered in many contexts of everyday life and in numerous scientific applications. They can for instance be SMS typeset on mobile phones, web pages reached while crossing hyperlinks, system logs or DNA samples, to name a few. Generating such data defines a sequential process. This thesis is concerned with the modeling of sequential processes from observed data. Sequential processes are here modeled using probabilistic models, namely discrete time Markov chains (MC), Hidden Markov Models (HMMs) and Partially Observable Markov Models (POMMs). Such models can answer questions such as (i) Which event will occur a couple of steps later? (ii) How many times will a particular event occur? and (iii) When does an event occur for the first time given the current situation? The last question is of particular interest in this thesis and is mathematically formalized under the notion of First Passage Times (FPT) dynamics of a process. The FPT dynamics is used here to solve the three following problems related to machine learning and data mining: (i) HMM/POMM induction, (ii) supervised sequence classification and (iii) relevant subgraph mining. Firstly, we propose a novel algorithm, called POMMStruct, for learning the structure and the parameters of POMMs to best fit the empirical FPT dynamics observed in the samples. Experimental results illustrate the benefit of POMMStruct in the modeling of sequential processes with a complex temporal dynamics while compared to classical induction approaches. Our second contribution is concerned with the classification of sequences. We propose to model the FPT in sequences with discrete phase-type (PH) distributions using a novel algorithm called PHit. These distributions are used to devise a new string kernel and a probabilistic classifier. Experimental results on biological data shows that our methods provides state-of-the-art classification results. Finally, we address the problem of mining subgraphs, which are relevant to model the relationships between selected nodes of interest, in large graphs such as biological networks. A new relevance criterion based on particular random walks called K-walks is proposed as well as efficient algorithms to compute this criterion. Experiments on the KEGG metabolic network and on randomly generated graphs are presented.

Analyses are addressed for a number of problems in queueing systems and stochastic modeling that arose due to an investigation into techniques that could be used to approximate general closed networks. In Chapter II, a method is presented to calculate the system size distribution at an arbitrary point in time and at departures for a (n)/G/1/N queue. The analysis is carried out using an embedded Markov chain approach. An algorithm is also developed that combines our analysis with the recursive method of Gupta and Rao. This algorithm compares favorably with that of Gupta and Rao and will solve some situations when Gupta and Rao's method fails or becomes intractable. In Chapter III, an approach is developed for generating exact solutions of the time-dependent conditional joint probability distributions for a phase-type renewal process. Closed-form expressions are derived when a class of Coxian distributions are used for the inter-renewal distribution. The class of Coxian distributions was chosen so that solutions could be obtained for any mean and variance desired in the inter-renewal times. In Chapter IV, an algorithm is developed to generate numerical solutions for the steady-state system size probabilities and waiting time distribution functions of the SM/PH/1/N queue by using the matrix-analytic method. Closed form results are also obtained for particular situations of the preceding queue. In addition, it is demonstrated that the SM/PH/1/N model can be implemented to the analysis of a sequential two-queue system. This is an extension to the work by Neuts and Chakravarthy. In Chapter V, principal results developed in the preceding chapters are employed for approximate analysis of the closed network of queues with arbitrary service times. Specifically, the (n)/G/1/N queue is applied to closed networks of a general topology, and a sequential two-queue model consisting of the (n)/G/1/N and SM/PH/1/N queues is proposed for tandem queueing networks.

這一篇論文裡，我們討論如何計算開放式有限容量等候系統的穩定機率。其中到達時間和服務時間的機率分配都是Coxian分配。我們利用向量表示法（Product-Form Method）求解穩定機率，並建立C_{k}/C_{m}/1/4與C_{k}/C_{m}/1/6的穩定機率之表格。在使用向量表示法的過程中，計算所需的時間與系統容量無關。因此，在我們計算穩定機率的經驗中，當N>100時，我們可以明顯感覺出向量表示法比一般傳統方法有更快的計算速度。 / In this thesis, we study the C_{k}/C_{m}/1/N open queueing system with finite capacity, N. We use the product-form method to solve the steady-state probabilities and give tables of numerical results in examples of C_{k}/C_{m}/1/4 and C_{k}/C_{m}/1/6. The merit of this method is that the computation time is independent of N. In our computational experiments, we have observed that when the capacity size of queueing system, N>100, the computing efficiency of the product-form method is much better than that of a traditional method.

The main focus of this thesis is Markovian decision processes with an emphasis on incorporating time-dependence into the system dynamics. When considering such decision processes, we provide value equations that apply to a large range of classes of Markovian decision processes, including Markov decision processes (MDPs) and semi-Markov decision processes (SMDPs), time-homogeneous or otherwise. We then formulate a simple decision process with exponential state transitions and solve this decision process using two separate techniques. The first technique solves the value equations directly, and the second utilizes an existing continuous-time MDP solution technique. To incorporate time-dependence into the transition dynamics of the process, we examine a particular decision process with state transitions determined by the Erlang distribution. Although this process is originally classed as a generalized semi-Markov decision process, we re-define it as a time-inhomogeneous SMDP. We show that even for a simply stated process with desirable state-space properties, the complexity of the value equations becomes so substantial that useful analytic expressions for the optimal solutions for all states of the process are unattainable. We develop a new technique, utilizing phase-type (PH) distributions, in an effort to address these complexity issues. By using PH representations, we construct a new state-space for the process, referred to as the phase-space, incorporating the phases of the state transition probability distributions. In performing this step, we effectively model the original process as a continuous-time MDP. The information available in this system is, however, richer than that of the original system. In the interest of maintaining the physical characteristics of the original system, we define a new valuation technique for the phase-space that shields some of this information from the decision maker. Using the process of phase-space construction and our valuation technique, we define an original system of value equations for this phasespace that are equivalent to those for the general Markovian decision processes mentioned earlier. An example of our own phase-space technique is given for the aforementioned Erlang decision process and we identify certain characteristics of the optimal solution such that, when applicable, the implementation of our phase-space technique is greatly simplified. These newly defined value equations for the phase-space are potentially as complex to solve as those defined for the original model. Restricting our focus to systems with acyclic state-spaces though, we describe a top-down approach to solution of the phase-space value equations for more general processes than those considered thus far. Again, we identify characteristics of the optimal solution to look for when implementing this technique and provide simplifications of the value equations where these characteristics are present. We note, however, that it is almost impossible to determine a priori the class of processes for which the simplifications outlined in our phase-space technique will be applicable. Nevertheless, we do no worse in terms of complexity by utilizing our phase-space technique, and leave open the opportunity to simplify the solution process if an appropriate situation arises. The phase-space technique can handle time-dependence in the state transition probabilities, but is insufficient for any process with time-dependent reward structures or discounting. To address such decision processes, we define an approximation technique for the solution of the class of infinite horizon decision processes whose state transitions and reward structures are described with reference to a single global clock. This technique discretizes time into exponentially distributed length intervals and incorporates this absolute time information into the state-space. For processes where the state-transitions are not exponentially distributed, we use the hazard rates of the transition probability distributions evaluated at the discrete time points to model the transition dynamics of the system. We provide a suitable reward structure approximation using our discrete time points and guidelines for sensible truncation, using an MDP approximation to the tail behaviour of the original infinite horizon process. The result is a finite-state time-homogeneous MDP approximation to the original process and this MDP may be solved using standard existing solution techniques. The approximate solution to the original process can then be inferred from the solution to our MDP approximation. / Thesis (Ph.D.) -- University of Adelaide, School of Mathematical Sciences, 2008

Thèse numérisée par la Division de la gestion de documents et des archives de l'Université de Montréal.