Optimal strategy policy in batch arrival queue with server breakdowns and multiple vacations

This paper considers a like-queue production system in which server vacations and breakdowns are possible. The decision-maker can turn a single server on at any arrival epoch or off at any service completion. We model the system by an M^[x]/M/1 queueing system with N policy. The server can be turned off and takes a vacation with exponential random length whenever the system is empty. If the number of units waiting in the system at any vacation completion is less than N, the server will take another vacation. If the server returns from a vacation and finds at least N units in the system, he immediately starts to serve the waiting units. It is assumed that the server breaks down according to a Poisson process and the repair time has an exponential distribution. We derive the distribution of the system size through the probability generating function. We further study the steady-state behavior of the system size distribution at random (stationary) point of time as well as the queue size distribution at departure point of time. Other system characteristics are obtained by means of the grand process and the renewal process. Finally, the expected cost per unit time is considered to determine the optimal operating policy at a minimum cost. The sensitivity analysis is also presented through numerical experiments.     

Modified nodal cubic spline collocation for biharmonic equations

We formulate a modified nodal cubic spline collocation scheme for the solution of the biharmonic Dirichlet problem on the unit square. We prove existence and uniqueness of a solution of the scheme and show how the scheme can be solved on an N × N uniform partition of the square at a cost O(N ² log₂ N + mN ²) using fast Fourier transforms and m iterations of the preconditioned conjugate gradient method. We demonstrate numerically that m proportional to log₂ N guarantees the desired convergence rates. Numerical results indicate the fourth order accuracy of the approximations in the global maximum norm and the fourth order accuracy of the approximations to the first order partial derivatives at the partition nodes.      

Availability and failure frequency of a Gnedenko system

This paper considers anN-unit series system supported by a warm standby unit and a single repair facility. Suppose that the operating units and the standby unit have constant failure ratesa anda ₁, respectively. When the system is down, all the operable units have constant failure ratea ₂. The repair time of a failed unit has an arbitrary distribution. Using Takács' method and a Markov renewal process, we discuss the stochastic behavior of this system and obtain the explicit formulae of the system availability and failure frequency.Project supported by the National Natural Science Foundation of China.     

Single Supplier Scheduling for Multiple Deliveries

The problem of scheduling the production and delivery of a supplier to feed the production of F manufacturers is studied. The orders fulfilled by the supplier are delivered to the manufacturers in batches of the same size. The supplier's production line has to be set up whenever it switches from processing an order of one manufacturer to an order of another manufacturer. The objective is to minimize the total setup cost, subject to maintaining continuous production for all manufacturers. The problem is proved to be NP-hard. It is reduced to a single machine scheduling problem with deadlines and jobs belonging to F part types. An O(NlogF) algorithm, where N is the number of delivery batches, is presented to find a feasible schedule. A dynamic programming algorithm with O(N ^F /F ^F–2) running time is presented to find an optimal schedule. If F=2 and setup costs are unit, an O(N) time algorithm is derived.     

Approximations for the <Emphasis Type="Italic">M</Emphasis>/<Emphasis Type="Italic">GI</Emphasis>/<Emphasis Type="Italic">N</Emphasis>+<Emphasis Type="Italic">GI</Emphasis> type call center

In this paper, we propose approximations to compute the steady-state performance measures of the M/GI/N+GI queue receiving Poisson arrivals with N identical servers, and general service and abandonment-time distributions. The approximations are based on scaling a single server M/GI/1+GI queue. For problems involving deterministic and exponential abandon times distributions, we suggest a practical way to compute the waiting time distributions and their moments using the Laplace transform of the workload density function. Our first contribution is numerically computing the workload density function in the M/GI/1+GI queue when the abandon times follow general distributions different from the deterministic and exponential distributions. Then we compute the waiting time distributions and their moments. Next, we scale-up the M/GI/1+GI queue giving rise to our approximations to capture the behavior of the multi-server system. We conduct extensive numerical experiments to test the speed and performance of the approximations, which prove the accuracy of their predictions.      

An M/G/1 queue under hysteretic vacation policy with an early startup and un-reliable server

This paper considers the bi-level control of an M/G/1 queueing system, in which an un-reliable server operates N policy with a single vacation and an early startup. The server takes a vacation of random length when he finishes serving all customers in the system (i.e., the system is empty). Upon completion of the vacation, the server inspects the number of customers waiting in the queue. If the number of customers is greater than or equal to a predetermined threshold m, the server immediately performs a startup time; otherwise, he remains dormant in the system and waits until m or more customers accumulate in the queue. After the startup, if there are N or more customers waiting for service, the server immediately begins serving the waiting customers. Otherwise the server is stand-by in the system and waits until the accumulated number of customers reaches or exceeds N. Further, it is assumed that the server breaks down according to a Poisson process and his repair time has a general distribution. We obtain the probability generating function in the system through the decomposition property and then derive the system characteristics     

