An explicit solution to a tandem queueing model

We consider two queues in tandem, each with an exponential server, and with deterministic arrivals to the first queue. We obtain an explicit solution for the steady state distribution of the process (N₁(t), N₂(t), Y(t)), where N_j(t) is the queue length in the jth queue and Y(t) measures the time elapsed since the last arrival. Then we obtain the marginal distributions of (N₁(t), N₂(t)) and of N₂(t). We also evaluate the solution in various limiting cases, such as heavy traffic. This revised version was published online in June 2006 with corrections to the Cover Date.     

The busy period distribution in a closed tandem of queues

We derive the busy period distribution in a closed tandem of FCFS queues with general service times.     

Waiting time analysis of a two-stage queueing system with priorities

A two-stage queueing system with two types of customers and non-preemptive priorities is analyzed. There is no waiting space between stages and so the blocking phenomenon is observed. The arrivals follow a Poisson distribution for the high priority customers and a gamma distribution for the low priority customers, while all service times are arbitrarily distributed. We derive expressions for the Laplace transform of the waiting time density of a low priority customer both in the transient and the steady state.     

Rough asymptotics for tandem non-homogeneous $$M/G/\infty$$ queues via Poissonized empirical processes

We obtain a large deviations principle and moderate deviations principle for the joint distribution of the queue length processes and departure process for tandem queues. The results are obtained by applying a result providing necessary and sufficient conditions on a class of functions for a large deviations principle and moderate deviations principle to hold for a Poissonized empirical process over the class of functions. As an application, we examine how large queue lengths and numbers of departures are built up. This revised version was published online in June 2006 with corrections to the Cover Date.     

A two-stage tandem queue attended by a moving server with holding and switching costs

We consider a two-stage tandem queue attended by a moving server, with homogeneous Poisson arrivals and general service times. Two different holding costs for stages 1 and 2 and different switching costs from one stage to the other are considered. We show that the optimal policy in the second stage is greedy; and if the holding cost rate in the second stage is greater or equal to the rate in the first stage, then the optimal policy in the second stage is also exhaustive. Then, the optimality condition for sequential service policy in systems with zero switchover times is introduced. Considering some properties of the optimal policy, we then define a Triple-Threshold (TT) policy to approximate the optimal policy in the first stage. Finally, a model is introduced to find the optimal TT policy, and using numerical results, it is shown that the TT policy accurately approximates the optimal policy. This revised version was published online in June 2006 with corrections to the Cover Date.     

An analytical solution for a tandem queue with blocking

The model considered in this paper involves a tandem queue with two waiting lines, and as soon as the second waiting line reaches a certain upper limit, the first line is blocked. Both lines have exponential servers, and arrivals are Poisson. The objective is to determine the joint distribution of both lines in equilibrium. This joint distribution is found by using generalized eigenvalues. Specifically, a simple formula involving the cotangent is derived. The periodicity of the cotangent is then used to determine the location of the majority of the eigenvalues. Once all eigenvalues are found, the eigenvectors can be obtained recursively. The method proposed has a lower computational complexity than all other known methods. This revised version was published online in June 2006 with corrections to the Cover Date.     

Optimality of a Threshold Policy in theM/M/ queue with repeated vacations

Consider anM/M/1 queueing system with server vacations where the server is turned off as soon as the queue gets empty. We assume that the vacation durations form a sequence of i.i.d. random variables with exponential distribution. At the end of a vacation period, the server may either be turned on if the queue is non empty or take another vacation. The following costs are incurred: a holding cost ofh per unit of time and per customer in the system and a fixed cost of each time the server is turned on. We show that there exists a threshold policy that minimizes the long-run average cost criterion. The approach we use was first proposed in Blanc et al. (1990) and enables us to determine explicitly the optimal threshold and the optimal long-run average cost in terms of the model parameters.     

Optimal integrated production and inventory control of an assemble-to-order system with multiple non-unitary demand classes

