On the infinite server shortest queue problem: Non-symmetric case

We consider two parallel M/M/∞ queues. All servers in the first queue work at rate μ₁ and all in the second work at rate μ₂. A new arrival is routed to the system with the lesser number of customers. If both queues have equal occupancy, the arrival joins the first queue with probability ν₁, and the second with probability ν₂ = 1−ν₁. We analyze this model asymptotically. We assume that the arrival rate λ is large compared to the two service rates. We give several different asymptotic formulas, that apply for different ranges of the state space. The numerical accuracy of the asymptotic results is tested. AMS subject classification 60K25 60K30 34E20     

Author Index to Volumes 100 and 101: 1998

Through both analytical and numerical methods, we solve the eigenproblem u_zz >+(1/ z −λ−( z −1/ε)²) u =0 on the unbounded interval z ∈[−∞, ∞], where λ is the eigenvalue and u ( z )→0 as | z |→∞. This models an equatorially trapped Rossby wave in a shear flow in the ocean or atmosphere. It is the usual parabolic cylinder equation with Hermite functions as the eigenfunctions except for the addition of an extra term, which is a simple pole. The pole, which is on the interior of the interval, is interpreted as the limit δ→0 of 1/( z − i δ). The eigenfunction has a branch point of the form z  log( z ) at z =0, where the branch cut is on the upper imaginary axis. The eigenvalue is complex valued with an imaginary part, which we show, through matched asymptotics, to be approximately √ π exp(−1/ε²){1−2ε log ε+ε log 2+γε}. Because T ( λ ) is transcendentally small in the small parameter ε, it lies "beyond all orders" in the usual Rayleigh–Schrödinger power series in ε. Nonetheless, we develop special numerical algorithms that are effective in computing T ( λ ) for ε as small as 1/100.     

Some first passage time problems for the shortest queue model

We consider the symmetric shortest queue (SQ) problem. Here we have a Poisson arrival stream of rate λ feeding two parallel queues, each having an exponential server that works at rate μ. An arrival joins the shorter of the two queues; if both are of equal length the arrival joins either with probability 1/2. We consider the first passage time until one of the queues reaches the value m ₀, and also the time until both reach this level. We give explicit expressions for the first two first passage moments, conditioned on the initial queue lengths, and also the full first passage distribution. We also give some asymptotic results for m ₀→∞ and various values of ρ=λ/μ. H. Yao work was partially supported by PSC-CUNY Research Award 68751-0037. C. Knessl work was supported in part by NSF grants DMS 02-02815 and DMS 05-03745.     

Some Asymptotic Results for the M/M/∞ Queue with Ranked Servers

We consider an M/M/ model with m primary servers and infinitely many secondary ones. An arriving customer takes a primary server, if one is available. We derive integral representations for the joint steady state distribution of the number of occupied primary and secondary servers. Letting =/ be the ratio of arrival and service rates (all servers work at rate ), we study the joint distribution asymptotically for . We consider both m=O(1) and m scaled to be of the same order as . We also give results for the marginal distribution of the number of secondary servers that are occupied.     

Asymptotic Expansions for Two Singularly Perturbed Convection–Diffusion Problems with Discontinuous Data: The Quarter Plane and the Infinite Strip

We consider a singularly perturbed convection–diffusion equation,     , defined on two domains: a quarter plane,  ( x , y ) ∈ (0, ∞) × (0, ∞)  , and an infinite strip,  ( x , y ) ∈ (−∞, ∞) × (0, 1)  . We consider for both problems discontinuous Dirichlet boundary conditions:   u ( x , 0) = 0  and   u (0, y ) = 1  for the first one and   u ( x , 0) =χ_{[ a , b ]}( x )  and   u ( x , 1) = 0  for the second. For each problem, asymptotic expansions of the solution are obtained from an integral representation in two limits: (a) when the singular parameter  ε→ 0⁺  (with fixed distance r to the discontinuity points of the boundary condition) and (b) when that distance   r → 0⁺  (with fixed ε). It is shown that in both problems, the first term of the expansion at  ε= 0  is an error function or a combination of error functions. This term characterizes the effect of the discontinuities on the ε-behavior of the solution and its derivatives in the boundary or internal layers. On the other hand, near the discontinuities of the boundary condition, the solution u ( x , y ) of both problems is approximated by a linear function of the polar angle at the discontinuity points.     

Asymptotic Analysis of a Perturbed Periodic Solution for the KdV Equation

We consider the solution of the Korteweg–de Vries (KdV) equation with periodic initial value where C , A , k , μ, and β are constants. The solution is shown to be uniformly bounded for all small ɛ, and a formal expansion is constructed for the solution via the method of multiple scales. By using the energy method, we show that for any given number   T > 0  , the difference between the true solution v ( x , t ; ɛ) and the N th partial sum of the asymptotic series is bounded by  ɛ ^{N +1}  multiplied by a constant depending on T and N , for all  −∞ < x < ∞, 0 ≤ t ≤ T /ɛ  , and  0 ≤ɛ≤ɛ₀  .     

