服务率可变的批服务排队网络

大部分排队网络的研究结果是在服务率不变的条件下给出的。本文分析了两类成批服务的排队网络。并在服务率依赖于批服务大小的条件下，利用各节点的准可逆性，给出了不带信号和带消极信号的两类排队网络的乘积形式稳态解．并利用不动点原理，证明了交通方程解的存在性．并给出求法。     

一个具有随机丢弃分组机制且分组成批到达的GI~X/M/1/N排队系统

利用排队论中输入流稀疏化的方法,在标准的GIX/M/1/N排队系统中嵌入网络交换设备随机丢弃分组的机制,建立了一个具有随机丢弃分组机制的扩充的GIX/M/1/N排队系统,并讨论了该排队系统的分组丢失率、系统利用率、队列长度的均值/方差、平均等待时间等性能评价指标.     

多服务台排队系统下提高顾客等待满意度的两类排队管理策略北大核心CSCD

文章在周文慧,等(2014)研究的基础上提出了等待因子t_r,得出了在排队系统M/M/C(C≥2)中顾客处于第n位时到接受服务的等待时间,用全概率公式得到的顾客在系统中的等待时间t的概率密度函数,进而建立了在M/M/C(C≥2)排队系统下提高顾客等待满意度的两类排队管理策略的优化模型.并进一步将两类排队管理策略推广到了M/M/C(C≥2)排队系统,给银行、超市等服务类企业提供了如何选择两类排队管理策略的科学依据.     

多类顾客共享排队系统的信息理论

多类顾客的共享排队系统是排队论中一个既重要又困难的研究方向,它在计算机网络、生产制造系统与交通网络等领域中有着许多重要的实际应用.近年来,国外学者对多类顾客的共享排队系统已经开展了一些关键性的研究工作,给出了稳态联合队长的母函数,由此可以得到稳态联合队长的一阶矩和二阶矩.然而,由这个母函数反演来提供多类顾客共享排队系统的稳态联合队长的直接表达式却是一个多年来的困难问题.基于此,本文利用信息论中的最大熵原理,提供了一个高精度的近似表达式,其中这个近似表达式与它的精确表达式能够保证前三阶矩是相同的.另一方面,针对这个近似表达式,本文实现了它的有效数值计算,并通过数值算例分析了这个近似表达式中的重要因子是如何依赖于系统的原始参数.因此这个近似表达式对于推进多类顾客共享排队系统的实际应用具有重要的理论意义,同时本文的方法与结果不仅为研究多类顾客的共享排队系统提供了一条新的重要途径,而且为如何将信息理论应用于排队系统、排队网络以及更一般的随机模型研究提供了理论依据与技术支撑.     

多服务台排队系统下提高顾客等待满意度的两类排队管理策略

文章在周文慧,等(2014)研究的基础上提出了等待因子t_r,得出了在排队系统M/M/C(C≥2)中顾客处于第n位时到接受服务的等待时间,用全概率公式得到的顾客在系统中的等待时间t的概率密度函数,进而建立了在M/M/C(C≥2)排队系统下提高顾客等待满意度的两类排队管理策略的优化模型.并进一步将两类排队管理策略推广到了M/M/C(C≥2)排队系统,给银行、超市等服务类企业提供了如何选择两类排队管理策略的科学依据.     

具有两类服务中断的离散时间重试排队分析

本文考虑了具有破坏性和非破坏性服务中断的离散重试排队系统.两类中断都发生在顾客接受服务的过程中,假设服务台在工作时发生破坏性中断,则正在接受服务的顾客中断服务,进入到重试空间中去,重新尝试以接受服务;若服务台在工作时发生非破坏性中断,则正在接受服务的顾客将等待中断结束后再继续完成剩余的服务量.求出了系统存在稳态的充分必要条件.利用补充变量法,求出了系统稳态时系统和重试区域中队长分布的概率母函数,以及其他一些重要的排队指标,并且给出了对应的连续时间下具有两类服务中断的M/G/1排队的队长分布的概率母函数.最后,通过数值算例研究了各种参数对平均队长的影响.     

具有两类平行顾客的不完全故障排队系统均衡分析

考虑了具有两类平行顾客,系统服务器不完全可靠且带延迟维修特性的排队系统中顾客的均衡策略行为.在该排队系统中,顾客的到达类型有两种,到达过程相互独立且分别服从不同的负指数分布.系统服务器不完全可靠,系统发生故障时,不再接受顾客,以较低的服务率服务完在场顾客后进行维修,直到恢复正常工作.假定顾客到达时为了实现自身利益的最大化都有选择进入和止步的决策,在系统信息完全可见和几乎可见两种情形下,文章分析了两类平行到达顾客的均衡止步策略和系统的平均社会收益,并在此基础上,通过一些数值例子展示系统参数对顾客策略行为的影响.     

基于Stackelberg博弈的时变双层交通分配模型

