具有p-进入规则和Min(N, D, V)-策略的M/G/1排队系统容量问题研究

摘要/Abstract

摘要：

该文研究具有p-进入规则和系统采取Min（N，D，V）-策略的M/G/1排队系统，其中在服务员多重休假期间到达的顾客以概率p（0 < p ≤ 1）进入系统.运用全概率分解技术和拉普拉斯变换工具讨论了系统从任意初始状态出发，在任意时刻t的瞬态队长分布，得到瞬态队长分布的拉普拉斯变换的表达式，进一步得到稳态队长分布的递推表达式.同时，结合稳态队长分布，通过数值计算实例讨论了系统容量的优化设计问题.最后，在建立系统费用结构模型的基础上，导出了系统长期单位时间内的期望费用的显示表达式，并通过数值实例确定了使得系统在长期单位时间内的期望费用最小的联合最优控制策略（N^*，D^*）.

关键词: 多重休假, p-进入规则, Min(N, D, V)-策略, 队长分布, 最优控制策略

Abstract:

This paper considers a M/G/1 queueing system with p-entering discipline and Min(N, D, V)-policy, in which the customers who arrive during multiple vacations enter the system with probability p(0 < p ≤ 1). By using the total probability decomposition technique and the Laplace transform, we discuss the transient distribution of queue length at any time t which started from an arbitrary initial state, and obtain the expressions of the Laplace transform of transient queue-length distribution. Moreover, we obtain the recursion expressions of the steady-state queue length distribution. Meanwhile, we discuss the optimal capacity design by combining the steady-state queue length distribution and numerical example. Finally, the explicit expression of the long-run expected cost rate is derived under a given cost structure. And by through numerical calculation, we determine the optimal control policy (N^*, D^*) for minimizing the long-run expected cost per unit time.

Key words: Multiple vacation, p-Entering discipline, Min(N, D, V)-policy, Queue length distribution, Optimal control policy

中图分类号:

O121

罗乐,唐应辉. 具有p-进入规则和Min(N, D, V)-策略的M/G/1排队系统容量问题研究[J]. 数学物理学报, 2019, 39(5): 1228-1246.

Le Luo,Yinghui Tang. System Capacity Optimization Design and Optimal Control Policy (N^*, D^*) for M/G/1 Queue with p-Entering Discipline and Min(N, D, V)-Policy[J]. Acta mathematica scientia,Series A, 2019, 39(5): 1228-1246.

图/表 3

表 1

图 1

表 2

参考文献 38

1	Yadin M , Naor P . Queueing system with a removable service station. Operation Research Quarterly, 1963, 14 (4): 393- 405 doi: 10.1057/jors.1963.63
2	Balachandran K . Control policies for a single server system. Management Science, 1973, 19 (4): 1013- 1018
3	Heyman D P . $T$-policy for the $M/G/1$ queue. Management Science, 1977, 23 (7): 775- 778 doi: 10.1287/mnsc.23.7.775
4	Doshi B . Queueing systems with vacations-A survey. Queueing Systems, 1986, 1: 29- 66 doi: 10.1007/BF01149327
5	Ke J C . Modified $T$ vacation policy for an $M/G/1$ queueing system with an unreliable server and startup. Mathematical and Computer Modeling, 2005, 41: 1267- 1277 doi: 10.1016/j.mcm.2004.08.009
6	Lee H W , Beak J W , Jeon J . 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
7	Wang K H , Kuo C C , Ke J C . Optical control of the $D$-policy $M/G/1$ queueing system with server breakdowns. American Journal of Applied Science, 2008, 5 (5): 565- 573 doi: 10.3844/ajassp.2008.565.573
8	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
9	Tang Y H , Tang X W . The queue-length distribution for $M^X/G/1$ queue with single server vacation. Acta Mathematica Scientia, 2000, 20B (3): 397- 408
10	骆川义, 唐应辉, 刘仁彬. 多级适应性休假$M^X/G/1$排队系统的队长分布. 系统科学与数学, 2007, 27 (6): 899- 907 doi: 10.3969/j.issn.1000-0577.2007.06.011
	Luo C Y , Tang Y H , Liu R B . The queue length distribution of $M^X/G/1$ with adartive mulitistage vacation. Journal of Systems Science & Mathematical Sciences, 2007, 27 (6): 899- 907 doi: 10.3969/j.issn.1000-0577.2007.06.011
