Schedule for: 20w2253 - Canadian Queueing Theorists and Practitioners Conference (Online)

A brief introduction to BIRS with important logistical information, technology instruction, and opportunity for participants to ask questions.

In this paper, we study a double-sided queueing model with marked Markovian arrival processes and finite discrete abandonment times. We apply the theory of multi-layer Markov modulated fluid flow (MMFF) processes to analyze the queueing model. First, we define three age processes for the queueing system and convert them into a multi-layer MMFF process. Then we analyze the multi-layer MMFF process to find queueing performance measures related to the age processes, matching rates/probabilities, waiting times, and queue lengths for both sides of the queueing system. We obtain a number of aggregate quantities as well as quantities for individual types of inputs, which can be useful for the analysis and design of, for examples, passenger-taxi service systems and organ transplantation systems.

We consider a class of phase-type distributions, to be called the MMPP class of PH-distributions, and find bounds of their mean and squared coefficient of variation (SCV). As an application, we have shown that the SCV of the event-stationary inter-event time of Markov modulated Poisson processes (MMPPs) is greater than or equal to unity, which answers an open problem about MMPPs

We study the asymptotic periodic distribution of queues with time-varying periodic transition rates and catastrophes that occur randomly according to an exponential distribution with time-varying periodic rate. When a disaster occurs, the system resets, all customers are lost and an exponentially distributed period of time elapses before the repair is complete. Service is governed by a phase distribution. The asymptotic periodic distribution of the queue process is analogous to the steady state distribution for a system with constant transition rates.

We are concerned with an M /M /- join the shortest queue model with N parallel queues for an arbitrary large N, in which each queue has a dedicated input stream. Each server has an exponential service rate μ. Assuming the steady-state case, a bayesian paradigm is used in estimating the traffic intensity based on queue length data only and based on the mean field interaction model for the limiting behavior of the JSQ model studied by Daw- son et al. (2019) . Several prior distributions are taken into account and numerical results show the accuracy of our estimate of the traffic intensity.

In this paper, we construct the bound copula, which can reach both Frechet's lower and upper bounds for perfect positive and negative dependence cases. Since it has a wide range of dependency, it can be very useful. This new copula is simple for the computational purpose. It is very difficult to use copulas such as Archemedes, Guassian, $t$-copula to find the distribution function and the expected value in explicit form. For both copulas, we derive the strength of measures of the dependency such as Spearman's rho, Kendall's tau, Blomqvist's beta and Gini's gamma, and the coefficients of the tail dependency. For the application part, we analyze the dependency between two service times to evaluate the mean waiting time and the mean service time when customers launch two replicas of each task on two parallel servers using the cancel-on-finish policy. We assume that the inter-arrival time is exponential and the service time is general.

Assume that the time to complete a task without interruption is T. Assume interruptions occur according to a Poisson process with rate lambda. If a process is interrupted, it must begin again. Let W be the total time to completion. We find the Laplace transform of W. One application is a solution of the classic problem of the time to cross a one way street assuming Poisson traffic.

Powerpoint slides: Click here

Algorithms for queueing systems with reneging and priorities modeled as quasi-birth-death processes By Amir Rastpour, Ontario Tech. University Abstract: We develop an iterative algorithm for a class of infinite level-dependent quasi-birth-and-death (LDQBD) systems. The class of queueing systems that we focus on includes the Erlang A system with two priority classes where customers from both classes are impatient, and they can have different arrival, service, and abandonment rates. Our algorithm provides upper and lower bounds for stationary probabilities and automatically proceeds until a pre-specified error tolerance is achieved. Our algorithm exploits an approach that can be used to obtain element-wise bounds for the rate matrix of any LDQBD system within any desired error tolerance. We generate a wide range of instances and perform numerical analyses on them. We report numerical results and discuss algorithm limitation, accuracy and speed.

When job sizes are known, Shortest Remaining Processing Time (SRPT) is known to be an optimal (in a very strong sense) scheduling policy for a single server queue under general assumptions on underlying random variables. However, the performance of SRPT is known not to be robust to errors in processing time estimates. For a popular error model, we characterize the optimal policy using a Gittins Index approach and discuss its properties. The implementability of the policy is studied, with the structure of the optimal policy guiding heuristic policies that appear to perform well. Time permitting, issues for multiple server queues will be highlighted.

There are many applications where users of different types arrive to a finite set of resources and request temporary use of subsets of these resources. The manager of the resources is entitled to charge for their use and might incur some costs in making them available.

In this context, the manager has an admission control problem. Given the current state of allocation, can they admit a user of a particular type? If they can, should they, or wait for a more lucrative user to arrive in the future? In the situation where a user is indifferent between different sets of resources, which ones should they choose?

In this talk I shall discuss my long history of engaging with different versions of this problem, culminating with some current work with Jing Fu and Bill Moran in which we are looking at a restless multi-armed bandit formulation.

Monte Carlo simulation is one of the most successful techniques, not only in operations research and performance evaluation, but in science in general. One reason for this extraordinary success is its flexibility. In contrast, most queueing models are rather specialized. In this talk, we suggest methods to make queueing theory more flexible. In particular, we suggest an event-based approach, which provides great flexibility for the modeller. We also show how to convert such event-based models into Markov chains, which can then be solved by classical numerical methods. The suggested method is particularly suited for small models, where its execution times are much lower than Monte-Carlo simulation. For larger problems, the curse of dimensionality takes over, and the execution times based on classical numerical methods increase exponentially. This means that for complex models, simulation finds numerical solutions with less computer time than classical numerical methods.

