具有修正(p, N)-策略与单重休假的M/G/1排队分析

doi:10.15960/j.cnki.issn.1007-6093.2024.04.001

摘要/Abstract

摘要：

本文考虑一个具有修正$(p, N)$-策略和单重休假的$M/G/1$排队系统, 其中修正$(p, N)$-策略是指当服务员的休假结束回到系统时, 如果系统中有顾客但顾客数少于$N$, 则服务员以概率$p(0 \le p \le 1)$启动服务, 以概率$(1-p)$不启动服务直到系统中的顾客数累积到$N$个。运用更新过程理论、全概率分解技术和Laplace变换工具, 我们讨论了系统队长的瞬态分布, 得到队长瞬态分布关于时间$t$的L变换表达式。然后使用洛必达法则, 通过直接运算得到队长稳态分布的递推公式, 同时获得稳态队长分布的概率母函数和平均队长的显示表达式。最后, 应用更新报酬定理给出系统在长期运行单位时间内的期望费用的显示表达式, 并通过数值实例讨论了使得系统期望费用最小的最优控制策略$N^*$, 以及休假时间为定长$T(T\geqslant 0)$时的二维最优控制策略$(N^*, T^*)$。

关键词: M/G/1排队, 修正(p, N)-策略, 单重休假, 队长分布, 最优控制策略

Abstract:

This paper considers an $M/G/1$ queueing model with single vacation and modified $(p, N)$-policy. The modified $(p, N)$-policy means that when the vacation ends and the server returns to the system, if there are less than $N$ customers but at least one customer in the system, the server begins service with probability $p (0 \le p \le 1)$ or stays idle with probability $(1-p)$ until there are $N$ customers in the system and starts its service at once. By the renewal process theory, total probability decomposition technique and Laplace transform tool, we study the transient queue length distribution of the system, and obtain the expressions of the Laplace transform of the transient queue length distribution with respect to time $t$. Then, employing L'Hospital's rule and some algebraic manipulations, the recursive formulas of the steady-state queue length distribution are derived. Meanwhile, the explicit expressions for probability generating function of the steady-state queue length distribution and the expected queue size are presented. Finally, employing the renewal reward theorem, the explicit expression of the long-run expected cost per unit time is also presented. Numerical examples are provided to discuss the optimal control policy $N^*$ for economizing the system cost as well as the optimal two-dimensional control policy $(N^*, T^*)$ when the vacation time is a fixed length $T (T \ge 0)$.

Key words: M/G/1 queue, modified (p, N)-policy, single vacation, queue length distribution, optimal control policy

中图分类号:

O226

罗彦君, 唐应辉. 具有修正(p, N)-策略与单重休假的M/G/1排队分析[J]. 运筹学学报（中英文）, 2024, 28(4): 1-17.

Yanjun LUO, Yinghui TANG. Analysis of M/G/1 queue with single vacation and modified (p, N)-policy[J]. Operations Research Transactions, 2024, 28(4): 1-17.

图/表 4

表1

图1

表2

图2

参考文献 28

