A Lower Bounding Result for the Optimal Policy in an Adaptive Staffing Problem

We derive a lower bound for the staffing levels required to meet a projected load in a retail service facility. We model the queueing system as a Markovian process with non-homogeneous Poisson arrivals. Motivated by an application from the postal services, we assume that the arrival rate is piecewise constant over the time horizon and retain such transient effects as build-up in the system. The optimal staffing decision is formulated as a multiperiod dynamic programming problem where staff is allocated to each time period to minimize the total costs over the horizon. The main result is the derivation of a lower bound on the staffing requirements that is computed by decoupling successive time periods. Keywords: dynamic programming, staffing, service operations 1 M.C. Fu is supported in part by the National Science Foundation under Grant No. NSF EEC 94-02384. 1 Introduction Queueing theory is frequently used to determine the staffing required to meet a desired level of service. Stan..