
-
Previous Article
Optimum pricing strategy for complementary products with reservation price in a supply chain model
- JIMO Home
- This Issue
-
Next Article
Stochastic machine breakdown and discrete delivery in an imperfect inventory-production system
Optimal threshold control of a retrial queueing system with finite buffer
School of Mathematics and Statistics, Central South University, Changsha 410083, Hunan, China |
In this paper, we analyze the optimal control of a retrial queueing system with finite buffer K. At any decision epoch, if the buffer is full, the controller have to make two decisions: one is for the new arrivals, to decide whether they are allowed to join the orbit or not (admission control); the other one is for the repeated customers, to decide whether they are allowed to get back to the orbit or not (retrial control). The problems are constructed as a Markov decision process. We show that the optimal policy has a threshold-type structure and the thresholds are monotonic in operating parameters and various cost parameters. Furthermore, based on the structure of the optimal policy, we construct a performance evaluation model for computing efficiently the thresholds. The expression of the expected cost is given by solving the quasi-birth-and-death (QBD) process. Finally, we provide some numerical results to illustrate the impact of different parameters on the optimal policy and average cost.
References:
[1] |
H.-S. Ahn, I. Duenyas and M. E. Lewis,
Optimal control of a two-stage tandem queuing system with flexible servers, Probability in the Engineering and Informational Sciences, 16 (2002), 453-469.
doi: 10.1017/S0269964802164047. |
[2] |
A. S. Alfa and K. S. Isotupa,
An M/PH/k retrial queue with finite number of sources, Computers & Operations Research, 31 (2004), 1455-1464.
doi: 10.1016/S0305-0548(03)00100-X. |
[3] |
J. R. Artalejo,
Accessible bibliography on retrial queues: Progress in 2000--2009, Mathematical and Computer Modelling, 51 (2010), 1071-1081.
doi: 10.1016/j.mcm.2009.12.011. |
[4] |
Y. Aviv and A. Federgruen,
The value iteration method for countable state markov decision processes, Operations Research Letters, 24 (1999), 223-234.
doi: 10.1016/S0167-6377(99)00015-2. |
[5] |
S. Benjaafar, J.-P. Gayon and S. Tepe,
Optimal control of a production--inventory system with customer impatience, Operations Research Letters, 38 (2010), 267-272.
doi: 10.1016/j.orl.2010.03.008. |
[6] |
L. Breuer,
Threshold policies for controlled retrial queues with heterogeneous servers, Annals of Operations Research, 141 (2006), 139-162.
doi: 10.1007/s10479-006-5297-5. |
[7] |
R. Cavazos-Cadena and L. I. Sennott,
Comparing recent assumptions for the existence of average optimal stationary policies, Operations Research Letters, 11 (1992), 33-37.
doi: 10.1016/0167-6377(92)90059-C. |
[8] |
E. B. Çil, F. Karaesmen and E. L. Örmeci,
Dynamic pricing and scheduling in a multi-class single-server queueing system, Queueing Systems, 67 (2011), 305-331.
doi: 10.1007/s11134-011-9214-5. |
[9] |
E. B. Çil, E. L. Örmeci and F. Karaesmen,
Effects of system parameters on the optimal policy structure in a class of queueing control problems, Queueing Systems, 61 (2009), 273-304.
doi: 10.1007/s11134-009-9109-x. |
[10] |
S. D. Flapper, J.-P. Gayon and L. L. Lim,
On the optimal control of manufacturing and remanufacturing activities with a single shared server, European Journal of Operational Research, 234 (2014), 86-98.
doi: 10.1016/j.ejor.2013.10.049. |
[11] |
D. Gaver, P. Jacobs and G. Latouche,
Finite birth-and-death models in randomly changing environments, Advances in Applied Probability, 16 (1984), 715-731.
doi: 10.1017/S0001867800022916. |
[12] |
B. Hajek,
Optimal control of two interacting service stations, IEEE Transactions on Automatic Control, 29 (1984), 491-499.
doi: 10.1109/TAC.1984.1103577. |
[13] |
W. E. Helm and K.-H. Waldmann,
Optimal control of arrivals to multiserver queues in a random environment, Journal of Applied Probability, 21 (1984), 602-615.
doi: 10.1017/S0021900200028795. |
[14] |
D. P. Heyman,
Optimal operating policies for M/G/1 queuing systems, Operations Research, 16 (1968), 362-382.
doi: 10.1287/opre.16.2.362. |
[15] |
G. Koole,
Monotonicity in Markov Reward and Decision Chains: Theory and Applications vol. 1, Now Publishers Inc, 2007.
doi: 10.1561/0900000002. |
[16] |
B. K. Kumar and J. Raja,
On multiserver feedback retrial queues with balking and control retrial rate, Annals of Operations Research, 141 (2006), 211-232.
doi: 10.1007/s10479-006-5300-1. |
[17] |
B. K. Kumar, R. Rukmani and V. Thangaraj,
On multiserver feedback retrial queue with finite buffer, Applied Mathematical Modelling, 33 (2009), 2062-2083.
doi: 10.1016/j.apm.2008.05.011. |
[18] |
M. L. Puterman, Markov Decision Processes: Discrete Stochastic Dynamic Programming, John Wiley & Sons, New York, 1994.
![]() |
[19] |
L. I. Sennott,
Stochastic Dynamic Programming and the Control of Queueing Systems vol. 504, John Wiley & Sons, New York, 1999. |
[20] |
J.-D. Son,
Optimal admission and pricing control problem with deterministic service times and sideline profit, Queueing Systems, 60 (2008), 71-85.
doi: 10.1007/s11134-008-9087-4. |
[21] |
S. Stidham Jr and R. Weber,
A survey of markov decision models for control of networks of queues, Queueing Systems, 13 (1993), 291-314.
doi: 10.1007/BF01158935. |
[22] |
H. C. Tijms,
Stochastic Models: An Algorithmic Approach vol. 303, John Wiley & Sons Inc, 1994. |
[23] |
T. Van Do,
An efficient computation algorithm for a multiserver feedback retrial queue with a large queueing capacity, Applied Mathematical Modelling, 34 (2010), 2272-2278.
doi: 10.1016/j.apm.2009.10.025. |
[24] |
J. Wu and Z. Lian,
Analysis of the $M_{1}, M_{2}$/G/1 G-queueing system with retrial customers, Nonlinear Analysis: Real World Applications, 14 (2013), 365-382.
doi: 10.1016/j.nonrwa.2012.06.009. |
[25] |
J. Wu, J. Wang and Z. Liu,
A discrete-time Geo/G/1 retrial queue with preferred and impatient customers, Applied Mathematical Modelling, 37 (2013), 2552-2561.
doi: 10.1016/j.apm.2012.06.011. |
[26] |
S. Yoon and M. E. Lewis,
Optimal pricing and admission control in a queueing system with periodically varying parameters, Queueing Systems, 47 (2004), 177-199.
doi: 10.1023/B:QUES.0000035313.20223.3f. |
[27] |
X. Zhang, J. Wang and T. Van Do,
Threshold properties of the M/M/1 queue under T-policy with applications, Applied Mathematics and Computation, 261 (2015), 284-301.
doi: 10.1016/j.amc.2015.03.109. |
show all references
References:
[1] |
H.-S. Ahn, I. Duenyas and M. E. Lewis,
Optimal control of a two-stage tandem queuing system with flexible servers, Probability in the Engineering and Informational Sciences, 16 (2002), 453-469.
doi: 10.1017/S0269964802164047. |
[2] |
A. S. Alfa and K. S. Isotupa,
An M/PH/k retrial queue with finite number of sources, Computers & Operations Research, 31 (2004), 1455-1464.
doi: 10.1016/S0305-0548(03)00100-X. |
[3] |
J. R. Artalejo,
Accessible bibliography on retrial queues: Progress in 2000--2009, Mathematical and Computer Modelling, 51 (2010), 1071-1081.
doi: 10.1016/j.mcm.2009.12.011. |
[4] |
Y. Aviv and A. Federgruen,
The value iteration method for countable state markov decision processes, Operations Research Letters, 24 (1999), 223-234.
doi: 10.1016/S0167-6377(99)00015-2. |
[5] |
S. Benjaafar, J.-P. Gayon and S. Tepe,
Optimal control of a production--inventory system with customer impatience, Operations Research Letters, 38 (2010), 267-272.
doi: 10.1016/j.orl.2010.03.008. |
[6] |
L. Breuer,
Threshold policies for controlled retrial queues with heterogeneous servers, Annals of Operations Research, 141 (2006), 139-162.
doi: 10.1007/s10479-006-5297-5. |
[7] |
R. Cavazos-Cadena and L. I. Sennott,
Comparing recent assumptions for the existence of average optimal stationary policies, Operations Research Letters, 11 (1992), 33-37.
doi: 10.1016/0167-6377(92)90059-C. |
[8] |
E. B. Çil, F. Karaesmen and E. L. Örmeci,
Dynamic pricing and scheduling in a multi-class single-server queueing system, Queueing Systems, 67 (2011), 305-331.
doi: 10.1007/s11134-011-9214-5. |
[9] |
E. B. Çil, E. L. Örmeci and F. Karaesmen,
Effects of system parameters on the optimal policy structure in a class of queueing control problems, Queueing Systems, 61 (2009), 273-304.
doi: 10.1007/s11134-009-9109-x. |
[10] |
S. D. Flapper, J.-P. Gayon and L. L. Lim,
On the optimal control of manufacturing and remanufacturing activities with a single shared server, European Journal of Operational Research, 234 (2014), 86-98.
doi: 10.1016/j.ejor.2013.10.049. |
[11] |
D. Gaver, P. Jacobs and G. Latouche,
Finite birth-and-death models in randomly changing environments, Advances in Applied Probability, 16 (1984), 715-731.
doi: 10.1017/S0001867800022916. |
[12] |
B. Hajek,
Optimal control of two interacting service stations, IEEE Transactions on Automatic Control, 29 (1984), 491-499.
doi: 10.1109/TAC.1984.1103577. |
[13] |
W. E. Helm and K.-H. Waldmann,
Optimal control of arrivals to multiserver queues in a random environment, Journal of Applied Probability, 21 (1984), 602-615.
doi: 10.1017/S0021900200028795. |
[14] |
D. P. Heyman,
Optimal operating policies for M/G/1 queuing systems, Operations Research, 16 (1968), 362-382.
doi: 10.1287/opre.16.2.362. |
[15] |
G. Koole,
Monotonicity in Markov Reward and Decision Chains: Theory and Applications vol. 1, Now Publishers Inc, 2007.
doi: 10.1561/0900000002. |
[16] |
B. K. Kumar and J. Raja,
On multiserver feedback retrial queues with balking and control retrial rate, Annals of Operations Research, 141 (2006), 211-232.
doi: 10.1007/s10479-006-5300-1. |
[17] |
B. K. Kumar, R. Rukmani and V. Thangaraj,
On multiserver feedback retrial queue with finite buffer, Applied Mathematical Modelling, 33 (2009), 2062-2083.
doi: 10.1016/j.apm.2008.05.011. |
[18] |
M. L. Puterman, Markov Decision Processes: Discrete Stochastic Dynamic Programming, John Wiley & Sons, New York, 1994.
![]() |
[19] |
L. I. Sennott,
Stochastic Dynamic Programming and the Control of Queueing Systems vol. 504, John Wiley & Sons, New York, 1999. |
[20] |
J.-D. Son,
Optimal admission and pricing control problem with deterministic service times and sideline profit, Queueing Systems, 60 (2008), 71-85.
doi: 10.1007/s11134-008-9087-4. |
[21] |
S. Stidham Jr and R. Weber,
A survey of markov decision models for control of networks of queues, Queueing Systems, 13 (1993), 291-314.
doi: 10.1007/BF01158935. |
[22] |
H. C. Tijms,
Stochastic Models: An Algorithmic Approach vol. 303, John Wiley & Sons Inc, 1994. |
[23] |
T. Van Do,
An efficient computation algorithm for a multiserver feedback retrial queue with a large queueing capacity, Applied Mathematical Modelling, 34 (2010), 2272-2278.
doi: 10.1016/j.apm.2009.10.025. |
[24] |
J. Wu and Z. Lian,
Analysis of the $M_{1}, M_{2}$/G/1 G-queueing system with retrial customers, Nonlinear Analysis: Real World Applications, 14 (2013), 365-382.
doi: 10.1016/j.nonrwa.2012.06.009. |
[25] |
J. Wu, J. Wang and Z. Liu,
A discrete-time Geo/G/1 retrial queue with preferred and impatient customers, Applied Mathematical Modelling, 37 (2013), 2552-2561.
doi: 10.1016/j.apm.2012.06.011. |
[26] |
S. Yoon and M. E. Lewis,
Optimal pricing and admission control in a queueing system with periodically varying parameters, Queueing Systems, 47 (2004), 177-199.
doi: 10.1023/B:QUES.0000035313.20223.3f. |
[27] |
X. Zhang, J. Wang and T. Van Do,
Threshold properties of the M/M/1 queue under T-policy with applications, Applied Mathematics and Computation, 261 (2015), 284-301.
doi: 10.1016/j.amc.2015.03.109. |
arrival rate | Optimal thresholds and average cost | |||
| | | | |
0.8 | (4, 3, 8.1688) | (17, 14, 0.7604) | (22, 18, 0.2148) | (22, 18, 0.0699) |
0.85 | (3, 3, 9.3409) | (14, 11, 1.2510) | (16, 12, 0.4664) | (16, 12, 0.2033) |
0.9 | (3, 2, 10.5053) | (11, 8, 1.9359) | (12, 8, 0.9216) | (10, 7, 0.5109) |
0.95 | (3, 2, 11.6892) | (9, 6, 2.7854) | (8, 5, 1.5937) | (7, 4, 1.0490) |
1 | (3, 2, 12.9001) | (7, 5, 3.7574) | (6, 3, 2.4441) | (4, 1, 1.8044) |
1.05 | (3, 2, 14.1340) | (6, 4, 4.8209) | (4, 2, 3.4291) | (2, 1, 2.7468) |
arrival rate | Optimal thresholds and average cost | |||
| | | | |
0.8 | (4, 3, 8.1688) | (17, 14, 0.7604) | (22, 18, 0.2148) | (22, 18, 0.0699) |
0.85 | (3, 3, 9.3409) | (14, 11, 1.2510) | (16, 12, 0.4664) | (16, 12, 0.2033) |
0.9 | (3, 2, 10.5053) | (11, 8, 1.9359) | (12, 8, 0.9216) | (10, 7, 0.5109) |
0.95 | (3, 2, 11.6892) | (9, 6, 2.7854) | (8, 5, 1.5937) | (7, 4, 1.0490) |
1 | (3, 2, 12.9001) | (7, 5, 3.7574) | (6, 3, 2.4441) | (4, 1, 1.8044) |
1.05 | (3, 2, 14.1340) | (6, 4, 4.8209) | (4, 2, 3.4291) | (2, 1, 2.7468) |
service rate | Optimal thresholds and average cost | |||
| | | | |
0.75 | (3, 2, 10.7715) | (5, 3, 4.1044) | (3, 1, 2.9138) | (2, 1, 2.3607) |
0.8 | (3, 2, 10.1999) | (6, 4, 3.1936) | (5, 2, 2.0532) | (3, 1, 1.4776) |
0.85 | (3, 2, 9.6629) | (8, 6, 2.3784) | (7, 4, 1.3332) | (6, 3, 0.8377) |
0.9 | (3, 2, 9.1583) | (11, 8, 1.6889) | (11, 8, 0.7815) | (10, 6, 0.4095) |
0.95 | (3, 3, 8.6564) | (14, 11, 1.1467) | (16, 12, 0.4167) | (15, 11, 0.1738) |
1 | (4, 3, 8.1688) | (17, 14, 0.7604) | (22, 18, 0.2148) | (22, 18, 0.0699) |
service rate | Optimal thresholds and average cost | |||
| | | | |
0.75 | (3, 2, 10.7715) | (5, 3, 4.1044) | (3, 1, 2.9138) | (2, 1, 2.3607) |
0.8 | (3, 2, 10.1999) | (6, 4, 3.1936) | (5, 2, 2.0532) | (3, 1, 1.4776) |
0.85 | (3, 2, 9.6629) | (8, 6, 2.3784) | (7, 4, 1.3332) | (6, 3, 0.8377) |
0.9 | (3, 2, 9.1583) | (11, 8, 1.6889) | (11, 8, 0.7815) | (10, 6, 0.4095) |
0.95 | (3, 3, 8.6564) | (14, 11, 1.1467) | (16, 12, 0.4167) | (15, 11, 0.1738) |
1 | (4, 3, 8.1688) | (17, 14, 0.7604) | (22, 18, 0.2148) | (22, 18, 0.0699) |
retrial rate | Optimal thresholds and average cost | |||
| | | | |
0.1 | (1, 1, 17.0052) | (5, 3, 4.9228) | (10, 6, 2.4449) | (15, 9, 1.6616) |
0.12 | (2, 1, 16.8627) | (6, 3, 4.7616) | (12, 7, 2.3554) | (16, 10, 1.6257) |
0.14 | (2, 1, 16.7071) | (6, 4, 4.6076) | (13, 8, 2.2816) | (17, 10, 1.6030) |
0.16 | (2, 2, 16.5549) | (7, 4, 4.4670) | (14, 9, 2.2220) | (17, 11, 1.5898) |
0.18 | (2, 2, 16.4067) | (8, 5, 4.3381) | (15, 10, 2.1744) | (17, 11, 1.5828) |
0.2 | (2, 2, 16.2641) | (8, 5, 4.2173) | (15, 10, 2.1358) | (18, 11, 1.5809) |
retrial rate | Optimal thresholds and average cost | |||
| | | | |
0.1 | (1, 1, 17.0052) | (5, 3, 4.9228) | (10, 6, 2.4449) | (15, 9, 1.6616) |
0.12 | (2, 1, 16.8627) | (6, 3, 4.7616) | (12, 7, 2.3554) | (16, 10, 1.6257) |
0.14 | (2, 1, 16.7071) | (6, 4, 4.6076) | (13, 8, 2.2816) | (17, 10, 1.6030) |
0.16 | (2, 2, 16.5549) | (7, 4, 4.4670) | (14, 9, 2.2220) | (17, 11, 1.5898) |
0.18 | (2, 2, 16.4067) | (8, 5, 4.3381) | (15, 10, 2.1744) | (17, 11, 1.5828) |
0.2 | (2, 2, 16.2641) | (8, 5, 4.2173) | (15, 10, 2.1358) | (18, 11, 1.5809) |
[1] |
Xiaohong Li, Mingxin Sun, Zhaohua Gong, Enmin Feng. Multistage optimal control for microbial fed-batch fermentation process. Journal of Industrial & Management Optimization, 2021 doi: 10.3934/jimo.2021040 |
[2] |
Tao Wu, Yu Lei, Jiao Shi, Maoguo Gong. An evolutionary multiobjective method for low-rank and sparse matrix decomposition. Big Data & Information Analytics, 2017, 2 (1) : 23-37. doi: 10.3934/bdia.2017006 |
[3] |
Chih-Chiang Fang. Bayesian decision making in determining optimal leased term and preventive maintenance scheme for leased facilities. Journal of Industrial & Management Optimization, 2020 doi: 10.3934/jimo.2020127 |
[4] |
Yves Dumont, Frederic Chiroleu. Vector control for the Chikungunya disease. Mathematical Biosciences & Engineering, 2010, 7 (2) : 313-345. doi: 10.3934/mbe.2010.7.313 |
[5] |
Charles Fulton, David Pearson, Steven Pruess. Characterization of the spectral density function for a one-sided tridiagonal Jacobi matrix operator. Conference Publications, 2013, 2013 (special) : 247-257. doi: 10.3934/proc.2013.2013.247 |
[6] |
Armin Lechleiter, Tobias Rienmüller. Factorization method for the inverse Stokes problem. Inverse Problems & Imaging, 2013, 7 (4) : 1271-1293. doi: 10.3934/ipi.2013.7.1271 |
[7] |
J. Frédéric Bonnans, Justina Gianatti, Francisco J. Silva. On the convergence of the Sakawa-Shindo algorithm in stochastic control. Mathematical Control & Related Fields, 2016, 6 (3) : 391-406. doi: 10.3934/mcrf.2016008 |
[8] |
Diana Keller. Optimal control of a linear stochastic Schrödinger equation. Conference Publications, 2013, 2013 (special) : 437-446. doi: 10.3934/proc.2013.2013.437 |
[9] |
Alberto Bressan, Ke Han, Franco Rampazzo. On the control of non holonomic systems by active constraints. Discrete & Continuous Dynamical Systems - A, 2013, 33 (8) : 3329-3353. doi: 10.3934/dcds.2013.33.3329 |
[10] |
Qiang Guo, Dong Liang. An adaptive wavelet method and its analysis for parabolic equations. Numerical Algebra, Control & Optimization, 2013, 3 (2) : 327-345. doi: 10.3934/naco.2013.3.327 |
[11] |
M. Grasselli, V. Pata. Asymptotic behavior of a parabolic-hyperbolic system. Communications on Pure & Applied Analysis, 2004, 3 (4) : 849-881. doi: 10.3934/cpaa.2004.3.849 |
[12] |
Elena Bonetti, Pierluigi Colli, Gianni Gilardi. Singular limit of an integrodifferential system related to the entropy balance. Discrete & Continuous Dynamical Systems - B, 2014, 19 (7) : 1935-1953. doi: 10.3934/dcdsb.2014.19.1935 |
[13] |
Dmitry Treschev. A locally integrable multi-dimensional billiard system. Discrete & Continuous Dynamical Systems - A, 2017, 37 (10) : 5271-5284. doi: 10.3934/dcds.2017228 |
[14] |
Nizami A. Gasilov. Solving a system of linear differential equations with interval coefficients. Discrete & Continuous Dynamical Systems - B, 2021, 26 (5) : 2739-2747. doi: 10.3934/dcdsb.2020203 |
[15] |
Paula A. González-Parra, Sunmi Lee, Leticia Velázquez, Carlos Castillo-Chavez. A note on the use of optimal control on a discrete time model of influenza dynamics. Mathematical Biosciences & Engineering, 2011, 8 (1) : 183-197. doi: 10.3934/mbe.2011.8.183 |
[16] |
Guirong Jiang, Qishao Lu. The dynamics of a Prey-Predator model with impulsive state feedback control. Discrete & Continuous Dynamical Systems - B, 2006, 6 (6) : 1301-1320. doi: 10.3934/dcdsb.2006.6.1301 |
[17] |
A. K. Misra, Anupama Sharma, Jia Li. A mathematical model for control of vector borne diseases through media campaigns. Discrete & Continuous Dynamical Systems - B, 2013, 18 (7) : 1909-1927. doi: 10.3934/dcdsb.2013.18.1909 |
[18] |
Luke Finlay, Vladimir Gaitsgory, Ivan Lebedev. Linear programming solutions of periodic optimization problems: approximation of the optimal control. Journal of Industrial & Management Optimization, 2007, 3 (2) : 399-413. doi: 10.3934/jimo.2007.3.399 |
[19] |
John T. Betts, Stephen Campbell, Claire Digirolamo. Examination of solving optimal control problems with delays using GPOPS-Ⅱ. Numerical Algebra, Control & Optimization, 2021, 11 (2) : 283-305. doi: 10.3934/naco.2020026 |
[20] |
Deren Han, Zehui Jia, Yongzhong Song, David Z. W. Wang. An efficient projection method for nonlinear inverse problems with sparsity constraints. Inverse Problems & Imaging, 2016, 10 (3) : 689-709. doi: 10.3934/ipi.2016017 |
2019 Impact Factor: 1.366
Tools
Metrics
Other articles
by authors
[Back to Top]