1沙特国王大学,理学院,部门统计和运筹学,利雅得,沙特阿拉伯
2菲尔勒迪金森大学Silberman学院业务信息系统与决策科学系的,加拿大
收到日期:23/07/2016;接受日期:24/08/2016;发表日期:27/08/2016
访问更多的相关文章研究和评论:统计和数学雷竞技苹果下载科学杂志》上
分析一个MX / G / 1排队系统,服务器接受随机故障和服务器应用D-policy提供服务。稳态概率分布队列大小使用嵌入式马尔可夫链技术获得。系统的关键性能指标推导获得最优值的阈值水平D最小化预期的单位时间的总成本。发表的特殊情况与理论结果进行了验证公式。
米X/ G / 1队列、复合泊松过程、稳态分布、破裂、波动理论、嵌入式马尔可夫链,D政策
单一服务器排队模型与控制策略广泛应用质量控制的电话交换系统和生产系统。因此,控制排队模型的一些变体在文献中已经被广泛的研究。这些研究产生的几种控制策略。仅举几例,雅丁和Naor [1]分析了控制策略的服务器没有启动服务在空闲期间,除非有N个顾客队列,这叫做N政策。的T政策是另一个控制策略,引入了海曼(2]。的T政策建议将服务器变为活动状态的时间间隔后长度T当服务器处于闲置状态。后,D提出的政策是Balachendran [3这是本研究的重点。在D政策,服务器仍不活跃,直到总共D服务时间累计在队列中。许多变化的控制政策建议在文献中。论文在这个话题是一个全面的调查发现在Crabill et al。4]和Doshi [5,6]。
在这个研究中,我们推导出稳态分布的bulk-arrival排队模型与一个不可靠的单独的服务器D政策。考虑排队模型中,服务器切换到非活动模式的完成每一个繁忙的时期。之后,服务器切换到主动模式时的总服务时间所有客户在队列中等待超过一些预先确定的价值进一步d,它假定服务器不可预知的故障。服务器修理发生故障时立即然后放回服务。
的D政策的M / G / 1排队系统首次引入Balachandran [3],Balachandran和Tijms [7),饿鬼et al。8)和许多其他文献中,假设服务器没有故障。Balachandran和Tijms提出最优D政策与可靠的服务器系统中使用的平均顾客数。饿鬼等人获得的概率在繁忙的服务器在单一服务器队列D政策。提出一个近似技术Sivazlian [9获取最优D使用的政策。Sivazlian方法使用前三个时刻的服务时间分布近似系统的行为。此外,饿鬼等人的概率数学表明服务器正忙着在稳态等于交通强度。李和妞妞10]分析了一般的GI / G / 1队列D政策获得的概率分布在排队等待的客户。下一个服务器队列的延伸D政策是由鲁宾和张(11),他们将打开服务的设置时间。Abolnikov和Dshalalow12)第一段使用技术分析的随机模型。Dshalalow [13,14]调查系统的队列长度的组合N政策和D政策。Dshalalow提议在他的作品中一个(N, D)政策的服务器仍然闲置,直到队列的平均顾客数N或为客户服务的总额乘以队列超过王D . et al。(15,16)获得最优D策略使用的预期长度繁忙的时期,空闲时间,崩溃的时期。最近,刘和邓17]研究了离散时间D政策地理/ G / 1队列和伯努利获得反馈和稳态系统大小分布使用分解方法。
bulk-arrival队列研究自1959年以来得到了极大关注由于其广泛的应用。给(18)似乎是第一个明确研究bulk-arrival队列。此后的几款批量到达队列进化。毛重和哈里斯(19)提供一个好的调查控制bulk-arrival队列。为控制bulk-arrival队列、雅丁和Naor bulk-arrival队列下分析N政策,如果至少有N客户服务器启动服务的队列。Dshalalow多余的级别使用流程分析散装排队系统的N - D-policies组合成一个政策。李等人。20.成功结合批到达队列N政策,得到了解析解。后来,李et al。21)详细分析了相同的系统N政策有一个假期。然而,我们注意到bulk-arrival队列D政策没有收到相同的关注N政策。
在实践中,有很多的情况D政策。刘和邓17)的使用D政策在一个无线局域网(WLAN)。在WLAN,信号接收的特殊访问点和他们识别和传播如果接入点是免费的。否则,接收到的信号是放置在队列中。由于节电,接入点旨在提供详尽每当信号达到某种程度上的工作负载。这种控制策略的另一个实例是邮件处理系统引入了王et al。16]。在邮件处理办公室,包裹被分类组织。的排队系统被认为是排序。当排序过程超过D单位时间,分配机打开,开始分发包裹成槽根据目的地邮局。预计这台机器可能打破在排序过程中,它必须立即修理。
本文的目的是获得一个显式表达式的稳态分布队列的平均顾客数。使用稳态分布,传统的性能措施,例如:预期长度繁忙期间,预期在队列中,等待时间,预计空闲周期的长度,和概率,服务器很忙很容易计算。此外,稳态分布给灵活性获得非常规性能的措施可能会从应用程序的性质。论文的另一个目标是计算的最优值D政策的最低预期操作成本函数。
在模型中我们认为,顾客到达系统大小不同的批次。批次的到来都要遵循泊松过程的恒速λ> 0。因此,客户说到一个复合泊松过程。批量的大小是离散的独立同分布随机变量X与一般的分布函数,概率生成函数(Z) = E [ZX)和有限的前两个时刻1= E [X)和一个2= E [X2]。一旦批到达系统,客户在批处理输入系统和单一队列中等待服务。每个客户在系统中单个服务请求和保持系统中,直到收到他的服务。
服务器提供服务与随机时间为每个客户服务。的服务* B客户独立同分布随机变量有一个总体分布函数(CDF) B (t) Laplace-Stieltjes变换(LST)定义为B * (s) = E (E某人b),有限的第一时刻1和有限的二阶矩b2。
在这个模型中,服务器接受随机突发性故障。失败的速率发生在服务器上被假定为常数α> 0和失败遵循泊松过程。修复服务器发生故障时立即开始。维修时间需要一个随机时间R和修复时间是独立同分布变量一般CDF实验组的R (t), LST的R * (s) = E (E某人),有限的第一时刻r1和有限的二阶矩r2。
将故障和修复时间在我们的排队模型中,我们定义了一个修改相结合的服务时间的实际服务时间可能维修。我们定义的随机变量G修改的服务时间,包括服务和可能的修复时间。修改后的服务时间G CDF实验组的G (t)和LST G * (s) = E (Esg有限的第一和第二时刻g1和g2,分别。修改后的服务时间与实际服务时间和维修时间通过以下表达式:
(1)
使用方程(1),前两个时刻的修改服务给出如下:
(2)
我们也假设服务器下适用“先来先得”的原则D政策。在服务完成时代,服务器服务下一个客户。否则,如果没有客户在队列中最后服务完成后,服务器仍然闲置,等待工作积累。在空闲时间,服务才开始忙碌的时期的总服务时间和目前的客户至少D单位时间客户的到来。
我们需要定义的稳态分布系统中客户的数量。表示排队过程的Q (t)系统中客户的数量在时间t≥0。考虑以下随机变量:
问(t):系统在时间t的客户数量;
Tn:完成n服务的时代;
问n:系统在服务的客户数量完成时代
τn:n组顾客到达的时间,让τ0= 0;
Xn:n组的大小客户,让X0= 0;
Yn:n客户的服务时间,让Y0= 0;
Bn:累计服务时间,n个客户,
我们的方法是获得的概率生成函数(PGF)系统中客户的数量将被用来获得{Q的稳态分布n}运用波动理论。从Abolnikov Dshalalow [12),我们国家以下定理:
定理1
为单个服务器队列D政策与复合泊松到达率λ> 0,服务时间LST B * (s),上面定义的随机变量的边缘分布:
到达客户引起的索引第一超过D,用
边缘分布如下:
鉴于第一个多余的级别B的投影υ在过程{n},
第一个超过D的水平,用Sυ边缘分布如下:
的时间到达批客户原因第一次超过D,用τυ边缘分布如下:
(5)
操作员LD(¢)被定义为:
和L1拉普拉斯逆变换。
从上面的定理,我们得到的PGF排队过程{问n}。这个过程{问n}是一个嵌入式马尔可夫链与转换定义如下:
(6)
在Vn代表客户移民的数量在修改服务时间。因此,
(7)
表示的转移概率矩阵(TPM){问n},我(z)的概率母函数th行a。然后,
(8)
注意索引的概率生成函数的第一个多余的是:
(9)
定理2
Leρ=λg1在g1代表第一次修改后的服务时间。然后,嵌入过程{问n}是遍历当且仅当,
(10)
从(1)
(11)
从定理2,稳态概率分布p TPM的存在,
然后,从关系
我们有:
(12)
和稳态概率分布表示的PGF P (z)
(13)
来自初始条件P(1) = 1和E [υ表示为:
(14)
在本节中,我们用数学表达一些关键性能的措施,使决策能够改善系统的行为。
平均数量的客户(左)
在排队理论中,性能的主要措施之一是客户的平均数量在系统(L)。这个测量得到的值为我们的模型:
(15)
在g1由(11)和
由(14),而g2和
分别给出了
(16)
(17)
服务周期分布
在实践中,一些系统遇到操作使成本高D政策一个不错的选择来控制系统对降低运营成本。因此,估计连续操作时间的长度是重要的成本降到最低。服务周期为单个服务器排队系统D与大部分移民政策和不可靠的服务器之间的时间间隔定义为两个连续的客户离开,即。连续两个服务之间,完成时间。处于平衡状态,服务周期的随机变量(C)的LST表示如下:
(18)
第一段时间LST在哪里
(19)
意味着服务周期
(20)
均衡的平均服务周期的负导数LST在θ= 0 (17)。然后,两个服务之间的预期时间完成时代处于平衡状态是由:
另一种确定这个结果是被注意到
自
然后
意思是空闲的
在这个模型中,服务器的平均时间是空闲的时间总工作量积累超过价值。因此,意味着闲置期间,我用1,等于的意思是第一个多余的时间。然后,
(21)
意思是繁忙的周期
繁忙的周期的开始之间的时间无所事事的时期,开始下一个阶段,即。,之间的差异开始的时间两个连续的空闲时间。从半马尔科夫过程理论,看到Cinlar [22),一个繁忙的周期的平均长度是多少
,因此
(22)
意思是繁忙的时期
忙期之间的时间测量即时客户到达空系统即时客户离开之前留下一个空系统。然后,繁忙的时期的平均长度是多少
因此
(23)
服务器空闲概率
在这个模型中,服务器启动当负载超过d .这意味着空闲服务器的概率的概率不等于空系统在经典排队论。因此,空闲服务器的概率,表示为π0是由:
(24)
概率服务器正忙着
繁忙的服务器的概率是在队列中常用的性能措施做出决策。这项措施是用来衡量服务器的有效性是由:
(25)
在实践中,有许多需要一套新的绩效指标的应用程序除了前面提到的措施。系统的稳态概率的大小获得的PGF可以表达任何性能测量除了下面提到的措施。
本文介绍的排队模型被认为是许多其他单一服务器排队模型的泛化。这个模型的设计参数,即:政策参数D和parameterα失败,给许多实际情况灵活的建模。例如:
•不可靠的M / G / 1
这个模型可以很容易地获得的PGF设置D = 0和υz (z)。然后关系(12)就变成:
在哪里
这是pgf的M / G / 1服务器接受随机故障。
•可靠的米X/ G / 1下D政策
设置α= 0,关系(1)收益率G * (s) = B * (s)和(12)的关系是:
在哪里
这是的pgf MX/ G / 1服务器之前的地方D政策。
•经典M / G / 1
最后设置D = 0,υ(z) = z,α= 0,收益率著名Pollaczeck-Khintchine公式:
在哪里
我们的方法在优化这个模型是一个成本驱动的优化方法。成本驱动的优化使用关键绩效指标在一个成本函数然后成本函数最小化。看到Tadj Choudhury [23为更多的细节在排队优化方法。
现在,我们定义时间的预计总成本单位使用的一些性能措施在第四节。这个表达式的决策变量是d的目标是找到最优值最小化代价函数的参数。这将优化系统的性能,因为它可以让服务器知道何时结束空闲时间。
系统的总成本函数考虑持有客户的总成本在服务器操作系统和总成本。假设服务器需要设置操作每次服务器在闲置期。此外,它假定服务器将执行准备工作开始前,每个忙碌的时期。每个成本的单位成本类别给出如下:
ch:单位时间内储存成本为每个客户的系统;
co:单位时间成本保持服务器和操作;
c年代:设置成本忙周期;
c一个:单位时间内启动成本服务器的准备工作开始前服务。
然后,单位时间内的期望总成本函数是由
获得最优值D使用一阶最优性条件。由此产生的方程是一个非线性方程,可以使用一些数学数值求解方案。
我们认为本文排队模型泛化的许多模型研究的文献。Customerside,他们被允许到散装。服务端,两个功能。第一个是服务器不可靠,可能打破任何时间而提供服务。第二个是它实现了众所周知的D政策。
对于这个模型,我们得到系统的PGF概率大小。我们也得到许多性能措施和显示如何获取阈值的最优值D。
未来的研究方向可能包括,例如,从客户端模式功能,如慢行和/或违约,或从服务器端更多的功能,如单个或多个假期。
科学研究的作者感谢院长以来,沙特国王大学学院科学研究中心资助这项研究。
菜单