可修排队系统GI/G(M/G)/1的可靠性分析

利用更新过程理论和向量马氏过程方法全面考察了可修排队系统GI/G(M/G)/1的结 构,得到了所有感兴趣的指标,并证明了服务台的可靠性指标只与系统的忙期、闲期和忙期循 环时间有关.     

基于移动边缘计算的GI/GI/1排队建模与调度算法EI北大核心CSCD

针对车联网环境下路侧边缘计算节点部署不均衡、服务密度小、实时调度计算压力大等问题,提出一种基于智能车移动边缘计算(Mobile edge computing,MEC)的任务排队建模与调度算法,提供弹性计算服务,将具备感知、计算、控制功能的智能车作为移动边缘计算服务器,设计了车联网环境下的MEC体系架构.首先基于虚拟化技术对智能车进行虚拟化抽象,利用排队论对虚拟车任务构建了GI/GI/1排队模型.然后基于云平台Voronoi分配算法对虚拟车任务进行分配绑定,进而实现了智能车的优化调度与分布式弹性服务,解决了边缘计算任务分配不均衡等问题.最后通过城市交通路网中的车辆污染排放的实时计算实验,验证了该方法的有效性.     

基于自相似聚合业务流量的AQM算法性能评价

现有TCP/AQM忽略了非响应业务流量对AQM算法性能的影响,但非响应业务流量约占Internet业务流量的70%～80%.因此,评价非响应业务流量对AQM算法性能的影响具有重要意义.借助于在标准GI/M/1/N排队系统中嵌入AQM算法随机丢包机制的手段,提出了一种利用"扩充的GI/M/1/N排队系统"评价AQM算法在非响应业务流量下的性能的分析方法.最后评价了TD,RED和GRED这3种经典的AQM算法,评价结果与NS-2模拟结果一致,表明该分析方法可能用于评价AQM算法在非响应业务流量下的性能.     

混凝土生产浇筑过程的建模及资源配置分析

在详细描述混凝土生产浇筑系统工作过程和资源配置的基础上,建立了混凝土生产浇筑系统的排队论模型,针对所建立的排队论模型GI/M/4,对混凝土生产浇筑系统资源配置的合理性进行了理论分析,结果表明,实际系统的资源配置基本合理,同时验证了文中建立的排队论模型的正确性.     

大型M/P/C/C排队系统仿真研究

理论上推测Erlang B 公式对服务时问为任意分布的M/G/C/C系统的呼叫损失概率是有效的但缺乏严格证明.据此,对服务时间呈 Pareto 分布的M/P/C/C排队系统的仿真问题进行了研究,特别是对排队系统中服务装置数目很大的情况进行了研究.采用一种名为红黑树的数据结构较好地解决了超长序列、超大C值所造成的计算时间问题,并采用基于事件驱动的时间调度法进行排队仿真,结果与 Erlang-B 公式相符.表明Erlang B公式对M/P/C/C系统的呼叫损失概率是有效的.为采用仿真方法对自相似流下的网络性能进行深入研究打下了基础.     

输入匹配排队系统M/D^r/1’/Q的灵敏度分析

对M/Dr/1’/Q输入匹配排队系统进行了分析和研究,提出了顾客到达是两个独立的泊松过程的一种新的排队规则,即在服务机制为修正的先到先服务且为群体服务台,成批接受定长服务的排队系统中引入快速通道。快速通道是一种减少排队系统等待时间的有效方式。详细分析了单通道和双通道M/Dr/1’/Q两种排队系统的性态。大量的仿真试验表明具有快速通道的双通道M/Dr/1’/Q排队系统在很大程度上提高了系统性能,包括减少平均队长和缩短收敛时间。     

GI/Gm排队系统梯度估计的一种新方法

梯度估计是研究复杂离散事件动态系统的关键问题之一.这里对GI/G/m排队系统提 出一种新方法,在一次采样(仿真)的基础上,通过分析采样路径,可得到性能指标关于参数的 局部函数表达式.由此可直接求导,得到采样梯度,并证明了由该方法得到的梯度估计的无偏 性.该方法计算量小、精度高,还可以进一步拓广到其它系统上.     

基于输入匹配排队系统M/Dr/1''/Q的多目标规划模型研究

