An approximate transient analysis of the M(t)/M/1 queue

An approach, based on recent work by Stern [56], is described for obtaining the approximate transient behavior of both the M/M/1 and M(t)/M/1 queues, where the notation M(t) indicates an exponential arrival process with time-varying parameter λ(t). The basic technique employs an M/M/1K approximation to the M/M/1 queue to obtain a spectral representation of the time-dependent behavior for which the eigen values and eigenvectors are real.Following a general survey of transient analysis which has already been accomplished, Stern's M/M/1/K approximation technique is examined to determine how best to select a value for K which will yield both accurate and computationally efficient results. It is then shown how the approximation technique can be extended to analyze the M(t)/M/1 queue where we assume that the M(t) arrival process can be approximated by a discretely time-varying Poisson process.An approximate expression for the departure process of the M/M/1 queue is also proposed which implies that, for an M(t)/M/1 queue whose arrival process is discretely time-varying, the departure process can be approximated as discretely time-varying too (albeit with a different time-varying parameter).In all cases, the techniques and approximations are examined by comparison with exact analytic results, simulation or alternative discrete-time approaches.     

A polynomial factorization approach to the discrete time GI/G/1/(N) queue size distribution

The queue of a single server is considered with independent and identically distributed interarrivai and service times and an infinite (GI/G/1) or finite (GI/G/1/N) waiting room. The queue discipline is non-preemptive and independent of the service times.

A discrete time version of the system is analyzed, using a two-component state model at the arrival and departure instants of customers. The equilibrium equations are solved by a polynomial factorization method. The steady state distribution of the queue size is then represented as a linear combination of geometrical series, whose parameters are evaluated by closed formulae depending on the roots of a characteristic polynomial.

Considering modified boundary constraints, systems with finite waiting room or with an exceptional first service in each busy period are included.     

Analysis of a finite-capacity M/G/1 queue with a resume level

In order to model the buffer pool behavior in a data communication component, an M/G/1/K queue where input is shut down when the queue size (number of messages) attains K until it decreases to a specified level is analyzed. By use of semi-Markov process approach, the queue length distribution at an arbitrary time is found, and the resultant performance measures (utilization, loss probability, and mean response time) are computed.     

Computing steady state probabilities in λ(n)/G/1/K queue

In this paper a recursive method is developed to obtain the steady state probability distribution of the number in system at arbitrary and departure time epochs of a single server state-dependent arrival rate queue λ(n)/G/1/K in which the arrival process is Markovian with arrival rates λ(n) which depend on the number of customers n in the system and general service time distribution. It is assumed that there exists an integer K such that λ(n) > 0 for all 0 n < K and λ(n) = 0 for all n K. Numerical results have been presented for many queueing models by suitably defining the function λ(n). These include machine interference model, queues with balking, queues with finite waiting space and machine interference model with finite waiting space. These models have wide application in computer/communication networks.     

On the overflow processes from the PH1 + PH2/M/S/K queue with two independent PH-renewal inputs

This paper presents an analysis of overflow processes from a PH₁ + PH₂/M/S/K queue having two independent phase type renewal input streams. Both the superposed overflow process and individual overflow processes for the PH₁- and PH₂-streams are analyzed using first passage time distributions for the number of customers in the system. Each overflow process is characterized as a Markov renewal process. The nth moment of the number of customers in an infinite server group to which these overflows have been offered is derived using a theory for the MR/M/∞ queue with a Markov renewal input. The numerical examples for means and variance-to-mean ratios (peakednesses) of the individual overflow streams are given for an H₂ + H₂/M/S/S queue with interrupted Poisson inputs, which is a vital model for telephone network planning. In addition, overflow traffic characteristics are discussed by using these examples.     

Optimal (N,T)-policy for M/G/1 system with cost structures

In this paper, the optimal (N,T)-policy for M/G/1 system with cost structure is studied. The system operates only intermittently. It is shut down when no customers are present. A fixed set-up cost of K>0 is incurred each time the system is reopened. Also, a holding cost of h>0 per unit time is incurred for each customer present. The (N,T)-policy studied for this system is as follows: the system reactivates as soon as N customers are present or the waiting time of the leading customer reaches a predefined time T (see A.S. Alfa, I. Frigui, Eur. J. Oper. Res. 88 (1996) 599-613; Y.N. Doganata, in: E. Arikan (Ed.), Communication, Control, and Signal Processing, 1990, pp. 1663–1669). Later on, as a comparison, the start of the timer count is relaxed as follows: the system reactivates as soon as N customers are present or the time units after the end of the last busy period reaches a predefined time T. For both cases, the explicit optimal policy (N^*,T^*) for minimizing the long-run average cost per unit time are obtained. As extreme cases, we include the simple optimal policies for N-and T-polices. Several counter-intuitive results are obtained about the optimal T-policies for both types of models.     

Performance analysis of an integrated hybrid-switched multiplex structure

