Tandem queues with general blocking: A unified model and comparison results

We study tandem queues with finite intermediate buffers and develop a general blocking scheme that unifies and generalizes various blocking schemes previously studied in the literature, such as manufacturing blocking, communication blocking, kanban blocking and its variations. In the general blocking scheme, job movement and service at each stage are controlled by three parameters, which represent, respectively, the upper limits (at that stage) on work-in-process inventory, finished goods inventory, and buffer space. We derive a set of recursive equations that characterize the dynamics of the system, in terms of the job completion and departure processes, and establish comparison results for these processes in the settings of stochastic ordering, variability ordering and stochastic convexity. Free of distributional assumptions, the results provide characterization of system behavior with respect to the control parameters as well as to the arrival and service processes. We also compare system performance under two different modes of operation: make-to-order versus make-to-stock, and demonstrate the trade-off between improving service and reducing inventory. Numerical studies are also presented to illustrate the diversity of performance trade-off, including composition of inventory, offered by the general model.Supported in part by NSF under grant ECS-89-96201.     

A maximum entropy optimization approach to tandem queues with generalized blocking

We study a general blocking scheme for an open tandem queueing network with finite intermediate buffers. The service time at each node as well as interarrival time at the first node is assumed to be exponentially distributed. The interarrival and service time at each intermediate node of the tandem queue, under the general blocking scheme, depend upon three parameters at each node, namely, the maximum number of raw jobs, the upper limit on the number of finished but blocked jobs and the buffer capacity. This three-parameter analysis was introduced by Cheng and Yao (1993), and was shown, using Monte Carlo simulations, to provide good results. Our analysis is also based on this three-parameter approach, but with a different view. We first decompose the tandem queue into a group of two-node subsystems in order to derive a set of equations for the effective interarrival and service time distributions at each node. Each of these two-node subsystems is treated as a finite capacity queueing system with population size constraints. Then we apply the principle of maximum entropy to evaluate different parameters such as the blocking probabilities, starvation probabilities, etc., of each subsystem. We propose a step-by-step algorithm along with its convergence properties. A comparison of numerical results with the simulation results is also discussed.     

A tandem queue with general bulk service and servers' “vacation”

This paper analyses two queueing models consisting of two units I and II connected in series, separated by a finite buffer of size N. In both models, unit I has only one exponential server capable of serving customers one at a time and unit II consist of c parallel exponential servers, each of them serving customers in groups according to general bulk service rules. When the queue length in front of unit II is less than the minimum of batch size, the free servers take a vacation. On return from vacation, if the queue length is less than the minimum, they leave for another vacation in the first model, whereas in the second model they wait in the system until they get the minimum number of customers and then start servicing. The steady-state probability vector of the number of customers waiting and receiving service in unit I and waiting in the buffer is obtained for both the models, using the modified matrix geometric method. Numerical results are also presented.     

A discrete-time single-server queue with a modified N -policy

We consider a discrete-time single-server queue where the idle server waits for reaching a level N in the queue size to start a batch service of N messages, although the following arrivals during the busy period receive single services. We find the stationary distributions of the queue and system lengths as well as some performance measures. The vacation and busy periods of the system and the number of messages served during a busy period are also analyzed. The stationary distributions of the time spent waiting in the queue and in the system are studied too. Finally, a total expected cost function is developed to determine the optimal operating N-policy at minimum cost.     

Optimal control of a class of DEDS: Flow-shops with state-dependent processing times

We consider a permutation flow-shop withn jobs andm machines, where the job processing times are given by a monotone nondecreasing function of the time elapsed since the release of the jobs. In this class of discrete event dynamic systems (DEDS), the dynamics is bothevent dependent, andtime dependent. Unless processing times are constant, it cannot be linearized using the (max, +) algebra. In order to schedule the jobs, we first need to know how to compute the (optimal) value of each schedule, i.e., when the jobs should be released. This optimal control problem is solved here by proving apredictive feedback control law, which holds for any regular performance criterion. Then we derive aBellman principle for this type of DEDS, and prove closed form control formulas for the minimum of: the makespan (C _max), the maximum lateness (L _max), and the maximum tardiness (T _max). We also prove some minimax theorems for a class of nonconvex maps derived from the dynamics of the system. The optimal control problem is solved in polynomial time, provided the inverse of the processing time functions can be computed in polynomial time.Research supported by the M.E.S.S. Québec Actions Structurantes, F.C.A.R. 86CE-130, 89EQ3528, NRC grants OGP38915, OGP37148, the Belgian Program on Interuniversity Poles of Attraction, and the CNRS, France.     

