Strong Stability of Queues with Multiple Vacation of the Server

Abstract

The main purpose of this article is to use the strong stability method to approximate the characteristics of the M/G/1//N queue with server vacation by those of the classical M/G/1//N queue, when the rate of the vacations is sufficiently small. This last queue is simpler and more exploitable in practice. For this, we proof the stability conditions and next obtain quantitative stability estimates with an exact computation of constants. From these theoretical results, we can develop an algorithm in order to check the conditions of approximation. These results of approximation have a great practical and economic interest in reliability systems and maintenance optimization policy, when we consider elements with constant failure rate.     

Analysis of a finite MAP/G/1 queue with group services

The finite capacity queues, GI/PH/1/N and PH/G/1/N, in which customers are served in groups of varying sizes were recently introduced and studied in detail by the author. In this paper we consider a finite capacity queue in which arrivals are governed by a particular Markov renewal process, called a Markovian arrival process (MAP). With general service times and with the same type of service rule, we study this finite capacity queueing model in detail by obtaining explicit expressions for (a) the steady-state queue length densities at arrivals, at departures and at arbitrary time points, (b) the probability distributions of the busy period and the idle period of the server and (c) the Laplace-Stieltjes transform of the stationary waiting time distribution of an admitted customer at points of arrivals. Efficient algorithmic procedures for computing the steady-state queue length densities and other system performance measures when services are of phase type are discussed. An illustrative numerical example is presented.     

Nonadaptive algorithms for threshold group testing

Threshold group testing first proposed by Damaschke is a generalization of classic group testing. Specifically, a group test is positive (negative) if it contains at least u (at most l) positives, and if the number of positives is between l and u, the test outcome is arbitrary. Although sequential group testing algorithms have been proposed, it is unknown whether an efficient nonadaptive algorithm exists. In this paper, we give an affirmative answer to this problem by providing efficient nonadaptive algorithms for the threshold model. The key observation is that disjunct matrices, a standard tool for group testing designs, also work in this threshold model. This paper improves and extends previous results in three ways:1. The algorithms we propose work in one stage, which saves time for testing.2. The test complexity is lower than previous results, at least for the number of elements which need to be tested is sufficiently large.3. A limited number of erroneous test outcomes are allowed.     

Stationary distributions in a queueing system with vacation times and limited service

This paper deals with a modified M/G/1 queueing system with finite capacity and a walking server. Units waiting are served up to a limited number before the server takes a vacation time and later returns to the queue again. A computational method for the stationary queue length distribution is developed and illustrated with a numerical example. The model was motivated by similar channel access mechanisms in token-ring local area networks.     

Travel times in queueing networks and network sojourns

We first describe expected values of sojourn times for semi-stationary (or synchronous) networks. This includes sojourn times for units and sojourn times for the entire network. A typical sojourn time of a unit is the time it spends in a sector (set of nodes) while it travels through the network, and a typical network sojourn time is the busy period of a sector. Our results apply to a wide class of networks including Jackson networks with general service times, general Markov or regenerative networks, and networks with batch processing and concurrent movement of units. The results also shed more light on when Little's law for general systems, holds for expectations as well as for limiting averages. Next, we describe the expectation of a unit's travel time on a general route in a basic Markov network process (such as a Jackson process). Examples of travel times are the time it takes for a unit to travel from one sector to another, and the time between two successive entrances to a node by a unit. Finally, we characterize the distributions of the sojourn times at nodes on certain overtake-free routes and the travel times on such routes for Markov network processes.This research was supported in part by the Air Force Office of Scientific Research under contract 89-0407 and NSF grant DDM-9007532.     

Applications of bulk queues to group testing models with incomplete identification

A population of items is said to be “group-testable”, (i) if the items can be classified as “good” and “bad”, and (ii) if it is possible to carry out a simultaneous test on a batch of items with two possible outcomes: “Success” (indicating that all items in the batch are good) or “failure” (indicating a contaminated batch). In this paper, we assume that the items to be tested arrive at the group-testing centre according to a Poisson process and are served (i.e., group-tested) in batches by one server. The service time distribution is general but it depends on the batch size being tested. These assumptions give rise to the bulk queueing model M/G^(m,M)/1, where m and M(>m) are the decision variables where each batch size can be between m and M. We develop the generating function for the steady-state probabilities of the embedded Markov chain. We then consider a more realistic finite state version of the problem where the testing centre has a finite capacity and present an expected profit objective function. We compute the optimal values of the decision variables (m, M) that maximize the expected profit. For a special case of the problem, we determine the optimal decision explicitly in terms of the Lambert function.     

