Hostname: page-component-cd9895bd7-gvvz8 Total loading time: 0 Render date: 2024-12-28T17:22:13.309Z Has data issue: false hasContentIssue false
  • English
  • Français

OPTIMAL CONTROL OF A TWO-SERVER QUEUEING SYSTEM WITH FAILURES

Published online by Cambridge University Press:  27 June 2014

Erhun Özkan  and
Jeffrey P. Kharoufeh
Erhun Özkan
Affiliation:
Department of Industrial Engineering, University of Pittsburgh, 1048 Benedum Hall, 3700 O'Hara Street, Pittsburgh, PA 15261, USA E-mails: [email protected]; [email protected]
Jeffrey P. Kharoufeh
Affiliation:
Department of Industrial Engineering, University of Pittsburgh, 1048 Benedum Hall, 3700 O'Hara Street, Pittsburgh, PA 15261, USA E-mails: [email protected]; [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

We consider the problem of controlling a two-server Markovian queueing system with heterogeneous servers. The servers are differentiated by their service rates and reliability attributes (i.e., the slower server is perfectly reliable, whereas the faster server is subject to random failures). The aim is to dynamically route customers at arrival, service completion, server failure, and server repair epochs to minimize the long-run average number of customers in the system. Using a Markov decision process model, we prove that it is always optimal to route customers to the faster server when it is available, irrespective of its failure and repair rates, if the system is stable. For the slower server, there exists an optimal threshold policy that depends on the queue length and the state of the faster server. Additionally, we analyze a variant of the main model in which there are multiple unreliable servers with identical service rates, but distinct reliability characteristics. For that case it is always optimal to route customers to idle servers, and the optimal policy is insensitive to the servers’ reliability characteristics.

Type
Research Article
Information
Probability in the Engineering and Informational Sciences , Volume 28 , Issue 4 , October 2014 , pp. 489 - 527
Copyright
Copyright © Cambridge University Press 2014 

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.Andradóttir, S., Ayhan, H. & Down, D.G. (2007). Compensating for failures with flexible servers. Operations Research 55:753–768.CrossRefGoogle Scholar
2.Andradóttir, S., Ayhan, H. & Down, D.G. (2008). Maximizing the throughput of tandem lines with flexible failure-prone servers and finite buffers. Probability in the Engineering and Informational Sciences 22:191–211.CrossRefGoogle Scholar
3.Bertsekas, D.P. (2001). Dynamic programming and optimal control, 2nd edition, volume II. Athena Scientific, Belmont, MA.Google Scholar
4.de Véricourt, F. & Zhou, Y.P. (2005). Managing response time in a call-routing problem with service failure. Operations Research 53:968–981.Google Scholar
5.de Véricourt, F. & Zhou, Y.P. (2006). On the incomplete results for the heterogeneous server problem. Queueing Systems 52:189–191.CrossRefGoogle Scholar
6.Efrosinin, D. (2013). Queueing model of a hybrid channel with faster link subject to partial and complete failures. Annals of Operations Research 202:75–102.Google Scholar
7.Kim, J.H., Ahn, H.S. & Righter, R. (2011). Managing queues with heterogeneous servers. Journal of Applied Probability 48:435–452.Google Scholar
8.Koole, G. (1995). A simple proof of the optimality of a threshold policy in a two-server queueing system. Systems and Control Letters 26:301–303.Google Scholar
9.Larsen, R.L. (1981). Control of Multiple Exponential Servers with Application to Computer Systems. PhD thesis, University of Maryland, College Park, MD, USA.Google Scholar
10.Larsen, R.L. & Agrawala, A.K. (1983). Control of a heterogeneous two-server exponential queueing system. IEEE Transactions on Software Engineering SE–9:522–526.CrossRefGoogle Scholar
11.Lin, W. & Kumar, P.R. (1984). Optimal control of a queueing system with two heterogeneous servers. IEEE Transactions on Automatic Control 29:696–703.Google Scholar
12.Luh, H.P. & Viniotis, I. (2002). Threshold control policies for heterogeneous server systems. Mathematical Methods of Operations Research 55:121–142.Google Scholar
13.Özkan, E. & Kharoufeh, J. (2013). Incompleteness of results for the slow-server problem with an unreliable fast server. Annals of Operations Research doi:10.1007/s10479-014-1615-5.Google Scholar
14.Puterman, M.L. (2005). Markov Decision Processes: Discrete Stochastic Dynamic Programming. John Wiley & Sons, Inc., Hoboken, NJ.Google Scholar
15.Rubinovitch, M. (1985). The slow server problem: a queue with stalling. Journal of Applied Probability 22:879–892.Google Scholar
16.Rykov, V.V. (2001). Monotone control of queueing systems with heterogeneous servers. Queueing Systems 37:391–403.Google Scholar
17.Sennott, L.I. (1989). Average cost optimal stationary policies in infinite state Markov decision processes with unbounded costs. Operations Research 37:626–633.Google Scholar
18.Viniotis, I. & Ephremides, A. (1988). Extension of the optimality of the threshold policy in heterogeneous multiserver queueing systems. IEEE Transactions on Automatic Control 33:104–109.Google Scholar
19.Walrand, J. (1984). A note on “Optimal control of a queuing system with two heterogeneous servers”. Systems and Control Letters 4:131–134.Google Scholar
20.Wu, C.H., Down, D.G. & Lewis, M.E. (2008). Heuristics for allocation of reconfigurable resources in a serial line with reliability considerations. IIE Transactions 40:595–611.Google Scholar
21.Wu, C.H., Lewis, M.E. & Veatch, M. (2006). Dynamic allocation of reconfigurable resources in a two-stage tandem queueing system with reliability considerations. IEEE Transactions on Automatic Control 51:309–314.Google Scholar
22.Xu, S.H. (1994). A duality approach to admission and scheduling control of queues. Queueing Systems 18:273–300.Google Scholar