Exact analysis of a two-workstation one-buffer flow line with parallel unreliable machines

This paper examines a model of a serial flow line with two workstations and an intermediate buffer. Each workstation consists of multiple unreliable parallel machines which are not necessarily identical, viz., the processing times, failure times and repair times of the parallel machines at each workstation are assumed to be exponentially distributed with non-identical mean rates. The system under consideration is solved via exact Markovian analysis. More specifically, a recursive algorithm that generates the transition matrix for any value of the intermediate buffer capacity is developed and all possible transition equations are derived and solved analytically. Once the transition equations are solved the performance measures of the model under consideration can be easily evaluated. This model may be used as a decomposition block for solving larger flow lines with parallel unreliable machines at each workstation.     

A decomposition method for approximate evaluation of continuous flow multi-stage lines with general Markovian machines

In this paper, a decomposition method for evaluating the performance of continuous flow lines with machines characterized by general Markovian fluid models and finite capacity buffers is proposed. This study uses the exact solution of general two-stage Markovian fluid models as a building block. Decomposition equations are provided to propagate the effect of partial and complete blocking and starvation phenomena throughout the system. A decomposition algorithm that solves the new decomposition equations is proposed. Numerical results prove the good accuracy of the developed method. In particular, a comparison with existing techniques shows that our method is generally more accurate, especially in the estimation of the average buffer levels. Moreover, additional information can be collected by the application of our approach which enables a deeper analysis of the system behavior. Finally, the generality of the approach allows for modeling and studying many different system configurations within a unique framework, also including several previously uninvestigated layouts.     

Time dependent analysis of finite buffer fluid flows and risk models with a dividend barrier

Based on the matrix-analytic approach to fluid flows initiated by Ramaswami, we develop an efficient time dependent analysis for a general Markov modulated fluid flow model with a finite buffer and an arbitrary initial fluid level at time 0. We also apply this to an insurance risk model with a dividend barrier and a general Markovian arrival process of claims with possible dependencies in successive inter-claim intervals and in claim sizes. We demonstrate the implementability and accuracy of our algorithms through a set of numerical examples that could also serve as test cases for comparing other solution approaches.      

The combinatorics of birth-death processes and applications to queues

In this paper we present a combinatorial technique which allows the derivation of the transition functions of general birth-death processes. This method provides a flexible tool for the transient analysis of Markovian queueing systems with state dependent transition rates, like M/M/c models or systems with balking and reneging. This revised version was published online in June 2006 with corrections to the Cover Date.     

Multi-state throughput analysis of a two-stage manufacturing system with parallel unreliable machines and a finite buffer

This paper models and analyzes the throughput of a two-stage manufacturing system with multiple independent unreliable machines at each stage and one finite-sized buffer between the stages. The machines follow exponential operation, failure, and repair processes. Most of the literature uses binary random variables to model unreliable machines in transfer lines and other production lines. This paper first illustrates the importance of using more than two states to model parallel unreliable machines because of their independent and asynchronous operations in the parallel system. The system balance equations are then formulated based on a set of new notations of vector manipulations, and are transformed into a matrix form fitting the properties of the Quasi-Birth–Death (QBD) process. The Matrix-Analytic (MA) method for solving the generic QBD processes is used to calculate the system state probability and throughput. Numerical cases demonstrate that solution method is fast and accurate in analyzing parallel manufacturing systems, and thus prove the applicability of the new model and the effectiveness of the MA-based method. Such multi-state models and their solution techniques can be used as a building block for analyzing larger, more complex manufacturing systems.     

Performance measures of a multi-layer Markovian fluid model

Our goal is to model the behaviour of the fluid in a buffer with threshold controls with a wide range of behaviour possible at the boundaries. To model this, we consider a class of Markovian fluid flow models with several layers, each with their own parameters, separated by boundaries. The behaviour of the fluid at each boundary is modelled by parameters unique to that boundary. We derive the Laplace-Stieltjes transforms of time-related performance measures of this model. This is illustrated with numerical examples. All results are obtained via techniques within the fluid flow environment, and useful physical interpretations are presented.     

Profit maximization in flexible serial queueing networks

We analyze the tradeoff between efficiency and service quality in tandem systems with flexible servers and finite buffers. We reward efficiency by assuming that a revenue is earned each time a job is completed, and penalize poor service quality by incorporating positive holding costs. We study the dynamic assignment of servers to tasks with the objective of maximizing the long-run average profit. For systems of arbitrary size, structured service rates, and linear or nonlinear holding costs, we determine the server assignment policy that maximizes the profit. For systems with two stations, two servers with arbitrary service rates, and linear holding costs, we show that the optimal server assignment policy is of threshold type and determine the value of this threshold as a function of the revenue and holding cost. The threshold can be interpreted as the best possible buffer size, and hence our results prove the equivalence of addressing service quality via a holding cost and via limiting the buffer size. Furthermore, we identify the optimal buffer size when each buffer space comes at a cost. We provide numerical results that suggest that the optimal policy also has a threshold structure for nonlinear holding costs. Finally, for larger systems with arbitrary service rates, we propose effective server assignment heuristics.     

