Algorithms for computing waiting time distributions under different queue disciplines for the D-BMAP/PH/1

A queueing system characterized by the discrete batch Markovian arrival process (D-BMAP) and a probability of phase type distribution for the service time is one that arises frequently in the area of telecommunications. Under this arrival process and service time distribution we derive the waiting time distribution for three queue disciplines: first in first out (FIFO), last in first out (LIFO), and service in random order (SIRO). We also outline efficient algorithmic procedures for computing the waiting time distributions under each discipline. © 1997 John Wiley & Sons, Inc. Naval Research Logistics 44: 559–576, 1997     

Waiting time analysis for a queueing system with time‐limited service and exponential timer

We consider a single‐queue with exhaustive or gated time‐limited services and server vacations, in which the length of each service period at the queue is controlled by a timer, i.e., the server serves customers until the timer expires or the queue becomes empty, whichever occurs first, and then takes vacations. The customer whose service is interrupted due to the timer expiration may be attended according to nonpreemptive or preemptive service disciplines. For the M/G/1 exhaustive/gated time‐limited service queueing system with an exponential timer and four typical preemptive/nonpreemptive service disciplines, we derive the Laplace—Stieltjes transforms and the moment formulas for waiting times and sojourn times through a unified approach, and provide some new results for these time‐limited service disciplines. © John Wiley & Sons, Inc. Naval Research Logistics 48: 638–651, 2001.     

Bounds on parallel-processing of queues with multiple-phase jobs

Currently, both the hardware and software designs of many large computing systems aim at improved system performance through exploitation of parallelism in multiprocessor systems. In studying these systems, mathematical modelling and analysis constitute an important step towards providing design tools that can be used in building such systems. With this view the present paper describes a queueing model of a multiprocessor system operating in a job-shop environment in which arriving jobs consist of a random number of segments (sub-jobs). Two service disciplines are considered: one assumes that the sub-jobs of a given job are capable of parallel operation on different processors while the other assumes that the same sub-jobs must be operated in a strictly serial sequ'snce. The results (in particular, the mean number in the system and waiting time in queue) obtained for these two disciplines are shown to be bounds for more general job structures.     

Stochastic analysis of a single server retrial queue with general retrial times

Retrial queueing systems are widely used in teletraffic theory and computer and communication networks. Although there has been a rapid growth in the literature on retrial queueing systems, the research on retrial queues with nonexponential retrial times is very limited. This paper is concerned with the analytical treatment of an M/G/1 retrial queue with general retrial times. Our queueing model is different from most single server retrial queueing models in several respectives. First, customers who find the server busy are queued in the orbit in accordance with an FCFS (first‐come‐first‐served) discipline and only the customer at the head of the queue is allowed for access to the server. Besides, a retrial time begins (if applicable) only when the server completes a service rather upon a service attempt failure. We carry out an extensive analysis of the queue, including a necessary and sufficient condition for the system to be stable, the steady state distribution of the server state and the orbit length, the waiting time distribution, the busy period, and other related quantities. Finally, we study the joint distribution of the server state and the orbit length in non‐stationary regime. © 1999 John Wiley & Sons, Inc. Naval Research Logistics 46: 561–581, 1999     

Approximation for the departure process of a queue in a network

A simple renewal process is identified to approximate the complex departure process of a queue often found in queueing network models. The arrival process to the queue is the superposition or merging of several independent component-renewal processes that are approximations of departure processes from other queues and external arrival processes; there is a single server with exponential service times, and the waiting space is infinite. The departure process of this queue is of interest because it is the arrival process to other queues in the network. The approximation proposed is a hybrid; the mean and variance of the approximating departure intervals is a weighted average of those determined by basic methods in Whitt [41] with the weighting function empirically determined using simulation. Tandem queueing systems with superposition arrival processes and exponential service times are used to evaluate the approximation. The departure process of the first queue in the tandem is approximated by a renewal process, the tandem system is replaced by two independent queues, and the second queue is solved analytically. When compared to simulation estimates, the average absolute error in hybrid approximations of the expected number in the second queue is 6%, a significant improvement over 22–41% in the basic methods.     

Sojourn times in a two‐stage queueing network with blocking

The model considered in this paper involves a tandem queue consisting of a sequence of two waiting lines. The main feature of our model is blocking, i.e., as soon as the second waiting line reaches a certain upper limit, the first line is blocked. The input of units to the tandem queue is the MAP (Markovian arrival process), and service requirements are of phase type. Our objective is to study the sojourn time distribution under the first‐come‐first‐serve discipline by analyzing the sojourn time through times until absorption in appropriately defined quasi‐birth‐and‐death processes and continuous‐time Markov chains. © 2004 Wiley Periodicals, Inc. Naval Research Logistics, 2004     

