Hostname: page-component-cd9895bd7-hc48f Total loading time: 0 Render date: 2024-12-26T22:26:19.556Z Has data issue: false hasContentIssue false
  • English
  • Français

Bias optimal admission control policies for a multiclass nonstationary queueing system

Part of: Special processes

Published online by Cambridge University Press:  14 July 2016

Mark E. Lewis ,
Hayriye Ayhan  and
Robert D. Foley
Mark E. Lewis*
Affiliation:
University of Michigan
Hayriye Ayhan*
Affiliation:
Georgia Institute of Technology
Robert D. Foley*
Affiliation:
Georgia Institute of Technology
*
∗ Postal address: Department of Industrial and Operations Engineering, University of Michigan, 1205 Beal Avenue, Ann Arbor, MI 48109-2117, USA. Email address: [email protected]
∗∗ Postal address: School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, GA 30332-0205, USA.
∗∗ Postal address: School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, GA 30332-0205, USA.
Get access Rights & Permissions [Opens in a new window]

Abstract

We consider a finite-capacity queueing system where arriving customers offer rewards which are paid upon acceptance into the system. The gatekeeper, whose objective is to ‘maximize’ rewards, decides if the reward offered is sufficient to accept or reject the arriving customer. Suppose the arrival rates, service rates, and system capacity are changing over time in a known manner. We show that all bias optimal (a refinement of long-run average reward optimal) policies are of threshold form. Furthermore, we give sufficient conditions for the bias optimal policy to be monotonic in time. We show, via a counterexample, that if these conditions are violated, the optimal policy may not be monotonic in time or of threshold form.

Keywords

Dynamic programmingapplicationssensitive optimalityqueuesnonstationaryoptimal controlmonotone policies

MSC classification

Primary: 90C40: Markov and semi-Markov decision processes
Secondary: 60K25: Queueing theory
Type
Research Papers
Information
Journal of Applied Probability , Volume 39 , Issue 1 , March 2002 , pp. 20 - 37
Copyright
Copyright © Applied Probability Trust 2002 

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

[1]. Altman, E. and Stidham, S. Jr (1995). Optimality of monotone policies for two-action Markovian decision processes, with applications to control of queues with delayed information. Queueing Systems 21, 267–291.Google Scholar
[2]. Dutta, P. K. (1991). What do discounted optima converge to? A theory of discount rate asymptotics in economic models. J. Econom. Theory 55, 64–94.CrossRefGoogle Scholar
[3]. Fu, M. C., Marcus, S. I., and Wang, I-J. (2000). Monotone optimal policies for a transient queueing staffing problem. Operat. Res. 48, 327–331.Google Scholar
[4]. Ghoneim, H. A. and Stidham, S. Jr (1985). Control of arrivals to two queues in series. Europ. J. Operat. Res. 21, 399–409.Google Scholar
[5]. Haviv, M., and Puterman, M. L. (1998). Bias optimality in controlled queueing systems. J. Appl. Prob. 35, 136–150.Google Scholar
[6]. Helm, W. E., and Waldmann, K.-H. (1984). Optimal control of arrivals to multi-server queues in a random environment. J. Appl. Prob. 21, 602–615.Google Scholar
[7]. Hernández-Lerma, O., and Lasserre, J. B. (1999). Further Topics on Discrete-Time Markov Control Processes. Springer, New York.Google Scholar
[8]. Heyman, D. P. (1968). Optimal operating policies for M/G/1 queueing systems. Operat. Res. 16, 362–382.CrossRefGoogle Scholar
[9]. Lewis, M. E. (1998). Bias optimality in a two-class nonstationary queueing system. Doctoral Thesis, Georgia Institute of Technology.Google Scholar
[10]. Lewis, M. E. (2001). Average optimal policies in a controlled queueing system with dual admission control. J. Appl. Prob. 38, 369–385.CrossRefGoogle Scholar
[11]. Lewis, M. E., and Puterman, M. L. (2000). A note on bias optimality in controlled queueing systems. J. Appl. Prob. 37, 300–305.Google Scholar
[12]. Lewis, M. E., and Puterman, M. L. (2001). A probabilistic analysis of bias optimality in unichain Markov decision processes. IEEE Trans. Automatic Control 46, 96–100.Google Scholar
[13]. Lewis, M. E., and Puterman, M. L. (2001). Bias optimality. In Handbook of Markov Decision Processes: Methods and Applications, eds Feinberg, E. and Shwartz, A., Kluwer, Dordrecht, pp. 89–111.Google Scholar
[14]. Lewis, M. E., Ayhan, H., and Foley, R. D. (1999). Bias optimality in a queue with admission control. Prob. Eng. Inf. Sci. 13, 309–327.Google Scholar
[15]. Lippman, S. A. (1975). Applying a new device in the optimization of exponential queueing systems. Operat. Res. 23, 687–712.Google Scholar
[16]. Lippman, S. A., and Ross, S. M. (1971). The streetwalker's dilemma: a job shop model. SIAM J. Appl. Math. 20, 336–342.Google Scholar
[17]. Massey, W. A., and Whitt, W. (1996). Stationary-process approximations for the nonstationary Erlang loss model. Operat. Res. 44, 976–983.Google Scholar
[18]. Massey, W. A., and Whitt, W. (1997). Peak congestion in multi-service systems with slowly varying arrival rates. QUESTA 25, 157–172.Google Scholar
[19]. Miller, B. L. (1969). A queueing reward system with several customer classes. Manag. Sci. 16, 234–245.Google Scholar
[20]. Reiman, M. I. (1989). Asymptotically optimal trunk reservation for large trunk groups. In Proc. 28th Conf. Decision Control (Tampa, FL, December 1989), IEEE, New York, pp. 2536–2541.Google Scholar
[21]. Stidham, S. Jr (1985). Optimal control of admission to a queueing system. IEEE Trans. Automatic Control 30, 705–713.Google Scholar
[22]. Veinott, A. F. Jr (1966). On finding optimal policies in discrete dynamic programming with no discounting. Ann. Math. Statist. 37, 1284–1294.Google Scholar
[23]. Veinott, A. F. Jr (1974). Markov decision chains. In Studies in Optimization (Studies Math. 10), eds Dantzig, G. B. and Eaves, B. C., Mathematical Association of America, Washington, pp. 124–159.Google Scholar
[24]. Yadin, M., and Naor, P. (1963). Queueing systems with a removable service station. Operat. Res. Quart. 14, 393–405.Google Scholar