Powerpoint slides: Click here

In this talk, we provide a method, called L, based on distributional law of Little (DLL) to determine the equilibrium distribution of the number of elements in a discrete-time GI/G/1 queueing system. We also clarify a number of issues, and provide a number of new results. We assume that the inter-arrival times range from 1 to g+1 and the service times from 1 to h+1. The majority of authors have formulated the system in question as a quasi birth and death process, which can be solved by the matrix iterative methods pioneered by Neuts, methods that are cubic in the number of phases, and in fact, if g=h, all matrix analytic methods we found in literature are cubic in g, or worse. In contrast, our method L, which finds the distribution of the number of elements in the system in quadratic time. This implies that for large enough g and h, our algorithm will outperform all cubic algorithms, a claim verified by numerical tests. In particular, for realistic values g and h, algorithm L is more than 50 times faster than the different algorithms based on matrix analytic methods we found in literature.

Using Mazur’s theorem on torsions of elliptic curves, an upper bound 24 for the order of the finite Galois group H associated with weighted walks in the quarter plane Z2+ is obtained. The explicit criterion of H having order 4 or 6 is given by geometric argument. Using division polynomial, a recursive criterion for H having order 4m or 4m + 2 is also obtained and explicit criterion for H having order 8 is given.

Standing orders allow triage nurses in emergency departments (EDs) to order tests for certain medical conditions before the patient sees a physician, which could reduce the patient’s ED length of stay (LOS). Several studies in the medical literature documented a decrease in average ED LOS for a target patient population, resulting from the use of standing orders. We formulate models of the operational impact of standing orders and test several policies for whether to order tests at triage for individual target patients, as a function of ED congestion. We find that a threshold policy, with a threshold whose value can be estimated easily from model primitives, performs well across a wide range of parameter values. We demonstrate potential unintended consequences of the use of standing orders, including over testing and spillover effects on non-target patients.

We consider the customers' equilibrium strategy and socially optimal strategy in a single server Markovian queueing system with changeable service rates controlled by a threshold. When a customer arrives at an empty system, he is served by the server at a lower service rate. When the queue length reaches the threshold, customers are served at a high service rate. The optimal joining strategies of customers are studied under two information scenarios. The first scenario, where the server' state and the queue length are observable, is called a fully observable case. The second scenario, where the system state is not observable, is called an unobservable case. We analyze the steady-state distribution and performance measures of the system, and derive the equilibrium strategy. Finally, we compare the equilibrium strategy with socially optimal strategy via numerical examples.

Blood transfusion is one of the most crucial and commonly administered therapeutics worldwide. The need for more accurate and efficient ways to manage blood demand and supply is an increasing concern in many healthcare systems. Building a technology-based, robust blood demand and supply chain that can achieve the goals of reducing ordering frequency, inventory level, wastage and shortage, while maintaining the safety of blood usage, is essential in modern healthcare systems. In this study, we summarize the key challenges in current demand and supply management for red blood cells (RBCs). We combine ideas from statistical time series modeling, machine learning, and operations research in developing an ordering decision strategy for RBCs integrating a hybrid demand forecasting model using clinical predictors, and a data-driven multi-period inventory problem considering inventory and reorder constraints. We have applied the integrated ordering strategy to the blood inventory management system in Hamilton, Ontario using a large clinical database from 2008 to 2018. The proposed hybrid demand forecasting model provides robust and accurate predictions, and identifies important clinical predictors for short-term RBC demand forecasting. Compared with the actual historical inventory levels, ordering decisions, and wastage due to expiration, our integrated ordering strategy reduces the inventory level by approximately 40% and decreases the ordering frequency by approximately 60%, with low incidence of shortages and wastage due to expiration. If implemented successfully, our proposed strategy can achieve significant cost savings for healthcare systems and blood suppliers. The proposed ordering strategy is generalizable to other blood products or even other perishable products.

We present a Queueing and Markov chain decomposition method based on the total expectation theorem. Our decomposition method requires partial flow to be conserved, which we call a termination scheme. This scheme is useful when deriving analytical formulas for complex queueing systems. As an example, we apply our method to derive an exact set of stationary equations for the probability generating functions of decomposed chains of Markov-modulated continuous-time Markov chains.

The Transmission Control Protocol (TCP) is one of the main protocols of the Internet protocol suite and major internet applications rely on it. The TCP protocol provides reliability, flow control and congestion control. Alongside the TCP, the User Datagram Protocol (UDP) is another transport protocol which, in contrast to TCP, is a simplified request-response protocol that does not have any connection setup time and does not provide any flow, congestion or error controls. We consider in this presentation a fluid model for multiple TCP and UDP connections interacting through a network of queues. We suppose that the connections are randomly routed according to a dynamical routing table protocol which takes into account the topology of the network and adapts the routing dynamically. Our model extends the multi-class model studied in Graham et al (2009). The dynamic of the TCP flows follows the additive increase/multiplicative-decrease (AIMD) protocol and is represented by a stochastic differential equation w.r.t. a Poisson random measure and the UDP flows are represented by simple point processes. Using an adequate scaling, a mean-field result is proved where, as the number of connections goes to infinity, the behaviour of the different connections can be represented by the solution of an original nonlinear stochastic differential equation. The existence and uniqueness of the solution of this equation are derived. Moreover, we discuss some open problems and possible extensions. This talk is based on a current ongoing joint work with Donald A.Dawson and Yiqiang Q.Zhao.