Duality in staffing problems: Between holding costs and waiting constraints

Seung Bum Soh, Itai Gurvich

Research output: Working paper


There are two alternative ways to capture the tension between capacity expenses and customer-delay costs in staffing problems. The cost paradigm assigns a price tag to customer delay and optimizes the combined costs of staffing and waiting. The constraint paradigm, in contrast, replaces the waiting-time cost with constraints and seeks to minimize staffing costs subject to these constraints. The duality of these two formulations is important for both the implementation of delay costs through constraints (e.g., specifying constraints in a contract) and for the reverse engineering of the dollar value that a provider, solving a given constraint formulation, assigns implicitly to customer delay.

In the single-class queue, this duality is a simple matter: the optimal trade-off of capacity and delay can be implemented via a staffing problem with, for example, average waiting constraints. Given the waiting-time constraints that a provider uses, we can figure out the underlying implicit delay costs.

In the multiclass case—where one must determine both the optimal staffing and the optimal prioritization—things become more involved. Strictly convex costs can be reliably implemented by any strictly convex constraints. Linear waiting constraints, while common in practice, do not provide a “safe” implementation of any simple cost structure. They can be made safe, however, by augmenting them with a variance constraint. When seeking to reverse engineer constraints to costs, strictly convex constraints are straightforward. Linear constraints are, however, not uniquely reversible, and strictly concave constraints cannot be an implementation of any strictly increasing waiting costs.

Finally, since strictly convex costs have multiple implementations through constraints, it is desirable to propose a “best” implementation. We numerically study the robustness of different implementations.
Original languageEnglish (US)
Number of pages35
StatePublished - 2014


Dive into the research topics of 'Duality in staffing problems: Between holding costs and waiting constraints'. Together they form a unique fingerprint.

Cite this