×

zbMATH — the first resource for mathematics

A skill based parallel service system under FCFS-ALIS – steady state, overloads, and abandonments. (English) Zbl 1305.60091
Summary: We consider a queueing system with \(J\) parallel servers \(\mathcal{S} =\{m_{1},\dots,m_{J}\}\), and with customer types \(\mathcal{C} =\{a,b,\dots\}\). A bipartite graph \(G\) describes which pairs of server-customer types are compatible. We consider FCFS-ALIS policy: A server always picks the first, longest waiting compatible customer, and a customer is always assigned to the longest idle compatible server. We assume Poisson arrivals and server dependent exponential service times. We derive an explicit product-form expression for the stationary distribution of this system when service capacity is sufficient. We also calculate fluid limits of the system under overload, to show that local steady state exists. We distinguish the case of complete resource pooling when all the customers are served at the same rate by the pooled servers, and the case when the system has a unique decomposition into subsets of customer types, each of which is served at its own rate by a pooled subset of the servers. Finally, we discuss possible behavior of the system with generally distributed abandonments, under many server scaling. This paper complements and extends previous results of R. Caldentey et al. [Adv. Appl. Probab. 41, No. 3, 695–730 (2009; Zbl 1247.90099)], and of R. Talreja and W. Whitt [Manage. Sci. 54, No. 8, 1513–1527 (2008; Zbl 1232.90156)], as well as previous results of the authors [Oper. Res. 60, No. 2, 475–489 (2012; Zbl 1298.60089)] and J. Visschers et al. [Queueing Syst. 70, No. 3, 269–298 (2012; Zbl 1275.60091)] on this topic.