The performance of an integrated voice/data hybrid-switched multiplex structure is analyzed. The approach is based on an imbedded two-dimensional Markov chain associated with the voice and data queueing processes, which accounts for their interaction. Using generating functions, a method for determining exactly the average data delay is given. As an application, an analytical expression for the average data delay is derived for the so-called single channel case. These results should be considered primarily as a theoretical contribution since the numerical difficulties involved in the solution procedure for the general case are formidable.     

Approximation models of feed-forward G/G/1/N queueing networks with correlated arrivals

In this paper we develop approximation models for feed-forward networks of G/G/1/N queues. We use Linear Algebra Queueing Theory (LAQT) techniques to create reduced state space representations for the queue departure processes. Reduced state space departure processes are presented where the first three moments and the correlation decay are mapped to a two state process. A three state process is also presented matching the first five moments and the first three lag autocorrelations. Numerical examples of end-to-end performance for high-speed communications networks with correlated arrival traffic are presented. The results are compared with simulation models and other approximation methods.     

Fast solution of large N×N matrix equations in an MIMD–SIMD Hybrid System

In this paper, we propose a new high-speed computation algorithm for solving a large N×N matrix system using the MIMD–SIMD Hybrid System. The MIMD–SIMD Hybrid System (also denoted as Hybrid System in this paper) is a new parallel architecture consisting of a combination of Cluster of Workstations (COWs) and SIMD systems working concurrently to produce an optimal parallel computation. We first introduce our prototype SIMD system and our Hybrid System setup before presenting how it can be implemented to find the unknowns in a large N×N linear matrix equation system using the Gauss–LU algorithm. This algorithm basically performs the ‘Divide and Conquer’ approach by breaking down the large N×N matrix system into a manageable 32 × 32 matrix for fast computation.     

Analysis of the M/G/1 queue with discriminatory random order service policy

We consider an M/G/1 queue with different classes of customers and discriminatory random order service (DROS) discipline. The DROS discipline generalizes the random order service (ROS) discipline: when the server selects a customer to serve, all customers waiting in the system have the same selection probability under ROS discipline, whereas customers belonging to different classes may have different selection probabilities under DROS discipline. For the M/G/1 queue with DROS discipline, we derive equations for the joint queue length distributions and for the waiting time distributions of each class. We also obtain the moments of the queue lengths and the waiting time of each class. Numerical results are given to illustrate our results.     

Exact transient solution of an M/M/1 driven fluid queue

The transient solution of a fluid queue driven by an M/M/1 queue is obtained explicitly using continued fractions. The probability that the buffer is empty at a specified time is also determined and illustrated graphically.     

G/M/1 queue study of buffer behavior in the decoding system of computer communication

This paper deals with the buffer behavior at the decoding center of a computer communication system in which the messages are in the Huffman code of English text. It is assumed that the arrival of messages has an arbitrary distribution, with the message lengths having negative exponential distribution. The situation is well described by the G/M/1 model of queue theory. The waiting time model is simulated on the EC-1030 computer, assuming the HP2100A computer is the decoding machine. The simulation results are used for estimation of buffer size in a character-oriented system and block-oriented system for a very low overflow probability.     

基于CPN的空竭服务单重休假M/G/1型排队系统建模与分析

空竭服务单重休假M/G/1型排队系统是经典排队系统的推广,在许多领域有着广泛的应用.到目前为止对其的处理方法还都是建立在概率论和数理统计的基础上,运用马尔可夫随机过程求解,推导十分复杂,没有直观的模型描述.因此,利用着色Petri网对空竭服务单重休假M/G/1型排队系统进行建模,并对主要性能指标进行仿真分析是迫切以及可行地.仿真软件选用CPNTools[1],仿真结果证明该方法具有较高的精确度以及实用价值.     

Analysis of the discrete-time Geo/G/1 working vacation queue and its application to network scheduling

In this paper we present an exact steady-state analysis of a discrete-time Geo/G/1 queueing system with working vacations, where the server can keep on working, but at a slower speed during the vacation period. The transition probability matrix describing this queuing model can be seen as an M/G/1-type matrix form. This allows us to derive the probability generating function (PGF) of the stationary queue length at the departure epochs by the M/G/1-type matrix analytic approach. To understand the stationary queue length better, by applying the stochastic decomposition theory of the standard M/G/1 queue with general vacations, another equivalent expression for the PGF is derived. We also show the different cases of the customer waiting to obtain the PGF of the waiting time, and the normal busy period and busy cycle analysis is provided. Finally, we discuss various performance measures and numerical results, and an application to network scheduling in the wavelength division-multiplexed (WDM) system illustrates the benefit of this model in real problems.     

Randomized control of T-policy for an M/G/1 system

