在$D$-策略控制下服务员单重休假且休假不中断的$M$/$G$/1排队系统分析

摘要/Abstract

摘要：

该文研究在 $D$ -策略控制下服务员单重休假且休假不中断的 $M/G/1$ 排队系统，其中当服务员休假结束归来时，如果系统中等待服务的顾客所需的总服务时间之和不小于事先给定的正数阀值 $D$ ，服务员就立即开始服务.运用全概率分解技术、更新过程理论和拉普拉斯变换工具，本文在任意初始状态下讨论了队长的瞬态分布，导出了队长瞬态分布的拉普拉斯变换的表达式和稳态队长分布的递推表达式.同时给出了稳态队长的随机分解结构、附加队长分布的显示表达式.进一步借用稳态队长分布 $\left\{ {{p}_{j}}，j=0，1，2，\cdots \right\}$ ，讨论了系统容量的优化设计，并阐述了稳态队长分布对系统容量优化设计所起的重要作用.最后，在建立费用模型的基础上，导出了系统在长期单位时间内期望费用的显示表达式，并通过数值实例不仅确定了使系统在长期单位时间内的期望费用最小的控制策略 ${{D}^{*}}$ ，而且还得到了当休假时间长度为固定时长 $T(>0)$ 时系统的联合控制策略 $({{T}^{*}}，{{D}^{*}})$ .

关键词: D-策略, 单重休假且休假不中断, 全概率分解技术, 系统容量设计, 最优控制策略

Abstract:

This paper studies the $M/G/1$ queueing system for single server vacation without interruption under the control of $D$ -policy, in which when the server is transferred on vacation, the server starts service immediately if the total service times of waiting customers is no less than a given positive threshold $D$ . Applying the total probability decomposition technique, renewal theory and the Laplace transform tool, the transient queue length distribution from any initial state is discussed. Both the expressions of the Laplace transformation of the transient queue length distribution and the recursive expressions of the steady-state queue length distribution are derived. Meanwhile, the stochastic decomposition structure of the steady-state queue length and the explicit expression of the additional queue distribution are displayed. Furthermore, by employing the steady-state queue length distribution $\left\{ {{p}_{j}}, j=0, 1, 2, \cdots \right\}$ , we discuss the optimization design of the system capacity and illustrate the important effect of the steady-state queue length distribution. Finally, the explicit expression of the long-run expected cost rate is derived under a given cost structure. And by numerical calculation, we determine the optimal control policy ${{D}^{*}}$ for minimizing the long-run expected cost per unit time as well as the combined control strategy $({{T}^{*}}, {{D}^{*}})$ when the vacation time is fixed duration $T(>0)$ .

Key words: D-Policy, Single vacation without interruption, Total probability decomposition technique, System capacity design, Optimal control policy

中图分类号:

O213.2

刘琼琳,唐应辉. 在 $D$ -策略控制下服务员单重休假且休假不中断的 $M$ / $G$ /1排队系统分析[J]. 数学物理学报, 2021, 41(1): 269-288.

Qionglin Liu,Yinghui Tang. Analysis of $M$ / $G$ /1 Queueing System for Single Server Vacation Without Interruption Under the Control of $D$ -Policy[J]. Acta mathematica scientia,Series A, 2021, 41(1): 269-288.

图/表 10

图 1

图 2

图 3

图 4

图 5

表 1

$\lambda = 0.5, \mu = 1.5, D = 5, T = 15$ 时稳态队长分布及平均队长"

p₀	p₁	p₂	p₃	p₄	p₅	p₆	p₇	p₈
0.0696	0.0927	0.1005	0.1030	0.1033	0.1018	0.0971	0.0881	0.074
p₉	p₁₀	p₁₁	p₁₂	p₁₃	p₁₄	p₁₅	p₁₆	p₁₇
0.0587	0.0426	0.0285	0.0178	0.0103	0.0056	0.0029	0.0014	0.0007
p₁₈	p₁₉	p₂₀	p₂₁	p₂₂	p₂₃	p₂₄	......	E[L_D]
0.0003	0.0001	0.0001	0.0000	0.0000	0.0000	0.0000		3.6376

表 1

图 6