研究了M/D^r/1’/Q输入匹配排队系统。提出了一种新的排队规则,即顾客到达是两个独立的泊松过程,在排队系统中引入快速通道,服务机制为修正的先到先服务,一个群体服务台,成批接受定长服务。快速通道是一种减少排队系统等待时间的有效方式。详细分析了单通道和双通道M/D^r/1’/Q两种排队系统的性态,建立了具有快速通道的双通道M/D^r/1’/Q排队系统的多目标规划模型,模型仅有一个决策变量。最后利用理想点法给出了多目标规划模型的有效解,表明模型有良好的性质。     

带启动时间和可修服务台的M/M/1/N工作休假排队系统

分析带有启动时间、服务台可故障的M/M/1/N单重工作休假排队系统.在该系统中,服务台在休假期间不是完全停止工作,而是处于低速服务状态.假定服务台允许出现故障且当出现故障时,服务台停止为顾客服务且立即进行修理.服务台的失效时间和修理时间均服从指数分布,且工作休假期和正规忙期具有不同的取值;同时,从关闭期到正规忙期有服从指数分布的启动时间.建立此工作休假排队系统的有限状态拟生灭过程(QBD),使用矩阵几何方法得到QBD的各稳态概率相互依赖的率阵,从而求得稳态概率向量.通过有限状态QBD的最小生成元和稳态概率向量得到系统的基本阵和协方差矩阵,求解出系统方差、系统稳态可用度、系统吞吐率、系统稳态队长、系统稳态故障频度等系统性能.数值分析体现了所提出方法的有效性和实用性,通过敏感性分析将各参数对系统性能的影响进行了初探,为此模型的实际应用提供了很好的理论依据.     

基于CPN的空竭服务单重休假M/G/1型排队系统建模与分析

空竭服务单重休假M/G/1型排队系统是经典排队系统的推广,在许多领域有着广泛的应用.到目前为止对其的处理方法还都是建立在概率论和数理统计的基础上,运用马尔可夫随机过程求解,推导十分复杂,没有直观的模型描述.因此,利用着色Petri网对空竭服务单重休假M/G/1型排队系统进行建模,并对主要性能指标进行仿真分析是迫切以及可行地.仿真软件选用CPNTools[1],仿真结果证明该方法具有较高的精确度以及实用价值.     

The GI/M/1 queue and the GI/Geo/1 queue both with single working vacation

We first consider the continuous-time GI/M/1 queue with single working vacation (SWV). During the SWV, the server works at a different rate rather than completely stopping working. We derive the steady-state distributions for the number of customers in the system both at arrival and arbitrary epochs, and for the FIFO sojourn time for an arbitrary customer. We then consider the discrete-time GI/Geo/1/SWV queue by contrasting it with the GI/M/1/SWV queue.     

On asymptotics of the emptiness probability in the M/GI/1 queue

We obtain the asymptotic estimation for the non-stationary emptiness probability in the M/GI/1 queue for the case of regularly varying tails of service-time distribution.     

A polynomial factorization approach to the discrete time GI/G/1/(N) queue size distribution

The queue of a single server is considered with independent and identically distributed interarrivai and service times and an infinite (GI/G/1) or finite (GI/G/1/N) waiting room. The queue discipline is non-preemptive and independent of the service times.

A discrete time version of the system is analyzed, using a two-component state model at the arrival and departure instants of customers. The equilibrium equations are solved by a polynomial factorization method. The steady state distribution of the queue size is then represented as a linear combination of geometrical series, whose parameters are evaluated by closed formulae depending on the roots of a characteristic polynomial.

Considering modified boundary constraints, systems with finite waiting room or with an exceptional first service in each busy period are included.     

Steady state analysis of the GI/M/1/N queue with a variant of multiple working vacations

This paper studies the GI/M/1/N queue with a variant of multiple working vacations, where the server leaves for a working vacation as soon as the system becomes empty. The server takes at most H consecutive working vacations if the system remains empty after the end of a working vacation. Employing the supplementary variable and embedded Markov chain methods, we obtain the queue length distribution at different time epochs. Based on the various system length distribution, the probability of blocking, mean waiting times and mean system lengths have been derived. Finally, numerical results are discussed.     

