The optimal allocation of server time slots over different classes of patients

We present a model for assigning server time slots to different classes of patients. The objective is to minimize the total expected weighted waiting time of a patient (where different patient classes may be assigned different weights). A bulk service queueing model is used to obtain the expected waiting time of a patient of a particular class, given a feasible allocation of service time slots. Using the output of the bulk service queueing models as the input of an optimization procedure, the optimal allocation scheme may be identified. For problems with a large number of patient classes and/or a large number of feasible allocation schemes, a step-wise heuristic is developed. A common example of such a system is the allocation of operating room time slots over different medical disciplines in a hospital.     

The Discrete-Time GI/Geo/1 Queue with Multiple Vacations

We study a discrete-time GI/Geo/1 queue with server vacations. In this queueing system, the server takes vacations when the system does not have any waiting customers at a service completion instant or a vacation completion instant. This type of discrete-time queueing model has potential applications in computer or telecommunication network systems. Using matrix-geometric method, we obtain the explicit expressions for the stationary distributions of queue length and waiting time and demonstrate the conditional stochastic decomposition property of the queue length and waiting time in this system.     

Expansions for Joint Laplace Transform of Stationary Waiting Times in (max,+)-linear Systems with Poisson Input

We give a Taylor series expansion for the joint Laplace transform of stationary waiting times in open (max,+)-linear stochastic systems with Poisson input. Probabilistic expressions are derived for coefficients of all orders. Even though the computation of these coefficients can be hard for certain systems, it is sufficient to compute only a few coefficients to obtain good approximations (especially under the assumption of light traffic). Combining this new result with the earlier expansion formula for the mean stationary waiting times, we also provide a Taylor series expansion for the covariance of stationary waiting times in such systems.It is well known that (max,+)-linear systems can be used to represent stochastic Petri nets belonging to the class of event graphs. This class contains various instances of queueing networks like acyclic or cyclic fork-and-join queueing networks, finite or infinite capacity tandem queueing networks with various types of blocking, synchronized queueing networks and so on. It also contains some basic manufacturing models such as kanban networks, assembly systems and so forth. The applicability of this expansion technique is discussed for several systems of this type.     

Laplace Transform and Moments of Waiting Times in Poisson Driven (max,+) Linear Systems

(Max,+) linear systems can be used to represent stochastic Petri nets belonging to the class of event graphs. This class contains various instances of queueing networks like acyclic or cyclic fork-and-join queueing networks, finite or infinite capacity tandem queueing networks with various types of blocking, synchronized queueing networks and so on. It also contains some basic manufacturing models such as kanban networks, assembly systems and so forth.In their 1997 paper, Baccelli, Hasenfuss and Schmidt provide explicit expressions for the expected value of the waiting time of the nth customer in a given subarea of a (max,+) linear system. Using similar analysis, we present explicit expressions for the moments and the Laplace transform of transient waiting times in Poisson driven (max,+) linear systems. Furthermore, starting with these closed form expressions, we also derive explicit expressions for the moments and the Laplace transform of stationary waiting times in a class of (max,+) linear systems with deterministic service times. Examples pertaining to queueing theory are given to illustrate the results.     

Staff optimization for time-dependent acute patient flow

The emergency department is a key element of acute patient flow, but due to high demand and an alternating rate of arriving patients, the department is often challenged by insufficient capacity. Proper allocation of resources to match demand is, therefore, a vital task for many emergency departments.Constrained by targets on patient waiting time, we consider the problem of minimizing the total amount of staff-resources allocated to an emergency department. We test a matheuristic approach to this problem, accounting for both patient flow and staff scheduling restrictions. Using a continuous-time Markov chain, patient flow is modeled as a time-dependent queueing network where inhomogeneous behavior is evaluated using the uniformization method. Based on this modeling approach, we recursively evaluate and allocate staff to the system using integer linear programming until the waiting time targets are respected in all queues of the network. By comparing to discrete-event simulations of the associated system, we show that this approach is adequate for both modeling and optimizing the patient flow. In addition, we demonstrate robustness to the service time distribution and the associated system with multiple classes of patients.     

Stationary Distributions of GI/M/c Queue with PH Type Vacations

We study a GI/M/c type queueing system with vacations in which all servers take vacations together when the system becomes empty. These servers keep taking synchronous vacations until they find waiting customers in the system at a vacation completion instant.The vacation time is a phase-type (PH) distributed random variable. Using embedded Markov chain modeling and the matrix geometric solution methods, we obtain explicit expressions for the stationary probability distributions of the queue length at arrivals and the waiting time. To compare the vacation model with the classical GI/M/c queue without vacations, we prove conditional stochastic decomposition properties for the queue length and the waiting time when all servers are busy. Our model is a generalization of several previous studies.     

A network of priority queues in heavy traffic: One bottleneck station