The cross-entropy method with patching for rare-event simulation of large Markov chains

There are various importance sampling schemes to estimate rare event probabilities in Markovian systems such as Markovian reliability models and Jackson networks. In this work, we present a general state-dependent importance sampling method which partitions the state space and applies the cross-entropy method to each partition. We investigate two versions of our algorithm and apply them to several examples of reliability and queueing models. In all these examples we compare our method with other importance sampling schemes. The performance of the importance sampling schemes is measured by the relative error of the estimator and by the efficiency of the algorithm. The results from experiments show considerable improvements both in running time of the algorithm and the variance of the estimator.     

Optimal solutions for a dock assignment problem with trailer transportation

This paper presents a model for a dock assignment problem, where trailers need to be assigned to gates for a given period of time for loading or unloading activities. The parking lot is used as a buffer zone. Transportation between the parking lot and the gates is performed by additional resources called terminal tractors. The problem is modeled as a three-stage flexible flow shop, where the first and the third stage share the same identical parallel machines and the second stage consists of a different set of identical parallel machines. We examine multiple integer-programming formulations for the parallel-machine model in stage two and for the three-stage flow shop and we provide extensive computational results. Our goal is to explore the limits of the instance sizes that can be solved to guaranteed optimality within acceptable running times using integer programming.     

Discrete storage processes and their Poisson flow and fluid flow approximations

Consider discrete storage processes that are modulated by environmental processes. Environmental processes cause interruptions in the input and/or output processes of the discrete storage processes. Due to the difficulties encountered in the exact analysis of such discrete storage systems, often Poisson flow and/or fluid flow models with the same modulating environmental processes are proposed as approximations for these systems. The analysis of Poisson flow and fluid flow models is much easier than that of the discrete storage processes. In this paper we give sufficient conditions under which the content of the discrete storage processes can be bounded by the Poisson flow and the fluid flow models. For example, we show that Poisson flow models and the fluid flow models developed by Kosten (and by Anick, Mitra and Sondhi) can be used to bound the performance of infinite (finite) source packetized voice/data communication systems. We also show that a Poisson flow model and the fluid flow model developed by Mitra can be used to bound the buffer content of a two stage automatic transfer line. The potential use of the bounding techniques presented in this paper, of course, transcends well beyond these examples.Supported in part by NSF grant DMS-9308149.     

A Genetic Algorithm for the Allocation of Buffer Storage Capacities in a Production Line with Unreliable Machines

In this paper, we consider a flow-line manufacturing system organized as a series of workstations separated by finite buffers. The failure and repair times of machines are supposed to be exponentially distributed. The production rate of each machine is deterministic, and different machines may have different production rates. The buffer allocation problem consists in determining the buffer capacities with respect to a given optimality criterion, which depends on the average production rate of the line, the buffer acquisition and installation cost, and the inventory cost. For this problem we propose a genetic algorithm where the tentative solutions are evaluated with an approximate method based on the Markov-model aggregation approach.     

On the Decay Rates of Buffers in Continuous Flow Lines

Consider a tandem system of machines separated by infinitely large buffers. The machines process a continuous flow of products, possibly at different speeds. The life and repair times of the machines are assumed to be exponential. We claim that the overflow probability of each buffer has an exponential decay, and provide an algorithm to determine the exact decay rates in terms of the speeds and the failure and repair rates of the machines. These decay rates provide useful qualitative insight into the behavior of the flow line. In the derivation of the algorithm we use the theory of Large Deviations.     

On a methodology for discrete–continuous scheduling

Discrete–continuous problems of scheduling nonpreemptable jobs on parallel machines are considered. The problems arise e.g. when jobs are assigned to multiple parallel processors driven by a common electric, hydraulic or pneumatic power source. Existing models have assumed job processing rates as a function of the number of jobs currently being processed, or equivalently the number of machines currently in operation. In this paper a more general model is proposed in which processing rates of a job assigned to a machine depend on the amount of a continuous, i.e. continuously divisible resource (e.g. power) allotted to this job at a time. Thus the problem consists of two interrelated subproblems: (i) to sequence jobs on machines, and (ii) to allocate the continuous resource among jobs already sequenced. We provide a comprehensive analysis of the problem. This includes properties of optimal schedules, efficiently (in particular analytically) solvable cases, formulations of the possibly simplest mathematical programming problems for finding optimal schedules in the general case, heuristics and the worst-case analysis. Although our objective function in this paper is to minimize makespan of a set of independent jobs, the presented methodology can be applied to other criteria, precedence-related jobs, and many resource types (apart from, or instead of machines).     

