Stability Conditions of the MMAP [ K ]/ G [ K ]/1/ LCFS Preemptive Repeat Queue

In this paper, we study the stability conditions of the MMAP[K]/G[K]/1/LCFS preemptive repeat queue. We introduce an embedded Markov chain of matrix M/G/1 type with a tree structure and identify conditions for the Markov chain to be ergodic. First, we present three conventional methods for the stability problem of the queueing system of interest. These methods are either computationally demanding or do not provide accurate information for system stability. Then we introduce a novel approach that develops two linear programs whose solutions provide sufficient conditions for stability or instability of the queueing system. The new approach is numerically efficient. The advantages and disadvantages of the methods introduced in this paper are analyzed both theoretically and numerically.     

闭排队网络中性能势与无穷小实现因子之间的关系

In this paper,the concept of the infinitesimal realization factor is extended to the parameter-dependent performance functions in closed queueing networks. Then the concepts of realization matrix (its elements are called realization factors) and performance potential are introduced,and the relations between infinitesimal realization factors and these two quantities are discussed. This provides a united framework for both IPA and non IPA approaches. Finally,another physical meaning of the service rate is given.     

Asymptotic analysis of the effect of arrival model uncertainties in some optimal routing problems

We study the effect of arrival model uncertainties on the optimal routing in a system of parallel queues. For exponential service time distributions and Bernoulli routing, the optimal mean system delay generally depends on the interarrival time distribution. Any error in modeling the arriving process will cause a model-based optimal routing algorithm to produce a mean system delay higher than the true optimum. In this paper, we present an asymptotic analysis of the behavior of this error under heavy traffic conditions for a general renewal arrival process. An asymptotic analysis of the error in optimal mean delay due to uncertainties in the service time distribution for Poisson arrivals was reported in Ref. 6, where it was shown that, when the first moment of the service time distribution is known, this error in performance vanishes asymptotically as the traffic load approaches the system capacity. In contrast, this paper establishes the somewhat surprising result that, when only the first moment of the arrival distribution is known, the error in optimal mean delay due to uncertainties in the arrival model is unbounded as the traffic approaches the system capacity. However, when both first and second moments are known, the error vanishes asymptotically. Numerical examples corroborating the theoretical results are also presented.This work was supported by the National Science Foundation under Grants ECS-88-01912 and EID-92-12122 and by NASA under Contract NAG 2-595.The authors wish to thank an anonymous referee for pointing out Ref. 20, thus avoiding the need for an explicit proof of convexity of the cost function considered in the paper.     

Allocation of jobs and identical resources with two pooling centers

We examine the resource allocation problem of partitioning identical servers into two parallel pooling centers, and simultaneously assigning job types to pooling centers. Each job type has a distinct Poisson arrival rate and a distinct holding cost per unit time. Each pooling center becomes a queueing system with an exponential service time distribution. The goal is to minimize the total holding cost. The problem is shown to be polynomial if a job type can be divided between the pooling centers, and NP-hard if dividing job types is not possible. When there are two servers and jobs cannot be divided, we demonstrate that the two pooling center configuration is rarely optimal. A heuristic which checks the single pooling center has an upper bound on the relative error of 4/3. The heuristic is extended for the multiple server problem, where relative error is bounded above by the number of servers.      

Markovian network processes: Congestion-dependent routing and processing

A Markovian network process describes the movement of discrete units among a set of nodes that process the units. There is considerable knowledge of such networks, often called queueing networks, in which the nodes operate independently and the routes of the units are independent. The focus of this study, in contrast, is on networks with dependent nodes and routings. Examples of dependencies are parallel processing across several nodes, blocking of transitions because of capacity constraints on nodes, alternate routing of units to avoid congestion, and accelerating or decelerating the processing rate at a node depending on downstream congestion. We introduce a general network process representing the numbers of units at the nodes and derive its equilibrium distribution. This distribution takes the form of a product of functions of vectors in which the arguments of the functions satisfy an interchangeability property. This new type of distribution may apply to other multi-variate processes as well. A basic idea in our approach is a linking of certain micro-level balance properties of the network routing to the processing rates at the nodes. The link is via routing-balance partitions of nodes that are inherent in any network. A byproduct of this approach is a general characterization of blocking of transitions without the restriction that the process is reversible, which had been a standard assumption. We also give necessary and sufficient conditions under which a unit moving in the network sees a time average for the unmoved units (called the MUSTA property). Finally, we discuss when certain flows between nodes in an open network are Poisson processes.This research was sponsored in part by Air Force Office of Scientific Research contract 84-0367.     

