离散时间优先队列的尾部渐近性分析

本文研究在离散情形下,两类不同优先权的顾客进入服务系统的情况.稳态概率可以用矩阵形式表示出来.用矩阵分析法,联合稳态概率在一定条件下几何衰减.     

离散时间优先队列的尾部渐近性分析（英文）

本文研究在离散情形下,两类不同优先权的顾客进入服务系统的情况.稳态概率可以用矩阵形式表示出来.用矩阵分析法,联合稳态概率在一定条件下几何衰减.     

Optimal Decisions in a Time Priority Queue

We show how the position of a limit order (LO) in the queue influences the decision of whether to cancel the order or let it rest. Using ultra-high-frequency data from the Nasdaq exchange, we perform empirical analysis on various LO book events and propose novel ways for modelling some of these events, including cancellation of LOs in various positions and size of market orders. Based on our empirical findings, we develop a queuing model that captures stylized facts on the data. This model includes a distinct feature which allows for a potentially random effect due to the agent’s impulse control. We apply the queuing model in an algorithmic trading setting by considering an agent maximizing her expected utility through placing and cancelling of LOs. The agent’s optimal strategy is presented after calibrating the model to real data. A simulation study shows that for the same level of standard deviation of terminal wealth, the optimal strategy has a 2.5% higher mean compared to a strategy which ignores the effect of position, or an 8.8% lower standard deviation for the same level of mean. This extra gain stems from posting an LO during adverse conditions and obtaining a good queue position before conditions become favourable.     

排队系统平稳等待时间的性质

讨论了M/G/1排队系统平稳等待时间的随机序关系及利用Mathematica 4.0软件探讨了爱尔朗排队系统Er/M/1（r≤6）的平稳等待时间的分布。     

Discrete-Time Geo X /G/1 Queue with Preemptive Repeat Different Priority

This paper considers a discrete-time Geo ^X /G/1 queue accepting two classes of messages with preemptive repeat different priority. Service times of messages of each priority class are i.i.d. according to a general discrete distribution function that may differ between two classes. The completion time and the stability condition for our system are investigated. By using the supplementary variable method and the generating function technique, we derive the joint system contents distributions at various observation instants and also compute the probability distribution for the unfinished work.     

Mean Waiting Time Approximations in the G/G/1 Queue

It is known that correlations in an arrival stream offered to a single-server queue profoundly affect mean waiting times as compared to a corresponding renewal stream offered to the same server. Nonetheless, this paper uses appropriately constructed GI/G/1 models to create viable approximations for queues with correlated arrivals. The constructed renewal arrival process, called PMRS (Peakedness Matched Renewal Stream), preserves the peakedness of the original stream and its arrival rate; furthermore, the squared coefficient of variation of the constructed PMRS equals the index of dispersion of the original stream. Accordingly, the GI/G/1 approximation is termed PMRQ (Peakedness Matched Renewal Queue). To test the efficacy of the PMRQ approximation, we employed a simple variant of the TES⁺ process as the autocorrelated arrival stream, and simulated the corresponding TES ⁺/G/1 queue for several service distributions and traffic intensities. Extensive experimentation showed that the proposed PMRQ approximations produced mean waiting times that compared favorably with simulation results of the original systems. Markov-modulated Poisson process (MMPP) is also discussed as a special case.     

Waiting Time Asymptotics in the Single Server Queue with Service in Random Order

We consider the single server queue with service in random order. For a large class of heavy-tailed service time distributions, we determine the asymptotic behavior of the waiting time distribution. For the special case of Poisson arrivals and regularly varying service time distribution with index ?ν, it is shown that the waiting time distribution is also regularly varying, with index 1?ν, and the pre-factor is determined explicitly. Another contribution of the paper is the heavy-traffic analysis of the waiting time distribution in the M/G/1 case. We consider not only the case of finite service time variance, but also the case of regularly varying service time distribution with infinite variance.     

Analytical Distribution of Waiting Time in the M/{iD}/1 Queue

We give an analytical formula for the steady-state distribution of queue-wait in the M/G/1 queue, where the service time for each customer is a positive integer multiple of a constant D > 0. We call this an M/{iD}/1 queue. We give numerical algorithms to calculate the distribution. In addition, in the case that the service distribution is sparse, we give revised algorithms that can compute the distribution more quickly.AMS subject classification: 60K25, 90B22     

批到达离散时间轮询系统中顾客等待时间及队长

本对批到达离散时间轮询系统进行研究,在门限服务原则下,推出了原客等待时间和轮询周期的概率母函数,利用Markov链理论,得出了队列队长均值。     

Distributions of the Numbers of Failures and Successes in a Waiting Time Problem

Abstract. In this article we consider infinite sequences of Bernoulli trials and study the exact and asymptotic distribution of the number of failures and the number of successes observed before the r-th appearance of a pair of successes separated by a pre-specified number of failures. Several formulae are provided for the probability mass function, probability generating function and moments of the distribution along with some asymptotic results and a Poisson limit theorem. A number of interesting applications in various areas of applied science are also discussed.     