We study an M/G/1 queueing system with a server that can be switched on and off. The server can take a vacation time T after the system becomes empty. In this paper, we investigate a randomized policy to control a server with which, when the system is empty, the server can be switched off with probability p and take a vacation or left on with probability (1 − p) and continue to serve the arriving customers. For this system, we consider the operating cost and the holding cost where the operating cost consists of the system running and switching costs (start up and shut down costs). We describe the structure and characteristics of this policy and solve a constrained problem to minimize the average operating cost per unit time under the constraint for the holding cost per unit time.     

Design and control of an ethyl acetate process: coupled reactor/column configuration

In this paper, design and control of a realistic coupled reactor/column process to produce ethyl acetate is studied. The process design is more complicated because the ethyl acetate product is neither the lightest nor the heaviest component in the system. A search procedure is proposed to obtain the optimum process design and operating condition of this process. The optimum process design is the one that minimize the Total Annual Cost (TAC) of this process while satisfying the stringent product impurity specifications. The optimum overall process design includes a continuous-stirred tank reactor (CSTR) coupled with a rectifier, a decanter, another stripper, and a recycle stream. After the process design is established, the next step is to use dynamic simulation to test the appropriate control strategy for this process. Sensitivity analysis is performed to obtain the suitable temperature control points for the columns. The proposed control strategy is very simple containing only one temperature control loop in each column. This recommended simpler control strategy uses the ratio of acetic acid feed rate to ethanol feed rate to control the 5th stage temperature of the rectifier and uses the stripper reboiler duty to control the 5th stage temperature of the stripper. The proposed control strategy does not need any on-line composition measurements and can properly hold product purity in spite of feed flow rate and feed composition disturbances. For small deviations of the product impurity compositions during disturbances, a slow cascade outer composition loop structure can be implemented using off-line composition measurements from the quality lab.     

A matrix approach for the transient solution of an M/M/1/N queue with discouraged arrivals and reneging

This paper illustrates a computable matrix technique that can be used to derive explicit expressions for the transient state probabilities of a finite waiting space single-server queue, namely (M/M/1/N), having discouraged arrivals and reneging. The discipline is the classical first-come, first-served (FCFS). We obtain the transient solution of the system, with results in terms of the eigenvalues of a symmetric tridiagonal matrix. Finally, numerical calculations are given to illustrate the effectiveness of this technique and system behaviour.     

Performance analysis of non-preemptive GE/G/1 priority queueing of LER system with bulk arrivals

M^X/G/1 non-preemptive priority queue with bulk arrivals has already been analysed in many papers. Two problems are known in this area: first, when the number of priorities is greater than 2, the analysis for priority processes is obviously very difficult to handle. Therefore, the earlier work on the subject was restricted mostly to two priority classes; and second, although analytically explicit results are available, they require sophisticated closed-form expressions of the mean queue length. One particular bulk size distribution – the GE distribution – is motivated by an ME (Maximum Entropy) formulation for the behavior of a G/G/1 queue. The choice of a GE distribution is motivated by the fact that measurements of actual inter-arrival traffic or service times may be generally limited and so only few parameters, such as mean and variance, can be computed reliably. Thus this paper we can obtain very simple and analytic closed-form expression for the mean queue length of a GE/G/1 priority queue and a significant increase in performance evaluation has been achieved. We present the four-class priority queues, performance analysis and simulation of the LER (Label Edge Router) system in the ATM-based MPLS (Multiprotocol Label Switching) network. We wish to obtain the boundary conditions of the mean queue lengths and the mean queueing delays for each priority class, since this metric is one of the most important in performance evaluation parameters for improving QoS and system performance of the LER system in ATM-based MPLS network. A significant numerical example is presented and discussed as well. In order to obtain optimizing the performance analysis for EF flow, AF 1 flow, AF 2 flow and BE flow, the optimum ratios of COV (Coefficient of Variation) can be found via many numerical experiments carried out by the authors for queueing network model with HOL (Head of Line) priority rules. However, the ratios of COV value constraints exist. Furthermore, we find that each service class gradually begins to deteriorate when SQVs (Squared Coefficient of Variations), , and traffic intensity is greater than 0.95. We also find the values of maximum allowed burst size for EF flow and AF 1 flow and perform necessary policing actions on EF flow and AF 1 flow at the boundary node of the network. Finally, the four-class GE/G/1 priority queues and performance analysis of the LER system are shown accurate and robust after the comparison between theoretical evaluates and computer simulation results.     

The optimal control of an M/G/1 queueing system with server vacations, startup and breakdowns

This paper studies the control policy of the N policy M/G/1 queue with server vacations, startup and breakdowns, where arrivals form a Poisson process and service times are generally distributed. The server is turned off and takes a vacation whenever the system is empty. If the number of customers waiting in the system at the instant of a vacation completion is less than N, the server will take another vacation. If the server returns from a vacation and finds at least N customers in the system, he requires a startup time before providing service until the system is again empty. It is assumed that the server breaks down according to a Poisson process and his repair time has a general distribution. The system characteristics of such a model are analyzed and the total expected cost function per unit time is developed to determine the optimal threshold of N at a minimum cost.