×

zbMATH — the first resource for mathematics

Optimal routeing in two-queue polling systems. (English) Zbl 1402.60117
Summary: We consider a polling system with two queues, exhaustive service, no switchover times, and exponential service times with rate \(\mu\) in each queue. The waiting cost depends on the position of the queue relative to the server: it costs a customer \(c\) per time unit to wait in the busy queue (where the server is) and \(d\) per time unit in the idle queue (where there is no server). Customers arrive according to a Poisson process with rate \(\lambda\). We study the control problem of how arrivals should be routed to the two queues in order to minimize the expected waiting costs and characterize individually and socially optimal routeing policies under three scenarios of available information at decision epochs: no, partial, and complete information. In the complete information case, we develop a new iterative algorithm to determine individually optimal policies (which are symmetric Nash equilibria), and show that such policies can be described by a switching curve. We use Markov decision processes to compute the socially optimal policies. We observe numerically that the socially optimal policy is well approximated by a linear switching curve. We prove that the control policy described by this linear switching curve is indeed optimal for the fluid version of the two-queue polling system.

MSC:
60K25 Queueing theory (aspects of probability theory)
90B22 Queues and service in operations research
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Altman, E.; Shimkin, N., Individual equilibrium and learning in processor sharing systems, Operat. Res., 46, 776-784, (1998) · Zbl 0987.90020
[2] Bertsekas, D. P., Dynamic Programming and Optimal Control, (2005), Athena Scientific: Athena Scientific, Belmont, MA · Zbl 1125.90056
[3] Boon, M. A. A., Polling models: from theory to traffic intersections, (2011)
[4] Boon, M. A. A.; Van Der Mei, R. D.; Winands, E. M. M., Applications of polling systems, Surveys Operat. Res. Manag. Sci., 16, 67-82, (2011)
[5] Boon, M. A. A.; Van Der Mei, R. D.; Winands, E. M. M., Waiting times in queueing networks with a single shared server, Queueing Systems, 74, 403-429, (2013) · Zbl 1273.60107
[6] Boon, M. A. A.; Van Wijk, A. C. C.; Adan, I. J. B. F.; Boxma, O. J., A polling model with smart customers, Queueing Systems, 66, 239-274, (2010) · Zbl 1255.90038
[7] Boxma, O. J.; Levy, H.; Weststrate, J. A., Efficient visit frequencies for polling tables: minimization of waiting cost, Queueing Systems, 9, 133-162, (1991) · Zbl 0738.68008
[8] Bryson, A. E., Jr.; Ho, Y. C., Applied Optimal Control: Optimization, Estimation, and Control, (1975), Hemisphere: Hemisphere, Washington, DC
[9] Burnetas, A.; Economou, A., Equilibrium customer strategies in a single server Markovian queue with setup times, Queueing Systems, 56, 213-228, (2007) · Zbl 1124.60069
[10] Haijema, R.; Van Der Wal, J., An MDP decomposition approach for traffic control at isolated signalized intersections, Prob. Eng. Inf. Sci., 22, 587-602, (2008) · Zbl 1152.90386
[11] Hassin, R.; Haviv, M., To Queue or not to Queue: Equilibrium Behavior in Queueing Systems, (2003), Kluwer: Kluwer, Boston, MA · Zbl 1064.60002
[12] Klimov, G. P., Time-sharing service systems. I, Theory Prob. Appl., 19, 532-551, (1975) · Zbl 0378.60102
[13] Klimov, G. P., Time-sharing service systems. II, Theory Prob. Appl., 23, 314-321, (1979) · Zbl 0421.60085
[14] Kulkarni, V. G., Modeling and Analyisis of Stochastic Systems, (2016), CRC: CRC, Boca Raton, FL
[15] Kurtz, T. G., Solutions of ordinary differential equations as limits of pure jump Markov processes, J. Appl. Prob., 7, 49-58, (1970) · Zbl 0191.47301
[16] Lefeber, E.; Lämmer, S.; Rooda, J. E., Optimal control of a deterministic multiclass queuing system for which several queues can be served simultaneously, Systems Control Lett., 60, 524-529, (2011) · Zbl 1222.49042
[17] Levy, H.; Sidi, M., Polling systems: applications, modeling, and optimization, IEEE Trans. Commun., 38, 1750-1760, (1990)
[18] Lippman, S. A.; Stidham, S., Jr., Individual versus social optimization in exponential congestion systems, Operat. Res., 25, 233-247, (1977) · Zbl 0369.90079
[19] Ross, S., Introduction to Stochastic Dynamic Programming, (1983), Academic Press: Academic Press, New York · Zbl 0567.90065
[20] Sharafali, M.; Co, H. C.; Goh, M., Production scheduling in a flexible manufacturing system under random demand, Europ. J. Operat. Res., 158, 89-102, (2004) · Zbl 1061.90039
[21] Sidi, M.; Levy, H.; Fuhrmann, S. W., A queueing network with a single cyclically roving server, Queueing Systems, 11, 121-144, (1992) · Zbl 0752.60069
[22] Takagi, H., Analysis of Polling Systems, (1986), MIT Press: MIT Press, Cambridge, MA
[23] Takine, T.; Takagi, H.; Hasegawa, T., Sojourn times in vacation and polling systems with Bernoulli feedback, J. Appl. Prob., 28, 422-432, (1991) · Zbl 0733.60113
[24] Van Der Wal, J.; Yechiali, U., Dynamic visit-order rules for batch-service polling, Prob. Eng. Inf. Sci., 17, 351-367, (2003) · Zbl 1336.90027
[25] Vishnevskiĭ, V. M.; Semenova, O. V., Mathematical methods for investigating polling systems, Autom. Remote Control, 67, 173-220, (2006) · Zbl 1126.60321
[26] Weiss, G., Proceedings of the 37th Allerton Conference, Scheduling and control of manufacturing systems—a fluid approach, 577-586, (1999)
[27] Winands, E. M. M., Polling, production & priorities, (2007) · Zbl 1149.90044
[28] Winands, E. M. M.; Adan, I. J. B. F.; Van Houtum, G. J., Mean value analysis for polling systems, Queueing Systems, 54, 35-44, (2006) · Zbl 1137.90434
[29] Yechiali, U., Performance Evaluation of Computer and Communication Systems, Analysis and control of polling systems, 630-650, (1993), Springer: Springer, Berlin
[30] Van Zwieten, D. A. J.; Lefeber, E.; Adan, I. J. B. F., Optimal steady-state and transient trajectories of multi-queue switching servers with a fixed service order of queues, Performance Evaluation, 97, 16-35, (2016)
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.