Multi-Server Queueing Systems with Multiple Priority Classes

We present the first near-exact analysis of an M/PH/k queue with m > 2 preemptive-resume priority classes. Our analysis introduces a new technique, which we refer to as Recursive Dimensionality Reduction (RDR). The key idea in RDR is that the m-dimensionally infinite Markov chain, representing the m class state space, is recursively reduced to a 1-dimensionally infinite Markov chain, that is easily and quickly solved. RDR involves no truncation and results in only small inaccuracy when compared with simulation, for a wide range of loads and variability in the job size distribution. Our analytic methods are then used to derive insights on how multi-server systems with prioritization compare with their single server counterparts with respect to response time. Multi-server systems are also compared with single server systems with respect to the effect of different prioritization schemes—“smart” prioritization (giving priority to the smaller jobs) versus “stupid” prioritization (giving priority to the larger jobs). We also study the effect of approximating m class performance by collapsing the m classes into just two classes. Supported by NSF Career Grant CCR-0133077, NSF Theory CCR-0311383, NSF ITR CCR-0313148, and IBM Corporation via Pittsburgh Digital Greenhouse Grant 2003. AMS subject classification: 60K25, 68M20, 90B22, 90B36     

An Eigenvalue Approach to Analyzing a Finite Source Priority Queueing Model

In this paper, we present a novel approach to determining the steady-state distribution for the number of jobs present in a 2-class, single server preemptive priority queueing model where the low priority source population is finite. Arrivals are assumed to be Poisson with exponential service times. The system investigated is a quasi birth and death process, and the joint distribution is derived via the method of generalized eigenvalues. Using this approach, we are able to obtain all eigenvalues and corresponding eigenvectors explicitly. Furthermore, we link this method to the matrix analytic approach by obtaining an explicit solution for the rate matrix R. Two numerical examples are given to illustrate the procedure and highlight some important computational features.     

A Priority Discrete Queueing Model for Multimedia Multiplexers

Multiplexers have been extensively modeled as discrete time queueing systems. In this article, we model a multimedia multiplexer handling traffic of two classes. One class represents real-time traffic, e.g., packets of live audio or video transmissions, and the other nonreal-time traffic, e.g., packets of file transfer transmissions. These packets arrive into the multiplexer in batches. In each time slot, one batch of each class arrive. The multiplexer gives service priority to class-1 packets over class-2. The demands of each class are in conflict with that of the other, and thus they are treated by the multiplexer differently. The multiplexer is thus modeled as a (preemptive) priority discrete queueing system with simultaneous batch arrivals and geometric service time. The system occupancy is analyzed and the joint probability generating function (PGF) of the number of packets of each class is derived. From this PGF, marginal PGFs of interest are obtained. The results for deterministic service time, most suitable for ATM purposes, are readily obtainable as a special case from the results of this article.     

An Exact Algorithm for the Simplified Multiple Depot Crew Scheduling Problem

The Multiple Depot Crew Scheduling Problem (MD-CSP) appears in public transit systems (e.g., airline, bus and railway industry) and consists of determining the optimal duties for a set of crews (or vehicles) split among several depots in order to cover a set of timetabled trips satisfying a number of constraints. We consider the case in which every crew must return to the starting depot and limits are imposed on both the elapsed time and the working time of any duty. The MD-CSP is an extension of both the Multiple Depot Vehicle Scheduling Problem (MD-VSP) and the single depot Crew Scheduling Problem (CSP). The MD-CSP is formulated as a set partitioning problem with side constraints (SP), where each column corresponds to a feasible duty. In this paper we extend to the MD-CSP the exact method used by Bianco, Mingozzi and Ricciardelli (1994) for MD-VSP and that used by Mingozzi et al. (1999) for the CSP. We also introduce a new bounding procedure based on Lagrangian relaxation and column generation which can deal with the MD-CSP constraints. The computational results for both random and real-world test problems from the literature show that the new exact procedure outperforms, on the test problems used, other exact methods proposed in the literature for the MD-VSP and the CSP.     

Solving Queueing Systems with Increasing Priority Numbers