In this paper we consider an open queueing network having multiple classes, priorities, and general service time distributions. In the case where there is a single bottleneck station we conjecture that normalized queue length and sojourn time processes converge, in the heavy traffic limit, to one-dimensional reflected Brownian motion, and present expressions for its drift and variance. The conjecture is motivated by known heavy traffic limit theorems for some special cases of the general model, and some conjectured “Heavy Traffic Principles” derived from them. Using the known stationary distribution of one-dimensional reflected Brownian motion, we present expressions for the heavy traffic limit of stationary queue length and sojourn time distributions and moments. For systems with Markov routing we are able to explicitly calculate the limits.     

Transient and stationary waiting times in (max,+)-linear systems with Poisson input

We consider a certain class of vectorial evolution equations, which are linear in the (max,+) semi-field. They can be used to model several Types of discrete event systems, in particular queueing networks where we assume that the arrival process of customers (tokens, jobs, etc.) is Poisson. Under natural Cramér Type conditions on certain variables, we show that the expected waiting time which the nth customer has to spend in a given subarea of such a system can be expanded analytically in an infinite power series with respect to the arrival intensity λ. Furthermore, we state an algorithm for computing all coefficients of this series expansion and derive an explicit finite representation formula for the remainder term. We also give an explicit finite expansion for expected stationary waiting times in (max,+)-linear systems with deterministic queueing services. This revised version was published online in June 2006 with corrections to the Cover Date.     

Homogeneous Customers Renege from Invisible Queues at Random Times under Deteriorating Waiting Conditions

We consider a memoryless first-come first-served queue in which customers' waiting costs are increasing and convex with time. Hence, customers may opt to renege if service has not commenced after waiting for some time. We assume a homogeneous population of customers and we look for their symmetric Nash equilibrium reneging strategy. Besides the model parameters, customers are aware only, if they are in service or not, and they recall for how long they are have been waiting. They are informed of nothing else. We show that under some assumptions on customers' utility function, Nash equilibrium prescribes reneging after random times. We give a closed form expression for the resulting distribution. In particular, its support is an interval (in which it has a density) and it has at most two atoms (at the edges of the interval). Moreover, this equilibrium is unique. Finally, we indicate a case in which Nash equilibrium prescribes a deterministic reneging time.     

Queueing models for appointment-driven systems

Many service systems are appointment-driven. In such systems, customers make an appointment and join an external queue (also referred to as the “waiting list”). At the appointed date, the customer arrives at the service facility, joins an internal queue and receives service during a service session. After service, the customer leaves the system. Important measures of interest include the size of the waiting list, the waiting time at the service facility and server overtime. These performance measures may support strategic decision making concerning server capacity (e.g. how often, when and for how long should a server be online). We develop a new model to assess these performance measures. The model is a combination of a vacation queueing system and an appointment system.     

A queueing model with bonus service for certain customers

A queueing model is introduced in which the management has a policy, because of economic reasons, of not operating the service counter unless a certain number, R + 1, of customers are available during each busy period. Thus, the first R customers who arrive must wait until the service counter is opened. Such a policy may cause the management to provide or render additional services to the first R customers. Assuming Poisson arrivals and that both regular and additional services follow exponential distributions, explicit expressions are derived for the stationary queue length and busy period distributions and their expected values. In the special case where R = 1, an explicit expression is presented for the stationary distribution of the waiting time.     

Stochastic modelling and simulation of a kidney transplant waiting list

We created a dynamic stochastic model to evaluate the performance of a kidney transplantation system. Our model is applicable in the context of a small country where the legislation requires that a kidney from a deceased donor should be used whenever available. Using a systematic design of simulation experiments, we performed a complex simulation study based on real medical data to explore the impact of factors representing different rates of deceased kidneys harvesting, the proportion of patients with a willing living donor and different allocation policies. On the basis of careful statistical analysis carried out by two different statistical methodologies, ANOVA and bootstrap, we draw some important conclusions about the effects of these factors and recommendations for the medical community. The results of the study clearly demonstrate that in addition to increasing the numbers of kidney donors, deceased as well as living, the introduction of a kidney exchange program leads to further expansion of the numbers of donations and to shortening of waiting time for transplantation. Moreover, we observed that the largest and most counter-intuitive effect on waiting time and transplantation probability was obtained by replacing the currently implemented first-come-first-transplanted allocation policy to a policy that prioritizes the most vulnerable group of patients. This change has led to shortening the waiting time of these patients by enormous 28 months on average while leaving the waiting time of other patients practically the same.

     

A Markovian queueing model for ambulance offload delays

Ambulance offload delays are a growing concern for health care providers in many countries. Offload delays occur when ambulance paramedics arriving at a hospital Emergency Department (ED) cannot transfer patient care to staff in the ED immediately. This is typically caused by overcrowding in the ED. Using queueing theory, we model the interface between a regional Emergency Medical Services (EMS) provider and multiple EDs that serve both ambulance and walk-in patients. We introduce Markov chain models for the system and solve for the steady state probability distributions of queue lengths and waiting times using matrix-analytic methods. We develop several algorithms for computing performance measures for the system, particularly the offload delays for ambulance patients. Using these algorithms, we analyze several three-hospital systems and assess the impact of system resources on offload delays. In addition, simulation is used to validate model assumptions.     