A mixed‐type Galerkin variational formulation and fast algorithms for variable‐coefficient fractional diffusion equations

We consider the variable‐coefficient fractional diffusion equations with two‐sided fractional derivative. By introducing an intermediate variable, we propose a mixed‐type Galerkin variational formulation and prove the existence and uniqueness of the variational solution over . On the basis of the formulation, we develop a mixed‐type finite element procedure on commonly used finite element spaces and derive the solvability of the finite element solution and the error bounds for the unknown and the intermediate variable. For the Toeplitz‐like linear system generated by discretization, we design a fast conjugate gradient normal residual method to reduce the storage from O(N²) to O(N) and the computing cost from O(N³) to O(NlogN). Numerical experiments are included to verify our theoretical findings. Copyright © 2017 John Wiley & Sons, Ltd.     

Optimal Spreading in an n Dimensional Rectilinear Grid

A disturbance spreads in a rectilinear n dimensional grid moving from each affected point to at most one neighbor in each unit of time. The question how many points can be affected in N units of time is answered to the two leading orders of N.     

Expected hitting and cover times of random walks on some special graphs

We give general bounds (and in some cases exact values) for the expected hitting and cover times of the simple random walk on some special undirected connected graphs using symmetry and properties of electrical networks. In particular we give easy proofs for an N–1H_N-1 lower bound and an N² upper bound for the cover time of symmetric graphs and for the fact that the cover time of the unit cube is Φ(NlogN). We giver a counterexample to a conjecture of Freidland about a general bound for hitting times. Using the electric approach, we provide some genral upper and lower bounds for the expected cover times in terms of the diameter of the graph. These bounds are tight in many instances, particularly when the graph is a tree. © 1994 John Wiley & Sons, Inc.     

On bulk-service MAP/PH L,N /1/N G-Queues with repeated attempts

We consider a retrial queue with a finite buffer of size N, with arrivals of ordinary units and of negative units (which cancel one ordinary unit), both assumed to be Markovian arrival processes. The service requirements are of phase type. In addition, a PH^L,N bulk service discipline is assumed. This means that the units are served in groups of size at least L, where 1≤ L≤ N. If at the completion of a service fewer than L units are present at the buffer, the server switches off and waits until the buffer length reaches the threshold L. Then it switches on and initiates service for such a group of units. On the contrary, if at the completion of a service L or more units are present at the buffer, all units enter service as a group. Units arriving when the buffer is full are not lost, but they join a group of unsatisfied units called “orbit”. Our interest is in the continuous-time Markov chain describing the state of the queue at arbitrary times, which constitutes a level dependent quasi-birth-and-death process. We start by analyzing a simplified version of our queueing model, which is amenable to numerical calculation and is based on spatially homogeneous quasi-birth-and-death processes. This leads to modified matrix-geometric formulas that reveal the basic qualitative properties of our algorithmic approach for computing performance measures. AMS Subject Classification: Primary 60K25 Secondary 68M20 90B22.     

Diophantine Approximations on Fractals

We exploit dynamical properties of diagonal actions to derive results in Diophantine approximations. In particular, we prove that the continued fraction expansion of almost any point on the middle third Cantor set (with respect to the natural measure) contains all finite patterns (hence is well approximable). Similarly, we show that for a variety of fractals in [0, 1]², possessing some symmetry, almost any point is not Dirichlet improvable (hence is well approximable) and has property C (after Cassels). We then settle by similar methods a conjecture of M. Boshernitzan saying that there are no irrational numbers x in the unit interval such that the continued fraction expansions of {nx mod 1}_{n ? \mathbb N}{\{nx\,{\rm mod}\,1\}_{n \in {\mathbb N}}} are uniformly eventually bounded.     

Spectral methods with sparse matrices

Summary Spectral methods employ global polynomials for approximation. Hence they give very accurate approximations for smooth solutions. Unfortunately, for Dirichlet problems the matrices involved are dense and have condition numbers growing asO(N ⁴) for polynomials of degree N in each variable. We propose a new spectral method for the Helmholtz equation with a symmetric and sparse matrix whose condition number grows only asO(N ²). Certain algebraic spectral multigrid methods can be efficiently used for solving the resulting system. Numerical results are presented which show that we have probably found the most effective solver for spectral systems.     

Large Closed Queueing Networks in Semi-Markov Environment and Their Application