11	Tang Y H . The departure process of the $M/G/1$ queueing model with server vacation and exhaustive service discipline. J of Applied Probability, 1994, 31 (4): 1070- 1082 doi: 10.2307/3215330
12	Tang Y H , Yun X , Huang S J . Discrete-time queue with unreliable server and multiple adaptive delayed vacation. J of Computational and Applied Mathematics, 2008, 220 (3): 439- 455
13	Yu M M , Tang Y H , Fu Y H , Pan L M . $GI/Geom/1/MWV$ queue with changeover time and searching for the optimum service rate in working vacation period. J of Computational and Applied Mathematics, 2011, 235 (8): 2170- 2184 doi: 10.1016/j.cam.2010.10.013
14	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
15	Luo C Y , Tang Y H , Chao B S , Xiang K L . Performance analysis of a discrete-time $Geo/G/1$ queue with randomized vacations and at most J vacations. Applied Mathematics Modelling, 2013, 37 (9): 6489- 6504 doi: 10.1016/j.apm.2013.01.033
16	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 ${\rm Min}(N, V)$-policy. Journal of Industrial & Management Optimization, 2016, 12 (4): 1435- 1464
17	Gu J X , Wei Y Y , Tang Y H , Yu M M . Queue size distribution of $Geo/G/1$ queue under the ${\rm Min}(N, D)$-policy. J of Systems Science and Complexity, 2016, 29 (3): 752- 771 doi: 10.1007/s11424-016-4180-y
18	井彩霞, 崔颖, 田乃硕. ${\rm Min}(N, V)$ -策略休假的$M/G/1$排队系统分析. 运筹与管理, 2006, 15 (3): 53- 58 doi: 10.3969/j.issn.1007-3221.2006.03.011
	Jing C X , Cui Y , Tian N S . Analysis of the $M/G/1$ queueing system with ${\rm Min}(N, V)$-policy. Operations Research & Management Science, 2006, 15 (3): 53- 58 doi: 10.3969/j.issn.1007-3221.2006.03.011
19	唐应辉, 吴文青, 刘云颇, 刘晓云. 基于多重休假的${\rm Min}(N, V)$ -策略$M/G/1$排队系统的队长分布. 系统工程理论与实践, 2014, 34 (6): 1533- 1546
	Tang Y H , Wu W Q , Liu Y P , Liu X Y . The queue length distribution of $M/G/1$ queueing system with ${\rm Min}(N, V)$-policy based on multiple server vacations. Systems Engineering-Theory & Practice, 2014, 34 (6): 1533- 1546
