Search

We study the problem of staffing (specifying a time-varying number of servers) and scheduling (assigning newly idle servers to a waiting customer from one of [Formula: see text] classes) in the many-server V model with class-dependent time-varying arrival rates. In order to stabilize performance at class-dependent delay targets, we propose the blind (model-free) head-of-line delay-ratio (HLDR) scheduling rule, which extends an earlier dynamic-priority rule that exploits the head-of-line delay information. We study the HLDR rule in the quality-and-efficiency-driven many-server heavy-traffic (MSHT) regime. We staff to the MSHT fluid limit plus a control function in the diffusion scale. We establish a MSHT limit for the Markov model, which has dramatic state-space collapse, showing that the targeted ratios are attained asymptotically. In the MSHT limit, meeting staffing goals reduces to a one-dimensional control problem for the aggregate queue content, which may be approximated by recently developed staffing algorithms for time-varying single-class models. Simulation experiments confirm that the overall procedure can be effective, even for non-Markov models. The online appendix is available at https://doi.org/10.1287/stsy.2018.0015 .

Heavy-traffic limits are established for the stationary departure process from a GI/GI/1 queue and its variance function. The limit process is a function of the Brownian motion limits of the arrival and service processes plus the stationary reflected Brownian motion (RBM) limit of the queue-length process. An explicit expression is given for the variance function, which depends only on the first two moments of the interarrival times and service times plus the previously determined correlation function of canonical (drift −1, diffusion coefficient 1) RBM. The limit for the variance function here is used to show that the approximation for the index of dispersion for counts of the departure process used in our new robust queueing network analyzer is asymptotically correct in the heavy-traffic limit.

We develop a flexible and efficient simulation algorithm of a stochastic (queueing network) model of group play over a conventional 18-hole golf course. We apply this algorithm to study ways to imp...

To understand the performance of a queueing system, it can be useful to focus on the evolution of the content that is initially in service at some time. That necessarily will be the case in service systems that provide service during normal working hours each day, with the system shutting down at some time, except that all customers already in service at the termination time are allowed to complete their service. Also, for infinite-server queues, it is often fruitful to partition the content into the initial content and the new input, because these can be analyzed separately. With i.i.d service times having a non-exponential distribution, the state of the initial content can be described by specifying the elapsed service times of the remaining initial customers. That initial content process is then a Markov process. This paper establishes a many-server heavy-traffic (MSHT) functional central limit theorem (FCLT) for the initial content process in the space 𝔻𝔻, assuming a FCLT for the initial age process, with the number of customers initially in service growing in the limit. The proof applies a symmetrization lemma from the literature on empirical processes to address a technical challenge: For each time, including time 0, the conditional remaining service times, given the ages, are mutually independent but in general not identically distributed.

This article proposes an approximation for the blocking probability in a many-server loss model with a non-Poisson time-varying arrival process and flexible staffing (number of servers) and shows that it can be used to set staffing levels to stabilize the time-varying blocking probability at a target level. Because the blocking probabilities necessarily change dramatically after each staffing change, we randomize the time of each staffing change about the planned time. We apply simulation to show that (i) the blocking probabilities cannot be stabilized without some form of randomization, (ii) the new staffing algorithm with randomiation can stabilize blocking probabilities at target levels and (iii) the required staffing can be quite different when the Poisson assumption is dropped.© 2017 Wiley Periodicals, Inc. Naval Research Logistics, 2017

This paper develops an aggregate stochastic model of an emergency department (ED) based on a careful study of data on individual patient arrival times and length of stay in the ED of the Rambam Hospital in Israel, which was used in a large-scale exploratory data analysis by Armony et al. (2015). This data set is of special interest because it has been made publicly available, so that the experiments are reproducible. Our analysis confirms the previous conclusions about the time-varying arrival rate and its consequences, but we also find that the probability of admission to an internal ward from the ED and the patient length-of-stay distribution should be time varying as well. Our analysis culminates in a new time-varying infinite-server aggregate stochastic model of the ED, where both the length-of-stay distribution and the arrival rate are periodic over a week.

