Some Numerical Data for Single-Server Queues Involving Deterministic Input Arrangements

The steady-state parameters of the bulk input queue D _c /M/1 and the Erlang service queue D/E _c /1 have been tabulated for C = 1(1)6(2)12(4)20 and 25, 50 and 100 and for ρ = 0·1(0·1)0·9. The tabulation includes the mean waiting time, idle time and queue size. In addition the queue D/E _c /1 has been compared with the queue M/E _c /1 to indicate the gains to be achieved by regularizing the arrival mechanism for a given E _c service facility.     

Optimal Operating Policy for a Random Additional Service Facility

This paper studies the steady state behaviour of a Markovian queue wherein there is a regular service facility serving the units one by one. A search for an additional service facility for the service of a group of units is started when the queue length increases to K (0 < K < L), where L is the maximum waiting space. The search is dropped when the queue length reduces to some tolerable fixed size L - N. The availability time of an additional service facility is a random variable. The model is directed towards finding the optimal operating policy (N,K) for a queueing system with a linear cost structure.     

The <Emphasis Type="Italic">p</Emphasis>-Centre Problem—Heuristic and Optimal Algorithms

The p-centre problem, or minimax location-allocation problem in location theory terminology, is the following: given n demand points on the plane and a weight associated with each demand point, find p new facilities on the plane that minimize the maximum weighted Euclidean distance between each demand point and its closest new facility. We present two heuristics and an optimal algorithm that solves the problem for a given p in time polynomial in n. Computational results are presented.     

On the Relative Waiting Times in the GI/M/s and the GI/M/1 Queueing Systems

The expected steady-state waiting time, Wq(s), in a GI/M/s system with interarrival-time distribution H(·) is compared with the mean waiting time, Wq, in an "equivalent" system comprised of s separate GI/M/1 queues each fed by an interarrival-time distribution G(·) with mean arrival rate equal to 1/s times that of H(·). For H(·) assumed to be Exponential, Gamma or Deterministic three possible relationships between H(·) and G(·) are considered: G(·) can be of the "same type" as H(·); G(·) can be derived from H(·) by assigning new arrivals to the individual channels in a cyclic order; and G(·) may be obtained from H(·) by assigning customers probabilistically to the different queues. The limiting behaviour of the ratio R = Wq/Wq(s) is studied for the extreme values (1 and 0) of the common traffic intensity, ρ. Closed form results, which depend on the forms of H(·) and G(·) and on the relationships between them, are derived. It is shown that Wq is greater than Wq(s) by a factor of at least (s + 1)/2 when ρ approaches one, and that R is at least s(s!) when ρ tends to zero. In the latter case, however, R goes to infinity (!) in most cases treated. The results may be used to evaluate the effect on the waiting times when, for certain (non-queueing) reasons, it is needed to partition a group of s servers into several small groups.     

The Transient Behaviour of a Cyclic Queue

This paper studies a cyclic queueing problem arising in civil engineering earthmoving projects. There are m excavators and n trucks which queue to be loaded by the excavators. The problem is therefore equivalent to a machine interference problem with m operators and n machines. The size of the haul fleet must be optimized, so as to minimize the cost per unit volume of earth moved. Graphs which show regions of optimal n in the parameter space are presented for the steady-state D/D/1, M/D/1 and E _k /M/1 models. The effect of operating the M/M/m system in short work shifts, so that the initial conditions and transient behaviour are important, is then analysed and quantified as a correction to the optimal number of trucks in the haul fleet from the steady-state solution.     

Further Results for the Queueing System <Emphasis Type="Italic">M</Emphasis><Superscript><Emphasis Type="Italic">x</Emphasis></Superscript>/<Emphasis Type="Italic">M</Emphasis>/<Emphasis Type="Italic">c</Emphasis>

For the multi-channel bulk-arrival queue, M ^x /M/c, Abol'nikov and Kabak independently obtained steady state results. In this paper the results of these authors are extended, corrected and simplified. A number of measures of efficiency are calculated for three cases where the arrival group size has: (i) a constant value, (ii) a geometric distribution, or (iii) a positive Poisson distribution. The paper also shows how to calculate fractiles for both the queue length and the waiting time distribution. Examples of extensive numerical results for certain measures of efficiency are presented in tabular and chart form.     

