×

Analysis of the optimal resource allocation for a tandem queueing system. (English) Zbl 1426.90078

Summary: We study a controllable two-station tandem queueing system, where customers (jobs) must first be processed at upstream station and then the downstream station. A manager dynamically allocates the service resource to each station to adjust the service rate, leading to a tradeoff between the holding cost and resource cost. The goal of the manager is to find the optimal policy to minimize the long-run average costs. The problem is constructed as a Markov decision process (MDP). In this paper, we consider the model in which the resource cost and service rate functions are more general than linear. We derive the monotonicity of the optimal allocation policy by the quasiconvexity properties of the value function. Furthermore, we obtain the relationship between the two stations’ optimal policy and conditions under which the optimal policy is unique and has the bang-bang control property. Finally, we provide some numerical experiments to illustrate these results.

MSC:

90B22 Queues and service in operations research
90C40 Markov and semi-Markov decision processes
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Koutsopoulos, I.
[2] Kuiper, A.; Mandjes, M., Appointment scheduling in tandem-type service systems, OMEGA, 57, 2, 145-156, (2015) · doi:10.1016/j.omega.2015.04.009
[3] Wu, C.-H.; Lin, J. T.; Chien, W.-C., Dynamic production control in a serial line with process queue time constraint, International Journal of Production Research, 48, 13, 3823-3843, (2010) · Zbl 1197.90309 · doi:10.1080/00207540902922836
[4] Kim, B.; Kim, J., Optimal admission control for two station tandem queues with loss, Operations Research Letters, 42, 4, 257-262, (2014) · Zbl 1408.90077 · doi:10.1016/j.orl.2014.04.006
[5] Silva, D. F.; Zhang, B.; Ayhan, H., Optimal admission control for tandem loss systems with two stations, Operations Research Letters, 41, 4, 351-356, (2013) · Zbl 1286.90164 · doi:10.1016/j.orl.2013.04.001
[6] Rosberg, Z.; Varaiya, P. P.; Walrand, J. C., Optimal control of service in tandem queues, IEEE Transactions on Automatic Control, 27, 3, 600-610, (1982) · Zbl 0497.90024 · doi:10.1109/TAC.1982.1102957
[7] Ahn, H.-S.; Duenyas, I.; Lewis, M. E., Optimal control of a two-stage tandem queuing system with flexible servers, Probability in the Engineering and Informational Sciences, 16, 4, 453-469, (2002) · Zbl 1038.90018 · doi:10.1017/S0269964802164047
[8] Arumugam, R.; Mayorga, M. E.; Taaffe, K. M., Inventory based allocation policies for flexible servers in serial systems, Annals of Operations Research, 172, 1-23, (2009) · Zbl 1181.90100 · doi:10.1007/s10479-008-0465-4
[9] Smith, J. M.; Barnes, R., Optimal server allocation in closed finite queueing networks, Flexible Services and Manufacturing Journal, 27, 1, 58-85, (2015) · doi:10.1007/s10696-014-9202-2
[10] Iravani, S. M.; Krishnamurthy, V.; Chao, G. H., Optimal server scheduling in nonpreemptive finite-population queueing systems, Queueing Systems, 55, 2, 95-105, (2007) · Zbl 1178.60065 · doi:10.1007/s11134-006-9006-5
[11] Yang, R.; Bhulai, S.; van der Mei, R., Structural properties of the optimal resource allocation policy for single-queue systems, Annals of Operations Research, 202, 211-233, (2013) · Zbl 1263.90028 · doi:10.1007/s10479-011-0933-0
[12] Yang, R.; Bhulai, S.; van der Mei, R., Optimal resource allocation for multiqueue systems with a shared server pool, Queueing Systems, 68, 2, 133-163, (2011) · Zbl 1231.90375 · doi:10.1007/s11134-011-9220-7
[13] Weber, R. R.; Stidham, J., Optimal control of service rates in networks of queues, Advances in Applied Probability, 19, 1, 202-218, (1987) · Zbl 0617.60090 · doi:10.2307/1427380
[14] Veatch, M. H.; Wein, L. M., Monotone control of queueing networks, Queueing Systems, 12, 3-4, 391-408, (1992) · Zbl 0825.90414 · doi:10.1007/BF01158810
[15] Mayorga, M. E.; Taaffe, K. M.; Arumugam, R., Allocating flexible servers in serial systems with switching costs, Annals of Operations Research, 172, 231-242, (2009) · Zbl 1181.90075 · doi:10.1007/s10479-009-0575-7
[16] Xia, L.; Shihada, B., Max-min optimality of service rate control in closed queueing networks, IEEE Transactions on Automatic Control, 58, 4, 1051-1056, (2013) · Zbl 1369.90054 · doi:10.1109/TAC.2012.2218145
[17] Xia, L.; Miller, D.; Zhou, Z.; Bambos, N., Service rate control of tandem queues with power constraints, IEEE Transactions on Automatic Control, 62, 10, 5111-5123, (2017) · Zbl 1390.90267 · doi:10.1109/TAC.2017.2678109
[18] Morozov, E.; Steyaert, B., Stability analysis of a two-station cascade queueing network, Annals of Operations Research, 202, 1, 135-160, (2013) · Zbl 1263.90025 · doi:10.1007/s10479-011-1034-9
[19] Koole, G., Monotonicity in Markov Reward and Decision Chains: Theory and Applications, 1, (2007), Breda, Netherlands: Now Publishers Inc, Breda, Netherlands
[20] Koole, G., Structural results for the control of queueing systems using event-based dynamic programming, Queueing Systems, 30, 3-4, 323-339, (1998) · Zbl 0917.90136 · doi:10.1023/A:1019177307418
[21] Kaufman, D. L.; Ahn, H.-S.; Lewis, M. E., On the introduction of an agile, temporary workforce into a tandem queueing system, Queueing Systems, 51, 1-2, 135-171, (2005) · Zbl 1098.90021 · doi:10.1007/s11134-005-2441-x
[22] Çil, E. B.; Örmeci, E. L.; Karaesmen, F., Effects of system parameters on the optimal policy structure in a class of queueing control problems, Queueing Systems, 61, 4, 273-304, (2009) · Zbl 1165.90381 · doi:10.1007/s11134-009-9109-x
[23] Tijms, H. C., Stochastic Models: An Algorithmic Approach. Stochastic Models: An Algorithmic Approach, Wiley Series in Probability and Mathematical Statistics: Applied Probability and Statistics, 303, (1994), Hoboken, NJ, USA: John Wiley & Sons Inc, Hoboken, NJ, USA · Zbl 0838.60075
[24] Puterman, M. L., Markov Decision Processes: Discrete Stochastic Dynamic Programming, (2014), Hoboken, NJ, USA: John Wiley & Sons, Hoboken, NJ, USA
[25] Aviv, Y.; Federgruen, A., The value iteration method for countable state Markov decision processes, Operations Research Letters, 24, 5, 223-234, (1999) · Zbl 0954.90060 · doi:10.1016/S0167-6377(99)00015-2
[26] Sennott, L. I., Stochastic Dynamic Programming and The Control of Queueing Systems. Stochastic Dynamic Programming and The Control of Queueing Systems, Wiley Series in Probability and Statistics: Applied Probability and Statistics, (1999), New York, NY, USA: John Wiley & Sons, Inc., New York, NY, USA · Zbl 0997.93503
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.