$\lambda = 0.5, \mu = 1.5, D = 5, T = 15$ 时稳态队长分布的直方图"

图 6

表 2

图 7

${{F}_{D}}$ 随 $D$ 和 $\rho$ 的变化情况"

图 7

图 8

$\lambda = 0.6, \rho = 0.8, h = 4, C = 150$ 时, ${{F}_{D}}$ 随 $D$ 与 $T$ 的变化"

图 8

参考文献 27

1	Doshi B . Queueing systems with vacations:a survey. Queueing Systems, 1986, 1: 29- 66 doi: 10.1007/BF01149327
2	田乃硕. 休假随机服务系统. 北京: 北京大学出版社, 2001
	Tian N S . Stochastic Service System with Vacations. Beijing: Peking University Press, 2001
3	唐应辉, 唐小我. 排队论-基础与分析技术. 北京: 科学出版社, 2006
	Tang Y H , Tang X W . Queueing Theory-Foundations and Analysis Techniques. Beijing: Science Press, 2006
4	骆川义, 唐应辉. 具有可变到达率的多重休假 $Geo^{{{\lambda }_{1}},{{\lambda }_{2}}}/G/1$ 排队分析. 数学学报, 2010, 53 (4): 805- 816
	Luo C Y , Tang Y H . Analysis of a multi-vacation $Geo^{{{\lambda }_{1}},{{\lambda }_{2}}}/G/1$ queue with variable arrival rate. Acta Mathematica Sinica, 2010, 53 (4): 805- 816
5	Luo C Y , Xiang X L , Yu M M , Tang Y H . Recursive solution of queue length distribution for $Geo/G/1$ queue with single server vacation and variable input rate. Computers and Mathematics with Applications, 2011, 61 (9): 2401- 2411 doi: 10.1016/j.camwa.2011.02.018
6	余妙妙, 唐应辉, 付永红. 具有中途准入机制和多重休假的离散时间 $GI/Geom(a,b)/1/N$ 早到达排队系统. 应用数学学报, 2011, 34 (5): 853- 872
	Yu M M , Tang Y H , Fu Y H . $GI/Geom(a,b)/1/N$ early queueing system with accessible mechanism of ongoing service and multiple vacation. Acta Mathematicae Applicatae Sinica, 2011, 34 (5): 853- 872
7	Luo C Y , Tang Y H . The recursive solution for $Geom/G/1(E,SV)$ queue with feedback and single server vacation. Acta Mathematicae Applicatae Sinica, 2011, 27 (1): 155- 166 doi: 10.1007/s10255-011-0049-y
8	Wei Y Y , Yu M M , Tang Y H , Gu J X . Queue size distribution and capacity optimum design for $N$ -policy $Geo^{({{\lambda }_{1}},{{\lambda }_{2}},{{\lambda }_{3}})}/G/1$ queue with setup time and variable input rate. Mathematical and Computer Modelling, 2013, 57 (5/6): 1559- 1571
9	唐应辉, 吴文青, 刘云颇. 基于单重休假的 $Min(N,V)$ -策略 $M/G/1$ 排队系统分析. 应用数学学报, 2014, 37 (6): 976- 996
	Tang Y H , Wu W Q , Liu Y P . Analysis of $M/G/1$ queueing system with $Min(N,V)$ -policy based on single server vacation. Acta Mathematicae Applicatae Sinica, 2014, 37 (6): 976- 996
10	贺灵悦, 唐应辉. 带启动时间和多重休假的 $Min(N,V)$ -策略 $M/G/1$ 排队系统. 系统科学与数学, 2017, 37 (3): 864- 862
	He L Y , Tang Y H . $M/G/1$ queueing system with set-up time and $Min(N,V)$ -policy based on multiple server vacations. Journal of Systems Science and Mathematical Sciences, 2017, 37 (3): 864- 862
11	蒋书丽, 唐应辉. 具有多级适应性休假和 $Min(N,V)$ -策略控制的 $M/G/1$ 排队系统. 系统科学与数学, 2017, 37 (8): 1866- 1884
	Jang S L , Tang Y H . $M/G/1$ queueing system with multiple adaptive vacations and $Min(N,V)$ -policy. Journal of Systems Science and Mathematical Sciences, 2017, 37 (8): 1866- 1884