We study a pure assemble-to-order system subject to multiple demand classes where customer orders arrive according to a compound Poisson process. The finished product is assembled from m different components that are produced on m distinct production facilities in a make-to-stock fashion. We show that the optimal production policy of each component is a state-dependent base-stock policy and the optimal inventory allocation policy is a multi-level state-dependent rationing policy. Using numerical experimentation, we first study the system behavior as a function of order size variability and order size. We show that the optimal average cost rate is more sensitive to order size variability than to order size. We also compare the optimal policy to the first-come first-serve policy and show that there is great benefit to inventory rationing. We also propose two simple heuristics and show that these can effectively mimic the optimal policy which is generally much more difficult to determine and, especially, to implement.     

Managing an integrated production inventory system with information on the production and demand status and multiple non-unitary demand classes

In this paper, we study a system consisting of a manufacturer or supplier serving several retailers or clients. The manufacturer produces a standard product in a make-to-stock fashion in anticipation of orders emanating from n retailers with different contractual agreements hence ranked/prioritized according to their importance. Orders from the retailers are non-unitary and have sizes that follow a discrete distribution. The total production time is assumed to follow a k₀-Erlang distribution. Order inter-arrival time for class l demand is assumed to follow a k_l-Erlang distribution. Work-in-process as well as the finished product incur a, per unit per unit of time, carrying cost. Unsatisfied units from an order from a particular demand class are assumed lost and incur a class specific lost sale cost. The objective is to determine the optimal production and inventory allocation policies so as to minimize the expected total (discounted or average) cost. We formulate the problem as a Markov decision process and show that the optimal production policy is of the base-stock type with base-stock levels non-decreasing in the demand stages. We also show that the optimal inventory allocation policy is a rationing policy with rationing levels non-decreasing in the demand stages. We also study several important special cases and provide, through numerical experiments, managerial insights including the effect of the different sources of variability on the operating cost and the benefits of such contracts as Vendor Managed Inventory or Collaborative Planning, Forecasting, and Replenishment. Also, we show that a heuristic that ignores the dependence of the base-stock and rationing levels on the demands stages can perform very poorly compared to the optimal policy.     

The robustness of the semi-Markov and delay time single-component inspection models to the Markov assumption

The context of planned preventive maintenance lends itself readilyto probabilistic modelling. Indeed, many of the published theoreticalmodels to be found in the literature adopt a Markov approach,where states are usually ‘operating’, ‘operatingat one of several levels of deterioration’, and ‘failed’.However, most of these models assume the required Markovianproperty and do not address the issue of testing the assumption,or the related task of estimating parameters. It is possiblethat data are inadequate to test the assumption, or that theMarkov property is believed to be not strictly valid, but acceptableas an approximation. In this paper we consider within a specificinspection–maintenance context the robustness of a Markov-basedmodel when the Markov assumption is not valid. This is achievedby comparing the output of an exact delay time model of an inspection–maintenanceproblem with that of a semi-Markov approximation. The importanceof establishing the vadility of the Markov property in the modellingapplication is highlighted. If the plant behaviour is seen tobe nearly Markov, in the case considered the semi-Markov modelgives a good approximation to the exact model. Conversley ifthe Markov assumption is not a good approximation, the semi-Markovmodel can lead to inappropriate advice.     

Multivariate Bayesian process control for a finite production run

Most industrial products and processes are characterized by several, typically correlated measurable variables, which jointly describe the product or process quality. Various control charts such as Hotelling’s T², EWMA and CUSUM charts have been developed for multivariate quality control, where the values of the chart parameters, namely the sample size, sampling interval and the control limits are determined to satisfy given economic and/or statistical requirements. It is well known that this traditional non-Bayesian approach to a control chart design is not optimal, but very few results regarding the form of the optimal Bayesian control policy have appeared in the literature, all limited to a univariate chart design. In this paper, we consider a multivariate Bayesian process mean control problem for a finite production run under the assumption that the observations are values of independent, normally distributed vectors of random variables. The problem is formulated in the POMDP (partially observable Markov decision process) framework and the objective is to determine a control policy minimizing the total expected cost. It is proved that under standard operating and cost assumptions the control limit policy is optimal. Cost comparisons with the benchmark chi-squared chart and the MEWMA chart show that the Bayesian chart is highly cost effective, the savings are larger for smaller values of the critical Mahalanobis distance between the in-control and out-of-control process mean.     

Optimal control of a production-inventory system with customer impatience

