Hostname: page-component-586b7cd67f-2brh9 Total loading time: 0 Render date: 2024-11-22T16:18:28.178Z Has data issue: false hasContentIssue false
  • English
  • Français

Multiple-server system with flexible arrivals

Part of: Operations research and management science Special processes

Published online by Cambridge University Press:  01 July 2016

Osman T. Akgun ,
Rhonda Righter  and
Ronald Wolff
Osman T. Akgun*
Affiliation:
University of California, Berkeley
Rhonda Righter*
Affiliation:
University of California, Berkeley
Ronald Wolff*
Affiliation:
University of California, Berkeley
*
∗ Postal address: Department of Industrial Engineering and Operations Research, 4141 Etcheverry Hall, Berkeley, CA 94720, USA.
∗ Postal address: Department of Industrial Engineering and Operations Research, 4141 Etcheverry Hall, Berkeley, CA 94720, USA.
∗ Postal address: Department of Industrial Engineering and Operations Research, 4141 Etcheverry Hall, Berkeley, CA 94720, USA.
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

In many service, production, and traffic systems there are multiple types of customers requiring different types of ‘servers’, i.e. different services, products, or routes. Often, however, a proportion of the customers are flexible, i.e. they are willing to change their type in order to achieve faster service, and even if this proportion is small, it has the potential of achieving large performance gains. We generalize earlier results on the optimality of ‘join the shortest queue’ (JSQ) for flexible arrivals to the following: arbitrary arrivals where only a subset are flexible, multiple-server stations, and abandonments. Surprisingly, with abandonments, the optimality of JSQ for minimizing the number of customers in the system depends on the relative abandonment and service rates. We extend our model to finite buffers and resequencing. We assume exponential service. Our optimality results are very strong; we minimize the queue length process in the weak majorization sense.

Keywords

JSQmajorizationabandonmentfinite buffermultiple-server station

MSC classification

Primary: 90B22: Queues and service
Secondary: 60K25: Queueing theory
Type
General Applied Probability
Information
Advances in Applied Probability , Volume 43 , Issue 4 , December 2011 , pp. 985 - 1004
Copyright
Copyright © Applied Probability Trust 2011 

References

