Hostname: page-component-586b7cd67f-dsjbd Total loading time: 0 Render date: 2024-11-28T22:08:35.070Z Has data issue: false hasContentIssue false
  • English
  • Français

ADMISSION CONTROL WITH INCOMPLETE INFORMATION TO A FINITE BUFFER QUEUE

Published online by Cambridge University Press:  15 December 2006

Dorothée Honhon  and
Sridhar Seshadri
Dorothée Honhon
Affiliation:
Department of Information, Risk and Operations Management, McCombs School of Business, The University of Texas at Austin, Austin, TX 78712, E-mail: [email protected]
Sridhar Seshadri
Affiliation:
Department of Information, Operations and Management Science, Leonard N. Stern School of Business, New York University, New York, NY 10012
Get access Rights & Permissions [Opens in a new window]

Abstract

We consider the problem of admission control to a multiserver finite buffer queue under partial information. The controller cannot see the queue but is informed immediately if an admitted customer is lost due to buffer overflow. Turning away (i.e., blocking) customers is costly and so is losing an admitted customer. The latter cost is greater than that of blocking. The controller's objective is to minimize the average cost of blocking and rejection per incoming customer. Lin and Ross [11] studied this problem for multiserver loss systems. We extend their work by allowing a finite buffer and the arrival process to be of the renewal type. We propose a control policy based on a novel state aggregation approach that exploits the regenerative structure of the system, performs well, and gives a lower bound on the optimal cost. The control policy is inspired by a simulation technique that reduces the variance of the estimators by not simulating the customer service process. Numerical experiments show that our bound varies with the load offered to the system and is typically within 1% and 10% of the optimal cost. Also, our bound is tight in the important case when the cost of blocking is low compared to the cost of rejection and the load offered to the system is high. The quality of the bound degrades with the degree of state aggregation, but the computational effort is comparatively small. Moreover, the control policies that we obtain perform better compared to a heuristic suggested by Lin and Ross. The state aggregation technique developed in this article can be used more generally to solve problems in which the objective is to control the time to the end of a cycle and the quality of the information available to the controller degrades with the length of the cycle.

Type
Research Article
Information
Probability in the Engineering and Informational Sciences , Volume 21 , Issue 1 , January 2007 , pp. 19 - 46
Copyright
© 2007 Cambridge University Press

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

REFERENCES

Altman, E. & Basar, T. (1995). Optimal rate control for high speed telecommunication networks: The case of delayed information. In First Workshop on ATM Traffic Management, WATM'95, IFIP, WG.6.2 Broadband Communication, Paris.
Altman, E., Kofman, D., & Yechiali, U. (1995). Discrete time queues with delayed information. Queueing Systems 19: 361–376.Google Scholar
Altman, E. & Koole, G. (1995). Control of a random walk with noisy delayed information. Systems and Control Letters 24: 207–213.Google Scholar
Altman, E., Marquez, R., & Yechiali, U. (2003). Admission and routing control with partial information and limited buffers. International Journal of Systems Science 34(10–11): 615–626.Google Scholar
Altman, E. & Nain, P. (1995). Closed-loop control with delayed information. In Proceedings of the ACM Sigmetrics Conference on Measurement and Modeling of Computer Systems, pp. 193–204.
Altman, E. & Stidham, S. (1995). Optimality of monotonic policies for two-action Markovian decision processes, with applications to control of queues with delayed information. QUESTA 21: 267–291.Google Scholar
Bertsekas, D. (1995). Dynamic programming and optimal control, Vol. 2. Belmont, MA: Athena Scientific.
Chung, K. (1974). A course in probability theory, 2nd ed. New York: Academic Press.
Kuri, J. & Kumar, A. (1995). Optimal control of arrivals to queues with delayed queue length information. IEEE Transactions on Automatic Control 40(8): 1444–1450.Google Scholar
Kuri, J. & Kumar, A. (1997). On the optimal control of arrivals to a single queue with arbitrary feedback delay. Queueing Systems 27(1–2): 1–16.Google Scholar
Lin, K. & Ross, S. (2003). Admission control with incomplete information of a queueing system. Operations Research 51(4): 645–654.Google Scholar
Lin, K. & Ross, S. (2004). Optimal admission control for a single-server loss queue. Journal of Applied Probability 41: 535–546.Google Scholar
Litvak, N. & Yiechiali, U. (2003). Routing in queues with delayed information. Queueing Systems 43: 147–165.Google Scholar
Ross, S. (1970). Applied probability models with optimization applications. New York: Dover.
Ross, S. (1997). Simulation, 2nd ed. New York: Academic Press.
Ross, S. & Seshadri, S. (2002). Hitting times in an Erlang loss system. Probability in the Engineering and Informational Sciences 16(2): 167–184.Google Scholar
Schäl, M. (1993). Average optimality in dynamic programming with general state space. Mathematics of Operations Research 18(1): 163–172.Google Scholar