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.     

A robust queueing network analyzer based on indices of dispersion

We develop a robust queueing network analyzer algorithm to approximate the steady-state performance of a single-class open queueing network of single-server queues with Markovian routing. The algorithm allows nonrenewal external arrival processes, general service-time distributions and customer feedback. The algorithm is based on a decomposition approximation, where each flow is partially characterized by its rate and a continuous function that measures the stochastic variability over time. This function is a scaled version of the variance-time curve, called the index of dispersion for counts (IDC). The required IDC functions for the external arrival processes can be calculated from the model primitives or estimated from data. Approximations for the IDC functions of the internal flows are calculated by solving a set of linear equations. The theoretical basis is provided by heavy-traffic limits for the flows established in our previous papers. A robust queueing technique is used to generate approximations of the mean steady-state performance at each queue from the IDC of the total arrival flow and the service specification at that queue. The algorithm's effectiveness is supported by extensive simulation studies.     

Workload distribution of discrete‐time parallel queues with two servers

We study discrete‐time, parallel queues with two identical servers. Customers arrive randomly at the system and join the queue with the shortest workload that is defined as the total service time required for the server to complete all the customers in the queue. The arrivals are assumed to follow a geometric distribution and the service times are assumed to have a general distribution. It is a no‐jockeying queue. The two‐dimensional state space is truncated into a banded array. The resulting modified queue is studied using the method of probability generating function (pgf) The workload distribution in steady state is obtained in form of pgf. A special case where the service time is a deterministic constant is further investigated. Numerical examples are illustrated. © 2000 John Wiley & Sons, Inc. Naval Research Logistics 47: 440–454, 2000     

Markov chain analyses of multiprogrammed computer systems

Most operating systems for large computing facilities involve service disciplines which base, to some extent, the sequencing of object program executions on the amount of running time they require. It is the object of this paper to study mathematical models of such service disciplines applicable to both batch and time-shared processing systems. In particular, Markov queueing models are defined and analyzed for round-robin and foreground-background service disciplines. With the round-robin discipline, the service facility processes each program or job for a maximum of q seconds; if the program's service is completed during this quantum, it leaves the system, otherwise it returns to the end of the waiting line to await another quantum of service. With the foreground-background discipline each new arrival joins the end of the foreground queue and awaits a single quantum of service. If it requires more it is subsequently placed at the end of the background queue which is allocated service only when the foreground queue is empty. The analysis focuses on the efficiency of the above systems by assuming a swap or set-up time (overhead cost) associated with the switching of programs on and off the processor. The analysis leads to generating functions for the equilibrium queue length probabilities, the moments of this latter distribution, and measures of mean waiting times. The paper concludes with a discussion of the results along with several examples.     

The effect of prior assumptions on the expected cost of m/m/1 queueing systems with unknown arrival rate

In this study we deal with the determination of optimal service rate in an M/M/1 queue. The arrival rate is unknown and assumed to be a random variable with a known distribution function. Holding and operating costs are considered and service rate is determined to minimize total expected discounted costs for infinite horizon. The effects of the arrival rate's distribution properties on the characteristics of the system are examined.     

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     

Controlling rates in a double queue

A double-ended queue with a Poisson arrival pattern is examined in a situation where the rates depend (in a restricted sense) on both the time and the state of the system. Under some circumstances, the rates can be controlled. This article studies the distribution of the difference in queue sizes for each member of a large class of control strategies and introduces the problem of determining the optimal times at which the control should be in effect in order to maximize certain objective functions.     

改进的累量域波达方向矩阵法

构造了一种可以进行高分辨二维波达方向估计的累量域波达方向矩阵。利用该矩阵的特征值和特征向量 ,就可以求出信号源的方位角和俯仰角。同其它的波达方向矩阵法相比 ,放宽了对阵列结构的要求 ,提高了阵列孔径的利用率。同时 ,由于采用了累量来构造波达方向矩阵 ,因此新方法具有对高斯噪声的自然盲性。     

On queues with dependent interarrival and service times

AnM/G/1 queueing system is studied in which the service time required by a customer is dependent on the interarrival time between his arrival and that of his predecessor Assuming the two variables are “associated,” we prove that the expected delay in this system is less than or equal to than of a conventional M/G/1 queue This conclusion has been verified via simulation by Mitchell and Paulson [9] for a special class of dependent M/M/1 queue. Their model is a special case of the one we consider here. We also study another modified GI/G/1 queue. where the arrival process and/or the service process are individually “associated”.     

On a single-server queue with state-dependent service

This paper discusses a class of queueing models in which the service time of a customer al a single server facility is dependent on the queue size at the onset of its service. The Laplace transform for the wait in queue distribution is derived and the utilization of the server is given when the arrival is a homogeneous Poisson process.     

基于MVEKF的单站无源定位跟踪方法研究

单站无源定位是电子战中的一项重要技术。采用基于到达方向(DOA)和到达时间差(TOA)测量信息,可以实现固定观测站对运动辐射源的无源定位和跟踪。讨论了扩展卡尔曼滤波(EKF)及其改进形式修正协方差的扩展卡尔曼滤波(MVEKF)2种算法的原理,指出了应用场合和适用条件,并运用EKF和MVEKF对无源定位进行滤波估计。通过仿真,说明了2种算法的有效性,并验证了MVEKF对定位性能的改善。     

Optimal admission pricing policies for M/Ek/1 queues