A model of dynamics of group structures of human institutions

Given is a review of the substantial theories of cognitivist's trend and also of static and dynamic models of group structures that are based on them. A model of human institutiosn is constructed that explains the origin of balanced structures. This model is realized by a system of locally interacting automatons which are connected by a system of relations and endowed with the ability to react.     

Group testing procedures with incomplete identification and unreliable testing results

We consider multistage group testing with incomplete identification and unreliability features. The objective is to find a cost‐efficient group testing policy to select a prespecified number of non‐defective items from some population in the presence of false‐positive and false‐negative test results, subject to reliability and other constraints. To confirm the status of tested groups, various sequential retesting procedures are suggested. We also extend the model to include the possibility of inconclusive test results. We derive all relevant cost functionals in analytically closed form. Numerical examples are also given. Copyright © 2006 John Wiley & Sons, Ltd.     

Overlaps help: Improved bounds for group testing with interval queries

Given a finite ordered set of items and an unknown distinguished subset P of up to p positive elements, identify the items in P by asking the least number of queries of the type ‘‘does the subset Q intersect P?”, where Q is a subset of consecutive elements of {1,2,…,n}. This problem arises, e.g., in computational biology, in a particular method for determining splice sites in genes. We consider time-efficient algorithms where queries are arranged in a fixed number s of stages: In each stage, queries are performed in parallel. In a recent bioinformatics paper, we proved optimality (subject to lower-order terms) with respect to the number of queries, of some strategies for the special cases p=1 or s=2. Exploiting new ideas, we are now able to provide improved lower bounds for any p?2 and s?3 and improved upper bounds for larger s. Most notably, our new bounds converge as s grows. Our new query scheme uses overlapping query intervals within a stage, which is effective for large enough s. This contrasts with our previous results for s?2 where optimal strategies were implemented by disjoint queries. The main open problem is whether overlaps help already in the case of small s?3. Anyway, the remaining gaps between the current upper and lower bounds for any fixed s?3 amount to small constant factors in the main term. The paper ends with a discussion of practical implications in the case that the positive elements are well separated.     

A queueing model of a production system with two machines,one operator and priorities

This paper studies a priority queueing model of a production system in which one operator serves two types of units with overlapping service times. The two types of units arrive in independent Poisson processes. There are two machines in the system. Units of type 1 receive two consecutive types of services at machine #1: the handwork performed by the operator and the automatic machining without the operator. Units of type 2 receive only the handwork performed by the operator at machine #2. The operator attends the two machines according to a strict-priority discipline which always gives units of type 2 higher priority than units of type 1. At each machine the handwork times have a general distribution, and at machine #1 the machining times have an exponential distribution. The Laplace-Stieltjes transform of the queue-size distributions and the waiting time distributions for a stationary process are obtained.     

A queueing system with random server capacity and multiple control

The authors study queueing, input and output processes in a queueing system with bulk service and state dependent service delay. The input flow of customers, modulated by a semi-Markov process, is served by a single server that takes batches of a certain fixed size if available or waits until the queue accumulates enough customers for service. In the latter case, the batch taken for service is of random size dependent on the state of the system, while service duration depends both on the state of the system and on the batch size taken. The authors establish a necessary and sufficient condition for equilibrium of the system and obtain the following results: Explicit formulas for steady state distribution of the queueing process, intensity of the input and output processes, and mean values of idle and busy periods. They employ theory of semi-regenerative processes and illustrate the results by a number of examples. In one of them an optimization problem is discussed.     

Kolmogorov–Smirnov‐type testing for the partial homogeneity of Markov processes—with application to credit risk

In banking, the default behaviour of the counterpart is not only of interest for the pricing of transactions under credit risk but also for the assessment of a portfolio credit risk. We develop a test against the hypothesis that default intensities are chronologically constant within a group of similar counterparts, e.g. a rating class. The Kolmogorov–Smirnov‐type test builds up on the asymptotic normality of counting processes in event history analysis. The right censoring accommodates for Markov processes with more than one no‐absorbing state. A simulation study and two examples of rating systems demonstrate that partial homogeneity can be assumed, however occasionally, certain migrations must be modelled and estimated inhomogeneously. Copyright © 2007 John Wiley & Sons, Ltd.     