12	蔡晓丽, 唐应辉. 具有温储备失效特征和单重休假 $Min(N,V)$ -控制策略的 $M/G/1$ 可修排队系统. 应用数学学报, 2017, 40 (5): 692- 701
	Cai X L , Tang Y H . $M/G/1$ repairable queueing system with warm standby failure and $Min(N,V)$ -policy based on single vacation. Acta Mathematicae Applicatae Sinica, 2017, 40 (5): 692- 701
13	Balachandran K R , Tijms H C . On the $D$ -policy for the $M/G/1$ queue. Management Science, 1975, 21 (9): 1073- 1076
14	Artalejo J R . On the queue with $D$ -policy. Applied Mathematical Modelling, 2001, 25 (12): 1055- 1069 doi: 10.1016/S0307-904X(01)00031-2
15	Lee H W , Beak J W . Analysis of the $M.X$ /G/1 queue under D-policy. Stochastic Analysis and Applications, 2005, 23 (4): 785- 808 doi: 10.1081/SAP-200064479
16	魏瑛源, 唐应辉, 顾建雄. 延迟 $D$ -策略 $Geo/G/1$ 排队系统队长分布及容量的优化设计. 系统工程理论与实践, 2013, 33 (4): 996- 1005 doi: 10.3969/j.issn.1000-6788.2013.04.022
	Wei Y Y , Tang Y H , Gu J X . Queue size distribution and capacity optimum design for $Geo/G/1$ queueing system with delayed $D$ -policy. Systems Engineering:Theory and Practice, 2013, 33 (4): 996- 1005 doi: 10.3969/j.issn.1000-6788.2013.04.022
17	魏瑛源, 唐应辉, 余妙妙. 基于 $Min(N,D)$ -策略的 $M/G/1$ 排队系统的队长分布及最优策略. 系统科学与数学, 2015, 35 (6): 729- 744
	Wei Y Y , Tang Y H , Yu M M . Queue length distribution and optimum policy for $M/G/1$ queueing system under $Min(N,D)$ -policy. Journal of Systems Science and Mathematical Sciences, 2015, 35 (6): 729- 744
18	Gu J X , Wei Y Y , Tang Y H , Yu M M . Queue size distribution of $Geo/G/1$ queue under the $Min(N,D)$ -policy. Journal of Systems Science and Complexity, 2016, 29 (3): 752- 771 doi: 10.1007/s11424-016-4180-y
19	兰绍军, 唐应辉. 具有Bernoulli反馈和 $Min(N,D)$ -策略控制的 $Geo\|^{({{\lambda }_{1}},{{\lambda }_{2}})}/G/1$ 离散时间可修排队的可靠性分析. 系统科学与数学, 2016, 36 (11): 2070- 2086
	Lan S J , Tang Y H . Reliability analysis of $Geo\|^{({{\lambda }_{1}},{{\lambda }_{2}})}/G/1$ discrete-time repairable queue with Bernoulli feedback and $Min(N,D)$ -policy. Journal of Systems Science and Mathematical Sciences, 2016, 36 (11): 2070- 2086
20	Lan S J , Tang Y H . Analysis of $D$ -policy discrete-time $Geo/G/1$ queue with second $J$ -optional service and unreliable server. RAIRO-Operations Research, 2017, 51 (1): 101- 122 doi: 10.1051/ro/2016006
21	高丽君, 唐应辉. 具有 $Min(N,D)$ -策略控制的 $M/G/1$ 可修排队系统及最优控制策略. 数学物理学报, 2017, 37A (2): 352- 365 doi: 10.3969/j.issn.1003-3998.2017.02.014
	Gao L J , Tang Y H . $M/G/1$ repairable queueing system and optimal control policy with $Min(N,D)$ -policy. Acta Mathematica Scientia, 2017, 37A (2): 352- 365 doi: 10.3969/j.issn.1003-3998.2017.02.014