提出一个时变双层交通分配模型,其中上层网络管理者设立了一个路段的最大排队长度,其目标是使由网络流和排队长度定义的总出行时间最小.目标函数在离散时段内以路段流量和排队长度作为决策变量,同时考虑不同类型的信号交叉口延误的影响.下层网络用户的反应依赖于上层管理者的决策,其选择是使自身感知阻抗最小的路径,服从一个基于成对组合Logit的路径选择模型,构成一个成对组合Logit的均衡分配问题.结合了交通分配和流传播方法,将其表示为一个均衡约束下的双层数学规划问题,形成了一个Stackelberg非合作博弈.使用遗传算法求解该双层规划问题,并采用实证分析来表现模型的特征和算法的计算表现.结果表明路径重叠、路段流量、路段排队长度等因素对网络均衡流分布均有显著影响.     

L^2-策略休假下可修的M_1+M_2/G^x(M/G)/1匹配排队系统分析

双输人匹配排队系统是通常排队系统的一种推广．本文对该系统考察了Ｌ２－策略休假和服务台可修的两个重要因素．其中假定系统有两个不同的Ｐｏｉｓｓｏｎ输入，两类顾客按１：１作成一批进行服务，服务台的寿命服从指数分布，服务时间，修理时间和休假时间都服从一般连续型分布，利用向量马氏过程方法，得到了该排队系统的一些重要的稳态排队论指标和可靠性指标．     

带有阈值转换和启动时间的优先权排队

在诸如ＩＳＤＮ的通信网络中,多种信息共用一条线路,为了满足不同类型信息的服务质量要求,带有阈值转换的优先权排队系统应是一种合适的模型。本文研究单服务员、两类顾客的带有阈值转换和启动时间的优先权排队系统,首先,分别就抢占和非抢占情形讨论了具有泊松到达、服务时间和启动时间均有指数贩系统,然后就非抢占情况进上步考虑了服务时间和启动时间有一般分布的系统,求出了系统中两类顾客队长的稳态联合概率母函数,藉助这     

Dynamic scheduling for minimum delay in tandem and parallel constrained queueing models

The optimal scheduling problem in two queueing models arising in multihop radio networks with scheduled link activation is investigated. A tandem radio network is considered. Each node receives exogenous arriving packets which are stored in its unlimited capacity buffer. Links adjacent to the same node cannot transmit simultaneously because of radio interference constraints. The problem of link activation scheduling for minimum delay is studied for two different traffic types. In the first type all packets have a common destination that is one end-node of the tandem. In this case the system is modeled by a tandem queueing network with dependent servers. The server scheduling policy that minimizes the delay is obtained. In the second type of traffic, the destination of each packet is an immediate neighbor of the node at which the packet enters the network. In this case the system corresponds to a set of parallel queues with dependent servers. It is shown that the optimal policy activates the servers so that the maximum number of packets are served at each slot.     

Stability of Earliest-Due-Date,First-Served Queueing Networks

We study multiclass queueing networks with the earliest-due-date, first-served (EDDFS) discipline. For these networks, the service priority of a customer is determined, upon its arrival in the network, by an assigned random due date. First-in-system, first-out queueing networks, where a customer's priority is given by its arrival time in the network, are a special case. Using fluid models, we show that EDDFS queueing networks, without preemption, are stable whenever the traffic intensity satisfies _j <1 for each station j.     

Structure-reversibility and departure functions of queueing networks with batch movements and state dependent routing

We consider characterizations of departure functions in Markovian queueing networks with batch movements and state-dependent routing in discrete-time and in continuous-time. For this purpose, the notion of structure-reversibility is introduced, which means that the time-reversed dynamics of a queueing network corresponds with the same type of queueing network. The notion is useful to derive a traffic equation. We also introduce a multi-source model, which means that there are different types of outside sources, to capture a wider range of applications. Characterizations of the departure functions are obtained for any routing mechanism of customers satisfying a recurrent condition. These results give a unified view to queueing network models with linear traffic equations. Furthermore, they enable us to consider new examples as well as show limited usages of this kind of queueing networks. This revised version was published online in June 2006 with corrections to the Cover Date.     

State space collapse with application to heavy traffic limits for multiclass queueing networks

Heavy traffic limits for multiclass queueing networks are a topic of continuing interest. Presently, the class of networks for which these limits have been rigorously derived is restricted. An important ingredient in such work is the demonstration of state space collapse. Here, we demonstrate state space collapse for two families of networks, first-in first-out (FIFO) queueing networks of Kelly type and head-of-the-line proportional processor sharing (HLPPS) queueing networks. We then apply our techniques to more general networks. To demonstrate state space collapse for FIFO networks of Kelly type and HLPPS networks, we employ law of large number estimates to show a form of compactness for appropriately scaled solutions. The limits of these solutions are next shown to satisfy fluid model equations corresponding to the above queueing networks. Results from Bramson [4,5] on the asymptotic behavior of these limits then imply state space collapse. The desired heavy traffic limits for FIFO networks of Kelly type and HLPPS networks follow from this and the general criteria set forth in the companion paper Williams [41]. State space collapse and the ensuing heavy traffic limits also hold for more general queueing networks, provided the solutions of their fluid model equations converge. Partial results are given for such networks, which include the static priority disciplines. This revised version was published online in June 2006 with corrections to the Cover Date.     