Pathwise rate- stability for input-output processes

An input-output processZ = {Z(t), t 0} is said to be-rate stable ifZ(t) = o((t)) for some non-negative function(t). We prove that the processZ is -rate stable under weak conditions that include the assumption that input satisfies a linear burstiness condition and Z is asymptotically average stable. In many cases of interest, the conditions for-rate-stability can be verified from input data. For example, using input information, we establish-rate stability of the workload for multiserver queues, an ATM multiplexer, and-rate stability of queue-length processes for infinite server queues.     

The permutational power of a priority queue

A priority queue transforms an input permutation of some set of sizen into an output permutation. It is shown that the number of such pairs (, ) is (n + 1) ^n–1. Some related enumerative and algorithmic questions are also considered.Supported by the National Science and Engineering Research Council of Canada under Grant A4219.     

The matched queueing network PH/M/c→oPH/PH/1

We consider a matched queueing network PH/M/coPH/PH/1, where the output of the first subsystem PH/M/c is regarded as one of the inputs of the second subsystem and matched with another input of PH-renewal process, and they are served by a single server with PH-service-distribution. The stationary state probabilities, the distribution of the virtual waiting times in the two subsystems, and the distribution of the total virtual waiting time are derived.The work was supported by the Max-Planck-Gesellschaft, Germany, and the Chinese Academy ofSciences.     

New indices for analysing partial ranking diagrams

Interest is growing in decision making strategies and several techniques are now available. The assessment of priorities is a typical premise before final decisions are taken. Total and partial order ranking (POR) strategies, which from a mathematical point of view are based on elementary methods of discrete mathematics, appear as an attractive and simple tool to asses priorities. Despite the well-known total ranking strategies, which are scalar methods combining the different criteria values into a global index which always ranks elements in an ordered sequence, the partial order ranking is a vectorial approach which recognises that not all the elements can be directly compared with all the others. In fact when many criteria are considered, contradictions in the ranking are bound to exist and the higher the number of criteria, the higher the probability that contradictions in the ranking occur. The Hasse diagram technique (HDT) is a very useful tool to perform partial order ranking. The results of the partial order ranking are visualised in a diagram, called Hasse diagram. Incomparable elements are located at the same geometrical height and as high as possible in the diagram, thus incomparable elements are arranged in levels. The quality of a ranking procedure has to be evaluated by a deep analysis and by several indices, i.e. scalar functions that describe features of an ordered set and allow comparison among different rankings. For this purpose, new indices for ranking analysis are proposed here, compared with the ones found in literature and tested on theoretical examples and on real data.     

The Efect of Queueing Strategy on Network Trafc

In recent years,the transportation system has been faced by increasing challenge in congestion and inefciency,and research in trafc network has become a significant area of interest.In this paper,we introduce a dynamic-information-based(DIB)queueing strategy into network trafc model under the efcient routing strategy.DIB makes a packet with higher priority to be delivered if there are less packets travelling along its path from the current node to the destination.It is found that,compared with the traditional first-in-first-out(FIFO)queueing strategy,DIB can efectively balance the trafc load of the system via delaying packets to be delivered to congested nodes.Although the network capacity has no obvious changes,some other indexes which reflect transportation efciency are efciently improved in the congestion state.Besides,extensive simulation results and discussions are provided to explain the phenomena.The results may provide novel insights for research on trafc systems.