Motivated by non-Poisson stochastic variability found in service system arrival data, we extend established service system staffing algorithms using the square-root staffing formula to allow for non-Poisson arrival processes. We develop a general model of the non-Poisson non-stationary arrival process that includes as a special case the non-stationary Cox process (a modification of a Poisson process in which the rate itself is a non-stationary stochastic process), which has been advocated in the literature. We characterize the impact of the non-Poisson stochastic variability upon the staffing through the heavy-traffic limit of the peakedness (ratio of the variance to the mean in an associated stationary infinite-server queueing model), which depends on the arrival process through its central limit theorem behavior. We provide simple formulas to quantify the performance impact of the non-Poisson arrivals upon the staffing decisions, in order to achieve the desired service level. We conduct simulation experiments with non-stationary Markov-modulated Poisson arrival processes with sinusoidal arrival rate functions to demonstrate that the staffing algorithm is effective in stabilizing the time-varying probability of delay at designated targets.

Motivated by applications to service systems, we develop simple engineering approximation formulas for the steady-state performance of heavily loaded G/GI/n+GI multiserver queues, which can have non-Poisson and nonrenewal arrivals and non-exponential service-time and patience-time distributions. The formulas are based on recently established Gaussian many-server heavy-traffic limits in the efficiency-driven (ED) regime, where the traffic intensity is fixed at ρ > 1, but the approximations also apply to systems in the quality-and-ED regime, where ρ > 1 but ρ is close to 1. Good performance across a wide range of parameters is obtained by making heuristic refinements, the main one being truncation of the queue length and waiting time approximations to nonnegative values. Simulation experiments show that the proposed approximations are effective for large-scale queuing systems for a significant range of the traffic intensity ρ and the abandonment rate θ, roughly for ρ > 1.02 and θ > 2.0. © 2016 Wiley Periodicals, Inc. Naval Research Logistics, 2016

A nonstationary point process can be efficiently simulated by exploiting a representation as the composition of a rate-one process and the cumulative arrival rate function, provided that an efficient algorithm is available for generating the rate-one process, as is the case for stationary renewal processes, Markov modulated Poisson processes and many other processes. Overall efficiency can be achieved by constructing a table of the inverse cumulative arrival rate function when it is not explicitly available.

The modified-offered-load approximation can be used to choose a staffing function (the time-varying number of servers) to stabilize delay probabilities at target levels in multi-server delay models with time-varying arrival rates, with or without customer abandonment. In contrast, as we confirm with simulations, it is not possible to stabilize blocking probabilities to the same extent in corresponding loss models, without extra waiting space, because these probabilities necessarily change dramatically after each staffing change. Nevertheless, blocking probabilities can be stabilized provided that we either randomize the times of staffing changes or average the blocking probabilities over a suitably small time interval. We develop systematic procedures and study how to choose the averaging parameters.

If the number of customers in a queueing system as a function of time has a proper limiting steady-state distribution, then that steady-state distribution can be estimated from system data by fitting a general stationary birth-and-death (BD) process model to the data and solving for its steady-state distribution using the familiar local-balance steady-state equation for BD processes, even if the actual process is not a BD process. We show that this indirect way to estimate the steady-state distribution can be effective for periodic queues, because the fitted birth and death rates often have special structure allowing them to be estimated efficiently by fitting parametric functions with only a few parameters, for example, 2. We focus on the multiserver Mt/GI/s queue with a nonhomogeneous Poisson arrival process having a periodic time-varying rate function. We establish properties of its steady-state distribution and fitted BD rates. We also show that the fitted BD rates can be a useful diagnostic tool to see if an Mt/GI/s model is appropriate for a complex queueing system. © 2015 Wiley Periodicals, Inc. Naval Research Logistics, 2015

We develop performance approximations that can help manage the pace of play in golf. In previous work we developed a stochastic model of successive groups of golfers playing on an 18-hole golf course and derived expressions for the capacity (maximum possible throughput) of each hole and the golf course as a whole. That model captures the realistic feature that, on most holes, more than one group can be playing at the same time, with precedence constraints. We now facilitate further performance analysis with that model by developing two new approximations. First, we develop an approximation involving a series of conventional single-server queues, without precedence constraints. The key idea is to use the times between successive departures on a fully loaded hole as aggregate service times in the new model. Second, we apply established heavy-traffic limits for a series of conventional queues to develop explicit approximation formulas for the mean and variance of the time required for group n to play the entire course, as a function of n. We conduct simulation experiments showing that both approximations are effective. We show how these formulas can help design and manage a golf course.

