Staffing service centers under arrival-rate uncertainty

We consider the problem of staffing large-scale service centers with multiple customer classes and agent types operating under quality-of-service (QoS) constraints. We introduce formulations for a class of staffing problems, minimizing the cost of staffing while requiring that the long-run average QoS achieves a certain pre-specified level. The queueing models we use to define such service center staffing problems have random inter-arrival times and random service times. The models we study differ with respect to whether the arrival rates are deterministic or stochastic. In the deterministic version of the service center staffing problem, we assume that the customer arrival rates are known deterministically.

It is computationally challenging to solve our service center staffing problem with deterministic arrival rates. Thus, we provide an approximation and prove that the solution of our approximation is asymptotically optimal in the sense that the gap between the optimal value of the exact model and the objective function value of the approximate solution shrinks to zero as the size of the system grows large.

In our work, we also focus on doubly stochastic service center systems; that is, we focus on solving large-scale service center staffing problems when the arrival rates are uncertain in addition to the inherent randomness of the system's inter-arrival times and service times. This brings the modeling closer to reality. In solving the service center staffing problems with deterministic arrival rates, we provide a solution procedure for solving staffing problems for doubly stochastic service center systems. We consider a decision making scheme in which we must select staffing levels before observing the arrival rates. We assume that the decision maker has distributional information about the arrival rates at the time of decision making. In the presence of arrival-rate uncertainty, the decision maker's goal is to minimize the staffing cost, while ensuring the QoS achieves a given level. We show that as the system scales large in size, there is at most one key scenario under which the probability of waiting converges to a non-trivial value, i.e., a value strictly between 0 and 1. That is, the system is either over- or under-loaded in any other scenario as the size of the system grows to infinity. Exploiting this result, we propose a two-step solution procedure for the staffing problem with random arrival rates. In the first step, we use the desired QoS level to identify the key scenario corresponding to the optimal staffing level. After finding the key scenario, the random arrival-rate model reduces to a deterministic arrival-rate model. In the second step, we solve the resulting model, with deterministic arrival rate, by using the approximation model we point to above. The approximate optimal staffing level obtained in this procedure asymptotically converges to the true optimal staffing level for the random arrival-rate problem.

The decision making scheme we sketch above, assumes that the distribution of the random arrival rates is known at the time of decision making. In reality this distribution must be estimated based on historical data and experience, and needs to be updated as new observations arrive. Another important issue that arises in service center management is that in the daily operation in service centers, the daily operational period is split into small decision time periods, for example, hourly periods, and then the staffing decisions need to be made for all such time periods. Thus, to achieve an overall optimal daily staffing policy, one must deal with the interaction among staffing decisions over adjacent time periods. In our work, we also build a model that handles the above two issues. We build a two-stage stochastic model with recourse that provides the staffing decisions over two adjacent decision time periods, i.e., two adjacent decision stages. The model minimizes the first stage staffing cost and the expected second stage staffing cost while satisfying a service quality constraint on the second stage operation. A Bayesian update is used to obtain the second-stage arrival-rate distribution based on the first-stage arrival-rate distribution and the arrival observations in the first stage. The second-stage distribution is used in the constraint on the second stage service quality. After reformulation, we show that our two-stage model can be expressed as a newsvendor model, albeit with a demand that is derived from the first stage decision. We provide an algorithm that can solve the two-stage staffing problem under the most commonly used QoS constraints.

This work uses stochastic programming methods to solve problems arising in queueing networks. We hope that the ideas that we put forward in this dissertation lead to other attempts to deal with decision making under uncertainty for queueing systems that combine techniques from stochastic programming and analysis tools from queueing theory.