Approximation algorithms for the robust facility leasing problem

In this paper, we consider the robust facility leasing problem (RFLE), which is a variant of the well-known facility leasing problem. In this problem, we are given a facility location set, a client location set of cardinality n, time periods \(\{1, 2, \ldots , T\}\) and a nonnegative integer \(q < n\). At each time period t, a subset of clients \(D_{t}\) arrives. There are K lease types for all facilities. Leasing a facility i of a type k at any time period s incurs a leasing cost \(f_i^{k}\) such that facility i is opened at time period s with a lease length \(l_k\). Each client in \(D_t\) can only be assigned to a facility whose open interval contains t. Assigning a client j to a facility i incurs a serving cost \(c_{ij}\). We want to lease some facilities to serve at least \(n-q\) clients such that the total cost including leasing and serving cost is minimized. Using the standard primal–dual technique, we present a 6-approximation algorithm for the RFLE. We further offer a refined 3-approximation algorithm by modifying the phase of constructing an integer primal feasible solution with a careful recognition on the leasing facilities.     

Long-range dependence of stationary processes in single-server queues

The stationary processes of waiting times {W _n } _{n = 1,2,…} in a GI/G/1 queue and queue sizes at successive departure epochs {Q _n}_{n = 1,2,…} in an M/G/1 queue are long-range dependent when 3 < κ _S < 4, where κ _S is the moment index of the independent identically distributed (i.i.d.) sequence of service times. When the tail of the service time is regularly varying at infinity the stationary long-range dependent process {W _n } has Hurst index ½(5?κ _S ), i.e.

${\rm sup} \left\{h : {\rm lim sup}_{n\to\infty}\, \frac{{\rm var}(W_1+\cdots+W_n)}{n^{2h}} = \infty \right\} = \frac{5-\kappa_S} {2}\,.$

If this assumption does not hold but the sequence of serial correlation coefficients {ρ _n } of the stationary process {W _n } behaves asymptotically as cn ^?α for some finite positive c and α ? (0,1), where α = κ _S ? 3, then {W _n } has Hurst index ½(5?κ _S ). If this condition also holds for the sequence of serial correlation coefficients {r _n } of the stationary process {Q _n } then it also has Hurst index ½(5κ _S )

     

Estimation Problems for Periodically Correlated Isotropic Random Fields

Spectral theory of isotropic random fields in Euclidean space developed by M. I. Yadrenko is exploited to find a solution to the problem of optimal linear estimation of the functional

$$ A\zeta ={\sum\limits_{t=0}^{\infty}}\,\,\,{\int_{S_n}} \,\,a(t,x)\zeta (t,x)\,m_n(dx) $$

which depends on unknown values of a periodically correlated (cyclostationary with period T) with respect to time isotropic on the sphere S _n in Euclidean space E ⁿ random field ζ(t, x), t?∈?Z, x?∈?S _n . Estimates are based on observations of the field ζ(t, x)?+?θ(t, x) at points (t, x), t?=???1,???2, ..., x?∈?S _n , where θ(t, x) is an uncorrelated with ζ(t, x) periodically correlated with respect to time isotropic on the sphere S _n random field. Formulas for computing the value of the mean-square error and the spectral characteristic of the optimal linear estimate of the functional Aζ are obtained. The least favourable spectral densities and the minimax (robust) spectral characteristics of the optimal estimates of the functional Aζ are determined for some special classes of spectral densities.

     

An exact algorithm for finding a vector subset with the longest sum

We consider the problem: Given a set of n vectors in the d-dimensional Euclidean space, find a subsetmaximizing the length of the sum vector.We propose an algorithm that finds an optimal solution to this problem in time O(n^d?1(d + logn)). In particular, if the input vectors lie in a plane then the problem is solvable in almost linear time.     

A Functional Central Limit Theorem for a Markov-Modulated Infinite-Server Queue