Painlevé IV Asymptotics for Orthogonal Polynomials with Respect to a Modified Laguerre Weight

We study polynomials that are orthogonal with respect to the modified Laguerre weight   z ^{− n +ν} e ^{− Nz} ( z − 1)^{2 b}   , in the limit where   n , N →∞  with   N / n → 1  and ν is a fixed number in     . With the effect of the factor (   z − 1)^{2 b}   , the local parametrix near the critical point z = 1 can be constructed in terms of Ψ functions associated with the Painlevé IV equation. We show that the asymptotics of the recurrence coefficients of orthogonal polynomials can be described in terms of specified solution of the Painlevé IV equation in the double scaling limit. Our method is based on the Deift/Zhou steepest decent analysis of the Riemann–Hilbert problem associated with orthogonal polynomials.     

Storage allocation under processor sharing I: exact solutions and asymptotics

We consider a processor-sharing storage allocation model, which has m primary holding spaces and infinitely many secondary ones, and a single processor servicing the stored items (customers). An arriving customer takes a primary space, if one is available. We define the traffic intensity ρ to be λ/μ where λ is the customers’ arrival rate and μ is the service rate of the processor. We study the joint probability distribution of the numbers of occupied primary and secondary spaces. For 0<ρ<1, we obtain the exact solutions for m=1 and m=2. For arbitrary m we study the problem in the asymptotic limit ρ↑1 with m fixed. We also give the tail of the distribution for a fixed ρ<1 and any m.     

Waiting time in a multi-server cutoff-priority gueue, and its application to an urban ambulance service

We consider a priority queue in steady state with N servers, two classes of customers, and a cutoff service discipline. Low priority arrivals are "cut off" (refused immediate service) and placed in a queue whenever N1 or more servers are busy, in order to keep N-N1 servers free for high priority arrivals. A Poisson arrival process for each class, and a common exponential service rate, are assumed. Two models are considered: one where high priority customers queue for service and one where they are lost if all servers are busy at an arrival epoch. Results are obtained for the probability of n servers busy, the expected low priority waiting time, and (in the case where high priority customers do not queue) the complete low priority waiting time distribution. The results are applied to determine the number of ambulances required in an urban fleet which serves both emergency calls and low priority patients transfers.     

Maximum Likelihood Estimates and Confidence Intervals of an M/M/R Queue with Heterogeneous Servers

This paper studies maximum likelihood estimates as well as confidence intervals of an M/M/R queue with heterogeneous servers under steady-state conditions. We derive the maximum likelihood estimates of the mean arrival rate and the three unequal mean service rates for an M/M/3 queue with heterogeneous servers, and then extend the results to an M/M/R queue with heterogeneous servers. We also develop the confidence interval formula for the parameter ρ, the probability of empty system P ₀, and the expected number of customers in the system E[N], of an M/M/R queue with heterogeneous servers     

On the Erlang Loss Model with Time Dependent Input

We consider the M(t)/M(t)/m/m queue, where the arrival rate λ(t) and service rate μ(t) are arbitrary (smooth) functions of time. Letting p_n(t) be the probability that n servers are occupied at time t (0≤ n≤ m, t > 0), we study this distribution asymptotically, for m→∞ with a comparably large arrival rate λ(t) = O(m) (with μ(t) = O(1)). We use singular perturbation techniques to solve the forward equation for p_n(t) asymptotically. Particular attention is paid to computing the mean number of occupied servers and the blocking probability p_m(t). The analysis involves several different space-time ranges, as well as different initial conditions (we assume that at t = 0 exactly n₀ servers are occupied, 0≤ n₀≤ m). Numerical studies back up the asymptotic analysis. AMS subject classification: 60K25,34E10 Supported in part by NSF grants DMS-99-71656 and DMS-02-02815     

关于亚纯代数体函数的奇异方向