Performance evaluation of scheduling control of queueing networks: Fluid model heuristics

Motivated by dynamic scheduling control for queueing networks, Chen and Yao [8] developed a systematic method to generate dynamic scheduling control policies for a fluid network, a simple and highly aggregated model that approximates the queueing network. This study addresses the question of how good these fluid policies are as heuristic scheduling policies for queueing networks. Using simulation on some examples these heuristic policies are compared with traditional simple scheduling rules. The results show that the heuristic policies perform at least comparably to classical priority rules, regardless of the assumptions made about the traffic intensities and the arrival and service time distributions. However, they are certainly not always the best and, even when they are, the improvement is seldom dramatic. The comparative advantage of these policies may lie in their application to nonstationary situations such as might occur with unreliable machines or nonstationary demand patterns.     

Dynamic routing in open queueing networks: Brownian models,cut constraints and resource pooling

We present an introductory review of recent work on the control of open queueing networks. We assume that customers of different types arrive at a network and pass through the system via one of several possible routes; the set of routes available to a customer depends on its type. A route through the network is an ordered set of service stations: a customer queues for service at each station on its route and then leaves the system. The two methods of control we consider are the routing of customers through the network, and the sequencing of service at the stations, and our aim is to minimize the number of customers in the system. We concentrate especially on the insights which can be obtained from heavy traffic analysis, and in particular from Harrison's Brownian network models. Our main conclusion is that in many respects dynamic routingsimplifies the behaviour of networks, and that under good control policies it may well be possible to model the aggregate behaviour of a network quite straightforwardly.Supported by SERC grant GR/F 94194.     

Workload in queues having priorities assigned according to service time

System designers often implement priority queueing disciplines in order to improve overall system performance; however, improvement is often gained at the expense of lower priority cystomers. Shortest Processing Time is an example of a priority discipline wherein lower priority customers may suffer very long waiting times when compared to their waiting times under a democratic service discipline. In what follows, we shall investigate a queueing system where customers are divided into a finitie number of priority classes according to their service times.We develop the multivariate generating function characterizing the joint workload among the priority classes. First moments obtained from the generating function yield traffic intensities for each priority class. Second moments address expected workloads, in particular, we obtain simple Pollaczek-Khinchine type formulae for the classes. Higher moments address variance and covariance among the workloads of the priority classes.This work was supported in part by National Science Foundation Grant DDM-8913658.     

Queueing models for the analysis of communication systems

Queueing models can be used to model and analyze the performance of various subsystems in telecommunication networks; for instance, to estimate the packet loss and packet delay in network routers. Since time is usually synchronized, discrete-time models come natural. We start this paper with a review of suitable discrete-time queueing models for communication systems. We pay special attention to two important characteristics of communication systems. First, traffic usually arrives in bursts, making the classic modeling of the arrival streams by Poisson processes inadequate and requiring the use of more advanced correlated arrival models. Second, different applications have different quality-of-service requirements (packet loss, packet delay, jitter, etc.). Consequently, the common first-come-first-served (FCFS) scheduling is not satisfactory and more elaborate scheduling disciplines are required. Both properties make common memoryless queueing models (M/M/1-type models) inadequate. After the review, we therefore concentrate on a discrete-time queueing analysis with two traffic classes, heterogeneous train arrivals and a priority scheduling discipline, as an example analysis where both time correlation and heterogeneity in the arrival process as well as non-FCFS scheduling are taken into account. Focus is on delay performance measures, such as the mean delay experienced by both types of packets and probability tails of these delays.     

Scheduling networks of queues: Heavy traffic analysis of a simple open network

We consider a queueing network with two single-server stations and two types of customers. Customers of type A require service only at station 1 and customers of type B require service first at station 1 and then at station 2. Each server has a different general service time distribution, and each customer type has a different general interarrival time distribution. The problem is to find a dynamic sequencing policy at station 1 that minimizes the long-run average expected number of customers in the system.The scheduling problem is approximated by a dynamic control problem involving Brownian motion. A reformulation of this control problem is solved, and the solution is interpreted in terms of the queueing system in order to obtain an effective sequencing policy. Also, a pathwise lower bound (for any sequencing policy) is obtained for the total number of customers in the network. We show via simulation that the relative difference between the performance of the proposed policy and the pathwise lower bound becomes small as the load on the network is increased toward the heavy traffic limit.     

A sufficient condition and a necessary condition for the diffusion approximations of multiclass queueing networks under priority service disciplines

We establish a sufficient condition for the existence of the (conventional) diffusion approximation for multiclass queueing networks under priority service disciplines. The sufficient condition relates to a sufficient condition for the weak stability of the fluid networks that correspond to the queueing networks under consideration. In addition, we establish a necessary condition for the network to have a continuous diffusion limit; the necessary condition is to require a reflection matrix (of dimension equal to the number of stations) to be completely-S. When applied to some examples, including generalized Jackson networks, single station multiclass queues, first-buffer-first-served re-entrant lines, a two-station Dai–Wang network and a three-station Dumas network, the sufficient condition coincides with the necessary condition.