22	潘取玉, 唐应辉. 在延迟 $Min(N,D)$ -控制策略下修理设备可更换的 $M/G/1$ 可修排队系统及最优控制策略. 数学物理学报, 2018, 38A (5): 1014- 1031 doi: 10.3969/j.issn.1003-3998.2018.05.017
	Pan Q Y , Tang Y H . Analysis of $M/G/1$ repairable queueing system and optimal control policy with a replaceable repair facility under delay $Min(N,D)$ -policy. Acta Mathematica Scientia, 2018, 38A (5): 1014- 1031 doi: 10.3969/j.issn.1003-3998.2018.05.017
23	王敏, 唐应辉. 基于 $Min(N,D,V)$ -策略和单重休假的 $M/G/1$ 排队系统的最优控制策略. 系统科学与数学, 2018, 38 (9): 1067- 1084
	Wang M , Tang Y H . Optimal control policy of $M/G/1$ queueing system based on $Min(N,D,V)$ -policy and single server vacation. Journal of Systems Science and Mathematical Sciences, 2018, 38 (9): 1067- 1084
24	罗乐, 唐应辉. 具有 $Min(N,D,V)$ -策略控制的 $M/G/1$ 排队系统. 运筹学学报, 2019, 23 (2): 1- 16
	Luo L , Tang Y H . $M/G/1$ queueing system with $Min(N,D,V)$ -policy Control. Operations Research Transactions, 2019, 23 (2): 1- 16
25	Liu R B , Alfa A S , Yu M M . Analysis of an $ND$ -policy $Geo/G/1$ queue and its application to wireless sensor networks. Operational Research:An International Journal, 2019, 19 (2): 449- 477
26	Lee H W , Seo W J , Lee S W , et al. Analysis of the $MAP/G/1$ queue under the $Min(N,D)$ -policy. Stochastic Models, 2010, 26 (1): 98- 123 doi: 10.1080/15326340903517121
27	Lee H W , Seo W J , Lee S W . Analysis of the $M/G/1$ queueing system under the $triadic(N,D,T)$ -policies. Quality Technology and Quantitative Management, 2011, 8 (3): 333- 357 doi: 10.1080/16843703.2011.11673262

D	ρ = 0.25	ρ = 0.45	ρ = 0.65	D	ρ = 0.25	ρ = 0.45	ρ = 0.65
1.0000	14.2233	12.832	11.3624	7.3471	11.8861	10.2411	9.7437
2.0000	12.6899	12.0542	10.9589	8.0000	11.7192	10.2460	9.7679
3.0000	11.7142	11.3958	10.5962	8.4000	12.4772	10.2945	9.7106
4.0000	11.2423	10.8906	10.2912	8.4100	12.5772	10.5945	9.7910
4.7490	11.1458	10.6144	10.1054	8.4200	12.4895	10.2964	9.7106
4.7491	11.1457	10.6144	10.1054	8.4272	12.4939	10.2971	9.7106
4.7492	11.1457	10.6143	10.1053	8.4273	12.4940	10.2971	9.7105
5.0000	11.1529	10.5405	10.0515	8.4300	12.4956	10.2974	9.7106
6.0000	11.3385	10.3320	9.8780	9.0000	12.2392	10.2629	9.7163
7.0000	11.7192	10.2460	9.7679	10.0000	12.8601	10.3652	9.7171
7.3400	11.8826	10.2411	9.7441	12.0000	15.0976	11.0448	9.9767
7.3466	11.8859	10.2411	9.7437	14.0000	16.7732	11.7094	10.3131
7.3467	11.8860	10.2411	9.7437	16.0000	18.5315	12.4821	10.7427
7.3469	11.8861	10.2411	9.7437	18.0000	20.3446	13.3305	11.2423
7.3470	11.8861	10.2411	9.7437	18.1110	20.5315	13.4821	11.7427

[1]	罗乐,唐应辉. 具有p-进入规则和Min(N, D, V)-策略的M/G/1排队系统容量问题研究[J]. 数学物理学报, 2019, 39(5): 1228-1246.
[2]	潘取玉,唐应辉. 在延迟Min (N, D)-策略M/G/1可修排队系统及最优控制策略[J]. 数学物理学报, 2018, 38(5): 1014-1031.
[3]	高丽君, 唐应辉. 具有Min(N,D)-策略控制的M/G/1可修排队系统及最优控制策略[J]. 数学物理学报, 2017, 37(2): 352-365.