Supervisory control of discrete event systems with state-dependent controllability

This article studies the supervisory control problem of discrete event systems (DES) with state-dependent controllability. The new problem is given with the background of operating systems where the processes and the interrupt service routines (ISR) are supervised and coordinated. The new model is novel because the controllability of an event is changeable in the lifetime of system evolution, and dependent on the system state. Two fundamental problems are concerned with the new model: supervisor existence problem and supervisor synthesis problem. We derive a necessary and sufficient condition for the existence of the supervisor, and introduce an algorithm to synthesise the supremal supervisor in a given specification. With the background of process and ISR management in operating systems, some examples are given to show how the new model can be applied to practical computing.     

Analysis of a nonpreemptive priority queue with SPP arrivals of high class

This paper considers a nonpreemptive priority queueing system with two priority classes of customers, where high priority customers arrive to the system in accordance with a switched Poisson process (SPP) and low priority customers in accordance with a Poisson process. Using the supplementary variable technique, we derive the joint probability generating function of the stationary queue length distributions and the Laplace-Stieltjes transforms of the stationary waiting time distributions of high and low priority customers. We also present some numerical results in order to show the computational feasibility of the analytical results.     

Managing Internet routers congested links with a Kohonen-RED queue

The behaviour of the TCP AIMD algorithm is known to cause queue length oscillations when congestion occurs at a router output link. Indeed, due to these queueing variations, end-to-end applications experience large delay jitter. Many studies have proposed efficient active queue management (AQM) mechanisms in order to reduce queue oscillations and stabilize the queue length. These AQM attempt to improve the random early detection (RED) model. Unfortunately, these enhancements do not react in a similar manner for various network conditions and are strongly sensitive to their initial setting parameters. Although this paper proposes a solution to overcome the difficulties of configuring the RED parameters by using a Kohonen neural network model; another goal of this study is to investigate whether cognitive intelligence could be placed in the core network to solve such stability problem. In our context, we use results from the neural network area to demonstrate that our proposal, named Kohonen-RED (KRED), enables a stable queue length without complex parameters setting or passive measurements to obtain a correct configuration.     

中心队列二次门限服务的轮询系统分析

采用嵌入Markov链和概率母函数的方法对门限服务优先级排队系统进行分析,提出普通队列和高优先级队列分别采用基本门限和二级门限的服务机制,得出了平均排队队长和平均查询周期的解析式。     

Dynamic optimization of dual-mode hybrid systems with state-dependent switching conditions

This paper presents a computational approach for optimizing a class of hybrid systems in which the state dynamics switch between two distinct modes. The times at which the mode transitions occur cannot be specified directly, but are instead governed by a state-dependent switching condition. The control variables, which should be chosen optimally by the system designer, consist of a set of continuous-time input signals. By introducing an auxiliary binary-valued control function to represent the system's current mode, we show that any dual-mode hybrid system with state-dependent switching conditions can be transformed into a standard dynamic system subject to path constraints. We then develop a computational algorithm, based on control parameterization, the time-scaling transformation, and an exact penalty method, for determining the optimal piecewise constant input signals for the original hybrid system. A numerical example on cancer chemotherapy is included to demonstrate the effectiveness of the proposed algorithm.     

Analysis of manufacturing blocking systems with Network Calculus

In this paper, the manufacturing blocking system (MBS) is studied from the Network Calculus (NetCal) perspective. By dominating an MBS by a window flow controller (WFC), we obtain service curves for systems with instantaneous and non-instantaneous acknowledgements. The explicit expression for the system service curve leads to the optimal allocation of the buffer sizes, which guarantees the ideal system service curve: that is, the service curve for the system with no restrictions on the sizes of in-between buffers. This allocation is more efficient than one based on guarantees of individual service curves. In addition, a method of simulation of NetCal systems is developed exploiting the duality between arrival curves and strict service curves. Simulation experiments are conducted to show the tightness of the theoretical bounds obtained using NetCal.     

Maximal coupling Rare Perturbation Analysis with a random horizon

In this article we present extension of the recently introduced maximal coupling Rare Perturbation Analysis (RPA), a novel approach for computing gradient estimates in sensitivity analysis, and we extend the result of Brémaud (1992) to the random horizon case. Also we interpret the analysis of Dai and Ho (1992) in terms of maximal coupling (one sided).     

A numerical approach of optimal control for generalized delay systems by general Legendre wavelets

A general Legendre wavelets approach is presented. The delay function is expanded by general Legendre wavelets. The general operational matrix of integration is introduced. By the general Legendre wavelets, the linear-quadratic problem of generalized delay systems are transformed into the optimization problem of multivariate functions. The approximate solutions of the optimal control and state as well as the optimal value of the objective functional are derived. The numerical examples demonstrate that the algorithms are valid.     