Queue Length Distribution in a FIFO Single-Server Queue with Multiple Arrival Streams Having Different Service Time Distributions

This paper considers the queue length distribution in a class of FIFO single-server queues with (possibly correlated) multiple arrival streams, where the service time distribution of customers may be different for different streams. It is widely recognized that the queue length distribution in a FIFO queue with multiple non-Poissonian arrival streams having different service time distributions is very hard to analyze, since we have to keep track of the complete order of customers in the queue to describe the queue length dynamics. In this paper, we provide an alternative way to solve the problem for a class of such queues, where arrival streams are governed by a finite-state Markov chain. We characterize the joint probability generating function of the stationary queue length distribution, by considering the joint distribution of the number of customers arriving from each stream during the stationary attained waiting time. Further we provide recursion formulas to compute the stationary joint queue length distribution and the stationary distribution representing from which stream each customer in the queue arrived.     

Refining Cosmetatos' Approximation for the Mean Waiting Time in the M/D/s Queue

This paper deals with refining Cosmetatos's approximation for the mean waiting time in an M/D/s queue. Although his approximation performs quite well in heavy traffic, it overestimates the true value when the number of servers is large or the traffic is light. We first focus on a normalized quantity that is a ratio of the mean waiting times for the M/D/s and M/M/s queues. Using some asymptotic properties of the quantity, we modify Cosmetatos's approximation to obtain better accuracy both for large s and in light traffic. To see the quality of our approximation, we compare it with the exact value and some previous approximations. Extensive numerical tests indicate that the relative percentage error is less than 1% for almost all cases with s ≤ 20 and at most 5% for other cases.     

The Virtual Waiting Time of the M/G/1 Queue with Impatient Customers

The M/G/1 queue with impatient customers is studied. The complete formula of the limiting distribution of the virtual waiting time is derived explicitly. The expected busy period of the queue is also obtained by using a martingale argument.     

Waiting Time Distributions Associated with Runs of Fixed Length in Two-State Markov Chains

In the present article a general technique is developed for the evaluation of the exact distribution in a wide class of waiting time problems. As an application the waiting time for the r-th appearance of success runs of specified length in a sequence of outcomes evolving from a first order two-state Markov chain is systematically investigated and asymptotic results are established. Several extensions and generalisations are also discussed.     

Workload and Waiting Time Analyses of MAP/G/1 Queue under D-policy

We study the workload (unfinished work) and the waiting time of the queueing system with MAP arrivals under D-policy. The D-policy stipulates that the idle server begin to serve the customers only when the sum of the service times of all waiting customers exceeds some fixed threshold D. We first set up the system equations for workload and obtain the steady-state distributions of workloads at an arbitrary idle and busy points of time. We then proceed to obtain the waiting time distribution of an arbitrary customer based on the workload results. The M/G/1/D-policy queue will be investigated as a special case.     

部分服务台休假的M/M/c排队的等待时间

我们证明了Erlang分布的若干有趣性质，使用这些性质，给出部分服务台休假的排队系统中等待时间分布的一个简洁而直观的表达式．     

Priority Queue Sorting and Labeled Trees

We construct a bijection between labeled trees and allowable pairs of permutations sorted by a priority queue. These are also the pairs of permutations that avoid the pattern pairs (12, 21) and (321, 132). Our bijection has the additional property that it maps leaves in the tree to descents in the output permutation in the allowable pair and, more generally, preserves the edge-deletion distribution of the tree.     

A Two Priority Queue with Crossover Feedback

This paper considers the delay distributions in a two-class non-preemptive priority queue with crossover feedback. Specifically, there are two priority classes, and the Poisson arrival process for each class can be subdivided into two groups: one group which only requires service at the priority level to which it arrives, and another group which requires subsequent service after it feeds back to the other queue. Our main result is the determination of explicit expressions for the distribution of delay until final service commences for each the four types of customers.     

Transient and Stationary Distributions for the GI/G/k Queue with Lebesgue-Dominated Inter-Arrival Time Distribution

In this paper, the multi-server queue with general service time distribution and Lebesgue-dominated iid inter-arival times is analyzed. This is done by introducing auxiliary variables for the remaining service times and then examining the embedded Markov chain at arrival instants. The concept of piecewise-deterministic Markov processes is applied to model the inter-arrival behaviour. It turns out that the transition probability kernel of the embedded Markov chain at arrival instants has the form of a lower Hessenberg matrix and hence admits an operator–geometric stationary distribution. Thus it is shown that matrix–analytical methods can be extended to provide a modeling tool even for the general multi-server queue.     

具有等待者的Kornai-Weibul排队模型的修正与分析

这篇文章首先明确地指出，具有等待的买者的Ｋｏｒｎａｉ－Ｗｅｉｂｕｌ排队模型与没有等待者的Ｋｏｒｎａｉ－Ｗｅｉｂｕｌ排队模型具有相同的纰漏．其次，本文在较自然的条件下严格地证明了修正后的模型存在“正常状态”．研究Ｋｏｒｎａｉ－Ｗｅｉｂｕｌ排队模型理论能够深刻地揭示计划经济的弊端．