Minimization of Concave Holding Costs in Queueing System

국문 초록 (Abstract)

기초적인 cµ 규칙이 발견된 시기부터 대기 시간과 관련한 비용을 최소화하는 것은 대기행렬이론에서 가장 중요한 문제 중 하나였다. 대기 시간 비용 최소화와 관련한 기초적인 결과는 비용이 선형적으로 증가한다는 가정에 의거한 것이었고 더 일반적인 볼록 함수비용의 경우 대기행렬을 근사하는 기법을 이용하여 최적해를 구했다. 지금까지 다양한 설정에서 어떤 최적해가 가능한지에 대한 연구가 이루어졌지만 선형 함수나 볼록 함수가 아닌 대기 비용 함수의 경우 최적해의 성질은 어떻게 되는지에 대해서는 충분한 연구가 이루어지지 않았다. 본 연구는 특히 연구가 이루어지지 않은 오목 비용 함수에 대해 다룬다. 본 연구 역시 대기행렬 근사를 통해 최적해를 도출한다.
본 연구에서는 고객 집단이 세분화되어있을 때 서비스 우선권이 어떻게 배분되어야 하는지를 다룬다. 모든 고객군의 대기 비용이 오목 비용 함수인 경우 온오프 조절(bang bang policy)이 최적해의 집합에 반드시 포함된다는 것을 보였고, 특히 대기 비용이 강오목함수인 경우 온오프 조절만이 최적해라는 것을 보였다. 이 특성을 통해 오목 비용 함수를 최소화하는 일반해를 도출한다. 추가적으로 모든 대기열이 하나의 고객군에 집적되는 것이 최적이도록 하는 조건도 도출된다.

다국어 초록 (Multilingual Abstract)

Since the advent of basic cµ 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.

목차 (Table of Contents)

• ABSTRACT
• 요약
• Ⅰ. Introduction
• Ⅱ. Literature Review
• Ⅲ. Model Setting
• Ⅳ. Heavy Traffic Model
• Ⅴ. State Space Collapse
• Ⅵ. Optimal Solution
• Ⅶ. Concluding Remark
• References

참고문헌 (Reference)

1 Smith, W. E., "Various optimizers for single-stage production" 3 (3): 59-66, 1956

2 Kleinrock, L., "Time dependent priority queues" 15 (15): 104-116, 1967

3 Neustadt, L. W., "The existence of optimal controls in the absence of convexity conditions" 7 (7): 110-117, 1963

4 Sonneborn, L. M., "The bang-bang principle for linear control systems" 2 (2): 151-159, 1964

5 Whitt, W., "Stochastic-process limits: an introduction to stochastic-process limits and their application to queues" Springer Science & Business Media 2002

6 Mandelbaum, A., "Scheduling flexible servers with convex delay costs:Heavy-traffic optimality of the generalized cμ-rule" 52 (52): 836-855, 2004

7 Gurvich, I., "Scheduling flexible servers with convex delay costs in many-server service systems" 11 (11): 237-253, 2009

8 Atar, R., "Scheduling control for queueing systems with many servers: Asymptotic optimality in heavy traffic" 15 (15): 2606-2650, 2005

9 Cox, D. R., "Queues. Methuen" 1961

10 Gurvich, I., "Queue-and-idleness-ratio controls in many-server service systems" 34 (34): 363-396, 2009

11 Dai, J. G., "Optimal control of parallel server systems with many servers in heavy traffic" 59 (59): 95-, 2008

12 Bellman, R., "On the “bang-bang” control problem" 14 (14): 11-18, 1956

13 Ata, B., "On scheduling a multiclass queue with abandonments under general delay costs" 74 (74): 65-104, 2013

14 Ata, B., "Near-optimal dynamic lead-time quotation and scheduling under convex-concave customer delay costs" 57 (57): 753-768, 2009

15 Guisewite, G. M., "Minimum concave-cost network flow problems:Applications, complexity, and algorithms" 25 (25): 75-99, 1990

16 Zangwill, W. I., "Minimum concave cost flows in certain networks" 14 (14): 429-450, 1968

17 Halfin, S., "Heavy-traffic limits for queues with many exponential servers" 29 (29): 567-588, 1981

18 Angell, T. S., "Existence of optimal control without convexity and a bang-bang theorem for linear Volterra equations" 19 (19): 63-79, 1976

19 Van Mieghem, J. A., "Dynamic scheduling with convex delay costs: The generalized cμ rule" 809-833, 1995

20 Tezcan, T., "Dynamic control of N-systems with many servers: Asymptotic optimality of a static priority policy in heavy traffic" 58 (58): 94-110, 2010

21 Artstein, Z., "Discrete and continuous bang-bang and facial spaces or: Look for the extreme points" 22 (22): 172-185, 1980

22 Bushaw, D., "Differential equations with a discontinuous forcing term" Princeton University. 1952

23 Billingsley, P., "Convergence of probability measures" John Wiley &Sons 2013

24 Akan, M., "Congestion-based lead-time quotation for heterogenous customers with convex-concave delay costs: Optimality of a cost-balancing policy based on convex hull functions" 60 (60): 1505-1519, 2012

25 De Wilde, M., "A note on the bang-bang principle" 2 (2): 753-759, 1969

26 Netterman, A., "A dynamic priority queue with general concave priority functions" 27 (27): 1088-1100, 1979

27 Kleinrock, L., "A delay dependent queue discipline" 11 (11): 329-341, 1964