Minimization of Concave Holding Costs in Queueing System

Since the advent of basic  rule, minimization of holding costs has been one of the most fundamental problems in queueing theory. The first results on holding cost minimization was under the linear cost assumption and the more general case of convex costs has been solved with help of queueing approximation method named heavy traffic. Even with many sophisticated solutions on general settings, there is scarce literature that goes beyond convex or linear cost structure. Especially, a holding cost minimization problem with concave cost structure has not been discuessed yet. As far as we know, our work is the first to study concave cost structure in queueing theory. We study how the customers from multiple classes should be prioritizized. We figure out that so-called bang-bang policy is always included in the set of optimal prioritization policies when the costs are concave and that all the optimal solutions to strict concave costs are bang-bang. With this property, we construct a simple and general solution for the concoave cost minimization problem. We also provide a condition that produces a solution that assigns the whole workload to a single class.