两类具有N-策略和单重休假的M/G/1排队系统的最优控制策略

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

摘要/Abstract

摘要：

本文考虑两类具有N-策略和服务员单重休假的M/G/1排队系统，其中一类是休假不可中断，另一类是休假可中断。利用系统稳态队长的随机分解特性导出稳态队长的概率母函数，并讨论了系统空闲率与附加平均队长对系统一些参数的敏感性。进一步，在建立费用结构的基础上，应用更新报酬过程理论导出了系统长期运行单位时间内所产生的成本期望费用的显示表达式，同时通过数值计算实例确定了使得系统在长期运行单位时间内所产生的成本期望费用最小的控制策略N^*，以及当休假时间为定长T时的二维最优控制策略（N^*，T^*）。

关键词: N-策略, 单重休假, 可中断的休假, 不可中断的休假, 最优控制策略

Abstract:

This paper considers two types of M/G/1 queueing systems with N-strategy and single vacation, one of which is uninterruptible on vacation and the other is of interruptible on vacation. Using the stochastic decomposition of the steady-state queue length, the expressions of the probability generating function of the steady-state queue length are obtained. And the sensitivity of the system's idle rate and the additional average queue-length towards system parameters is discussed. Furthermore, the explicit expressions of the long-run expected cost per unit time are derived under a given cost structure. At the same time, numerical calculation examples are used to determine the control strategy N^* for minimizing the long-run expected cost per unit time as well as the combined control strategy (N^*, T^*) when the vacation time is fixed duration T.

Key words: N-strategy, single vacation, interruptible vacation, uninterruptible vacation, optimal control strategy

中图分类号:

O226

唐蓓蕾, 唐应辉. 两类具有N-策略和单重休假的M/G/1排队系统的最优控制策略[J]. 运筹学学报, 2021, 25(4): 15-30.

Beilei TANG, Yinghui TANG. Optimal control strategies for two types of M/G/1 queueing systems with N-strategy and single vacation[J]. Operations Research Transactions, 2021, 25(4): 15-30.

图/表 18

表1

表2

图1

图2

表3

表4

图3

图4

表5

表6

表7

图5

图6

图7

表8

表9

图8

图9

1	Yadin M , Naor P . Queueing systems with a removable service station[J]. Operational Research Quarterly, 1963, 14, 393- 405. doi: 10.1057/jors.1963.63
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 . Queueing systems with vacations—a survey[J]. Queueing Systems, 1986, 1, 29- 66. doi: 10.1007/BF01149327
5	田乃硕. 休假随机服务系统[M]. 北京: 北京大学出版社, 2001.
6	Agarwal R P , Dshalalow J H . New fluctuation analysis of $ D $-policy bulk queues with multiple vacation[J]. Mathematical and Computer Modelling, 2005, 41 (2-3): 253- 269. doi: 10.1016/j.mcm.2003.12.012
7	唐应辉, 唐小我. 排队论——基础与分析技术[M]. 北京: 科学出版社, 2006.
8	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.
9	井彩霞, 崔颖, 田乃硕. Min($ N, V $)-策略休假的M/G/1排队系统分析[J]. 运筹与管理, 2006, 15 (3): 53- 58. doi: 10.3969/j.issn.1007-3221.2006.03.011
10	Wang K H , Kuo C C , Ke J C . Optimal control of the $ D $-policy M/G/1 queueing system with server breakdowns[J]. American Journal of Applied Sciences, 2008, 5 (5): 565- 573. doi: 10.3844/ajassp.2008.565.573
11	唐应辉, 刘名武. $ N $-策略单重休假M/G/1排队系统的队长分布[J]. 应用数学, 2008, 21 (1): 20- 26.
12	唐应辉, 吴文青, 刘云颇, 等. 基于多重休假的min($ N, V $)-策略M/G/1排队系统的队长分布[J]. 系统工程理论与实践, 2014, 34 (6): 1533- 1546.
13	唐应辉, 吴文青, 刘云颇. 基于单重休假的min($ N, V $)-策略M/G/1排队系统分析[J]. 应用数学学报, 2014, 37 (6): 976- 996.
14	蒋书丽, 唐应辉. 具有多级适应性休假和min($ N, V $)-策略控制的M/G/1排队系统[J]. 系统科学与数学, 2017, 37 (8): 1866- 1884.
15	Gu J X , Wei Y Y , Tang Y H , et al. Queue size distribution of Geo/G/1 queue under the min($ N, D $)-policy[J]. Journal of Systems Science and Complexity, 2016, 29 (3): 752- 771. doi: 10.1007/s11424-016-4180-y
16	蔡晓丽, 唐应辉. 具有温储备失效特征和单重休假min($ N, V $)-控制策略的M/G/1可修排队系统[J]. 应用数学学报, 2017, 40 (5): 702- 726.
17	魏瑛源, 唐应辉, 余玅妙. 基于min($ N, D $)-策略的M/G/1排队系统的队长分布及最优策略[J]. 系统科学与数学, 2015, 35 (6): 729- 744.
18	高丽君, 唐应辉. 具有min($ N, D $)-策略控制的M/G/1可修排队系统及最优控制策略[J]. 数学物理学报, 2017, 37A (2): 352- 365. doi: 10.3969/j.issn.1003-3998.2017.02.014
19	王敏, 唐应辉. 基于min($ N, D, V $)-策略和单重休假的M/G/1排队系统的最优控制策略[J]. 系统科学与数学, 2018, 38 (9): 1067- 1084.
20	罗乐, 唐应辉. 具有min($ N, D, V $)-策略控制的M/G/1排队系统[J]. 运筹学学报, 2019, 23 (2): 1- 16.
21	罗乐, 唐应辉. 具有$ p $-进入规则和min($ N, D, V $)-策略的M/G/1排队系统容量的优化设计及最优控制策略[J]. 数学物理学报, 2019, 39 (5): 1228- 1246. doi: 10.3969/j.issn.1003-3998.2019.05.024

