Optimal policy for controlling two-server queueing systems with jockeying

doi:10.23919/JSEE.2022.000015

Journal of Systems Engineering and Electronics ›› 2022, Vol. 33 ›› Issue (1): 144-155.doi: 10.23919/JSEE.2022.000015

• SYSTEMS ENGINEERING • Previous Articles Next Articles

Optimal policy for controlling two-server queueing systems with jockeying

Bing LIN^1,*(), Yuchen LIN²(), Rohit BHATNAGAR³()

¹ School of Business, Jiangsu Normal University, Xuzhou 221116, China
² Wenzheng College, Soochow University, Suzhou 215104, China
³ Nanyang Business School, Nanyang Technological University, Nanyang 639798, Singapore

Received:2020-10-19 Accepted:2021-12-27 Online:2022-01-18 Published:2022-02-22
Contact: Bing LIN E-mail:linbing_jsnu@163.com;yclin_ee@163.com;arbhatnagar@ntu.edu.sg
About author:|LIN Bing was born in 1969. He received his B.S. degree from Fudan University in 1992, MBA from Tsinghua University in 2003, and Ph.D. degree in operations management from Nanyang Technological University, Singapore in 2008. Currently, he is a lecturer in Jiangsu Normal University. His research interests are modeling and optimization of queueing systems, production/inventory systems, and supply chain systems. E-mail: linbing_jsnu@163.com||LIN Yuchen was born in 2000. She is currently an undergraduate student in electrical engineering at the Wenzheng College of Soochow University. She has publications on logistics technology and logistics science and technology. Her research interests are wireless charging technology, smart logistics system, and machine learning. E-mail: yclin_ee@163.com||BHATNAGAR Rohit was born in 1960. He received his B.Tech. degree from Indian Institute of Technology (BHU), India in 1983, MBA from the India Institute of Management, Bangalore, India in 1985, and Ph.D. degree in operations management from McGill University, Canada in 1994. Currently, he is an associate professor in Nanyang Business School, Nanyang Technological University, Singapore. His research interests are design and planning of manufacturing and supply chain systems. E-mail: arbhatnagar@ntu.edu.sg
Supported by:
This work was supported by the National Social Science Fund of China (19BGL100).

Abstract

Abstract:

This paper studies the optimal policy for joint control of admission, routing, service, and jockeying in a queueing system consisting of two exponential servers in parallel. Jobs arrive according to a Poisson process. Upon each arrival, an admission/routing decision is made, and the accepted job is routed to one of the two servers with each being associated with a queue. After each service completion, the servers have an option of serving a job from its own queue, serving a jockeying job from another queue, or staying idle. The system performance is inclusive of the revenues from accepted jobs, the costs of holding jobs in queues, the service costs and the job jockeying costs. To maximize the total expected discounted return, we formulate a Markov decision process (MDP) model for this system. The value iteration method is employed to characterize the optimal policy as a hedging point policy. Numerical studies verify the structure of the hedging point policy which is convenient for implementing control actions in practice.

Key words: queueing system, jockeying, optimal policy, Markov decision process (MDP), dynamic programming

Bing LIN, Yuchen LIN, Rohit BHATNAGAR. Optimal policy for controlling two-server queueing systems with jockeying[J]. Journal of Systems Engineering and Electronics, 2022, 33(1): 144-155.

Figures/Tables 9

Fig 1

Fig 2

Fig 3

Fig 4

Fig 5

Fig 6

Fig 7

Fig 8

Table 1

References 41