We consider a model in which the production of new molecules in a chemical reaction network occurs in a seemingly stochastic fashion, and can be modeled as a Poisson process with a varying arrival rate: the rate is λ _i when an external Markov process J(?) is in state i. It is assumed that molecules decay after an exponential time with mean μ ^?1. The goal of this work is to analyze the distributional properties of the number of molecules in the system, under a specific time-scaling. In this scaling, the background process is sped up by a factor N ^α , for some α>0, whereas the arrival rates become N λ _i , for N large. The main result of this paper is a functional central limit theorem (F-CLT) for the number of molecules, in that, after centering and scaling, it converges to an Ornstein-Uhlenbeck process. An interesting dichotomy is observed: (i) if α > 1 the background process jumps faster than the arrival process, and consequently the arrival process behaves essentially as a (homogeneous) Poisson process, so that the scaling in the F-CLT is the usual \(\sqrt {N}\), whereas (ii) for α≤1 the background process is relatively slow, and the scaling in the F-CLT is N ^1?α/2. In the latter regime, the parameters of the limiting Ornstein-Uhlenbeck process contain the deviation matrix associated with the background process J(?).     

Optimal M/G/1 Server Location on a Network Having a Fixed Facility

This paper considers the problem of locating a single mobile service unit on a network G where the servicing of a demand includes travel time to a permanent facility which is located at a predetermined point on G. Demands for service, which occur solely on the nodes of the network, arrive in a homogeneous Poisson manner. The server, when free, can be immediately dispatched to a demand: the service unit travels to the demand, performs some on-scene service, continues to the permanent facility, where off-scene service is rendered, and then it returns to its ‘home’ location, where possibly additional off-scene service is given. Previous research has examined the same problem, however without the presence of a permanent facility. The paper discusses methods of solving two cases when the server is unable to be immediately dispatched to service a demand: (1) the zero-capacity queueing system; (2) the infinite-capacity queueing system. For the first case we prove that the optimal location is included in a small set of points in the network, and we show how to find this set. For the second case, we present an 0(n³) algorithm (n is the number of nodes) to obtain the optimal location.     

Waiting times and stopping probabilities for patterns in Markov chains

Suppose that C is a finite collection of patterns. Observe a Markov chain until one of the patterns in C occurs as a run. This time is denoted by τ. In this paper, we aim to give an easy way to calculate the mean waiting time E(τ) and the stopping probabilities P(τ = τA)with A ∈ C, where τA is the waiting time until the pattern A appears as a run.     

Approximating the Mean Waiting Time in the <Emphasis Type="Italic">GI/G/s</Emphasis> Queue

We provide two distribution-dependent approximations for the mean waiting time in a GI/G/s queue. Both approximations are weighted combinations of the exact mean waiting times for the GI/M/s and M/D/s queues each of which has the same mean service time and traffic intensity as in the approximating GI/G/s queue. The weights in the approximations are expressed by the service-time c.d.f. and the first two moments of interarrival and service times. To examine the performance of our approximations, they are numerically compared with exact solutions and previous two-moment approximations for various cases. Extensive numerical comparisons indicate that the relative percentage errors of the approximations are of the order of 5% in moderate traffic and 1% in heavy traffic, except for extreme cases.     

On the principal ideal theorem and spectral synthesis on discrete Abelian groups

For positive integers n, m, and h, we let \({\rho\hat (\mathbb{Z}_n, m, h)}\) denote the minimum size of the h-fold restricted sumset among all m-subsets of the cyclic group of order n. The value of \({\rho\hat (\mathbb{Z}_n, m, h)}\) was conjectured for prime values of n and h = 2 by Erd?s and Heilbronn in the 1960s; Dias da Silva and Hamidoune proved the conjecture in 1994 and generalized it for an arbitrary h, but little is known about the case when n is composite. Here we exhibit an explicit upper bound for all n, m, and h; our bound is tight for all known cases (including all n, m, and h with \({n \leqq 40}\)). We also provide counterexamples for conjectures made by Plagne and by Hamidoune, Lladó, and Serra.     

Extremal behavior of recurrent random sequences

A process Y _n , n ≥ 1, satisfying the stochastic recurrent equation Y _n = A _n Y _n?1 + B _n , n ≥ 1, Y ₀ ≥ 0, is studied in the paper; here (A _n , B _n ), n ≥ 1, are independent identically distributed pairs of nonnegative random variables. The cases when the values A _n have a lognormal and log-Laplace distributions are considered. The tail index κ (for a stationary distribution) and the extremal index ? are studied. In the lognormal case, κ is determined and some useful properties of ? are established. In the log-Laplace case the both characteristics are obtained in explicit form.     