This paper extends the Low-Lippman M/M/1 model to the case of Gamma service times. Specifically, we have a queue in which arrivals are Poisson, service time is Gamma-distributed, and the arrival rate to the system is subject to setting an admission fee p. The arrival rate λ(p) is non-increasing in p. We prove that the optimal admission fee p^* is a non-decreasing function of the customer work load on the server. The proof is for an infinite capacity queue and holds for the infinite horizon continuous time Markov decision process. In the special case of exponential service time, we extend the Low-Lippman model to include a state-dependent service rate and service cost structure (for finite or infinite time horizon and queue capacity). Relatively recent dynamic programming techniques are employed throughout the paper. Due to the large class of functions represented by the Gamma family, the extension is of interest and utility.     

Level product form QSF processes and an analysis of queues with Coxian interarrival distribution

In this article, we study a class of Quasi‐Skipfree (QSF) processes where the transition rate submatrices in the skipfree direction have a column times row structure. Under homogeneity and irreducibility assumptions we show that the stationary distributions of these processes have a product form as a function of the level. For an application, we will discuss the ‐queue that can be modeled as a QSF process on a two‐dimensional state space. In addition, we study the properties of the stationary distribution and derive monotonicity of the mean number of the customers in the queue, their mean sojourn time and the variance as a function of for fixed mean arrival rate. © 2016 Wiley Periodicals, Inc. Naval Research Logisticsxs 66:57–72, 2019     

Analysis of a finite‐buffer bulk‐service queue with discrete‐Markovian arrival process: D‐MAP/Ga,b/1/N

Discrete‐time queues with D‐MAP arrival process are more useful in modeling and performance analysis of telecommunication networks based on the ATM environment. This paper analyzes a finite‐buffer discrete‐time queue with general bulk‐service rule, wherein the arrival process is D‐MAP and service times are arbitrarily and independently distributed. The distributions of buffer contents at various epochs (departure, random, and prearrival) have been obtained using imbedded Markov chain and supplementary variable methods. Finally, some performance measures such as loss probability and average delay are discussed. Numerical results are also presented in some cases. © 2003 Wiley Periodicals, Inc. Naval Research Logistics 50: 345–363, 2003.     

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     

A finite capacity GI/PH/1 queue with group services

We consider a finite-capacity single-server queue in which arrivals occur one at a time, according to a renewal process. The successive service times are mutually independent and have a common phase-type distribution. The customers are served in groups of size at least L, a preassigned threshold value. Explicit analytic expressions for the steady-state queue-length densities at arrivals and at arbitrary time points, and the throughput of the system are obtained. The Laplace-Stieltjes transform of the stationary waiting-time distribution of an admitted customer at points of arrivals is computed. It is shown to be of phase type when the arrival process is also of phase type. Efficient algorithmic procedures for the steady-state analysis of the model are presented. These procedures are used in arriving at an optimal value for L that minimizes the mean waiting time of an admitted customer. A conjecture on the nature of the mean waiting time is proposed.     

State-dependent gap acceptance

This paper considers a traffic problem in which vehicles queue up according to a Poisson process on a single-lane entrance ramp prior to merging into a major stream of vehicular traffic. In order to then prevent the ramp queue from becoming too large, a model is proposed which considers a lowering of the critical gap as the ramp queue size increases. With the critical gap assumed to be a nonincreasing function of the number of vehicles on the ramp at instances that correspond to departure times of lead vehicles from the ramp queue, the resultant model is an M/G/1 queue with state-dependent service times. Some general results are obtained for this model and a specific case discussed in moderate detail.     

Arrival and departure state distributions in the general bulk‐service queue

In this paper, we give an explicit relation between steady‐state probability distributions of the buffer occupancy at customer entrance and departure epochs, for the classical single‐server system G/G^[N]/1 with batch services and for the finite capacity case. The method relies on level‐crossing arguments. For the particular case of Poisson input, we also express the loss probability in terms of state probabilities at departure epochs, yielding probabilities observed by arriving customers. This work provides the “bulk queue” version of a result established by Burke, who stated the equality between probabilities at arrival and departure epochs for systems with “unit jumps.” © 1999 John Wiley & Sons, Inc. Naval Research Logistics 46: 107–118, 1999     

Scheduling policies for an antiterrorist surveillance system

This article concerns scheduling policies in a surveillance system aimed at detecting a terrorist attack in time. Terrorist suspects arriving at a public area are subject to continuous monitoring, while a surveillance team takes their biometric signatures and compares them with records stored in a terrorist database. Because the surveillance team can screen only one terrorist suspect at a time, the team faces a dynamic scheduling problem among the suspects. We build a model consisting of an M/G/1 queue with two types of customers—red and white—to study this problem. Both types of customers are impatient but the reneging time distributions are different. The server only receives a reward by serving a red customer and can use the time a customer has spent in the queue to deduce its likely type. In a few special cases, a simple service rule—such as first‐come‐first‐serve—is optimal. We explain why the problem is in general difficult and we develop a heuristic policy motivated by the fact that terrorist attacks tend to be rare events. © 2009 Wiley Periodicals, Inc. Naval Research Logistics, 2009     

运动模糊图像的运动模糊方向鉴别

曝光瞬间造成图像模糊的运动通常作为直线运动近似处理,若能找出模糊图像的运动模糊方向,并将之旋转到水平轴,则二维问题可简化为一维来处理,大大简化由模糊图像估计出运动模糊点扩散函数以及图像恢复的过程,并为图像恢复的并行计算创造有利条件。由于运动模糊降低了运动方向上图像的高频成分,沿着运动方向实施高通滤波(方向微分),可保证微分图像灰度值(绝对值)之和最小。基于此,本文利用双线性插值的方法,固定并适当选取方向微分的微元大小,构造出3×3方向微分乘子,得到了高效高精度的自动鉴别运动模糊方向的新方法,并通过数值实验进行了验证。