MSC:
60K25 Queueing theory (aspects of probability theory)
90B22 Queues and service in operations research
PDF BibTeX XML Cite
Full Text: DOI Euclid
References:
[1] Adan, I. J. B. F., Boon, M. A. A., Weiss, G. (2013). Design and evaluation of overloaded service systems with skill based routing, under FCFS policies. Performance Evaluation ,
[2] Adan, I. J. B. F., Foss, S., Weiss, G. (2012). Local stability in a transient Markov chain, working paper.
[3] Adan, I. J. B. F., Hurkens, C., Weiss, G. (2010). A reversible Erlang loss system with multitype customers and multitype servers. Probability in Engineering and Informational Sciences 24 535-548. · Zbl 1235.60124
[4] Adan, I. J. B. F., Weiss, G. (2011). Exact FCFS matching rates for two infinite multi-type sequences. Operations Research 60 475-489. · Zbl 1298.60089
[5] Adan, I. J. B. F., Weiss, G. (2011). A loss system with skill based servers under assign to longest idle server policy. Probability in Engineering and Informational Sciences 26 307-321. · Zbl 1277.60149
[6] Adan, I. J. B. F., Wessels, J., Zijm, W. H. M. (1989). Queuing analysis in a flexible assembly system with a job-dependent parallel structure. Operations Research Proceedings 1988 , Springer-Verlag, Berlin, 551-558.
[7] Adan, I. J. B. F., Wessels, J., Zijm, W. H. M. (1991). Flexible assembly and shortest queue problems. Modern Production Concepts, Theory and Applications , G. Fandel, G. Zaepfel (eds.), Springer-Verlag, Berlin, 644-659. · Zbl 0741.60093
[8] Adan, I., Foley, R., McDonald, D. (2009). Exact asymptotics of the stationary distribution of a Markov chain: A production model. Queueing Systems 62 311-344. · Zbl 1188.60046
[9] Aerts, J., Korst, J., Verhaegh, W. (2007). Load balancing for redundant storage strategies: Multiprocessor scheduling with machine eligibility. Journal of Scheduling 4 245-257. · Zbl 1014.90035
[10] Ahuja, R. K., Magnanti, T. L., Orlin, J. B. (1993). Network Flows: Theory, Algorithms, and Applications , Prentice Hall, NJ. · Zbl 1201.90001
[11] Aksin, Z., Armony, M., Mehrotra, V. (2007). The modern call-center, a multi-disciplinary perspective on operations management research. Production and Operations Management 16 665-688.
[12] Armony, M. (2005). Dynamic routing in large-scale service systems with heterogeneous servers. Queueing Systems 51 287-329. · Zbl 1094.60058
[13] Armony, M., Ward, A. R. (2010). Fair dynamic routing in large-scale heterogeneous-server systems. Operations Research 58 (3) 624-637. · Zbl 1231.90133
[14] Armony, M., Mandelbaum, A. (2011). Routing and staffing in large-scale service systems: The case of homogeneous impatient customers and heterogeneous servers. Operations Research 59 (1) 50-65. · Zbl 1217.90062
[15] Atar, R. (2005). Scheduling control for queueing systems with many servers: Asymptotic optimality in heavy traffic. The Annals of Applied Probability 15 2606-2650. · Zbl 1098.60083
[16] Atar, R., Mandelbaum, A., Shaikhet, G. (2009). Simplified control problems for multiclass many-server queueing systems. Mathematics of Operations Research 34 795-812. · Zbl 1213.60142
[17] Bramson, M. (2008). Stability of Queueing Networks , Springer. · Zbl 1152.60004
[18] Caldentey, R., Kaplan, E. H., Weiss, G. (2009). FCFS infinite bipartite matching of servers and customers. Advances in Applied Probability 41 695-730. · Zbl 1247.90099
[19] Chen, H., Mandelbaum, A. (1994). Hierarchical modeling of stochastic networks, Part I: Fluid models. Stochastic Modeling and Analysis of Manufacturing Systems , Springer, 47-105.
[20] Dai, J. G. (1995). On positive Harris recurrence of multiclass queueing networks: A unified approach via fluid limit models. Annals of Applied Probability 5 49-77. · Zbl 0822.60083
[21] Dai, J. G., Lin, W. (2005). Maximum pressure policies in stochastic processing networks. Operations Research 53 197-218. · Zbl 1165.90359
[22] Dai, J., Weiss, G. (1996). Stability and instability of fluid models for certain re-entrant lines. Mathematics of Operations Research 21 115-134. · Zbl 0848.60086
[23] Ford, L. R., Jr., Fulkerson, D. R. (1962). Flows in Networks , Princeton University Press, Princeton. · Zbl 0106.34802
[24] Foss, S., Chernova, N. (1998). On the stability of a partially accessible multi-station queue with state-dependent routing. Queueing Systems 29 55-73. · Zbl 0915.60089
[25] Garnett, O., Mandelbaum, A. (2000). An introduction to skill-based routing and its operational complexities. .
[26] Green, L. (1985). A queueing system with general-use and limited-use servers. Operations Research 33 168-182. · Zbl 0587.60092
[27] Gurvich, I., Whitt, W. (2010). Service-level differentiation in many-server service system via queue-ratio routing. Operations Research 58 316-328. · Zbl 1233.90116
[28] Harrison, J. M., Lopez, M. J. (1999). Heavy traffic resource pooling in parallel-server systems. Queueing Systems 33 339-368 · Zbl 0997.60108
[29] Jennings, O. B., Reed, J. E. (2012). An overloaded multiclass FIFO queue with abandonments. Operations Research 60 1282-1295. · Zbl 1257.90014
[30] Kaplan, E. H. (1988). A public housing queue with reneging and task-specific servers. Decision Sciences 19 383-391.
[31] Mandelbaum, A., Stoylar, A. L. (2004). Scheduling flexible servers with convex delay costs: Heavy-traffic optimality of the generalized c\(\mu\)-rule. Operations Research 52 836-855. · Zbl 1165.90402
[32] McManus, M. L., Long, M. C., Copper, A., Litvak, E. (2004). Queueing theory accurately models the need for critical care resources. Anesthesiology 100 1271-1276.
[33] Royden, H. L. (1988). Real Analysis , 3rd ed, Prentice Hall, New York. · Zbl 0704.26006
[34] Talreja, R., Whitt, W. (2007). Fluid models for overloaded multi-class many-service queueing systems with FCFS routing. Management Science 54 1513-1527. · Zbl 1232.90156
[35] Visschers, J., Adan, I. J. B. F., Weiss, G. (2012). A product form solution to a system with multi-type customers and multi-type servers. Queueing Systems 70 269-298. · Zbl 1275.60091
[36] Wallace, R. B., Whitt, W. (2005). A staffing algorithm for call centers with skill-based routing. Manufacturing and Service Operations Management 7 276-294.
[37] Zijm, W. H. M., Laarhoven, P. J. M. (1993). Production preparation and numerical control in PCB assembly. International Journal of Flexible Manufacturing Systems 5 187-207.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.