The paper studies closed queueing networks containing a server station and k client stations. The server station is an infinite server queueing system, and client stations are single-server queueing systems with autonomous service, i.e. every client station serves customers (units) only at random instants generated by a strictly stationary and ergodic sequence of random variables. The total number of units in the network is N. The expected times between departures in client stations are (N μ _j )⁻¹. After a service completion in the server station, a unit is transmitted to the jth client station with probability p _j (j=1,2,…,k), and being processed in the jth client station, the unit returns to the server station. The network is assumed to be in a semi-Markov environment. A semi-Markov environment is defined by a finite or countable infinite Markov chain and by sequences of independent and identically distributed random variables. Then the routing probabilities p _j (j=1,2,…,k) and transmission rates (which are expressed via parameters of the network) depend on a Markov state of the environment. The paper studies the queue-length processes in client stations of this network and is aimed to the analysis of performance measures associated with this network. The questions risen in this paper have immediate relation to quality control of complex telecommunication networks, and the obtained results are expected to lead to the solutions to many practical problems of this area of research.      

A geometric process model for M/M/1 queueing system with a repairable service station

In this paper, we study a geometric process model for M/M/1 queueing system with a repairable service station. By introducing a supplementary variable, some queueing characteristics of the system and reliability indices of the service station are derived. Then a replacement policy N for the service station by which the service station will be replaced following the Nth failure is applied. An optimal replacement policy N¹ for minimizing the long-run average cost per unit time for the service station is then determined.     

Efficient Algorithms for Finding the Maximum Number of Disjoint Paths in Grids

In a rectangular grid, given two sets of nodes, (sources) and (sinks), of size each, the disjoint paths (DP) problem is to connect as many nodes in to the nodes in using a set of “disjoint” paths. (Both edge-disjoint and vertex-disjoint cases are considered in this paper.) Note that in this DP problem, a node in can be connected to any node in . Although in general the sizes of and do not have to be the same, algorithms presented in this paper can also find the maximum number of disjoint paths pairing nodes in and . We use the network flow approach to solve this DP problem. By exploiting all the properties of the network, such as planarity and regularity of a grid, integral flow, and unit capacity source/sink/flow, we can optimally compress the size of the working grid (to be defined) from O(N²) to O(N^1.5) and solve the problem in O(N^2.5) time for both the edge-disjoint and vertex-disjoint cases, an improvement over the straightforward approach which takes O(N³) time.     

Talbot quadratures and rational approximations

Many computational problems can be solved with the aid of contour integrals containing e ^z in the integrand: examples include inverse Laplace transforms, special functions, functions of matrices and operators, parabolic PDEs, and reaction-diffusion equations. One approach to the numerical quadrature of such integrals is to apply the trapezoid rule on a Hankel contour defined by a suitable change of variables. Optimal parameters for three classes of such contours have recently been derived: (a) parabolas, (b) hyperbolas, and (c) cotangent contours, following Talbot in 1979. The convergence rates for these optimized quadrature formulas are very fast: roughly O(3^-N ), where N is the number of sample points or function evaluations. On the other hand, convergence at a rate apparently about twice as fast, O(9.28903^-N ), can be achieved by using a different approach: best supremum-norm rational approximants to e ^z for z∈(–∞,0], following Cody, Meinardus and Varga in 1969. (All these rates are doubled in the case of self-adjoint operators or real integrands.) It is shown that the quadrature formulas can be interpreted as rational approximations and the rational approximations as quadrature formulas, and the strengths and weaknesses of the different approaches are discussed in the light of these connections. A MATLAB function is provided for computing Cody–Meinardus–Varga approximants by the method of Carathéodory–Fejér approximation. In memory of Germund Dahlquist (1925–2005).AMS subject classification (2000) 65D30, 41A20     

A δ-shock maintenance model for a deteriorating system

In this paper, a δ-shock maintenance model for a deteriorating system is studied. Assume that shocks arrive according to a renewal process, the interarrival time of shocks has a Weibull distribution or gamma distribution. Whenever an interarrival time of shocks is less than a threshold, the system fails. Assume further the system is deteriorating so that the successive threshold values are geometrically nondecreasing, and the consecutive repair times after failure form an increasing geometric process. A replacement policy N is adopted by which the system will be replaced by an identical new one at the time following the Nth failure. Then the long-run average cost per unit time is evaluated. Afterwards, an optimal policy N^* for minimizing the long-run average cost per unit time could be determined numerically.     

A fourth–order orthogonal spline collocation method for two-dimensional Helmholtz problems with interfaces

Orthogonal spline collocation is implemented for the numerical solution of two-dimensional Helmholtz problems with discontinuous coefficients in the unit square. A matrix decomposition algorithm is used to solve the collocation matrix system at a cost of O(N² log N) on an N × N partition of the unit square. The results of numerical experiments demonstrate the efficacy of this approach, exhibiting optimal global estimates in various norms and superconvergence phenomena for a broad spectrum of wave numbers.