A note on a mixed routing and scheduling problem on a grid graph

We consider a particular case of the Fleet Quickest Routing Problem (FQRP) on a grid graph of m × n nodes that are placed in m levels and n columns. Starting nodes are placed at the first (bottom) level, and nodes of arrival are placed at the mth level. A feasible solution of FQRP consists in n Manhattan paths, one for each vehicle, such that capacity constraints are respected. We establish m*, i.e. the number of levels that ensures the existence of a solution to FQRP in any possible permutation of n destinations. In particular, m* is the minimum number of levels sufficient to solve any instance of FQRP involving n vehicles, when they move in the ways that the literature has until now assumed. Existing algorithms give solutions that require, for some values of n, more levels than m*. For this reason, we provide algorithm CaR, which gives a solution in a graph m* × n, as a minor contribution.     

<Emphasis Type="Italic">GI</Emphasis>/<Emphasis Type="Italic">M</Emphasis>/1 type queueing-inventory systems with postponed work,reservation, cancellation and common life time

In this paper we analyze two single server queueing-inventory systems in which items in the inventory have a random common life time. On realization of common life time, all customers in the system are flushed out. Subsequently the inventory reaches its maximum level S through a (positive lead time) replenishment for the next cycle which follows an exponential distribution. Through cancellation of purchases, inventory gets added until their expiry time; where cancellation time follows exponential distribution. Customers arrive according to a Poisson process and service time is exponentially distributed. On arrival if a customer finds the server busy, then he joins a buffer of varying size. If there is no inventory, the arriving customer first try to queue up in a finite waiting room of capacity K. Finding that at full, he joins a pool of infinite capacity with probability γ (0 < γ < 1); else it is lost to the system forever. We discuss two models based on ‘transfer’ of customers from the pool to the waiting room / buffer. In Model 1 when, at a service completion epoch the waiting room size drops to preassigned number L ? 1 (1 < L < K) or below, a customer is transferred from pool to waiting room with probability p (0 < p < 1) and positioned as the last among the waiting customers. If at a departure epoch the waiting room turns out to be empty and there is at least one customer in the pool, then the one ahead of all waiting in the pool gets transferred to the waiting room with probability one. We introduce a totally different transfer mechanism in Model 2: when at a service completion epoch, the server turns idle with at least one item in the inventory, the pooled customer is immediately taken for service. At the time of a cancellation if the server is idle with none, one or more customers in the waiting room, then the head of the pooled customer go to the buffer directly for service. Also we assume that no customer joins the system when there is no item in the inventory. Several system performance measures are obtained. A cost function is discussed for each model and some numerical illustrations are presented. Finally a comparison of the two models are made.     

Homology of braid groups,the Burau representation,and points on superelliptic curves over finite fields

The (reduced) Burau representation V _n of the braid group B _n is obtained from the action of B _n on the homology of an infinite cyclic cover of the disc with n punctures. In this paper, we calculate H _*(B _n ; V _n ). Our topological calculation has the following arithmetic interpretation (which also has different algebraic proofs): the expected number of points on a random superelliptic curve of a fixed genus over F _q is q.     

Galois theory and Lubin-Tate cochains on classifying spaces

We consider brave new cochain extensions F(BG ₊,R) → F(EG ₊,R), where R is either a Lubin-Tate spectrum E _n or the related 2-periodic Morava K-theory K _n , and G is a finite group. When R is an Eilenberg-Mac Lane spectrum, in some good cases such an extension is a G-Galois extension in the sense of John Rognes, but not always faithful. We prove that for E _n and K _n these extensions are always faithful in the K _n local category. However, for a cyclic p-group \(C_{p^r } \), the cochain extension \(F(BC_{p^r + } ,E_n ) \to F(EC_{p^r + } ,E_n )\) is not a Galois extension because it ramifies. As a consequence, it follows that the E _n -theory Eilenberg-Moore spectral sequence for G and BGdoes not always converge to its expected target.