$ N $	$ {p}_{\mbox{ 0, 模 1}} $	$ {p}_{\mbox{ 0, 模 2}} $	$ N $	$ {p}_{\mbox{ 0, 模 1}} $	$ {p}_{\mbox{ 0, 模 2}} $
1	0.226 2	0.700 0	11	0.063 1	0.233 9
2	0.197 3	0.452 7	12	0.058 0	0.231 9
3	0.168 9	0.359 0	13	0.053 6	0.230 4
4	0.144 5	0.311 3	14	0.049 9	0.229 3
5	0.124 4	0.283 5	15	0.046 6	0.228 5
6	0.108 3	0.265 9	16	0.043 7	0.227 9
7	0.095 3	0.254 3	17	0.041 1	0.227 5
8	0.084 8	0.246 3	18	0.038 9	0.227 1
9	0.076 2	0.240 7	19	0.036 8	0.226 9
10	0.069 0	0.236 8	20	0.035 0	0.226 7

$ N $	$ {p}_{\mbox{ 0, 模 1}} $	$ {p}_{\mbox{ 0, 模 2}} $	$ N $	$ {p}_{\mbox{ 0, 模 1}} $	$ {p}_{\mbox{ 0, 模 2}} $
1	0.032 3	0.100 0	11	0.009 0	0.033 4
2	0.028 2	0.064 7	12	0.008 3	0.033 1
3	0.024 1	0.051 3	13	0.007 7	0.032 9
4	0.020 6	0.044 5	14	0.007 1	0.032 8
5	0.017 8	0.040 5	15	0.006 7	0.032 6
6	0.015 5	0.038 0	16	0.006 2	0.032 6
7	0.013 6	0.036 3	17	0.005 9	0.032 5
8	0.012 1	0.035 2	18	0.005 6	0.032 4
9	0.010 9	0.034 4	19	0.005 3	0.032 4
10	0.009 9	0.033 8	20	0.005 0	0.032 4

$ N $	$ {\overline{L}}_{\mbox{ d, 模 1}} $	$ {\overline{L}}_{\mbox{ d, 模 2}} $	$ N $	$ {\overline{L}}_{\mbox{ d, 模 1}} $	$ {\overline{L}}_{\mbox{ d, 模 2}} $
1	2.594 5	0.000 0	11	5.081 1	2.211 7
2	2.390 6	0.353 3	12	5.558 2	2.289 1
3	2.334 4	0.694 3	13	6.041 9	2.351 9
4	2.430 7	1.000 3	14	6.530 3	2.402 5
5	2.648 2	1.268 3	15	7.021 9	2.443 2
6	2.952 8	1.499 5	16	7.515 9	2.475 6
7	3.317 8	1.696 5	17	8.011 6	2.501 4
8	3.724 3	1.862 7	18	8.508 4	2.521 8
9	4.159 1	2.001 7	19	9.006 1	2.537 8
10	4.613 3	2.116 9	20	9.504 5	2.550 5

$ N $	$ {\overline{L}}_{\mbox{ d, 模 1}} $	$ {\overline{L}}_{\mbox{ d, 模 2}} $	$ N $	$ {\overline{L}}_{\mbox{ d, 模 1}} $	$ {\overline{L}}_{\mbox{ d, 模 2}} $
1	0.387 8	0.000 0	11	5.000 0	0.266 4
2	0.626 7	0.115 7	12	5.500 0	0.266 5
3	1.044 8	0.191 4	13	6.000 0	0.266 5
4	1.516 7	0.231 6	14	6.500 0	0.266 5
5	2.006 4	0.251 0	15	7.000 0	0.266 5
6	2.502 5	0.259 8	16	7.500 0	0.266 5
7	3.001 0	0.263 7	17	8.000 0	0.266 5
8	3.500 4	0.265 3	18	8.500 0	0.266 5
9	4.000 2	0.266 0	19	9.000 0	0.266 5
10	4.500 1	0.266 3	20	9.500 0	0.266 5

$ N $	$ {{F}}_{\mbox{ 模 1}} $	$ {{F}}_{\mbox{ 模 2}} $	$ N $	$ {{F}}_{\mbox{ 模 1}} $	$ {{F}}_{\mbox{ 模 2}} $
1	34.344 7	61.642 9	11	32.907 7	33.085 7
2	30.866 2	42.388 0	12	34.861 4	33.297 5
3	28.172 5	36.125 3	13	36.909 9	33.484 1
4	26.575 7	33.605 7	14	39.031 8	33.644 2
5	$\bf{\fbox{25.961 5}}$	32.581 6	15	41.211 1	33.779 1
6	26.114 5	32.244 7	16	43.435 9	33.891 1
7	26.836 7	$\bf{\fbox{32.240 2}}$	17	45.697 2	33.983 1
8	27.974 3	32.393 9	18	47.988 2	34.057 9
9	29.415 1	32.614 7	19	50.303 6	34.118 2
10	31.078 6	32.853 8	20	52.639 2	34.166 5