1	NAOR P On the regulation of queue size by levying tolls. Econometrica, 1969, 37 (1): 15- 24. doi: 10.2307/1909200
2	LIPPMAN S, STIDHAM S Individual versus social optimization in exponential congestion systems. Operations Research, 1977, 25 (2): 233- 247. doi: 10.1287/opre.25.2.233
3	STIDHAM S Socially and individually optimal control of arrivals to a GI/M/1 queue. Management Science, 1978, 24 (15): 1598- 1610. doi: 10.1287/mnsc.24.15.1598
4	VAN NUNEN J A E E, PUTERMAN M L Computing optimal control limits for GI/M/s queueing systems with controlled arrivals. Management Science, 1983, 29 (6): 725- 734. doi: 10.1287/mnsc.29.6.725
5	EPHREMIDES A, VARAIYA P, WALRAND J A simple dynamic routing problem. IEEE Trans. on Automatic Control, 1980, 25 (4): 690- 693. doi: 10.1109/TAC.1980.1102445
6	HAJEK B Optimal control of two interacting service stations. IEEE Trans. on Automatic Control, 1984, 29 (6): 491- 498. doi: 10.1109/TAC.1984.1103577
7	WEBER R R On the optimal assignment of customers to parallel servers. Journal of Applied Probability, 1978, 15 (2): 406- 413. doi: 10.2307/3213411
8	KRISHNAN K R Joining the right queue: a Markov decision rule. Proc. of the 26th IEEE Conference on Decision and Control, 1987, 1863- 1868.
9	WEBER R R, STIDHAM S Optimal control of service rates in networks of queues. Advances in Applied Probability, 1987, 19 (1): 202- 218. doi: 10.2307/1427380
10	YAO D D, SCHECHNER Z Decentralized control of service rates in a closed Jackson network. IEEE Trans. on Automatic Control, 1989, 34 (2): 236- 240. doi: 10.1109/9.21110
11	DAVIS E L. Optimal control of arrivals to a two-server queueing system with separate queues. North Carolina, USA: North Carolina State University, 1977.
12	ABDEL-GAWAD E F. Optimal control of arrivals and routing in a network of queues. North Carolina, USA: North Carolina State University, 1984.
13	LI Q L, MA J Y, FAN R N, et al. An overview for Markov decision processes in queues and networks. LI Q , WANG J, YU H B, ed. Stochastic models in reliability, network security and system safety. Singapore: Springer, 2009.
14	CAI J H, WANG L P, ZHOU G G Supply chain coordination mechanisms under flexible contracts. Journal of Systems Engineering and Electronics, 2010, 21 (3): 440- 448. doi: 10.3969/j.issn.1004-4132.2010.03.014
15	LI H Y, YOU T H, LUO X Y Collaborative supply chain planning under dynamic lot sizing costs with capacity decision. Journal of Systems Engineering and Electronics, 2011, 22 (2): 247- 256. doi: 10.3969/j.issn.1004-4132.2011.02.010
16	WEN M L, LU B H, LI S Y, et al Location and allocation problem for spare parts depots on integrated logistics support. Journal of Systems Engineering and Electronics, 2019, 30 (6): 1252- 1259. doi: 10.21629/JSEE.2019.06.19
17	YUE F, SONG S J, JIA P, et al Robust single machine scheduling problem with uncertain job due dates for industrial mass production. Journal of Systems Engineering and Electronics, 2020, 31 (2): 350- 358. doi: 10.23919/JSEE.2020.000012
18	XU S H, ZHAO Y Q Dynamic routing and jockeying controls in a two-station queueing system. Advances in Applied Probability, 1996, 28 (4): 1201- 1226. doi: 10.2307/1428170
19	ADAN I J B F, WESSELS J, ZIJM W H M Analysis of the asymmetric shortest queue problem with threshold jockeying. Communications in Statistics. Stochastic Models, 1991, 7 (4): 615- 627. doi: 10.1080/15326349108807209
20	ADAN I J B F, WESSELS J, ZIJM W H M Matrix-geometric analysis of the shortest queue problem with threshold jockeying. Operations Research Letters, 1993, 13 (2): 107- 112. doi: 10.1016/0167-6377(93)90037-H
21	ZHAO Y Q, GRASSMANN W K Queueing analysis of a jockeying model. Operations Research, 1995, 43 (3): 520- 529. doi: 10.1287/opre.43.3.520
22	ZHAO Y Q, GRASSMANN W K A solution of the shortest queue model with jockeying-in terms of traffic intensity ρ . Naval Research Logistics, 1990, 37 (5): 773- 787. doi: 10.1002/1520-6750(199010)37:5<773::AID-NAV3220370514>3.0.CO;2-2
23	DISNEY R L, MITCHELL W E A solution for queues with instantaneous jockeying and other customer selection rules. Naval Research Logistics Quarterly, 1970, 17 (3): 315- 325. doi: 10.1002/nav.3800170308
24	ELSAYED E A, BASTANI A General solutions of jockeying problem. European Journal Operational Research, 1985, 22 (3): 387- 396. doi: 10.1016/0377-2217(85)90258-9
25	HAIGHT F A Two queues in parallel. Biometrika, 1958, 45 (3/4): 401- 410. doi: 10.1093/biomet/45.3-4.401
26	KAO E P C, LIN C A matrix-geometric solution of the jockeying problem. European Journal of Operational Research, 1990, 44 (1): 67- 74. doi: 10.1016/0377-2217(90)90315-3
27	KOENIGSBERG E On jockeying in queues. Management Science, 1966, 12 (5): 412- 436. doi: 10.1287/mnsc.12.5.412
28	SAKUMA Y Asymptotic behavior for MAP/PH/c queue with shortest queue discipline and jockeying. Operations Research Letters, 2010, 38 (1): 7- 10. doi: 10.1016/j.orl.2009.09.011
29	RAVID R A new look on the shortest queue system with jockeying. Probability in the Engineering and Informational Sciences, 2021, 35 (3): 557- 564. doi: 10.1017/S0269964819000469
30	JEGANATHAN K, SUMATHI J, MAHALAKSHMI G Markovian inventory model with two parallel queues, jockeying and impatient customers. Yugoslav Journal of Operations Research, 2016, 26 (4): 467- 506. doi: 10.2298/YJOR150326018J
31	STAGJE W A queueing system with two parallel lines, cost-conscious customers, and jockeying. Communications in Statistics-Theory and Methods, 2009, 38 (16/17): 3158- 3169. doi: 10.1080/03610920902947618
32	TARABIA A M K Analysis of two queues in parallel with jockeying and restricted capacities. Applied Mathematical Modelling, 2008, 32 (5): 802- 810. doi: 10.1016/j.apm.2007.02.014
33	BAYKASOGLU A, DURMUSOGLU Z D Flow time analyses of a simulated flexible job shop by considering jockeying. International Journal of Advanced Manufacturing Technology, 2012, 58 (5/8): 693- 707.
34	CHALESHTORI A E, JAHANI H, AGHAIE A Bi-objective optimization approach to a multi-layer location-allocation problem with jockeying. Computers & Industrial Engineering, 2020, 149, 106740.
35	DOWN D G, LEWIS M E Dynamic load balancing in parallel queueing systems: stability and optimal control. European Journal of Operational Research, 2006, 168 (2): 509- 519. doi: 10.1016/j.ejor.2004.04.041
36	ROSBERG Z, PENG Y, FU J, et al Insensitive job assignment with throughput and energy criteria for processor-sharing server farms. IEEE/ACM Trans. on Networking, 2014, 22 (4): 1257- 1270. doi: 10.1109/TNET.2013.2276427
37	DEHGHANIAN A, KHAROUFEH J P, MODARRES M Strategic dynamic jockeying between two parallel queues. Probability in the Engineering and Informational Sciences, 2016, 30 (1): 41- 60. doi: 10.1017/S0269964815000273
38	LIPPMAN S Applying a new device in the optimization of exponential queueing systems. Operations Research, 1975, 23 (4): 687- 710. doi: 10.1287/opre.23.4.687
39	PUTERMAN M L. Markov decision processes: discrete stochastic dynamic programming. New Jersey: John Wiley & Sons, 1994.
40	LIN B. Dynamic revenue management of airline and production systems. Singapore: Nanyang Technological University, 2008.
41	TIJMS H C. A first course in stochastic models. West Sussex, England: John Wiley & Sons, 2003.

