Matched queueing systems with a double input

In this paper, we study the matched queueing system with a double input, M o M/PH/1, where the two inputs are two independent Poisson processes, and the service time is of PH-distribution. The L.S. transforms and the expectations of the distributions of occupation time and virtual waiting time of the type-1 customer are derived. The probability that the server is working, the mean non-idle period, and the mean busy period are also derived. The related algorithms are given with numerical results.This project is supported by the National Natural Science Foundation of China.     

The matched queueing system GIoPh/Ph/1

We study the matched queueing system GIoPH/PH/1, where the type-I input is a renewal process, the type-II input is a PH renewal process, and the service times are i.i.d. random variables with PH-distributions. First, a condition is given for the stationarity of the system. Then the distributions of the number of type-I customers at the arrival epoches of type-I customers and the number of type-I customers at an arbitrary epoch are derived. We also discuss the occupation time and the waiting time. Their L.S. transforms are derived. Finally, we discuss some problems in numerical computation.This research is supported by the National Natural Science Foundation of China and partially by the Institute of Mathematics, the Chinese Academy of Sciences.     

动态输入率和服务率设定下的M/M/c模型扩展及其应用

为了解决M/M/c模型中恒定输入率和服务率假设与现实现象不符的问题,本文提出了随系统状态变化的输入概率和服务度,并通过新输入概率与平均输入率以及新服务度与平均服务率的结合分别构造了动态输入率和服务率。基于上述动态输入率和动态服务率,建立了依赖系统当前状态的状态转移过程,从状态转换强度方面优化了排队理论及其度量模型,同时,设计了结合系统实际的后确定法求解动态输入率与服务率的相关参数,从而构建了扩展M/M/c模型。由于输入率和服务率的动态性,扩展M/M/c模型具有比原排队论模型更广的适用范围和精度更高的模拟结果。最后,通过一个生活实例对新模型的有效性和实用性进行验证。     

匹配排队网络的忙期

本文考虑了匹配排队网络ＰＨ／Ｍ／ｃ→ｏＰＨ／１,研究了两个子系统和整个网络的忙期与非闲期的概率分布,得到了具有一致误差的算法。,然后证明了这些算法的时间与空间的计算复杂性都是多项式的．最后给出了数例。     

THE MATCHED QUEUEING SYSTEM GI。PH/PH/1

ＴＨＥＭＡＴＣＨＥＤＱＵＥＵＥＩＮＧＳＹＳＴＥＭＧＩ。ＰＨ／ＰＨ／１ＸＵＧＵＡＮＣＨＵＩ（ＧＵＡＮＧ－ＨＵＩＨＳＶ）（徐光煇）；ＨＥＱＩＭＩＮＧ（何启明）（ＩｎｓｔｉｔｕｔｅｏｆＡｐｐｌｉｅｄＭａｔｈｅｍａｔｉｃｓ，ｔｈｅＣｈｉｎｅｓｅＡｃａｄｅｍｙ...     

Combined Elapsed Time and Matrix-Analytic Method for the Discrete Time GI/G/1 and GI X /G/1 Systems

In this paper, we show that the discrete GI/G/1 system can be easily analysed as a QBD process with infinite blocks by using the elapsed time approach in conjunction with the Matrix-geometric approach. The positive recurrence of the resulting Markov chain is more easily established when compared with the remaining time approach. The G-measure associated with this Markov chain has a special structure which is usefully exploited. Most importantly, we show that this approach can be extended to the analysis of the GI ^X /G/1 system. We also obtain the distributions of the queue length, busy period and waiting times under the FIFO rule. Exact results, based on computational approach, are obtained for the cases of input parameters with finite support – these situations are more commonly encountered in practical problems.     