We consider the control of a production-inventory system with impatient customers. We show that the optimal policy can be described using two thresholds: a production base-stock level that determines when production takes place and an admission threshold that determines when orders should be accepted. We describe an algorithm for computing the performance of the system for any choice of base-stock level and admission threshold. In a numerical study, we compare the performance of the optimal policy against several other policies.     

Admission control and pricing in a queue with batch arrivals

We investigate a problem of admission control in a queue with batch arrivals. We consider a single server with exponential service times and a compound Poisson arrival process. Each arriving batch computes its expected benefit and decides whether or not to enter the system. The controller’s problem is to set state dependent prices for arriving batches. Once prices have been set we formulate the admission control problem, derive properties of the value function, and obtain the optimal admission policy.     

Optimal control of tandem reentrant queues

We consider optimal policies for reentrant queues in which customers may be served several times at the same station. We show that for tandem reentrant queues the last-buffer first-served (LBFS) policy stochastically maximizes the departure process. This revised version was published online in June 2006 with corrections to the Cover Date.     

Decomposable jump decision processes

A large class of continuous parameter jump decision processes is considered. Pontryagin's Maximum Principle is used to derive a necessary condition for optimality. An optimal strategy may frequently be obtained explicitly.     

Call Admission: A New Approach to Quality of Service

Quality of service guarantees are an important and much discussed aspect of ATM network design. However, there is no standard definition of quality of service. Moreover, some often-used criteria seem quite crude. We consider call admission to a bufferless ATM multiplexer with on/off sources. A new criterion for a guarantee on average cell loss is proposed. This criterion represents the quality of service from the point of view of the user, and is thus more reliable. We calculate the optimal policy that minimizes blocking subject to the guarantee, when there is only one type of user.The measure of cell-loss we propose is applicable to a wide range of models. It gives rise to a mathematical programming formulation, which we derive explicitly for our case.     

OPTIMAL CONTROL FOR A TANDEM NETWORK OF QUEUES WITH BLOCKING

1.IntroductionWeconsideratwo-stationtandemqueuewithnointermediatebuffer.Jobsatthefirststationmaybeblockedwhenthefollowingstationisoccupiedbyanotherjob.Thatis,ajobisblockedatstationoneuponservicecompletionifthefollowingstationisbeingoccupiedbyanotherjob.Afixedcostischargedforeveryenteringjob,forexample,thiscostcanbetheinputrawmaterialcostinamanufacturingsystem.Jobsinthesystemaresubjecttoaholdingcost.Arewardiscollectedwhenajobdepartsfromthesystem(i.e.,fromthesecondstation).Theproblemistocontro…     

Fluid approximation of a controlled multiclass tandem network

A two-station, four-class queueing network with dynamic scheduling of servers is analyzed. It is shown that the corresponding Markov decision problem converges under fluid scaling to a fluid optimal control model. The structure of the optimal policy for the fluid network, and of an asymptotically optimal policy for the queueing network are derived in an explicit form. They concur with the tandem μ-rule, if this policy gives priority to the same flow of customers in both stations. In general, they are monotone with a linear switching surface. This revised version was published online in June 2006 with corrections to the Cover Date.     

Optimal buffer allocation in tandems of last come first served queues

A large fixed number of buffer spaces is given. We consider the problem of allocating these spaces among the nodes of a tandem of last-come-first-served queues with general service time distributions and Poisson external arrivals so as to optimize some performance criterion associated with the time to buffer overflow, such as maximizing its mean or maximizing the probability that it exceeds some value. Consider the following rule of thumb: allocate the buffer spaces in inverse proportion to the logarithms of the effective service rates at the nodes. Here effective service rate denotes the ratio of the service rate to the stationary arrival rate. We prove that this rule of thumb achieves a nearly optimal buffer allocation under the assumption that the service time distributions satisfy an exponential tail condition. This problem has been studied earlier in the context of Jackson networks, where it was shown that the same rule of thumb achieves an allocation that is close to optimal. The technique of proof here is similar, but there are important differences. Both Jackson networks and the LCFS tandems considered here are product form networks (with infinite buffers). Optimism should lead us to expect that the near optimality of this rule of thumb holds much more generally for product-form networks, but this remains a conjecture at present.Research supported by NSF under NCR 8857731, by AT&T, and by Bellcore Inc.Research supported by IBM under a graduate fellowship.