  Service systems are labor intensive due to the large variation in the tasks
required to address service requests from multiple customers. Aligning the
staffing levels to the forecasted workloads adaptively in such systems is
nontrivial because of a large number of parameters and operational variations
leading to a huge search space. A challenging problem here is to optimize the
staffing while maintaining the system in steady-state and compliant to
aggregate service level agreement (SLA) constraints. Further, because these
parameters change on a weekly basis, the optimization should not take longer
than a few hours. We formulate this problem as a constrained Markov cost
process parameterized by the (discrete) staffing levels. We propose novel
simultaneous perturbation stochastic approximation (SPSA) based SASOC (Staff
Allocation using Stochastic Optimization with Constraints) algorithms for
solving the above problem. The algorithms include both first order as well as
second order methods and incorporate SPSA based gradient estimates in the
primal, with dual ascent for the Lagrange multipliers. Both the algorithms that
we propose are online, incremental and easy to implement. Further, they involve
a certain generalized smooth projection operator, which is essential to project
the continuous-valued worker parameter tuned by SASOC algorithms onto the
discrete set. We validated our algorithms on five real-life service systems and
compared them with a state-of-the-art optimization tool-kit OptQuest. Being 25
times faster than OptQuest, our algorithms are particularly suitable for
adaptive labor staffing. Also, we observe that our algorithms guarantee
convergence and find better solutions than OptQuest in many cases.