带负顾客和N-策略的Geo^{lambda_1, lambda_2/Geo/1(MWV)排队系统分析及最优控制策略N*

分析了一个带有负顾客、N-策略控制的Geo/Geo/1多重工作休假排队系统, 其中正顾客在工作休假及正规忙期以不同的到达率进入系统. 利用拟生灭过程和矩阵几何解方法, 给出了该模型的稳态队长分布及平均队长, 以及系统分别处于假期和忙期的概率. 同时, 对该系统的忙期进行了分析, 并讨论了稳态队长分布在系统容量的优化设计中的应用. 最后, 在给定的费用结构下, 用数值计算例子确定了使系统长期单位时间内期望费用最小的最优控制策 N*.     

Bayesian prediction inM/M/1 queues

Simple queues with Poisson input and exponential service times are considered to illustrate how well-suited Bayesian methods are used to handle the common inferential aims that appear when dealing with queue problems. The emphasis will mainly be placed on prediction; in particular, we study the predictive distribution of usual measures of effectiveness in anM/M/1 queue system, such as the number of customers in the queue and in the system, the waiting time in the queue and in the system, the length of an idle period and the length of a busy period.     

Low-dimensional I/O modeling of Distributed Parameter Systems

Many model reduction techniques take a semi-discretization of the original PDE model as starting point and aim then at an accurate approximation of its input/output map. In this contribution, we discuss the direct discretization of the i/o map of the original infinite-dimensional system. First, the input and output signals are discretized in space and time, second, the system dynamics are approximated in form of the underlying evolution operator, leading to an approximated i/o map with matrix representation. The discretization framework, corresponding error estimations, a SVD-based system reduction method and a numerical application in an optimization problem are presented for the example of a linear time-invariant heat equation. (© 2006 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

带有部分工作休假和休假中断的M/M/c排队

考虑了一个带有部分工作休假和休假中断的多服务台M/M/c排队.在休假期,d(d相似文献   

Discrete NT-policy single server queue with Markovian arrival process and phase type service

We consider a discrete time single server queueing system in which arrivals are governed by the Markovian arrival process. During a service period, all customers are served exhaustively. The server goes on vacation as soon as he/she completes service and the system is empty. Termination of the vacation period is controlled by two threshold parameters N and T, i.e. the server terminates his/her vacation as soon as the number waiting reaches N or the waiting time of the leading customer reaches T units. The steady state probability vector is shown to be of matrix-geometric type. The average queue length and the probability that the server is on vacation (or idle) are obtained. We also derive the steady state distribution of the waiting time at arrivals and show that the vacation period distribution is of phase type.     

The output of a buffered data communication system

The output process in a buffer-multiplexer data communication system with N identical input lines and one output line is considered. It is assumed that the rate of transmission on the input lines and on the output line is 1, that idle periods on the input lines follow an exponential distribution, and that active periods are allowed to have an arbitrary distribution function. The main result is that active periods on the output line follow the same distribution function as the busy period in a certain M/G/1 queue. First passage times from any state of the system to complete idleness are also considered and their Laplace transforms are derived.     

Optimal Flow Control of a G/G/c Finite Capacity Queue

The optimal flow control of a G/G/c finite capacity queue is investigated by approximating the general (G-type) distributions by a maximum entropy model with known first two moments. The flow-control mechanism maximizing the throughput, under a bounded time-delay criterion, is shown to be of window type (bang-bang control). The optimal input rate and the maximum number of packets in the system (i.e. sliding window size) are derived in terms of the maximum input rate and the second moment of the interinput time, the maximum allowed average time delay, the first two moments of the service times and the number of servers. Moreover, the relationship between the maximum throughput and maximum time delay is determined. Numerical examples provide useful information on how critically the optimal throughput is affected by the distributional form of the input and service patterns and the finite capacity of the queue.     

Fluid queue driven by anM/M/1 queue

A fluid queue receiving its input from the output of a precedingM/M/1 queue is considered. The input can be characterized as a Markov modulated rate process and the well known spectral decomposition technique can be applied. The novel features in this system relate to the nature of the spectrum, which is shown to be composed of a continuous part and one or two discrete points depending on whether the load of the fluid queue is less or greater than the output to input rate ratio. Explicit expressions of the generalized eigenvectors are given in terms of Chebyshev polynomials of the second kind, and the resolution of unity is determined. The solution for the buffer content distribution is obtained as a simple integral expression. Numerical examples are given.     

具有Bernoulli反馈且带有负顾客的PH/M/1排队系统

在PH/M/1排队模型中,引入了负顾客和Bernoulli反馈,并讨论了服务台容量为有限和无限两类模型,其中,模型一为服务台容量为无限的PH/M/1排队模型,利用拟生灭过程和矩阵几何解法得到了系统的转移速率矩阵,给出了系统正常返的充要条件,并得到了系统的稳态队长、忙期长度的拉普拉斯变换,以及系统的其它相关性能指标.模型二为服务台容量为有限的PH/M/1/N排队模型,同样使用拟生灭过程给出了马尔科夫过程的转移速率矩阵,并利用矩阵分析法进行求解,得到了该系统的稳态解和其它相关指标.     

Two acceleration mechanisms in verified global optimization

Acceleration devices are very important to speed up interval global optimization algorithms. We propose here two techniques which can be applied in addition to other known techniques. Firstly, we propose a test based on the one-dimensional Newton iteration to discard or split the current box. This test is usually cheap and it is likely to be successful when a good approximation of the minimum is known early. The other technique proposed deals with parallelization. We propose to share the task of the manager process among other non-idle processes in such a way that not only one process is responsible for the load balancing. Experimental results presented show that both techniques yield significant improvements in many cases.     

Performance Analysis of the GI/M/1 Queue with Single Working Vacation and Vacations

In this paper, we consider a new class of the GI/M/1 queue with single working vacation and vacations. When the system become empty at the end of each regular service period, the server first enters a working vacation during which the server continues to serve the possible arriving customers with a slower rate, after that, the server may resume to the regular service rate if there are customers left in the system, or enter a vacation during which the server stops the service completely if the system is empty. Using matrix geometric solution method, we derive the stationary distribution of the system size at arrival epochs. The stochastic decompositions of system size and conditional system size given that the server is in the regular service period are also obtained. Moreover, using the method of semi-Markov process (SMP), we gain the stationary distribution of system size at arbitrary epochs. We acquire the waiting time and sojourn time of an arbitrary customer by the first-passage time analysis. Furthermore, we analyze the busy period by the theory of limiting theorem of alternative renewal process. Finally, some numerical results are presented.     

Controlling the GI/M/1 queue by conditional acceptance of customers

In this paper we consider the problem of controlling the arrival of customers into a GI/M/1 service station. It is known that when the decisions controlling the system are made only at arrival epochs, the optimal acceptance strategy is of a control-limit type, i.e., an arrival is accepted if and only if fewer than n customers are present in the system. The question is whether exercising conditional acceptance can further increase the expected long run average profit of a firm which operates the system. To reveal the relevance of conditional acceptance we consider an extension of the control-limit rule in which the nth customer is conditionally admitted to the queue. This customer may later be rejected if neither service completion nor arrival has occurred within a given time period since the last arrival epoch. We model the system as a semi-Markov decision process, and develop conditions under which such a policy is preferable to the simple control-limit rule.     

启动时间的GI／G／1排队系统的非平衡理论

本文利用侯振挺等提出的马尔可夫骨架过程理论讨论了启动时间的GI/G/I排队系统，得到了此系统到达过程，队长，及等待时间的概率分布/     

A storage model for data communication systems

We consider a storage model where the input and demand are modulated by an underlying Markov chain. Such models arise in data communication systems. The input is a Markov-compound Poisson process and the demand is a Markov linear process. The demand is satisfied if physically possible. We study the properties of the demand and its inverse, which may be viewed as transformed time clocks. We show that the unsatisfied demand is related to the infimum of the net input and that, under suitable conditions, it is an additive functional of the input process. The study of the storage level is based on a detailed analysis of the busy period, using techniques based on infinitesimal generators. The transform of the busy period is the unique solution of a certain matrix-functional equation. Steady state results are also obtained; these are not obvious generalizations of the results for simple storage models. In particular, a generalization of the Pollaczek-Khinchin formula brings new insight.Research supported by Grant BD/645/90-RM from Junta Nacional de Investigação Cientifica e Tecnológica.