A note on mixed exponential approximations for Gi/G/1 waiting times

A method is offered for the effective estimation of the stationary waiting-time distribution of the GI/G/1 queue by a (possibly nonconvex) mixed exponential CDF. The approach relies on obtaining a generalized exponential mixture as an approximation for the distribution of the service times. This is done by the adaptation of a nonlinear optimization algorithm previously developed for the maximum-likelihood estimation of parameters from mixed Weibull distributions. The approach is particularly well-suited for obtaining the delay distribution beginning from raw interarrivai and service-time data.     

An Optimal Multithreshold Control for the Input Flow of the GI/PH/1 Queueing System with a BMAP Flow of Negative Customers

A GI/PH/1 queueing system with an additional flow of negative customers is studied. The system has many operation modes differing in the distribution of inter-arrival lengths. Mode control depends on the queue length at arrival instants defined by a multithreshold strategy. The stationary state probability distribution of the system for fixed thresholds is studied. Numerical examples are given to illustrate the determination of the optimal threshold set in a fixed search domain.     

Analytic and computational analysis of the discrete-time GI/D-MSP/1 queue using roots

This paper presents a simple closed-form analysis for evaluating system-length distributions at various epochs of the discrete-time GI/D-MSP/1 queue. The proposed analysis is based on roots of the associated characteristic equation of the vector-generating function of system-length distribution at prearrival epochs. We provide the steady-state system-length distribution at random epoch by using the classical argument based on Markov renewal theory. The queueing-time distribution has also been investigated. Numerical aspects have been tested for a variety of interarrival- and service-time distributions and a sample of numerical outputs is presented.     

On a singular feature of critical G/M/1 queues

In this paper, we consider a critically loaded G/M/1 queue and contrast its transient behaviour with the transient behaviour of stable (or unstable) G/M/1 queues. We show that the departure process from a critical G/M/1 queue converges weakly to a Poisson process. However, as opposed to the stable (or unstable) case, we show that the departure process of a critical GI/M/1 queue does not couple in finite time with a Poisson process (even though it converges weakly to one). Thus, as the traffic intensity (ratio of arrival to service rates), , ranges over (0, ∞), the point = 1 represents a singularity with regard to the convergence mode of the departure process.     

Distribution of the number of jobs in a GI/GI/1/∞ queue with a constant flow time constraint

We derive the Laplace transform of the joint distribution density of the number of jobs and of the vector of their flow time in a GI/GI/1/ queue with a constant constraint on job flow time.Translated from Kibernetika, No. 1, pp. 78–81, January–February, 1889.     

Processor sharing: A survey of the mathematical theory

During last few decades the Egalitarian Processor Sharing (EPS) has gained a prominent role in applied probability, especially, in queueing theory and its computer applications. While the EPS paradigm emerged in 1967 as an idealization of round-robin (RR) scheduling algorithm in time-sharing computer systems, it has recently capture renewed interest as a powerful concept for modeling WEB servers. This paper summarizes the most important results concerning the exact solutions for the M/GI/1 queue with egalitarian processor sharing. The material is drawn, mainly, from recent authors’ papers which are supplemented, in small degree, by other related results. Many of the further results are established under the direct influence of our earlier papers. Our main purpose is to give a survey of state-of-the-art with regard to main achievements of the contemporary theory of the M/GI/1 queueing system with processor sharing. The focus is on the methods and techniques of exact and asymptotic analysis of this queueing system. In contrast to the standard surveys, the abridged proofs (or their ideas) of some key theorems and corollaries are included in the paper. We outline recent developments in exact analysis of the M/GI/1-EPS queue with further emphasis on time-dependent (transient) probability distributions of the main characteristics. In particular, the present paper includes the results on the joint time-dependent distribution of the sojourn time of a job arriving at time t with the service demand (length) u, and of the number of jobs at time t- in the M/GI/1 queue with egalitarian processor sharing, which obtained in form of multiple transforms. We also show how the non-stationary solutions can be used to obtain known and new results which allow to predict the behaviour of the EPS queue and to yield additional insights into its new unexpected properties. We also discuss a number of limit theorems arising under the study of the processor sharing queues.