A comprehensive probabilistic analysis of approximate SIR-type epidemiological models via full randomized discrete-time Markov chain formulation with applications

This paper provides a comprehensive probabilistic analysis of a full randomization of approximate SIR-type epidemiological models based on discrete-time Markov chain formulation. The randomization is performed by assuming that all input data (initial conditions, the contagion, and recovering rates involved in the transition matrix) are random variables instead of deterministic constants. In the first part of the paper, we determine explicit expressions for the so called first probability density function of each subpopulation identified as the corresponding states of the Markov chain (susceptible, infected, and recovered) in terms of the probability density function of each input random variable. Afterwards, we obtain the probability density functions of the times until a given proportion of the population remains susceptible, infected, and recovered, respectively. The theoretical analysis is completed by computing explicit expressions of important randomized epidemiological quantities, namely, the basic reproduction number, the effective reproduction number, and the herd immunity threshold. The study is conducted under very general assumptions and taking extensive advantage of the random variable transformation technique. The second part of the paper is devoted to apply our theoretical findings to describe the dynamics of the pandemic influenza in Egypt using simulated data excerpted from the literature. The simulations are complemented with valuable information, which is seldom displayed in epidemiological models. In spite of the nonlinear mathematical nature of SIR epidemiological model, our results show a strong agreement with the approximation via an appropriate randomized Markov chain. A justification in this regard is discussed.     

具有中途准人机制和多重休假的离散时间GI/Geom(a,b)/1/N早到排队系统

运用补充变量方法和嵌入Markov链方法讨论了一个具有批量服务中途准入机制的离散时间多重休假排队系统.利用一种有效的数值迭代算法获得了系统中三种时刻的队长分布.进一步,使用不同时刻的队长分布,通过数值化方法研究了系统参数对阻塞概率,批量服务中途准入概率,顾客在缓冲空间中平均等待时间等几类重要性能指标的影响.     

Statistical simulation of one type of pairs of random variables with the use of fictitious jumps

Statistical simulation based on the sampling technique for a pair of random variables (T,

Open image in new window

), where T ∈ [0, +∞) and

Open image in new window

∈ ? ^d (d ≥ 1) is considered. The simultaneous distribution of the pair is specified in the form that is common for analogous problems in various fields. It has the form

Open image in new window

, where f is a function and m is a measure. The first variable T is the well-known random waiting time. A simulation method for the pair (T,

Open image in new window

) is constructed using a realization of an auxiliary Markov sequence of trial pairs. Applications of this method in particle transport theory and in kinetics of rarefied gases are discussed.

     

两参数指数分布产品全样本场合下步进应力加速寿命试验损伤失效率模型下的统计分析

本文给出了两参数指数分布产品全样本场合下步进应力加速寿命试验损伤失效率模型下参数的极大似然估计和拟矩估计,并通过Monte-Carlo模拟说明本文方法的可行性.     

Bulk input queues with hysteretic control

This paper deals with a bulk input-batch service queueing system and (r,N)-hysteretic control, i.e., under N-policy and r-quorum discipline. The model also includes state dependent service. The goal of such global control is to reduce the waste of server capacity (r-quorum), an unwanted number of switchovers between idle and busy modes (N-policy), and the queue length (by means of variable service rates). The analysis of the system is based on first excess level technique developed by the second author. This approach enables the authors to obtain major characteristics for the queueing process in a closed analytical form. This revised version was published online in June 2006 with corrections to the Cover Date.     

Analysis of GI<Superscript><Emphasis Type="Italic">X</Emphasis></Superscript>/<Emphasis Type="Italic">M</Emphasis>(<Emphasis Type="Italic">n</Emphasis>)//<Emphasis Type="Italic">N</Emphasis> systems with stochastic customer acceptance policy

We investigate GI ^X /M(n)//N systems with stochastic customer acceptance policy, function of the customer batch size and the number of customers in the system at its arrival. We address the time-dependent and long-run analysis of the number of customers in the system at prearrivals and postarrivals of batches and seen by customers at their arrival to the system, as well as customer blocking probabilities. These results are then used to derive the continuous-time long-run distribution of the number of customers in the system. Our analysis combines Markov chain embedding with uniformization and uses stochastic ordering as a way to bound the errors of the computed performance measures.