We develop stochastic models to help manage the pace of play on a conventional 18-hole golf course. These models are for group play on each of the standard hole types: par-3, par-4, and par-5. These models include the realistic feature that k−2 groups can be playing at the same time on a par-k hole, but with precedence constraints. We also consider par-3 holes with a “wave-up” rule, which allows two groups to be playing simultaneously. We mathematically determine the maximum possible throughput on each hole under natural conditions. To do so, we analyze the associated fully loaded holes, in which new groups are always available to start when the opportunity arises. We characterize the stationary interval between the times successive groups clear the green on a fully loaded hole, showing how it depends on the stage playing times. The structure of that stationary interval evidently can be exploited to help manage the pace of play. The mean of that stationary interval is the reciprocal of the capacity. The bottleneck holes are the holes with the least capacity. The bottleneck capacity is then the capacity of the golf course as a whole.

This paper investigates extensions to feed-forward queueing networks of an algorithm to set staffing levels (the number of servers) to stabilize performance % at Quality of Service (QoS) targets in anMt/GI/st+GImulti-server queue with a time-varying arrival rate. The model has a non-homogeneous Poisson process (NHPP), customer abandonment, and non-exponential service and patience distributions. For a single queue, simulation experiments showed that the algorithm successfully stabilizes abandonment probabilities and expected delays over a wide range of Quality-of-Service (QoS) targets. A limit theorem showed that stable performance at fixed QoS targets is achieved asymptotically as the scale increases (by letting the arrival rate grow while holding the service and patience distributions fixed). Here we extend that limit theorem to a feed-forward queueing network. However, these fixed QoS targets provide low QoS as the scale increases. Hence, these limits primarily support the algorithm with a low QoS target. For a high QoS target, effectiveness depends on the NHPP property, but the departure process never is exactly an NHPP. Thus, we investigate when a departure process can be regarded as approximately an NHPP. We show that index of dispersion for counts is effective for determining when a departure process is approximately an NHPP in this setting. In the important common case when all queues have high QoS targets, we show that both: (i) the departure process is approximately an NHPP from this perspective and (ii) the algorithm is effective.

Service systems such as call centers and hospital emergency rooms typically have strongly time-varying arrival rates. Thus, a nonhomogeneous Poisson process (NHPP) is a natural model for the arrival process in a queueing model for performance analysis. Nevertheless, it is important to perform statistical tests with service system data to confirm that an NHPP is actually appropriate, as emphasized by Brown et al. [8]. They suggested a specific statistical test based on the Kolmogorov–Smirnov (KS) statistic after exploiting the conditional-uniform (CU) property to transform the NHPP into a sequence of i.i.d. random variables uniformly distributed on [0,1] and then performing a logarithmic transformation of the data. We investigate why it is important to perform the final data transformation and consider what form it should take. We conduct extensive simulation experiments to study the power of these alternative statistical tests. We conclude that the general approach of Brown et al. [8] is excellent, but that an alternative data transformation proposed by Lewis [22], drawing upon Durbin [10], produces a test of an NHPP test with consistently greater power. We also conclude that the KS test after the CU transformation, without any additional data transformation, tends to be best to test against alternative hypotheses that primarily differ from an NHPP only through stochastic and time dependence. © 2014 Wiley Periodicals, Inc. Naval Research Logistics 61: 66–90, 2014

When waiting times cannot be observed directly, Little's law can be applied to estimate the average waiting time by the average number in system divided by the average arrival rate, but that simple indirect estimator tends to be biased significantly when the arrival rates are time-varying and the service times are relatively long. Here it is shown that the bias in that indirect estimator can be estimated and reduced by applying the time-varying Little's law (TVLL). If there is appropriate time-varying staffing, then the waiting time distribution may not be time-varying even though the arrival rate is time varying. Given a fixed waiting time distribution with unknown mean, there is a unique mean consistent with the TVLL for each time t. Thus, under that condition, the TVLL provides an estimator for the unknown mean wait, given estimates of the average number in system over a subinterval and the arrival rate function. Useful variants of the TVLL estimator are obtained by fitting a linear or quadratic function to arrival data. When the arrival rate function is approximately linear (quadratic), the mean waiting time satisfies a quadratic (cubic) equation. The new estimator based on the TVLL is a positive real root of that equation. The new methods are shown to be effective in estimating the bias in the indirect estimator and reducing it, using simulations of multi-server queues and data from a call center.