Tandem queueing system with infinite and finite intermediate buffers and generalized phase-type service time distribution

A tandem queueing system with infinite and finite intermediate buffers, heterogeneous customers and generalized phase-type service time distribution at the second stage is investigated. The first stage of the tandem has a finite number of servers without buffer. The second stage consists of an infinite and a finite buffers and a finite number of servers. The arrival flow of customers is described by a Marked Markovian arrival process. Type 1 customers arrive to the first stage while type 2 customers arrive to the second stage directly. The service time at the first stage has an exponential distribution. The service times of type 1 and type 2 customers at the second stage have a phase-type distribution with different parameters. During a waiting period in the intermediate buffer, type 1 customers can be impatient and leave the system. The ergodicity condition and the steady-state distribution of the system states are analyzed. Some key performance measures are calculated. The Laplace–Stieltjes transform of the sojourn time distribution of type 2 customers is derived. Numerical examples are presented.     

A Finite Buffer Fluid Queue Driven by a Markovian Queue

We consider a finite buffer fluid queue receiving its input from the output of a Markovian queue with finite or infinite waiting room. The input flow into the fluid queue is thus characterized by a Markov modulated input rate process and we derive, for a wide class of such input processes, a procedure for the computation of the stationary buffer content of the fluid queue and the stationary overflow probability. This approach leads to a numerically stable algorithm for which the precision of the result can be specified in advance.     

The Use of Derivatives for Optimizing Steady State Queues

To design queueing systems in an optimal way, one needs derivatives of the main queueing measures, such as the average number in the system and the throughput. In this paper we show how such measures can be obtained in a Markovian environment. For simplicity, we restrict our attention to queues with Poisson arrivals, having either a finite buffer capacity or a finite calling population. For these queues, we first determine the derivatives of their steady state probabilities, which allow us to find the derivatives of throughput and average number in the system. A number of examples show how these derivatives can be used for the purpose of optimization.     

Multiclass Markovian fluid queues

This paper considers a multiclass Markovian fluid queue with a buffer of infinite capacity. Input rates of fluid flows in respective classes and the drain rate from the buffer are modulated by a continuous-time Markov chain with finite states. We derive the joint Laplace-Stieltjes transform for the stationary buffer contents in respective classes, assuming the FIFO service discipline. Further we develop a numerically feasible procedure to compute the joint and marginal moments of the stationary buffer contents in respective classes. Some numerical examples are then provided.     

Mean Buffer Contents in Discrete-Time Single-Server Queues with Heterogeneous Sources

We consider discrete-time single-server queues fed by independent, heterogeneous sources with geometrically distributed idle periods. While being active, each source generates some cells depending on the state of the underlying Markov chain. We first derive a general and explicit formula for the mean buffer contents in steady state when the underlying Markov chain of each source has finite states. Next we show the applicability of the general formula to queues fed by independent sources with infinite-state underlying Markov chains and discrete phase-type active periods. We then provide explicit formulas for the mean buffer contents in queues with Markovian autoregressive sources and greedy sources. Further we study two limiting cases in general settings, one is that the lengths of active periods of each source are governed by an infinite-state absorbing Markov chain, and the other is the model obtained by the limit such that the number of sources goes to infinity under an appropriate normalizing condition. As you will see, the latter limit leads to a queue with (generalized) M/G/∞ input sources. We provide sufficient conditions under which the general formula is applicable to these limiting cases.AMS subject classification: 60K25, 60K37, 60J10This revised version was published online in June 2005 with corrected coverdate     

Pricing techniques for self regulation in Vehicle Sharing Systems

We study self regulation through pricing for Vehicle Sharing Systems (VSS). Without regulation VSS have poor performances. We want to improve the efficiency of VSS using pricing as incentive. We take as base model a Markovian formulation of a closed queuing network with finite buffer and time dependent service time. This model is unfortunately intractable for the size of instances we want to tackle. We discuss heuristics: a scenario approach, a fluid approximation, simplified stochastic models and asymptotic approximations. We compare these heuristics on toy cities.     

Open queueing networks in discrete time-some limit theorems

A finite number of nodes, each with a single server and infinite buffers, is considered in discrete time. The service may be FIFO and the service times are constant. The external arrivals and the routing decision variables form a general stationary sequence. Stability of the system is proved under these assumptions. Extension to multiple servers at a node and general stationary distributions holds. If the external input is i.i.d. and the routing is Markovian then stochastic ordering, continuity of stationary distributions, rates of convergence, a functional CLT and a functional LIL and various other limit theorems for the queue length process are also proved. Generalizations to multiple servers at nodes, customers with priority, multiple customer classes, general service length and Markov modulated external arrival cases are discussed.