设T(r, w)满足:lim_{r →∞}lg T(r, w)/lg r =0,lim_r→∞lg T(r, w)/lg lg r =+ ∞, 则一定存在一条方向arg z=θ₀ ,使对任意给定N>0,任意复数 a (至多有2 v个例外值), 有∑_i1/(lg|z_i(a;?(θ₀,δ))|)^N=∞.设T(r, w)满足:lim_r→∞T(r, w)/lg^Kr =+∞,lim_r→+∞lg T(r, w) /lg lg r =M, 则一定存在一条方向argz=θ₀ ,对任意复数a (至多有2 v个例外值),有∑_i1/lg|z_i(a;?(θ₀,δ))|)^σ=∞(σ = M-2或σ = M-2-ε.即使在亚纯函数,这些奇异方向也未见研究.     

Optimal allocation of priority in a M/M/1 queue with two types of customers

We consider a M/M/1 queue with two types of customers.The server suffers some loss when a non-priority customer joins the queue if the size of the queue is greater than some predetermined level N. The problem is to decide which group receives priority in such a way as to minimize the expected cost per unit of time.We show first how to determine the optimal decision. Then we introduce approximations that enable us to show that the optimal decision has a simple behaviour as a function of N, the arrival and service parameters.     

Heavy traffic limit for a tandem queue with identical service times

We consider a two-node tandem queueing network in which the upstream queue is M/G/1 and each job reuses its upstream service requirement when moving to the downstream queue. Both servers employ the first-in-first-out policy. We investigate the amount of work in the second queue at certain embedded arrival time points, namely when the upstream queue has just emptied. We focus on the case of infinite-variance service times and obtain a heavy traffic process limit for the embedded Markov chain.     

Asymptotic analysis of the M/G/1 queue with a time‐dependent arrival rate

We consider the M/G/1 queue with an arrival rate λ that depends weakly upon time, as λ = λ(εt) where ε is a small parameter. In the asymptotic limit ε → 0, we construct approximations to the probability p _n(t)that η customers are present at time t. We show that the asymptotics are different for several ranges of the (slow) time scale Τ= εt. We employ singular perturbation techniques and relate the various time scales by asymptotic matching. This revised version was published online in June 2006 with corrections to the Cover Date.     

The Stokes and Krasovskii Conjectures for the Wave of Greatest Height

The integral equation:
φ_μ(s) = (1/3 π)∫^π ₀((sin φ_μ(t))/(μ ⁻¹+ ∫^t ₀sin φ_μ(u) d u )) (log((sin½( s + t ))/ (sin½( s − t )))d t
was derived by Nekrasov to describe waves of permanent form on the surface of a nonviscous, irrotational, infinitely deep flow, the function φ_μ giving the angle that the wave surface makes with the horizontal. The wave of greatest height is the singular case μ=∞, and it is shown that there exists a solution φ_∞ to the equation in this case and that it can be obtained as the limit (in a specified sense) as μ→∞ of solutions for finite μ. Stokes conjectured that φ_∞( s )→⅙π as s ↓0, so that the wave is sharply crested in the limit case; and Krasovskii conjectured that sup _{s ∈[0,π]}φ_μ( s )≤⅙π for all finite μ. Stokes' conjecture was finally proved by Amick, Fraenkel, and Toland, and the present article shows Krasovskii's conjecture to be false for sufficiently large μ, the angle exceeding ⅙π in what is a boundary layer.     

Geometrical Optics Approach to Markov-Modulated Fluid Models

We analyze asymptotically a differential-difference equation, that arises in a Markov-modulated fluid model. Here, there are N identical sources that turn on and off , and when on they generate fluid at unit rate into a buffer, which processes the fluid at a rate   c < N   . In the steady-state limit, the joint probability distribution of the buffer content and the number of active sources satisfies a system of   N + 1  ODEs, that can also be viewed as a differential-difference equation analogous to a backward/forward parabolic PDE. We use singular perturbation methods to analyze the problem for   N →∞  , with appropriate scalings of the two state variables. In particular, the ray method and asymptotic matching are used.     

A fork-join queueing model: Diffusion approximation,integral representations and asymptotics

We consider two parallel M/M/1 queues which are fed by a single Poisson arrival stream. An arrival splits into two parts, with each part joining a different queue. This is the simplest example of a fork-join model. After the individual parts receive service, they may be joined back together, though we do not consider the join part here. We study this model in the heavy traffic limit, where the service rate in either queue is only slightly larger than the arrival rate. In this limit we obtain asymptotically the joint steady-state queue length distribution. In the symmetric case, where the two servers are identical, this distribution has a very simple form. In the non-symmetric case we derive several integral representations for the distribution. We then evaluate these integrals asymptotically, which leads to simple formulas which show the basic qualitative structure of the joint distribution function.     

半无穷区间广义Sturm-Liouville边值问题的多个正解存在性

该文利用Leggett-Williams 不动点定理, 研究半无穷区间边值问题 (p(t)x'(t))'+Φ(t) f (t, x(t), x'(t))=0, t∈[0,+∞), α₁x(0)-β₁lim_t→0⁺ p(t) x'(t)=a₁, α₂lim_t→+∞ x'(t)+β₂lim_t→+∞ p(t) x'(t)=a₂. 多个正解的存在性.     

On the Complex Differential Equation Y"+G(z)Y=0 in Banach Algebras

Asymptotic representations, as z →∞, are presented as a basis of solutions to linear complex differential equations in the framework of Banach algebras, such as d^kY / dz^k + G ( z ) Y =0, k =1, 2, z ∈Ω⊆ C . Here Ω is open, unbounded, and simply connected, and the coefficient G ( z ) is assumed to be "asymptotically negligible," in the sense that suitable "moments" of ‖ G ( z )‖ are finite on certain paths in Ω. Precise pathwise as well as uniform bounds for the asymptotic error terms are obtained by exploiting the geometric properties of the paths via the successive approximations method. Such results extend to the complex domain in previous work on matrix and abstract differential equations on the real domain, and also appear new for scalar and matrix differential equations on complex domains other than sectors.