Assembly-like queues with finite capacity: Bounds,asymptotics and approximations

In this paper we study a queueing model of assembly-like manufacturing operations. This study was motivated by an examination of a circuit pack testing procedure in an AT & T factory. However, the model may be representative of many manufacturing assembly operations. We assume that customers fromn classes arrive according to independent Poisson processes with the same arrival rate into a single-server queueing station where the service times are exponentially distributed. The service discipline requires that service be rendered simultaneously to a group of customers consisting of exactly one member from each class. The server is idle if there are not enough customers to form a group. There is a separate waiting area for customers belonging to the same class and the size of the waiting area is the same for all classes. Customers who arrive to find the waiting area for their class full, are lost. Performance measures of interest include blocking probability, throughput, mean queue length and mean sojourn time. Since the state space for this queueing system could be large, exact answers for even reasonable values of the parameters may not be easy to obtain. We have therefore focused on two approaches. First, we find upper and lower bounds for the mean sojourn time. From these bounds we obtain the asymptotic solutions as the arrival rate (waiting room, service rate) approaches zero (infinity). Second, for moderate values of these parameters we suggest an approximate solution method. We compare the results of our approximation against simulation results and report good correspondence.     

Analyzing the discrete-timeG (G)/Geo/1 queue using complex contour integration

In this paper, a discrete-time single-server queueing system with an infinite waiting room, referred to as theG ^(G)/Geo/1 model, i.e., a system with general interarrival-time distribution, general arrival bulk-size distribution and geometrical service times, is studied. A method of analysis based on integration along contours in the complex plane is presented. Using this technique, analytical expressions are obtained for the probability generating functions of the system contents at various observation epochs and of the delay and waiting time of an arbitrary customer, assuming a first-come-first-served queueing discipline, under the single restriction that the probability generating function for the interarrival-time distribution be rational. Furthermore, treating several special cases we rediscover a number of well-known results, such as Hunter's result for theG/Geo/1 model. Finally, as an illustration of the generality of the analysis, it is applied to the derivation of the waiting time and the delay of the more generalG ^(G)/G/1 model and the system contents of a multi-server buffer-system with independent arrivals and random output interruptions.Both authors wish to thank the Belgian National Fund for Scientific Research (NFWO) for support of this work.     

Workload in queues having priorities assigned according to service time

System designers often implement priority queueing disciplines in order to improve overall system performance; however, improvement is often gained at the expense of lower priority cystomers. Shortest Processing Time is an example of a priority discipline wherein lower priority customers may suffer very long waiting times when compared to their waiting times under a democratic service discipline. In what follows, we shall investigate a queueing system where customers are divided into a finitie number of priority classes according to their service times.We develop the multivariate generating function characterizing the joint workload among the priority classes. First moments obtained from the generating function yield traffic intensities for each priority class. Second moments address expected workloads, in particular, we obtain simple Pollaczek-Khinchine type formulae for the classes. Higher moments address variance and covariance among the workloads of the priority classes.This work was supported in part by National Science Foundation Grant DDM-8913658.     

On the M/G/2 queeing model

The M/G/2 queueing model with service time distribution a mixture of m negative exponential distributions is analysed. The starting point is the functional relation for the Laplace–Stieltjes transform of the stationary joint distribution of the workloads of the two servers. By means of Wiener–Hopf decompositions the solution is constructed and reduced to the solution of m linear equations of which the coefficients depend on the zeros of a polynome. Once this set of equations has been solved the moments of the waiting time distribution can be easily obtained. The Laplace–Stieltjes transform of the stationary waiting time distribution has been derived, it is an intricate expression.     

Skorohod–Loynes Characterizations of Queueing,Fluid, and Inventory Processes

We consider queueing, fluid and inventory processes whose dynamics are determined by general point processes or random measures that represent inputs and outputs. The state of such a process (the queue length or inventory level) is regulated to stay in a finite or infinite interval – inputs or outputs are disregarded when they would lead to a state outside the interval. The sample paths of the process satisfy an integral equation; the paths have finite local variation and may have discontinuities. We establish the existence and uniqueness of the process based on a Skorohod equation. This leads to an explicit expression for the process on the doubly-infinite time axis. The expression is especially tractable when the process is stationary with stationary input–output measures. This representation is an extension of the classical Loynes representation of stationary waiting times in single-server queues with stationary inputs and services. We also describe several properties of stationary processes: Palm probabilities of the processes at jump times, Little laws for waiting times in the system, finiteness of moments and extensions to tandem and treelike networks.     

The MacLaurin expansion for a G/G/1 queue with Markov-modulated arrivals and services

Consider a Markov-modulated G/G/1 queueing system in which the arrival and the service mechanisms are controlled by an underlying Markov chain. The classical approaches to the waiting time of this type of queueing system have severe computational difficulties. In this paper, we develop a numerical algorithm to calculate the moments of the waiting time based on Gong and Hu's idea. Our numerical results show that the algorithm is powerful. A matrix recursive equation for the moments of the waiting time is also given under certain conditions.