Case	Paremeters of the system											V(0,0)	Variation/%
Case	r₁	r₂	c₁	c₂	c₁₂	c₂₁	h₁	h₁	λ	μ₁	μ₂	V(0,0)	Variation/%
Base case	7	7	2	2	3	3	1	1	2	2	2	22.699	0
No jockeying	7	7	2	2	0	0	1	1	2	2	2	16.372	?27.87
1	7	7	2	2	2.1	2.1	1	1	2	2	2	26.395	16.28
2	7	7	2	2	3.5	3.5	1	1	2	2	2	21.47	?5.42
3	7	7	2	2	4	4	1	1	2	2	2	20.332	?10.43
4	7	7	2	2	4.5	4.5	1	1	2	2	2	19.275	?15.09
5	7	7	2	2	5	5	1	1	2	2	2	18.322	?19.28
6	7	7	2	2	3	3	1	1	1	2	2	?14.333	?163.15
7	7	7	2	2	3	3	1	1	1.5	2	2	5.205	?77.07
8	7	7	2	2	3	3	1	1	2.5	2	2	37.187	63.83
9	7	7	2	2	3	3	1	1	3	2	2	47.86	110.84
10	7	7	2	2	3	3	1	1	3.5	2	2	55.071	142.62
11	7	7	2	2	3	3	1	1	2	1.5	1.5	1.228	?94.59
12	7	7	2	2	3	3	1	1	2	1.5	2	13.327	?41.29
13	7	7	2	2	3	3	1	1	2	2.5	2	29.691	30.8
14	7	7	2	2	3	3	1	1	2	3	2	34.861	53.58
15	7	7	2	2	3	3	1	1	2	3	3	39.907	75.81