20	唐应辉, 吴文青, 刘云颇. 基于单重休假的${\rm 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 ${\rm Min}(N, V)$-policy based on single server vacation. Acta Mathematicae Applicatae Sinica, 2014, 37 (6): 976- 996
21	蒋书丽, 唐应辉. 具有多级适应性休假和${\rm Min}(N, V)$ -策略控制的$M/G/1$排队系统. 系统科学与数学, 2017, 37 (8): 1866- 1884
	Jiang S L , Tang Y H . $M/G/1$ queueing system with multiple adaptive vacations and ${\rm Min}(N, V)$-policy. Journal of Systems Science & Mathematical Sciences, 2017, 37 (8): 1866- 1884
22	高丽君, 唐应辉. 具有${\rm Min}(N, D)$ -策略控制的$M/G/1$可修排队系统及最优控制策略. 数学物理学报, 2017, 37A (2): 352- 365
	Gao L J , Tang Y H . $M/G/1$ repairable queueing system and optimal control policy with ${\rm Min}(N, D)$-policy. Acta Mathematica Scientia, 2017, 37A (2): 352- 365
23	蔡晓丽, 唐应辉. 具有温储备失效特征和单重休假${\rm Min}(N, V)$ -控制策略的$M/G/1$可修排队系统. 应用数学学报, 2017, 40 (5): 702- 726
	Cai X L , Tang Y H . $M/G/1$ repairable queueing system with warm standby failure and ${\rm Min}(N, V)$-policy based on single vacation. Acta Mathematicae Applicatae Sinica, 2017, 40 (5): 702- 726
24	Lee H W , Seo W J . The performance of the $M/G/1$ queue under the dyadic ${\rm Min}(N, D)$-policy and its cost optimization. Performance Evaluation, 2008, 65 (10): 742- 758 doi: 10.1016/j.peva.2008.04.006
25	Lee H W , Seo W J , Lee S W , Jeon J . Analysis of the $MAP/G/1$ queue under the ${\rm Min}(N, D)$-policy. Stochastic Models, 2010, 26 (1): 98- 123 doi: 10.1080/15326340903517121
26	魏瑛源, 唐应辉, 等. 基于${\rm Min}(N, D)$ -策略的$M/G/1$排队系统的队长分布及最优策略. 系统科学与数学, 2015, 35 (6): 729- 744
	Wei Y Y , Tang Y H , et al. Queue length distribution and optimum policy for $M/G/1$ Queueing system under ${\rm Min}(N, D)$-policy. Journal of Systems Science & Mathematical Sciences, 2015, 35 (6): 729- 744
27	罗乐, 唐应辉. 具有${\rm Min}(N, D, V)$ -策略控制的$M/G/1$排队系统. 运筹学学报, 2019, 23 (2): 1- 16
	Luo L , Tang Y H . $M/G/1$ queueing system with ${\rm Min}(N, D, V)$-policy control. Journal of Operations Research, 2019, 23 (2): 1- 16
28	王敏, 唐应辉. 基于${\rm 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 ${\rm Min}(N, D, V)$-policy and single server vacation. Journal of Systems Science & Mathematical Sciences, 2018, 38 (9): 1067- 1084
29	唐应辉, 毛勇. 服务员假期中以概率$p$进入的$M/G/1$排队系统的随机分解. 数学物理学报, 2004, 24 (6): 683- 688
	Tang Y H , Mao Y . The stochastic decomposition for $M/G/1$ queue with $ p$-entering discipline during server vacations. Acta Mathematica Scientia, 2004, 24 (6): 683- 688
30	骆川义, 唐应辉. 假期中以概率$p$进入的单重休假$M/G/1$排队. 应用数学, 2006, 19 (2): 246- 251
	Luo C Y , Tang Y H . The $M/G/1$ queue with $p$-entering discipline during single server vacation. Mathematic Application, 2006, 19 (2): 246- 251
31	李才良, 唐应辉, 牟永聪, 等. 在第二类故障期间以概率$p$进入的$M/G/1$可修排队系统. 数学物理学报, 2012, 32A (6): 1149- 1157
	Li C L , Tang Y H , Mu Y C , et al. $M/G/1$ repairable queueing system with $p$-entering discipline during second type failure times. Acta Mathematica Scientia, 2012, 32A (6): 1149- 1157
32	刘云颇, 唐应辉. 多重假期中以概率$p$进入的$M/G/1$可修排队系统. 系统工程学报, 2011, 26 (5): 718- 724
	Liu Y P , Tang Y H . $M/G/1$ repairable queueing system with $p$-entering discipline during server vacation. Journal of Systems Engineering, 2011, 26 (5): 718- 724
33	骆川义, 唐应辉. 具有可变到达率的多重休假$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 Mathematic Sinica, 2010, 53 (4): 805- 816
34	Luo C Y , Xiang K 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
35	Wei Y Y , Yu M M , Tang Y Y , 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
36	Luo C Y , Tang Y H , Yu K Z , Ding C . Optimal $(r, N)$ -policy for discrete-time $Geo/G/1$ queue with different input rate and setup time. Applied Stochastic Models in Business & Industry, 2015, 31 (4): 405- 423
37	Lan S J , Tang Y H . Analysis of a discrete-time $Geo^{\lambda_1, \lambda_2}/G/1$ queue with $N$-policy and $D$-policy. Journal of Applied Mathematics and Computing, 2017, 53 (1/2): 657- 681
38	唐应辉, 唐小我. 排队论－基础与分析技术. 北京: 科学出版社, 2006
	Tang Y H , Tang X W . Queueing Theory-Foundations and Analysis Techniques. Beijing: Science Press, 2006

$p_0$	$p_1$	$p_2$	$p_3$	$p_4$	$p_5$	$p_6$	$p_7$	$p_8$	$p_9$	$p_{10}$	$p_{11}$	$p_{12}$	$p_{13}$	$ p_{14}$	$ p_{15}$	$p_{16}$	$p_{17}$	$p_{18}$	$p_{19}$	$p_{20}$	$p_{21}$	$ p_{22}$	$E[L]$
0.262226	0.234005	0.173473	0.116078	0.073218	0.044167	0.025562	0.014185	0.007539	0.003839	0.001522	0.000609	0.000243	0.000097	0.000039	0.000016	0.000006	0.000002	0.000000	0.000000	0.000000	0.000000	0.000000	1.917604

DN	$1$	$2$	$3$	$4$	$5$	$6$
1	13.144737	9.991536	9.563765	9.521530	9.523348	9.525169
2	13.144737	9.312163	8.666641	8.606744	8.641893	8.668439
3	13.144737	9.098830	8.356363	8.300900	8.391288	8.474396
4	13.144737	9.024516	8.235207	8.184978	8.325796	8.476696
5	13.144737	8.997709	8.185816	8.138259	8.315510	8.527172
6	13.144737	8.987918	8.165466	8.118911	8.319459	8.577624
7	13.144737	8.984325	8.157101	8.110828	8.325154	8.615477
8	13.144737	8.983005	8.153686	8.107553	8.329470	8.640445
9	13.144737	8.982519	8.152304	8.106051	8.332170	8.655647
10	13.144737	8.982304	8.151748	8.105571	8.333699	8.664381
11	13.144737	8.982275	8.151526	8.105234	8.334510	8.669176
12	13.144737	8.982251	8.151438	8.105137	8.334921	8.671714
13	13.144737	8.982242	8.151404	8.105097	8.335123	8.673016
14	13.144737	8.982239	8.151390	8.105082	8.335298	8.673667
15	13.144737	8.982237	8.151385	8.105075	8.335265	8.673985
16	13.144737	8.982237	8.151383	8.105073	8.335285	8.674137
17	13.144737	8.982237	8.151382	8.105072	8.335294	8.674209
17.3	13.144737	8.982237	8.151382	8.105072	8.335296	8.674222
17.4	13.144737	8.982237	8.151382	$ \bf{\fbox{ 8.105071}}$	8.335296	8.674226
17.5	13.144737	8.982237	8.151382	8.105071	8.335297	8.674229
18	13.144737	8.982237	8.151382	8.105071	8.335298	8.674243
19	13.144737	8.982237	8.151381	8.105071	8.335300	8.674258
20	13.144737	8.982237	8.151381	8.105071	8.335301	8.674265

[1]	潘取玉,唐应辉. 在延迟Min (N, D)-策略M/G/1可修排队系统及最优控制策略[J]. 数学物理学报, 2018, 38(5): 1014-1031.
[2]	高丽君, 唐应辉. 具有Min(N,D)-策略控制的M/G/1可修排队系统及最优控制策略[J]. 数学物理学报, 2017, 37(2): 352-365.
[3]	李才良, 唐应辉, 牟永聪, 余玅妙. 在第二类故障期间以概率p进入的M/G/1可修排队系统[J]. 数学物理学报, 2012, 32(6): 1149-1157.