Perturbation analysis of theGI/GI/1 queue

We examine a family ofGI/GI/1 queueing processes generated by a parametric family of service time distributions,F(x,), and we show that under suitable conditions the corresponding customer stationary expectation of the system time is twice continuously differentiable with respect to. Expressions for the derivatives are given which are suitable for single run derivative estimation. These results are extended to parameters of the interarrival time distribution and expressions for the corresponding second derivatives (as well as partial second derivatives involving both interarrivai and service time parameters) are also obtained. Finally, we present perturbation analysis algorithms based on these expressions along with simulation results demonstrating their performance.     

排队论中之一问题——M/W/n

<正> 排队论问题中最常遇到的也是较为重要的问题之一,就是在随机输入,服务时间按负指数分布的假定之下,决定有关各种概率的问题.我们用符号 M/M/n 表示这样的一个服务系统:“顾客”输入服从参数λ的 Poisson 分布,先到来,先服务,服务时间的长短服从参数产的负指数分布,共有 n 个服务台.若“顾客”到来时发现服务台有空,则他可在空下的服务台中随意挑选一个而立刻受到服务,若无服务台空下,则他即依到来的次序列队等待,直到被服务完毕之后才离开.近年来,不少的作者([1],[2],[3],[4],[5]皆集中于     

On the output process of an M/M/1 queue with randomly varying system parameters

In this paper an analysis of the output process from an M/M/1 queue where the arrival and service rates vary randomly is presented. The results include expressions for the mean, variance and distribution of the interdeparture interval, the joint density function of two successive interdeparture intervals and their correlation. An interesting feature of the results is that the moments of the interdeparture time are expressed in terms of the expected times to first and second departures from an arbitrary point in time.     

The M/G/1 processor-sharing model: transient behavior

This paper deals with the M/G/1 model with processor-sharing service discipline. LetL ^* (t, x) denote the number of jobs present at timet whose attained service time is not greater thanx,x0, andV ₀(t,z) the sojourn time of a tagged job placed in the system at timet and requiringz units of service. Explicit analytical expressions are obtained for the joint distribution ofL ^*(t, ·) andV ⁰(t, ·) under various initial conditions in terms of the Laplace transform with respect tot. It is shown that for initial conditions of special kind (there is one job or none) the results can be expressed in a closed form.     

Equilibrium properties of the M/G/1 queue

Summary Various aspects of the equilibrium M/G/1 queue at large values are studied subject to a condition on the service time distribution closely related to the tail to decrease exponentially fast. A simple case considered is the supplementary variables (age and residual life of the current service period), the distribution of which conditioned upon queue length n is shown to have a limit as n. Similar results hold when conditioning upon large virtual waiting times. More generally, a number of results are given which describe the input and output streams prior to large values e.g. in the sense of weak convergence of the associated point processes and incremental processes. Typically, the behaviour is shown to be that of a different transient M/G/1 queueing model with a certain stochastically larger service time distribution and a larger arrival intensity. The basis of the asymptotic results is a geometrical approximation for the tail of the equilibrium queue length distribution, pointed out here for the GI/G/1 queue as well.     

推广的多重休假$M^X/G/1$排队系统

在平稳状态下,Baba利用补充变量方法研究了多重休假的MX/G/1排队,但作者假定了休假时间和服务时间都有概率密度函数.本文考虑推广的多重休假MX/G/1排队,在假定休假时间和服务时间都是一般概率分布函数下,我们研究了队长的瞬态和稳态性质.通过引进"服务员忙期"和使用不同于Baba文中使用的分析技术,我们导出了在任意时刻t瞬态队长分布的L变换的递推表达式和稳态队长分布的递推表达式,以及平稳队长的随机分解.特别地,通过本文可直接获得多重休假的M/G/1与标准的MX/G/1排队系统相应的结果.     

Representing workloads in GI/G/1 queues through the preemptive-resume LIFO queue discipline

We give in this paper a detailed sample-average analysis of GI/G/1 queues with the preemptive-resume LIFO (last-in-first-out) queue discipline: we study the long-run state behavior of the system by averaging over arrival epochs, departure epochs, as well as time, and obtain relations that express the resulting averages in terms of basic characteristics within busy cycles. These relations, together with the fact that the preemptive-resume LIFO queue discipline is work-conserving, imply new representations for both actual and virtual delays in standard GI/G/1 queues with the FIFO (first-in-first-out) queue discipline. The arguments by which our results are obtained unveil the underlying structural explanations for many classical and somewhat mysterious results relating to queue lengths and/or delays in standard GI/G/1 queues, including the well-known Bene's formula for the delay distribution in M/G/l. We also discuss how to extend our results to settings more general than GI/G/1.     

Two finite-difference methods for solving MAP(t)/PH(t)/1/K queueing models

In this paper two solution methods to the MAP(t)/PH(t)/1/K queueing model are introduced, one based on the Backwards Euler Method and the other on the Uniformization Method. Both methods use finite-differencing with a discretized, adaptive time-mesh to obtain time-dependent values for the entire state probability vector. From this vector, most performance parameters such as expected waiting time and expected number in the system can be computed. Also presented is a technique to compute the entire waiting (sojourn) time distribution as a function of transient time. With these two solution methods one can examine any transient associated with the MAP(t)/PH(t)/1/K model including time-varying arrival and/or service patterns. Four test cases are used to demonstrate the effectiveness of these methods. Results from these cases indicate that both methods provide fast and accurate solutions to a wide range of transient scenarios. This revised version was published online in June 2006 with corrections to the Cover Date.     

时间分数阶扩散方程的一个新的高阶有限差分/谱逼近

研究时间分数阶扩散方程,结合时间方向的有限差分格式和空间方向的Legendre Collocation谱方法,构造了一个高阶稳定数值格式.数值算例表明该格式是无条件稳定和长时间稳定的,其收敛阶为O(Δt^3-α+N^-m),其中Δt,N和m分别是时间步长,空间多项式阶数以及精确解的正则度.     

带启动-关闭期的多重休假M/G/1排队系统的队长分布

研究带启动—关闭期的多重休假M/G/1排队系统,讨论了队长的瞬态和稳态性质.通过引进的"服务员忙期"和使用全概率分解技术,导出了在任意时刻t队长的瞬态分布的L变换的递推表达式和稳态队长分布的递推表达式,以及稳态队长的随机分解结果.     

多重休假Mx/G/1排队系统的输出过程

本文首次研究服务员具有多重休假规则的成批到达Mx/G/1排队系统的输出过程.应用更新过程理论、拉普拉斯-司梯阶变换和本文提出的直接概率分解分析法,讨论了从任意初始状态出发,系统在(0,t]时间内输出顾客的平均数,以及其渐近展开,得到一些重要结果.     

An M/G/1 queueing model with vacation times

This paper deals with an M/G/1 queueing system with finite capacity for the workload, where the workload at timet is defined as the total amount of work in the system at timet. When the server provides service he will continue servicing until the system becomes empty, after which he leaves the system for a stochastic period of time, which will be called a vacation. When the server, returning from a vacation, finds the system still empty, he leaves for another vacation, otherwise he immediately starts servicing again.Using an embedding approach several characteristics of this system are derived amongst which the joint stationary distribution of the workload and the stage of the server.

---

Zusammenfassung Diese Arbeit befaßt sich mit einem M/G/1 Wartesystem, das hinsichtlich der anstehenden Arbeit eine endliche Kapazität hat. Wenn der Bediener tätig ist, bleibt er es solange, bis das System leer ist. Danach ist er während einer stochastischen Pausenzeit nicht verfügbar. Ist am Ende einer Pausenzeit das System immer noch leer, so schließt sich eine weitere Pausenzeit an; ansonsten wird unverzüglich die Bedienung am Ende der Pausenzeit wieder aufgenommen.Unter Verwendung eines eingebetteten Prozesses werden mehrere Kenngrößen des Systems ermittelt, darunter z.B. die gemeinsame Verteilung von anstehender Arbeit und Zustand des Bedieners.

     

Exact analysis of the M/M/k/setup class of Markov chains via recursive renewal reward

The M/M/k/setup model, where there is a penalty for turning servers on, is common in data centers, call centers, and manufacturing systems. Setup costs take the form of a time delay, and sometimes there is additionally a power penalty, as in the case of data centers. While the M/M/1/setup was exactly analyzed in 1964, no exact analysis exists to date for the M/M/k/setup with $k>1$ . In this paper, we provide the first exact, closed-form analysis for the M/M/k/setup and some of its important variants including systems in which idle servers delay for a period of time before turning off or can be put to sleep. Our analysis is made possible by a new way of combining renewal reward theory and recursive techniques to solve Markov chains with a repeating structure. Our renewal-based approach uses ideas from renewal reward theory and busy period analysis to obtain closed-form expressions for metrics of interest such as the transform of time in system and the transform of power consumed by the system. The simplicity, intuitiveness, and versatility of our renewal-based approach makes it useful for analyzing Markov chains far beyond the M/M/k/setup. In general, our renewal-based approach should be used to reduce the analysis of any 2-dimensional Markov chain which is infinite in at most one dimension and repeating to the problem of solving a system of polynomial equations. In the case where all transitions in the repeating portion of the Markov chain are skip-free and all up/down arrows are unidirectional, the resulting system of equations will yield a closed-form solution.     

N-控制策略且温储备失效M/G/1可修排队的可靠性指标

本文研究N-门限值进入控制策略且温储备失效M/G/1可修排队系统, 其中系统在处于温储备失效的状态下最多容许N(1)个顾客进入系统。 运用全概率分解技术和拉普拉斯变换工具, 对服务台第一次失效前的寿命概率分布、不可用度、(0,t]时间内的平均失效次数以及处于温储备失效而等待修理的概率等可靠性指标进行了讨论, 并给出了其稳态结果表达式。 最后, 通过数值实例分析了服务台因温储备故障的稳态不可用度和稳态故障频度随一些参数的变化情况。     

关于排队过程GI/E_k/l的若干結果

<正> §1.引言 采用Kendall的記号,所謂GI/E_k/1是指由下述条件規定的一个排队过程: (i)若用t_n表第n个顾客来到服务系统的时刻,而用ui=ti-t_(i-1)山表示相紕两顾客到达时刻間的間隔(簡称到达間隔),則这些u互相独立,并且服从同一分布     

Optimal monotone hysteretic Markov policies in anM/M/1 queueing model with switching costs and finite time horizon

In anM/M/1 queueing model, a decision maker can choosem pairs of arrival- and service rates. He can change his action at any time epoch, a switch of action costs an amount depending on the size of the switch. Besides that there are continuously incurring costs. Over a finite time horizon, there exists an optimal monotone hysteretic Markov policy. This is shown essentially by the technique of time discretization.The work producing this article was done during a half year stay at the University of Leiden, The Netherlands, with Prof. Arie Hordijk. A technical report (a more detailled version of this article) was written there [6]. The opportunity for this stay was given by the University of Bonn, Germany, where the author, at that time, worked as scientific assistant of Prof. M. Schäl.     

Optimal Lp-Lq-estimates for parabolic boundary value problems with inhomogeneous data

In this paper we investigate vector-valued parabolic initial boundary value problems , subject to general boundary conditions in domains G in with compact C ^2m -boundary. The top-order coefficients of are assumed to be continuous. We characterize optimal L ^p -L ^q -regularity for the solution of such problems in terms of the data. We also prove that the normal ellipticity condition on and the Lopatinskii–Shapiro condition on are necessary for these L ^p -L ^q -estimates. As a byproduct of the techniques being introduced we obtain new trace and extension results for Sobolev spaces of mixed order and a characterization of Triebel-Lizorkin spaces by boundary data.      

N-策略单重休假M/G/1排队系统的队长分布

本文考虑N-策略单重休假M/G/1排队系统,通过引进"服务员忙期"和使用全概率分解技术,从任意初始状态出发,研究了队长的瞬态分布和稳态分布,首次导出了在任意时刻t瞬态队长分布的L变换的递推表达式和稳态队长分布的递推表达式,以及平稳队长的随机分解.特别地,通过本文可直接获得一些特殊排队系统相应的结果.     

Some mildly wild circles in Sn arising from algebraic K-Theory

We study wild embeddings of S ¹ in S ⁿ which are tame in a sense introduced by Quinn. We show that if is a finitely presented group with H ₁()=H ₂()=0, then any finiteness obstruction K ₀() can be realized on the complement of such an embedded S ¹. We also realize trivially symmetric K _–1() obstructions on the complements of such embeddings. For trivially symmetric , the embeddings constructed are shown to be isotopy homogeneous.     

A 3/4-Approximation Algorithm for Multiple Subset Sum

The Multiple Subset Sum Problem (MSSP) is the variant of bin packing in which the number of bins is given and one would like to maximize the overall weight of the items packed in the bins. The problem is also a special case of the multiple knapsack problem in which all knapsacks have the same capacity and the item profits and weights coincide. Recently, polynomial time approximation schemes have been proposed for MSSP and its generalizations, see A. Caprara, H. Kellerer, and U. Pferschy (SIAM J. on Optimization, Vol. 11, pp. 308–319, 2000; Information Processing Letters, Vol. 73, pp. 111–118, 2000), C. Chekuri and S. Khanna (Proceedings of SODA 00, 2000, pp. 213–222), and H. Kellerer (Proceedings of APPROX, 1999, pp. 51–62). However, these schemes are only of theoretical interest, since they require either the solution of huge integer linear programs, or the enumeration of a huge number of possible solutions, for any reasonable value of required accuracy. In this paper, we present a polynomial-time 3/4-approximation algorithm which runs fast also in practice. Its running time is linear in the number of items and quadratic in the number of bins. The core of the algorithm is a procedure to pack triples of large items into the bins. As a byproduct of our analysis, we get the approximation guarantee for a natural greedy heuristic for the 3-Partitioning Problem.