1	Yadin M , Naor P . Queueing systems with a removable service station[J]. Operational Research Quarterly, 1963, 14 (6): 393- 405.
2	Balachandran K R . Control policies for a single server system[J]. Management Science, 1973, 19 (9): 1013- 1018. doi: 10.1287/mnsc.19.9.1013
3	Heyman D P . $T$-policy for the $M/G/1$ queue[J]. Management Science, 1977, 23 (7): 775- 778. doi: 10.1287/mnsc.23.7.775
4	Doshi B T . Queueing systems with vacations—–a survey[J]. Queueing Systems, 1986, 1 (1): 29- 66. doi: 10.1007/BF01149327
5	田乃硕. 休假随机服务系统[M]. 北京: 北京大学出版社, 2001.
6	唐应辉, 唐小我. 排队论: 基础与分析技术[M]. 北京: 科学出版社, 2006.
7	Tian N S , Zhang Z G . Vacation Queueing Models: Theory and Applications[M]. New York: Springer, 2006.
8	唐应辉, 吴文青, 刘云颇. 基于单重休假的Min$(N, V)$-策略$M/G/1$排队系统分析[J]. 应用数学学报, 2014, 37 (6): 976- 996.
9	唐应辉, 吴文青, 刘云颇, 等. 基于多重休假的Min$(N, V)$-策略$M/G/1$排队的队长分布[J]. 系统工程理论与实践, 2014, 34 (6): 1533- 1546.
10	蒋书丽, 唐应辉. 具有多级适应性休假和Min$(N, V)$-策略控制的$M/G/1$排队系统[J]. 系统科学与数学, 2017, 37 (8): 1866- 1884.
11	Lan S J , Tang Y H , Yu M M . System capacity optimization design and optimal threshold $N^$ for a $Geo/G/1$ discrete-time queue with single server vacation and under the control of Min$(N, V)$-policy[J]. Journal of Industrial and Management Optimization*, 2016, 12 (4): 1435- 1464. doi: 10.3934/jimo.2016.12.1435
12	Lan S J , Tang Y H . The structure of departure process and optimal control strategy $N^$ for $Geo/G/1$ discrete-time queue with multiple server vacations and Min$(N, V)$-policy[J]. Journal of Systems Science and Complexity*, 2017, 30 (6): 1382- 1402. doi: 10.1007/s11424-017-5279-5
13	Yu M M , Tang Y H , Fu Y H , et al. $GI/Geom/1/MWV$ queue with changeover time and searching for the optimum service rate in working vacation period[J]. Journal of Computational and Applied Mathematics, 2011, 235 (8): 2170- 2184. doi: 10.1016/j.cam.2010.10.013
14	Li J , Liu L W . On an $M/G/1$ queue in random environment with Min$(N,V)$-policy[J]. RAIRO-Operational Research, 2018, 52 (2): 61- 77.
15	唐蓓蕾, 唐应辉. 两类具有$N$-策略和单重休假的$M/G/1$排队系统的最优控制策略[J]. 运筹学学报, 2021, 25 (4): 15- 30.
16	Lee H W , Seo W J . The performance of the $M/G/1$ queue under the dyadic Min$(N,D)$-policy and its cost optimization[J]. Performance Evaluation, 2008, 65 (10): 742- 758. doi: 10.1016/j.peva.2008.04.006
17	罗乐, 唐应辉, 余玅妙, 等. 在修正的Min$(N, D)$-策略控制下延迟多级适应性休假$M/G/1$排队分析[J]. 系统科学与数学, 2021, 41 (9): 2549- 2570.
18	Wang K H , Wang T Y , Pearn W L . Optimal control of the $N$-policy $M/G/1$ queueing system with server breakdowns and general startup times[J]. Applied Mathematical Modelling, 2006, 31 (10): 2199- 2212.
19	曹晋华, 程侃. 服务台可修的$M/G/1$排队系统分析[J]. 应用数学学报, 1982, 5 (2): 113- 127.
20	Tang Y H . Some reliability problems arising in $GI/G/1$ queueing system with repairable service station[J]. Microelectronics and Reliability, 1995, 35 (4): 707- 712. doi: 10.1016/0026-2714(94)00069-Z
21	Tang Y H . A single server $M/G/1$ queueing system subject to breakdowns—–some reliability and queueing problems[J]. Microelectronics and Reliability, 1997, 37 (2): 315- 321. doi: 10.1016/S0026-2714(96)00018-2
22	蔡晓丽, 唐应辉. 具有温储备失效特征和单重休假Min$(N,V)$-控制策略的$M/G/1$可修排队系统[J]. 应用数学学报, 2017, 40 (5): 692- 701.
23	旷欣宇, 唐应辉. 带启动时间与双阈值$(m,N)$-策略的$M/G/1$可修排队系统的最优控制策略[J]. 运筹与管理, 2021, 30 (10): 64- 70.
24	Feinberg E A , Kim D J . Bi-criterion optimization of an $M/G/1$ queue with a removable server[J]. Probability in the Engineering and Informational Sciences, 1996, 10 (5): 57- 73.
25	Wang K H , Huang K B . A maximum entropy approach for the $(p,N)$-policy $M/G/1$ queue with a removable and unreliable server[J]. Applied Mathematical Modelling, 2009, 33 (10): 2024- 2034.
26	Wang T Y , Ke J C . The randomized threshold for the discrete-time $Geo/G/1$ queue[J]. Applied Mathematical Modelling, 2009, 33 (10): 3178- 3185.
27	Lan S J , Tang Y H . Performance and reliability analysis of a repairable discrete-time $Geo/G/1$ queue with Bernoulli feedback and randomized policy[J]. Applied Stochastic Model in Business and Industry, 2017, 33 (5): 522- 543. doi: 10.1002/asmb.2253
28	Jain M , Kaur S . $(p,N)$-policy for unreliable server bulk queue with Bernoulli feedback[J]. International Journal of Applied Mathematics and Computer Science, 2020, 6 (4): 170- 198.

$ N $	$ \rho = 0.7 $	$ N $	$ \rho = 0.7 $	$ N $	$ \rho = 0.7 $	$ N $	$ \rho = 0.7 $
1	30.451 7	6	30.696 6	11	36.978 8	16	46.353 0
2	30.159 2	7	31.542 4	12	38.629 9	17	48.411 0
3	29.902 3	8	32.629 9	13	40.500 8	18	50.509 8
4	$ \fbox{29.867 5} $	9	33.920 7	14	42.388 6	19	52.643 9
5	30.129 9	10	35.380 1	15	44.348 2	20	54.808 8

$ N $	$ T^* $	$ F\left( {N, {T^*}} \right) $	$ N $	$ T^* $	$ F\left( {N, {T^*}} \right) $
1	5.671 6	$ \fbox{26.494 6}$	6	5.714 3	26.652 0
2	5.671 8	26.496 5	7	5.735 6	26.802 0
3	5.672 0	26.500 2	8	5.778 3	27.021 6
4	5.678 1	26.517 1	9	5.842 2	27.314 6
5	5.693 0	26.562 0	10	5.927 5	27.680 4

[1]	唐蓓蕾, 唐应辉. 两类具有N-策略和单重休假的M/G/1排队系统的最优控制策略[J]. 运筹学学报, 2021, 25(4): 15-30.
[2]	钟瑶, 唐应辉. 具有两类失效模式的D-策略M/G/1可修排队系统分析[J]. 运筹学学报, 2020, 24(1): 40-56.
[3]	罗乐, 唐应辉. 具有Min(N,D,V)-策略控制的M/G/1排队系统[J]. 运筹学学报, 2019, 23(2): 1-16.
[4]	潘取玉, 唐应辉, 兰绍军. 带负顾客和N-策略的Geo^{lambda_1, lambda_2/Geo/1(MWV)排队系统分析及最优控制策略N*[J]. 运筹学学报, 2017, 21(3): 65-76.
[5]	魏瑛源, 唐应辉, 余玅妙. 延迟Min(N,D)-策略的M/G/1排队系统的队长分布与数值计算[J]. 运筹学学报, 2016, 20(2): 23-37.