The model we present here is a generalization of the De Vylder approximation for the probability of ultimate ruin in the classical risk model where claims occur according to a Poisson process and the claim size follows a known distribution. De Vylder's approach replaces the original risk process by a new risk process with exponentially distributed claims, such that the first three moments are the same. The present work generalizes this approach by allowing for claim amounts distributed according to either a mixture of two exponentials or a Coxian distribution of order two. Using matrix operations, it is relatively easy to find the exact probability of ruin for the approximating risk process. Our approximation is always at least as good de Vylder's original approximation, which is always one solution to our methodology. Through numerical examples we show that the approximation works quite well, much as the original approximation did. Finally, the links between our results and their consequences for the tail of the waiting time in the M/G/1 queue will be explored.
Analytical properties are derived for the PDF and CDF of the waiting time in M/D/1 queues and related models. A level crossing approach is used, which is intuitive and self-contained. In the standard M/D/1 queue a new kind of numerical sequence is defined, which leads to fast computation of the PDF and CDF. Numerical examples are presented. Analytical properties are exhibited graphically. The properties provide a benchmark to test new computational methods for obtaining probability distributions in general models.
We present two capacity choice scenarios for the socially optimal location of facilities with fixed servers, stochastic demand and congestion. Walk-in health clinics, motor vehicle inspection stations, automobile emissions testing stations, and internal service systems are motivating examples of such facilities. The choice of locations for such facilities influences not only distances for users traveling to the facilities but also user waiting times at the facilities. In contrast to most previous research in the area, we explicitly embed both customer travel and delay costs in the objective function and solve the location-allocation problem as well as choose service capacities for each open facility simultaneously. The choice of capacity for a facility that is viewed as a queueing system could mean choosing a service rate for the "servers" (scenario 1) or choosing the number of servers (scenario 2). In scenario 1, we are able to express the optimal service rate in closed form and, in scenario 2, we are able to express the (asymptotically) optimal number of servers in closed form. This allows us to eliminate both the number of servers and the service rates from the optimization problems, leading to relatively tractable models that can be solved using standard optimization procedures.
We consider a system of parallel queues with dedicated arrival streams. At each arrival time or service completion a decision maker can move customers from one queue to another. Assuming that the underlying random variables are exponential, we give results that characterize the optimal policy that minimizes the long-run average cost for a two server system. How these results may be used to develop heuristics for larger systems is a topic of current research and our initial work in this area will be discussed. Finally, we will discuss initial studies on how such schemes may be used to compensate for variability even when the nominal loads for the servers are identical.
As shown in a number of earlier papers, equilibrium solutions of QBD proces ses with repeating (block) rows can be obtained by solving a generalized eigenvalues problem, that is, by solving an equation of the form gQ(x)=0 for the vector g nd the scalar x, where Q(x) a matrix polynomial. The eigenvalue appraoch is especially attractive if some or most eigenvalues are zero, and this occurs in many models of practical importance. However, eigenvalues at zero can have some surprising side effects that will be explored. These effects may have importance for MAM methods as well.
The minimal nonnegative solution G of the matrix equation G=A_0+A_1G+A_2G^2, where the matrices A_i, (i=0, 1, 2) are nonnegative and A_0+A_1+A_2 is stochastic, plays an important role in the study of quasi-birth-death processes (QBDs). The Latouche--Ramaswami (LR) algorithm is a very efficient algorithm for finding the matrix G. Recently, a shift technique has been introduced to a cyclic reduction (CR) algorithm, which is closely related to the LR algorithm, for positive recurrent QBDs. In this talk, we apply the shift technique to the LR algorithm. We show that the convergence of the LR algorithm is quadratic for positive recurrent and null recurrent QBDs if the shift technique is used and no breakdown occurs. We also explain why it may be more appropriate to apply the shift technique to the LR algorithm instead of the CR algorithm.
It is well known that for a QBD process with a finite number of phases the spectrum of the finite rate matrix R characterizes the stationary probability measure $\pi$. For a QBD process with both infinite level and phase people are interested in knowing whether the spectral properties of the infinite rate matrix R analogously characterizes the stationary probability measure $\pi$ as in the finite phase setting. It seems as though this is not the case. This talk will illustrate this through examples. In general the characterization of R is difficult. Under some conditions we can show that the spectrum of R guarantees a stationary probability measure whose tails are jointly geometric. However, we expect heavy and light tails for the invariant probability measure in general. Finally, we provide conditions under which the tail is light.
We are studying the benefit of using an expert to order customers for a server prior to processing, when the service times are variable. As a starting point we considered the ordering of a single batch of customers, which turned out to be a fairly challenging problem in itself. We first saw this problem in a court situation where cases are chosen, as a daily batch, to be seen by a judge. The customers in our system will be reordered, based on the expert's service time estimates, in an attempt to reduce the total system time of all customers in the batch. Previously, we presented analytical results for the expectation of total waiting times, when we assume only two service times. We analyzed the amount by which the expert's ordering rule is better than the random order rule, and the affect of the expert's accuracy on the results.
This time we weaken our assumptions about the expert such as allowing him to be asymmetric in his judgment, but more importantly we show expressions for the variance and we want to get feedback on the meaning of these variances in terms of our problem. Our results will be shown as a set of recursive formula and then as closed analytical formulae, and graphs will be presented.
Wayne Horn and David Stanford, Department of Statistical and Actuarial
Sciences, University of Western Ontario
Guy Latouche, Département d'Informatique, Université
Libre de Bruxelles
We consider again the three-layer QBD model in which not only the level, but also the "sub-level" are allowed to be infinite. Phase changes (of finite dimension) are described at the lowest layer of the process. In many settings when the sub-level reaches 0, some service resources are freed up which can augment those resources that ordinarily serve those customers whose state variable is the level. What this implies in the standard QBD description is that the A_2 matrix possesses a block diagonal structure, with one finite-sized block for all transitions at positive sub-levels, and another for sub-level 0. For such a QBD, we prove several structural results. For the first time, we show for a spatial queue example that the bounding substochastic process is asymptotically stochastic, enabling us to determine several relevant quantities. Numerical examples are presented, and we hope to be able to present some examples of stationary probabilities.
In this presentation, we will present some preliminary results from an investigation of the use of empirical distributions as an alternative to distribution fitting for a variety of simple discrete time queueing systems. In performance modelling of real world queueing systems, it is common practice to sample, e.g. actual interarrival and service times and then to fit the data collected to a distribution using a flexible parametric family. The fitted distribution(s) are then used for as inputs to the performance analysis. Our preliminary work is to explore the impact of using the empirical data directly, rather than taking the intervening step of distribution fitting. We begin by assuming that an analyst samples interarrival and service times for a single server discrete time queue and then uses this empirical data to predict queue lengths with the use of the matrix geometric method. It is assumed that the 'true' interarrival and service time distributions are unknown to the analyst, but known to us. We then compare the analysts' results to the queue length distributions found by using the true interarrival and service time distributions. While it is generally accepted that use of empirical data will introduce error, the nature of the error is not well understood. Our talk will provide initial results for a variety of simple discrete time queues and an assessment of the promise of this approach.
In this talk, different accelerated procedures for simulation are discussed, including the "importance sampling" and "splitting". We also investigate the "rate-tilting" approach and its connection with the largest eigenvalue of the transition matrix inside the unit circle. The connections of importance sampling with the large deviation theory will also be addressed.
A reaction time experiment is studied in which a Poisson process of flashes is presented to an observer who responds by pushing and releasing a button. The data have the character of an M/G/infinity queue. Our interest is in understanding the server(s), i.e. the eye-brain-hand system of the observer. Using nonparametric point process techniques developed in a series of papers by Brillinger in conjunction with a simple parametric model, we can elucidate some of this structure. In particular, we study the behaviour of certain point process intensity functions under our simple model assumptions. This, in turn, tells us what kinds of features to look for in nonparametric estimates based on the real data.
In this talk, we would like to present a relation between the eigensolutions for different sizes of the buffer in a tandem queue with a movable server. It appears difficulties arise as N is getting large.
In this talk, we analyze a 2-class, single server preemptive priority queueing model with low priority balking customers. Arrivals are assumed to be Poisson with exponential service times. The system investigated is a QBD and the steady-state joint distribution is derived via the method of generalized eigenvalues. Numerical examples will be given to highlight some important computational features.