This paper deals with those queueing systems for which the priority numbers are increased perpetually. A general computational algorithm capable of solving the problem for preemptive and nonpreemptive priority is proposed; the corresponding operating characteristics, three representative examples and a military illustration are given.     

Two-Class Priority Queueing System with State-Dependent Arrivals

In this paper, we present a performance analysis of a 2-dimensional preemptive priority queueing system with state-dependent arrivals. Using a Markovian formulation we first compute the steady state distribution for the queue length of both classes. Then, waiting times and busy periods are characterized through (i) first and second moments and (ii) the approximation of their cumulative distribution functions (cdf) and Laplace–Stieltjes transforms (LST). We derive these approximations connecting bounds in the Laplace domain with bounds on the original time domain. We also, study the behavior of the inter-departure time for each class. Finally, we conclude the paper with a set of computational experiments testing our results.     

Implementation of Markovian Queueing Network Model with Multiple Closed Chains

Mathematical strategy portrays the performance evaluation of computer and communication system and it deals with the stochastic properties of the multiclass Markovian queueing system with class-dependent and server-dependent service times. An algorithm is designed where the job transitions are characterized by more than one closed Markov chain. Generating functions are implemented to derive closed form of solutions and product form solution with the parameters such as stability, normalizations constant and marginal distributions. For such a system with N servers and L chains, the solutions are considerably more complicated than those for the systems with one sub-chain only. In Multi-class queueing network, a job moves from a queue to another queue with some probability after getting a service. A multiple class of customer could be open or closed where each class has its own set of queueing parameters. These parameters are obtained by analyzing each station in isolation under the assumption that the arrival process of each class is a state-dependent Markovian process along with different service time distributions. An algorithmic approach is implemented from the generating function representation for the general class of Networks. Based on the algorithmic approach it is proved that how open and closed sub-chain interact with each other in such system. Specifically, computation techniques are provided for the calculation of the Markovian model for multiple chains and it is shown that these algorithms converge exponentially fast.     

带负顾客和强占优先权的不耐烦信元排队

考虑带有负顾客的两类信元的强占优先权M/M/1排队系统.两类信元及负顾客的到达过程均为泊松过程.两类信元到达后分别在各自有限的缓冲器内排队,第一类信元较第二类信元有强占优先权,同时第一类信元是不耐烦的.负顾客一对一抵消队尾的第一类信元(若有),若系统中无第一类信元,到达的负顾客就自动消失.负顾客不接受服务.采用矩阵分析的方法得到了两类信元各自的稳态分布,并作了相应的性能分析.     

Dynamic Scheduling of a Multiclass Fluid Model with Transient Overload

We study the optimal dynamic scheduling of different requests of service in a multiclass stochastic fluid model that is motivated by recent and emerging computing paradigms for Internet services and applications. In particular, our focus is on environments with specific performance guarantees for each class under a profit model in which revenues are gained when performance guarantees are satisfied and penalties are incurred otherwise. Within the context of the corresponding fluid model, we investigate the dynamic scheduling of different classes of service under conditions where the workload of certain classes may be overloaded for a transient period of time. Specifically, we consider the case with two fluid classes and a single server whose capacity can be shared arbitrarily among the two classes. We assume that the class 1 arrival rate varies with time and the class 1 fluid can more efficiently reduce the holding cost. Under these assumptions, we characterize the optimal server allocation policy that minimizes the holding cost in the fluid model when the arrival rate function for class 1 is known. Using the insights gained from this deterministic case, we study the stochastic fluid system when the arrival rate function for class 1 is random and develop various policies that are optimal or near optimal under various conditions. In particular, we consider two different types of heavy traffic regimes and prove that our proposed policies are strongly asymptotically optimal. Numerical examples are also provided to demonstrate further that these policies yield good results in terms of minimizing the expected holding cost.     

An Algorithm for Bus Scheduling Problems

The problem arose in the context of devising a schedule for buses to be operated by a State Transport Corporation. An algorithm for obtaining a schedule to minimize the number of buses required is described, in which computational advantage is taken of the special structure of the problem. A computer program has been written and some results of its use are described.     

