Staffing and control of many-server service systems

This dissertation considers large-scale service systems with multiple customer classes and agent types. Customers are classified according to their processing requirements, service-level guarantees, or both. The customers are served by agents of different types. These are classified according to the subset of customer classes that they can serve.;We consider the problem of optimally choosing the capacity allocations of the different agent types and the real-time routing of costumers to agents. As a first step towards solving two such optimization problems, we introduce and analyze the Queue-and-Idleness-Ratio (QIR) family of routing rules. The QIR rules are defined as follows: (i) an arriving customer is routed to the agent pool (among those that are eligible to serve him) whose idleness most exceeds a specified state-dependent proportion of the total number of idle agents, summed over all types; (ii) a newly-available agent serves the customer from the head of the queue (from among those he is eligible to serve) whose length most exceeds a specified state-dependent proportion of total queue length, summed over all classes. We identify regularity conditions on the network structure and on the system parameters under which QIR produces an important State-Space Collapse (SSC) in the Quality-and-Efficiency-Driven (QED) many-server heavy-traffic regime. We also provide convergence results for various performance measures.;The QIR family of rules is central to the solution of two optimization problems: Staffing subject to service-level targets. We consider the problem of minimizing labor costs subject to service-level constraints that are defined through probabilistic bounds on the waiting time. Agents of different types can have different salary costs. We show that a special case of QIR in which the queue ratios are fixed, i.e., a Fixed-Queue-Ratio (FQR) routing rule, can be used to construct solutions for this practical problem. The proportions can be set to achieve desired service-level constraints for all classes; these targets are achieved asymptotically as the total arrival rate increases. The SSC obtained under QIR facilitates establishing asymptotic results. In simplified settings, SSC allows us to solve a combined design-staffing-and-routing problem in a nearly optimal way. In other cases it provides a simple yet feasible solution at reasonable costs, namely, a solution that guarantees the achievement of the service-levels for the different classes while keeping the staffing costs reasonably close to optimality. Holding cost minimization. We consider also the problem of minimizing convex holding-costs. In the case where service rates depend on the agent type but not on the customer class (pool-dependent service rates), QIR with appropriately-chosen ratio functions is shown to be asymptotically optimal in the QED many-server heavy-traffic regime. In special cases, the QIR solution is reduced to a simple policy: linear costs produce a priority-type rule, in which the least-cost customers are given low priority. Strictly convex costs (plus other regularity conditions) produce a many-server analogue of the generalized-cmu ( Gcmu) rule, under which a newly-available agent selects a customer from the class experiencing the greatest marginal cost at that time.