Given measurements of the number of customers in a queueing system over a finite time interval, it is natural to try to fit a stationary birth-and-death process model, because it is remarkably tractable, even when the birth and death rates depend on the state in an arbitrary way. Natural estimators of the birth (death) rate in each state are the observed number of transitions up (down) from that state divided by the total time spent in that state. It is tempting to validate the model by comparing the steady-state distribution of the model based on those estimated rates to the empirical steady-state distribution recording the proportion of time spent in each state. However, it is inappropriate to draw strong conclusions from a close fit to the same data, because these two distributions are necessarily intimately related, even if the model assumptions are not nearly satisfied. We elaborate by (i) establishing stochastic comparisons between these two fitted distributions using likelihood-ratio stochastic ordering and (ii) quantifying their difference.

Motivated by large-scale service systems, we consider an infinite-server queue with batch arrivals, where the service times are dependent within each batch. We allow the arrival rate of batches to be time varying as well as constant. As regularity conditions, we require that the batch sizes be i.i.d. and independent of the arrival process of batches, and we require that the service times within different batches be independent. We exploit a recently established heavy-traffic limit for the number of busy servers to determine the performance impact of the dependence among the service times. The number of busy servers is approximately a Gaussian process. The dependence among the service times does not affect the mean number of busy servers, but it does affect the variance of the number of busy servers. Our approximations quantify the performance impact upon the variance. We conduct simulations to evaluate the heavy-traffic approximations for the stationary model and the model with a time-varying arrival rate. In the simulation experiments, we use the Marshall–Olkin multivariate exponential distribution to model dependent exponential service times within a batch. We also introduce a class of Marshall–Olkin multivariate hyperexponential distributions to model dependent hyper-exponential service times within a batch.

Under general conditions, the number of customers in a GI/D/s + GI many-server queue at time t converges to a unique stationary distribution as t → ∞. However, simulations show that the sample paths routinely exhibit nearly periodic behavior over long time intervals when the system is overloaded and s is large, provided that the system does not start in steady state. Moreover, the precise periodic behavior observed depends critically on the initial conditions. We provide insight into the transient behavior by studying the deterministic fluid model, which arises as the many-server heavy-traffic limit. The limiting fluid model also has a unique stationary point, but that stationary point is not approached from any other initial state as t → ∞. Instead, the fluid model performance approaches one of its uncountably many periodic steady states, depending on the initial conditions. Simulation experiments confirm that the time-dependent performance of the stochastic queueing model is well approximated by the fluid model. Like the fluid model, the behavior of the queueing system can be highly sensitive to the initial conditions over long intervals of time.

We develop new improved real-time delay estimators, based on recent customer delay history, in many-server service systems with time-varying arrivals, both with and without customer abandonment. These delay estimators may be used to make delay announcements. We model the arrival process by a nonhomogeneous Poisson process, which has a deterministic time-varying arrival-rate function. Our estimators eectively cope with time-varying arrivals

A lockup period for investment in a hedge fund is a time period after making the investment during which the investor cannot freely redeem his investment. It is routine to have a one-year lockup period, but recently the requested lockup periods have grown longer. We estimate the premium for such extended lockup, taking the point of view of a manager of a fund of funds, who has to choose between two investments in similar funds in the same strategy category, the first having a one-year lockup and the second having an n-year lockup. Assuming that the manager will rebalance his portfolio of hedge funds on a yearly basis, if permitted, we define the annual lockup premium as the difference between the rates of return from these investments. We develop a Markov chain model to estimate this lockup premium. By solving systems of equations, we fit the Markov chain transition probabilities to three directly observable hedge fund performance measures: the persistence of return, the variance of return and the hedge-fund death rate. The model quantifies the way the lockup premium depends on these parameters. Data from the TASS database are used to estimate the persistence, which is found to be statistically significant. Copyright © 2009 Wilmott Magazine Ltd