Simulation-based cutting plane methods for optimization of service systems.

摘要

Simulation is a powerful tool for analyzing a complex system. When decisions need to be made about the operating policies and settings of a system, some form of optimization is required. In this dissertation we develop two iterative subgradient based cutting plane methods for solving resource allocation problems in service systems, when the objective function and or the constraints are evaluated via simulation. This work is motivated by the call center staffing problem of minimizing cost while maintaining an acceptable level of service over multiple time periods. An analytical expression of the expected service level function in each period is typically not available. Instead, we formulate a sample average approximation (SAA) of the staffing problem. A proof of convergence is given for conditions under which the solutions of the SAA converge to the solutions of the original problem as the sample size increases. In addition, we prove that this occurs at an exponential rate with increasing sample size.; In some cases it is reasonable to assume that the expected service level functions are concave in the number of workers assigned in each period. In such cases, we show how Kelley's cutting plane method can be applied to solve the SAA. Empirical results suggest, however, that the expected service level function is approximately pseudoconcave. In that case, we develop the simulation-based analytic center cutting plane method (SACCPM). Proofs of converge for both methods are included.; Our cutting plane methods use subgradient information to iteratively add constraints that are violated by non-optimal solutions. Computing the subgradients is a particularly challenging problem. We suggest and compare three existing techniques for computing gradients via simulation: the finite difference method, the likelihood ratio method, and infinitesimal perturbation analysis. We show how these techniques can be applied to approximate the subgradients, even when the variables, i.e., number of workers, are discrete.; Finally, we include numerical implementations of the methods and an extensive numerical study that suggests that the SACCPM usually does as well and often outperforms traditional queuing methods for staffing call centers in a variety of settings.