Queues with stochastic service rates

The purpose of this paper is to explore an extension of the output discipline for the Poisson input, general output, single channel, first-come, first-served queueing system. The service time parameter, μ, is instead considered a random variable, M. In other words, the service time random variable, T, is to be conditioned by a parameter random variable, M. Therefore, if the distribution function of M is denoted by F_M(μ) and the known conditional service time distribution as B(t |_μ), then the unconditional service distribution is given by B(t) = Pr {T ≤ t}. = ∫_-∞^∞ B(t |_μ) dF_M(μ). Results are obtained that characterize queue size and waiting time using the imbedded Markov chain approach. Expressions are derived for the expected queue length and Laplace-Stieltjes transforms of the steady-state waiting time when conditional service times are exponential. More specific results are found for three special distributions of M: (1) uniform on [1.2]; (2) two-point; and (3) gamma.     

Estimation in single server queues

Moment and maximum likelihood estimates (m.l.e.'s) arc investigated for nonparametric and parametric models for a single server queue observed over a random time horizon, namely, up to the nth departure epoch. Also. m.l.e's of the mean interarrival time and mean service time in anM/M/1 queue observed over a fixed time-interval are studied Limit distributions of these estimates are obtained Without imposing steady state assumptions on the queue-size or waiting time processes.     

The single server queue in discrete time-numerical analysis III

This paper deals with the stationary analysis of the finite, single server queue in discrete time. The following stntionary distributions and other quantities of practical interest are investigated: (1) the joint density of the queue length and the residual service time, (2) the queue length distribution and its mean, (3) the distribution of the residual service time and its mean, (4) the distribution and the expected value of the number of customers lost per unit of time due to saturation of the waiting capacity, (5) the distribution and the mean of the waiting time, (6) the asymptotic distribution of the queue length following departures The latter distribution is particularly noteworthy, in view of the substantial difference which exists, in general, between the distributions of the queue lengths at arbitrary points of time and those immediately following departures.     

A note on sojourn times in M/G/1 queues with instantaneous,bernoulli feedback

Queueing systems which include the possibility for a customer to return to the same server for additional service are called queueing systems with feedback. Such systems occur in computer networks for example. In these systems a chosen customer will wait in the queue, be serviced and then, with probability p, return to wait again, be serviced again and continue this process until, with probability (1 – p) = q, it departs the system never to return. The time of waiting plus service time, the nth time the customer goes through, we will call his nth sojourn time. The (random) sum of these sojourn times we will call the total sojourn time (abbreviated, sojourn time when there is no confusion which sojourn time we are talking about). In this paper we study the total sojourn time in a queueing system with feedback. We give the details for M/G/1 queues in which the decision to feedback or not is a Bernoulli process. While the details of the computations can be more difficult, the structure of the sojourn time process is unchanged for the M/G/1 queue with a more general decision process as will be shown. We assume the reader is familiar with Disney, McNickle and Simon [1].     

随机环境中的M/MY/1排队系统

文献［４］讨论了随机环境中的Ｍ／Ｍ／１排队模型，本文提出和讨论随机环境中的Ｍ／Ｍｙ／１排队模型，在统计平衡条件下给出了队长和等待队长的平稳分布以及平均队长和平均等待队长，得到了等待时间和逗留时间分布以及平均等待时间和平均逗留时间。     

The queue G/M/m/N: Busy period and cycle,waiting time under reverse and random order service

The busy period, busy cycle, and the numbers of customers served and lost therein, of the G/M/m queue with balking is studied via the embedded Markov chain approach. It is shown that the expectations of the two discrete variables give the loss probability. For the special case G/M/1/N a closed expression in terms of contour integrals is obtained for the Laplace transform of these four variables. This yields as a byproduct the LIFO waiting time distribution for the G/M/m/N queue. The waiting time under random order service for this queue is also studied.     

A queueing system with vacations after N services

This article is devoted to the study of an M/G/1 queue with a particular vacation discipline. The server is due to take a vacation as soon as it has served exactly N customers since the end of the previous vacation. N may be either a constant or a random variable. If the system becomes empty before the server has served N customers, then it stays idle until the next customer arrival. Such a vacation discipline arises, for example, in production systems and in order picking in warehouses. We determine the joint transform of the length of a visit period and the number of customers in the system at the end of that period. We also derive the generating function of the number of customers at a random instant, and the Laplace–Stieltjes transform of the delay of a customer. © 2015 Wiley Periodicals, Inc. Naval Research Logistics 62: 646–658, 2015     

A queue with waiting time dependent service times

Sufficient conditions are developed for the ergodicity of a single server, first-come-first-serve queue with waiting time dependent service times.     

Computational analysis of MMAP[K]/PH[K]/1 queues with a mixed FCFS and LCFS service discipline

This paper studies a queueing system with a Markov arrival process with marked arrivals and PH‐distribution service times for each type of customer. Customers (regardless of their types) are served on a mixed first‐come‐first‐served (FCFS) and last‐come‐first‐served (LCFS) nonpreemptive basis. That is, when the queue length is N (a positive integer) or less, customers are served on an FCFS basis; otherwise, customers are served on an LCFS basis. The focus is on the stationary distribution of queue strings, busy periods, and waiting times of individual types of customers. A computational approach is developed for computing the stationary distribution of queue strings, the mean of busy period, and the means and variances of waiting times. The relationship between these performance measures and the threshold number N is analyzed in depth numerically. It is found that the variance of the virtual (actual) waiting time of an arbitrary customer can be reduced by increasing N. © 2000 John Wiley & Sons, Inc. Naval Research Logistics 47: 399–421, 2000     

Customer delays in M/M/c repair systems with spares

A service center to which customers bring failed items for repair is considered. The items are exchangeable in the sense that a customer is ready to take in return for the failed item he brought to the center any good item of the same kind. This exchangeability feature makes it possible for the service center to possess spares. The focus of the article is on customer delay in the system—the time that elapses since the arrival of a customer with a failed item and his departure with a good one—when repaired items are given to waiting customers on a FIFO basis. An algorithm is developed for the computation of the delay distribution when the item repair system operates as an M/M/c queue.     

Allocating capacity in parallel queues to improve their resilience to deliberate attack

We develop models that lend insight into how to design systems that enjoy economies of scale in their operating costs, when those systems will subsequently face disruptions from accidents, acts of nature, or an intentional attack from a well‐informed attacker. The systems are modeled as parallel M/M/1 queues, and the key question is how to allocate service capacity among the queues to make the system resilient to worst‐case disruptions. We formulate this problem as a three‐level sequential game of perfect information between a defender and a hypothetical attacker. The optimal allocation of service capacity to queues depends on the type of attack one is facing. We distinguish between deterministic incremental attacks, where some, but not all, of the capacity of each attacked queue is knocked out, and zero‐one random‐outcome (ZORO) attacks, where the outcome is random and either all capacity at an attacked queue is knocked out or none is. There are differences in the way one should design systems in the face of incremental or ZORO attacks. For incremental attacks it is best to concentrate capacity. For ZORO attacks the optimal allocation is more complex, typically, but not always, involving spreading the service capacity out somewhat among the servers. © 2011 Wiley Periodicals, Inc. Naval Research Logistics, 2011     

MPI并行程序中通信等待问题的诊断方法及其应用

随着并行规模的扩大,现有通信等待问题的诊断方法存在内存开销大、测量时间开销大等问题。通过对现有通信等待问题诊断方法的深入分析,同时考虑测量开销可控的实际需求,建立基于热点函数的通信等待问题诊断模型。基于上述模型,总结出一种更精简、更实用的通信等待问题诊断方法。将该诊断方法分别应用到二维LARED集成、LARED-S、LAP3D等大规模MPI并行程序的通信等待问题诊断过程,应用效果表明本诊断方法可精确定位导致通信等待问题的关键代码段,给出的优化方案及性能提升空间对于后续的程序改进具有参考价值,其中根据诊断结果优化后的LARED-S程序性能提升32%,通信等待时间减少44%。     

基于背景建模和前景建模的红外运动检测

为抑制了红外图像信噪比低、非静止背景等引起的虚警产生,将基于背景建模和前景建模运动检测(BM-FM)算法引入红外面目标检测中;为抑制因目标与背景对比度低引起的部分目标区域漏检,提出了基于空间邻域信息的前景建模方法(SNFM),利用前一帧图像在像素点邻域内的前景目标点为样本,用核密度估计进行前景建模.试验表明了基于该前景建模方法的BM-FM算法的有效性.     

Equilibrium customer strategies and social–profit maximization in the single‐server constant retrial queue

We consider the single‐server constant retrial queue with a Poisson arrival process and exponential service and retrial times. This system has not waiting space, so the customers that find the server busy are forced to abandon the system, but they can leave their contact details. Hence, after a service completion, the server seeks for a customer among those that have unsuccessfully applied for service but left their contact details, at a constant retrial rate. We assume that the arriving customers that find the server busy decide whether to leave their contact details or to balk based on a natural reward‐cost structure, which incorporates their desire for service as well as their unwillingness to wait. We examine the customers' behavior, and we identify the Nash equilibrium joining strategies. We also study the corresponding social and profit maximization problems. We consider separately the observable case where the customers get informed about the number of customers waiting for service and the unobservable case where they do not receive this information. Several extensions of the model are also discussed. © 2011 Wiley Periodicals, Inc. Naval Research Logistics, 2011