Queueing systems are systems in which customers arrive, wait their turn to be served, are served by a server, and then depart. Supermarket checkout lines, telephone operator service centers, bank teller windows and doctor's waiting rooms are examples of queueing systems. Queueing systems are advantageously characterized by five components:
1. the customer arrival process (formally described as a stochastic process, e.g. a random counting process that describes the probability that the number of customers arriving in any time interval is a value k), PA1 2. the service time process (more formally described by a probability cumulative distribution function for each time t which indicates the probability that the time required to serve a customer arriving at time t is less than or equal to a value y), PA1 3. the number of servers in the queueing system, PA1 4. the queueing discipline, which describes the order in which customers are taken from the queue (e.g. first come, first served or sickest patient first), and PA1 5. the amount of buffer space in the queue, which describes how long the queue may be before customers are "lost" or turned away from the system.
See, Andrew S. Tanenbaum, Computer Networks, 2 ed., Prentice Hall, Englewood Cliffs, N.J., 1989; R. W. Hall, Queueing Methods for Services and Manufacturing, Prentice Hall, Englewood Cliffs, N.J., 1991.
One important consideration in queueing systems is the determination of how many servers are needed as a function of time. In particular, it is often the case that servers are assigned as function of time in response to anticipated changing loads on the system (i.e., to projected changes in the customer arrival process or to projected changes in the service time required by customers). For example, the problem may be to assign a time-varying number of operators at a telephone office at the beginning of each day where the number of servers is allowed to change every hour or every quarter hour. This general problem is often referred to as the server staffing problem.
It is advantageous to analyze the server staffing problem in queueing systems by partially characterizing components of a queueing system by one or more functions. In particular, the arrival process advantageously is at least partially characterized by an arrival rate, .lambda.(t) (i.e., .lambda.(t).DELTA.t describes the expected number of arrivals in the time interval (t, t+.DELTA.t) for small .DELTA.t). If the arrival process is a Poisson process (useful in describing many chance phenomena), the arrival process is completely characterized by .lambda.(t). See, e.g., A. Papoulis, Probability, Random Variables, and Stochastic Processes, 2 ed., McGraw-Hill, New York, 1984. Otherwise, .lambda.(t) only partially characterizes the arrival process, and other functions, such as those describing variability about the rate .lambda.(t) need to be specified.
The problem of server staffing based on projected loads is a difficult problem if the arrival rates and/or service time processes of the queueing system are not constant (e.g. when .lambda.(t) is not a constant for all t). If the arrival rates and/or service time processes of the queueing system vary with time, then the queueing system is said to be nonstationary. Although the server staffing problem with a stationary arrival rate and stationary service time process has been analyzed extensively, if the queueing system is nonstationary, then it is difficult to determine the number of servers as a function of time, s(t), and approximations are typically used. See, e.g., Hall, supra.
One way to address the nonstationary server staffing problem is to use a steady state analysis. In such an analysis either 1) the arrival rate is assumed to change sufficiently slowly relative to the service times so that steady state formulas can be applied at specific points in time using the arrival rates prevailing at those times or 2) the arrival rate is assumed to be some long term average arrival rate and steady-state formulas are applied using this long term average arrival rate. See, e.g., Hall, supra.
Another way to address the nonstationary server staffing problem is to recognize that the probability distribution of the number of customers present at any given time is advantageously approximated as a normal distribution, which normal distribution is specified by mean and variance parameters. The mean and variance of the approximated normal distribution have been determined by various ad hoc methods, e.g., by refining to the steady state analysis. See, e.g., G. M. Thompson, "Accounting for the Multi-Period Impact of Service When Determining Employee Requirements for Labor Scheduling," J. Opns. Mgmt., vol. 11, pp. 269-288 (1993). Given the probability distribution of the number of customers in the queueing system at time t, it is possible to select the smallest possible value j for the number of servers such that the probability that all j servers are busy at time t is less than or equal to some target value .gamma.. The value .gamma. determines the probability that a customer arriving at time t will encounter a delay before beginning to receive service. If p.sub.n is the probability that the number of customers present is a value n at time t, then j is selected such that ##EQU1##
However, the techniques described above for allocating servers in nonstationary queueing systems typically are not sufficiently accurate to determine server staffing as a function of time. In particular the techniques typically over-allocate servers at some times (thereby increasing system costs since not all servers will be fully utilized) and/or under-allocate servers at other times (thereby causing congestion, i.e. long waiting times for customers in the queue). Hence there is a need for better techniques for allocating servers in nonstationary queueing systems.