Project Scheduling with Multiple Modes: A Genetic Algorithm

In this paper we consider the resource-constrained project scheduling problem with multiple execution modes for each activity and makespan minimization as objective. We present a new genetic algorithm approach to solve this problem. The genetic encoding is based on a precedence feasible list of activities and a mode assignment. After defining the related crossover, mutation, and selection operators, we describe a local search extension which is employed to improve the schedules found by the basic genetic algorithm. Finally, we present the results of our thorough computational study. We determine the best among several different variants of our genetic algorithm and compare it to four other heuristics that have recently been proposed in the literature. The results that have been obtained using a standard set of instances show that the new genetic algorithm outperforms the other heuristic procedures with regard to a lower average deviation from the optimal makespan.     

一类Sylvester矩阵方程的一个迭代算法

考虑这样一类Sylvester矩阵方程:AX XB=C,A,B分别为n阶正半定、正定矩阵,C为n阶矩阵.给出了一个收敛的迭代算法.     

Queueing Models with Multiple Waiting Lines

This paper discusses analytic solution methods for queueing models with multiple waiting lines. The methods are briefly illustrated, using key models like the 2×2 switch, the shortest queue and the cyclic polling system.     

带概率判断和模糊区间判断的一种排序算法

对于 AHP中一类判断为模糊、不确定性问题 ,用随机变量和模糊区间描述其判断 ,采用 0 .1～ 0 .9标度 ,建立模糊互补判断矩阵 ,利用数学变换得到模糊一致性判断矩阵 ,给出排序向量算法及公式 ,便于实际应用     

带有转换时间和阀值的非抢占优先权排队模型

在[3]中,我们研究了在抢占规则下带有转换时间和阈值的两类顾客优先权排队系统,本文就非抢占情形对这样的系统作进一步的研究,同样求出两类顾客队长的稳态联合概率母函数。籍助这些母函数可求出诸如平均队长这样一些重要的系统性能指标。     

区际救援物资中转调度的动态决策模型与算法

考虑灾害救援中灾区对应急物资的持续消耗,研究了区际多品种救援物资的动态中转调度问题.综合考虑各阶段调度费用、运输费用和库存费用总和最小化的救援物资中转调度安排和库存规划,建立了一个区际救援物资中转调度动态决策模型,并设计了一种矩阵编码的协进化遗传算法.最后通过一个算例验证了模型和算法的有效性.     

一种求多项式重零点的并行圆盘迭代法

本文给出一种三阶收敛的同时求多项式重零点的圆盘迭代法 ,并分析该法收敛的初始值条件 ,它改进了文献 [2 ]的结果 .     

一个关于非对称距离的旅行商问题的迭代算法

本对非对称距离的旅行商问题，给出了一个迭代算法，并分析了此迭代算法的复杂度为M^nO(N^4)，其中，N是问题中旅行商所要经过的城镇数，M是两城镇间的最大距离。最后用实例对此算法进行了验算和说明。     

一个构造增生映像零点的带误差的迭代算法

设E是一致光滑的Banach空间,A:D(A)E→2~E是一个满足值域条件的增生算子,进一步满足线性增长条件:‖Ax‖≤C(1+‖x‖)对某个常数C0, x∈D(A).设z∈D(A)是任意固定元,x_1∈D(A), A~(-1)0≠Φ.定义序列{x_n}D(A)如下:x_(n+1)∈x_n-λ_n(Ax_n+θ_n(x_n-z+e_n)),n≥1,其中{λ_n}与{θ_n}是满足一定条件的非负数列.则x_n→x~*∈A~(-1)(0),(n→∞).作为应用,我们推出构造连续伪压缩映像的不动点的收敛定理.     

求解变分不等式的Ishikawa类迭代算法

本文讨论Banach空间中子集非紧的情况下的变分不等式数值解.提出了求解相应问题的Ishikawa类迭代算法,证明了算法的子列收敛性和全局收敛性.同时也证明了变分不等式解的存在性.