Agrawal, S. and Ramaswamy, R. (1987). Analysis of the resequencing delay for M/M/m systems. In ACM Sigmetrics Performance Evaluation Review, Association for Computing Machinery, New York, pp. 27–35.Google Scholar
Akgun, O. T., Righter, R. and Wolff, R. (2011). Understanding the marginal impact of customer flexibility. Submitted.Google Scholar
Aksin, O. Z., Karaesmen, F. and Ormeci, E. L. (2007). Workforce cross training in call centers from an operations management perspective. In Workforce Cross Training Handbook, ed. Nembhard, D., CRC Press, Boca Raton, FL, pp. 211–240.Google Scholar
Argon, N. T., Ding, L., Glazebrook, K. D. and Ziya, S. (2009). Dynamic routing of customers with general delay costs in a multiserver queuing system. Prob. Eng. Inf. Sci. 23, 175–203.Google Scholar
Bambos, N. and Michailidis, G. (2002). On parallel queueing with random server connectivity and routing constraints. Prob. Eng. Inf. Sci. 16, 185–203.CrossRefGoogle Scholar
Ephremides, A., Varaiya, P. and Walrand, J. (1980). A simple dynamic routing problem. IEEE Trans. Automatic Control 25, 690–693.Google Scholar
Foley, R. D. and McDonald, D. R. (2001). Join the shortest queue: stability and exact asymptotics. Ann. Appl. Prob. 11, 569–607.CrossRefGoogle Scholar
Fulkerson, D. R. and Ryser, H. J. (1962). Multiplicities and minimal widths for (0,1)-matrices. Canad. J. Math. 14, 498–508.Google Scholar
Gans, N., Koole, G. and Mandelbaum, A. (2003). Telephone call centers: tutorial, review, and research prospects. Manufact. Service Operat. Manag. 5, 79–141.Google Scholar
Graves, S. C. and Tomlin, B. T. (2003). Process flexibility in supply chains. Manag. Sci. 49, 907–919.Google Scholar
Gogate, N. R. and Panwar, S. S. (1999). Assigning customers to two parallel servers with resequencing. IEEE Commun. Lett. 3, 119–121.Google Scholar
Gupta, V., Balter, M. H., Sigman, K. and Whitt, W. (2007). Analysis of Join-the-shortest-queue routing for web server farms. Performance Evaluation 64, 1062–1081.Google Scholar
He, Y.-T. and Down, D. G. (2009). On accommodating customer flexibility in service systems. INFOR. 47, 289–295.Google Scholar
Hopp, W. J. and Van Oyen, M. P. (2004). Agile workforce evaluation: A framework for crosstraining and coordination. IIE Trans. 36, 919–940.Google Scholar
Hopp, W. J., Tekin, E. and Van Oyen, M. P. (2004). Benefits of skill chaining in serial production lines with cross-trained workers. Manag. Sci. 50, 83–98.Google Scholar
Hordijk, A. and Koole, G. (1990). On the optimality of the generalized shortest queue policy. Prob. Eng. Inf. Sci. 4, 477–487.Google Scholar
Johri, P. K. (1989). Optimality of the shortest line discipline with state dependent service times. Europ. J. Operat. Res. 41, 157–161.Google Scholar
Jordan, W. C. and Graves, S. C. (1995). Principles on the benefits of manufacturing process flexibility. Manag. Sci. 41, 577–594.Google Scholar
Koole, G., Sparaggis, P. D. and Towsley, D. (1999). Minimizing response times and queue lengths in systems of parallel queues. J. Appl. Prob. 36, 1185–1193.Google Scholar
Kuri, J. and Kumar, A. (1994). On the optimal allocation of customers that must depart in sequence. Operat. Res. Lett. 15, 41–46.Google Scholar
Marshall, A. W. and Olkin, I. (1979). Inequalities: Theory of Majorization and Its Applications. Academic Press, New York.Google Scholar
Menich, R. and Serfozo, R. F. (1991). Optimality of routing and servicing in dependent parallel processing stations. Queueing Systems 9, 403–418.Google Scholar
Mitzenmacher, M. (2001). The power of two choices in randomized load balancing. IEEE Trans. Parallel Distributed Systems 12, 1094–1104.CrossRefGoogle Scholar
Movaghar, A. (2005). Optimal control of parallel queues with impatient customers. Performance Evaluation 60, 327–343.CrossRefGoogle Scholar
Reiman, M. I. (1984). Some diffusion approximations with state space collapse. In Modelling and Performance Evaluation Methodology (Paris, 1983; Lecture Notes Control Inf. Sci. 60), Springer, Berlin, pp. 209–240.Google Scholar
Shaked, M. and Shanthikumar, J. G. (1994). Stochastic Orders and Their Applications. Academic Press, Boston, MA.Google Scholar
Sparaggis, P. D. and Towsley, D. (1994). Optimal routing and scheduling of customers with deadlines. Prob. Eng. Inf. Sci. 8, 33–49.Google Scholar
Sparaggis, P. D., Towsley, D. and Cassandras, C. G. (1993). Extremal properties of the shortest/longest nonfull queue policies in finite-capacity systems with state-dependent service rates. J. Appl. Prob. 30, 223–236.CrossRefGoogle Scholar
Towsley, D., Sparaggis, P. D. and Cassandras, C. G. (1990). Stochastic ordering properties and optimal routing control for a class of finite capacity queueing systems. In Proc. 29th IEEE Conf. on Decision and Control, pp. 658–663.Google Scholar
Weber, R. R. (1978). On the optimal assignment of customers to parallel servers. J. Appl. Prob. 15, 406–413.Google Scholar
Whitt, W. (1986). Deciding which queue to Join: some counterexamples. Operat. Res. 34, 55–62.Google Scholar
Winston, W. (1977). Optimality of the shortest line discipline. J. Appl. Prob. 14, 181–189.Google Scholar