[1]	Xin ZENG, Yanwei ZHU, Leping YANG, Chengming ZHANG. A guidance method for coplanar orbital interception based on reinforcement learning [J]. Journal of Systems Engineering and Electronics, 2021, 32(4): 927-938.
[2]	Ning MA, Jimin YE, Junyuan WANG. A generalized geometric process based repairable system model with bivariate policy [J]. Journal of Systems Engineering and Electronics, 2021, 32(3): 631-641.
[3]	Zixuan ZHANG, Qinhao WU, Bo ZHANG, Xiaodong YI, Yuhua TANG. UAV flight strategy algorithm based on dynamic programming [J]. Journal of Systems Engineering and Electronics, 2018, 29(6): 1293-1299.
[4]	Kaifang WAN, Xiaoguang GAO, Bo LI, Fei LI. Using approximate dynamic programming for multi-ESM scheduling to track ground moving targets [J]. Journal of Systems Engineering and Electronics, 2018, 29(1): 74-85.
[5]	Mingyong Liu, Baogui Xu, and Xingguang Peng. Cooperative path planning for multi-AUV in time-varying ocean flows [J]. Systems Engineering and Electronics, 2016, 27(3): 612-618.
[6]	Mao Yang, Yong Li, Depeng Jin, Li Su, and Lieguang Zeng. Opportunistic spectrum sharing in software defined wireless network [J]. Journal of Systems Engineering and Electronics, 2014, 25(6): 934-941.
[7]	Lun Ran, Jinlin Li, Xujie Jia, and Hongrui Chu. Optimal redundancy allocation for reliability systems with imperfect switching [J]. Journal of Systems Engineering and Electronics, 2014, 25(2): 332-339.
[8]	Xiang Gao, Yangwang Fang, and Youli Wu. Fuzzy Q learning algorithm for dual-aircraft path planning to cooperatively detect targets by passive radars [J]. Journal of Systems Engineering and Electronics, 2013, 24(5): 800-810.
[9]	Fu Chen, Guangzhou Zhao, and Xiaoming Yu. Stabilizing model predictive control scheme for piecewise affine systems with maximal positively invariant terminal set [J]. Journal of Systems Engineering and Electronics, 2010, 21(6): 1090-1094.
[10]	Wu Li, Guanqi Guo, Chaoyuan Yue, and Yong Zhao. Dynamic programming methodology for multi-criteria group decision-making under ordinal preferences [J]. Journal of Systems Engineering and Electronics, 2010, 21(6): 975-980.
[11]	Shao Feng, Jiang Gangyi & Yu Mei. Multi-view video color correction using dynamic programming [J]. Journal of Systems Engineering and Electronics, 2008, 19(6): 1115-1120.
[12]	Wang Tao, Lu Xianliang & Hou Mengshu. Novel algorithm for distributed replicas management based on dynamic programming [J]. Journal of Systems Engineering and Electronics, 2006, 17(3): 669-672.
[13]	Thang Jing, Wang Changshun, Liao Wuling, Ou Zongying & Hua Shungang. View synthesis based on the serial images from camera lengthways motion [J]. Journal of Systems Engineering and Electronics, 2006, 17(2): 284-289.

Optimal policy for controlling two-server queueing systems with jockeying

RichHTML

PDF (PC)

Knowledge

Abstract

Cite this article

Share this article

Figures/Tables 9

References 41

Related Articles 13

Recommended Articles

Metrics

Comments