改进的RED队列管理算法：RED-r

为了避免RED缺陷,提出一种改进的RED算法——RED-r。该算法采用二次圆函数来计算丢包概率,减少了RED的设置参数,实现了在网络大延时和小延时时的队列稳定,且在小延时能获得比PID队列更平滑的效果。NS2仿真验证了RED-r算法的有效性。     

Approximate analysis of a discrete-time tandem network of cut-through queues with blocking and bursty traffic

A discrete-time tandem network of cut-through queues is presented. The model allows finite capacity queues, blocking, and bursty traffic. A new bursty arrival process, IBK(k), for cut-through traffic is introduced. The tandem network is analyzed using single-node decomposition. Each queue is analyzed numerically in isolation assuming that its arrival and service processes are known. The parameters of the arrival and service processes of the queues are obtained using an iterative scheme. The results obtained are approximate and validation tests have shown that the model has good accuracy. Using this model, the packet loss, throughput, and queue length distributions were obtained for different traffic parameters and queue sizes.     

Analysis of a finite buffer queue with different scheduling and push-out schemes

A queueing system M₁, M₂/G₁, G₂/1/N with different scheduling and push-out scheme is analyzed in this paper. This work is motivated by the study of the performance of an output link of ATM switches with traffic of two classes with different priorities. However, the queueing model developed in this paper is more general than that of the output link of ATM switches with two-class priority traffic. General service time distributions are allowed for classes 1 and 2 and a general service discipline function, ₁(i, j), is introduced where ₁(i, j) is the probability that a class 1 packet will be served, given that there are i class 1 and j class 2 packets waiting for service. An exact solution is obtained for the loss probabilities for classes 1 and 2, the queue length distribution and the mean waiting time for class 1. The queue length distribution and the mean waiting time for class 2 are calculated approximately. It is shown that the approximation is an upper bound and the error due to the approximation is very small when the loss probability of class 2 is small (e.g., less than 0.01).     

Analysis of a discrete-time queue with general three-state Markovian traffic sources

In this paper, we analyze the performance characteristics of an ATM switch, where cell arrivals are generated according to a three-state Markovian arrival law. This arrival process is an extension for the two-state ON/OFF source model that has already been extensively treated in the literature, and it allows a much more flexible modeling of a wide variety of VBR sources. As a result, for the finite storage capacity case, the system contents distribution, as well as the cell loss ratio are derived. On the other hand, for the infinite storage capacity case, a method for deriving an expression for the probability generating function of the system contents is presented. Furthermore, an approximation (consisting of multiple geometric terms) for the tail distribution of the system contents is given. The accuracy of this approximation as well as the impact of the traffic parameters on the buffer behavior are discussed via some numerical examples.     

Infinitesimal perturbation analysis of a multi-stage tandem of fluid queue with additive loss feedback

In this paper Infinitesimal Perturbation Analysis (IPA) is used to derive the gradient estimators for loss volume and queue workload in a multi-stage tandem of stochastic fluid queues with instantaneous additive loss-feedback for overall congestion control. These gradient estimators are then used to drive a standard stochastic approximation algorithm to optimize, with respect to the buffer limits of the individual queues, an objective function which is the weighted sum of loss volume and queue workload of the queues that make up the tandem.     

Analysis of a multi-server queue with two priority classes and (M, N)-threshold service schedule I: non-preemptive priority

In this paper, we propose an ( M , N )-threshold non-preemptive priority service schedule for a queueing system consisting of two-parallel queues and a multi-server. The arrival process for each queue is Poisson, and the service times are exponentially distributed with different means. We derive the generating functions of the stationary joint queue-length distribution, and then obtain the mean queue length and the mean waiting time for each queue.     

Algebraic structure of some stochastic discrete event systems,with applications

Generalized semi-Markov processes (GSMPs) and stochastic Petri nets (SPNs) are generally regarded as performance models (as opposed to logical models) of discrete event systems. Here we take the view that GSMPs and SPNS are essentially automata (generators) driven by input sequences that determine the timing of events. This view combines the deterministic, logical aspects and the stochastic, timed aspects of the two models. We focus on two conditions, (M) and (CX) (which we previously developed to study monotonicity and convexity properties of GSMPs), and the antimatroid and lattice structure they imply for the language generated by a GSMP or SPN. We illustrate applications of these structural properties in the areas of derivative estimation, simulation variance reduction, parallel simulation, and optimal control.Research supported in part by NSF grant ECS-89-96230.