Minimal LST representations of MAP(n)s: Moment fittings and queueing approximations

A Markovian arrival process of order n, MAP(n), is typically described by two n × n transition rate matrices in terms of rate parameters. While it is straightforward and intuitive, the Markovian representation is redundant since the minimal number of parameters is n² for non‐redundant MAP(n). It is well known that the redundancy complicates exact moment fittings. In this article, we present a minimal and unique Laplace‐Stieltjes transform (LST) representations for MAP(n)s. Even though the LST coefficients vector itself is not a minimal representation, we show that the joint LST of stationary intervals can be represented with the minimum number of parameters. We also propose another minimal representation for MAP(3)s based on coefficients of the characteristic polynomial equations of the two transition rate matrices. An exact moment fitting procedure is presented for MAP(3)s based on two proposed minimal representations. We also discuss how MAP(3)/G/1 departure process can be approximated as a MAP(3). A simple tandem queueing network example is presented to show that the MAP(3) performs better than the MAP(2) in queueing approximations especially under moderate traffic intensities. © 2016 Wiley Periodicals, Inc. Naval Research Logistics 63: 549–561, 2016     

Using a birth‐and‐death process to estimate the steady‐state distribution of a periodic queue

If the number of customers in a queueing system as a function of time has a proper limiting steady‐state distribution, then that steady‐state distribution can be estimated from system data by fitting a general stationary birth‐and‐death (BD) process model to the data and solving for its steady‐state distribution using the familiar local‐balance steady‐state equation for BD processes, even if the actual process is not a BD process. We show that this indirect way to estimate the steady‐state distribution can be effective for periodic queues, because the fitted birth and death rates often have special structure allowing them to be estimated efficiently by fitting parametric functions with only a few parameters, for example, 2. We focus on the multiserver M_t/GI/s queue with a nonhomogeneous Poisson arrival process having a periodic time‐varying rate function. We establish properties of its steady‐state distribution and fitted BD rates. We also show that the fitted BD rates can be a useful diagnostic tool to see if an M_t/GI/s model is appropriate for a complex queueing system. © 2015 Wiley Periodicals, Inc. Naval Research Logistics 62: 664–685, 2015     

Optimal service rates of a service facility with perishable inventory items

In this paper we optimally control service rates for an inventory system of service facilities with perishable products. We consider a finite capacity system where arrivals are Poisson‐distributed, lifetime of items have exponential distribution, and replenishment is instantaneous. We determine the service rates to be employed at each instant of time so that the long‐run expected cost rate is minimized for fixed maximum inventory level and capacity. The problem is modelled as a semi‐Markov decision problem. We establish the existence of a stationary optimal policy and we solve it by employing linear programming. Several numerical examples which provide insight to the behavior of the system are presented. © 2002 Wiley Periodicals, Inc. Naval Research Logistics 49: 464–482, 2002; Published online in Wiley InterScience (www.interscience.wiley.com). DOI 10.1002/nav.10021     

A robust queueing network analyzer based on indices of dispersion

We develop a robust queueing network analyzer algorithm to approximate the steady-state performance of a single-class open queueing network of single-server queues with Markovian routing. The algorithm allows nonrenewal external arrival processes, general service-time distributions and customer feedback. The algorithm is based on a decomposition approximation, where each flow is partially characterized by its rate and a continuous function that measures the stochastic variability over time. This function is a scaled version of the variance-time curve, called the index of dispersion for counts (IDC). The required IDC functions for the external arrival processes can be calculated from the model primitives or estimated from data. Approximations for the IDC functions of the internal flows are calculated by solving a set of linear equations. The theoretical basis is provided by heavy-traffic limits for the flows established in our previous papers. A robust queueing technique is used to generate approximations of the mean steady-state performance at each queue from the IDC of the total arrival flow and the service specification at that queue. The algorithm's effectiveness is supported by extensive simulation studies.     

Optimal control of an M/G/1 queue with impatient priority customers

An optimal operating policy is characterized for the infinite‐horizon average‐cost case of a single server queueing control problem. The server may be turned on at arrival epochs or off at departure epochs. Two classes of customers, each of them arriving according to an independent Poisson processes, are considered. An arriving 1‐customer enters the system if the server is turned on upon his arrival, or if the server is on and idle. In the former case, the 1‐customer is selected for service ahead of those customers waiting in the system; otherwise he leaves the system immediately. 2‐Customers remain in the system until they complete their service requirements. Under a linear cost structure, this paper shows that a stationary optimal policy exists such that either (1) leaves the server on at all times, or (2) turns the server off when the system is empty. In the latter case, we show that the stationary optimal policy is a threshold strategy, this feature being commonplace in most of priority queueing systems and inventory models. However, the optimal policy in our model is determined by two thresholds instead of one. © 2001 John Wiley & Sons, Inc. Naval Research Logistics 48: 201–209, 2001     

Quantifying the performance effects of idle time utilization in multiserver systems

In many practical multiserver queueing systems, servers not only serve randomly arriving customers but also work on the secondary jobs with infinite backlog during their idle time. In this paper, we propose a c‐server model with a two‐threshold policy, denoted by (e d), to evaluate the performance of this class of systems. With such a policy, when the number of idle servers has reached d (<c), then e (<d) idle agents will process secondary jobs. These e servers keep working on the secondary jobs until they find waiting customers exist in the system at a secondary job completion instant. Using the matrix analytic method, we obtain the stationary performance measures for evaluating different (e, d) policies. © 2006 Wiley Periodicals, Inc. Naval Research Logistics, 2007.     

Priority queue with customer upgrades

This article is concerned with a general multi‐class multi‐server priority queueing system with customer priority upgrades. The queueing system has various applications in inventory control, call centers operations, and health care management. Through a novel design of Lyapunov functions, and using matrix‐analytic methods, sufficient conditions for the queueing system to be stable or instable are obtained. Bounds on the queue length process are obtained by a sample path method, with the help of an auxiliary queueing system. © 2012 Wiley Periodicals, Inc. Naval Research Logistics, 2012     

Discrete‐time analysis of MAP/PH/1 multiclass general preemptive priority queue

We use the matrix‐geometric method to study the MAP/PH/1 general preemptive priority queue with a multiple class of jobs. A procedure for obtaining the block matrices representing the transition matrix P is presented. We show that the special upper triangular structure of the matrix R obtained by Miller [Computation of steady‐state probabilities for M/M/1 priority queues, Oper Res 29(5) (1981), 945–958] can be extended to an upper triangular block structure. Moreover, the subblock matrices of matrix R also have such a structure. With this special structure, we develop a procedure to compute the matrix R. After obtaining the stationary distribution of the system, we study two primary performance indices, namely, the distributions of the number of jobs of each type in the system and their waiting times. Although most of our analysis is carried out for the case of K = 3, the developed approach is general enough to study the other cases (K ≥ 4). © 2003 Wiley Periodicals, Inc. Naval Research Logistics 50: 662–682, 2003.     

Replicated batch means for steady‐state simulations

This paper studies a new steady‐state simulation output analysis method called replicated batch means in which a small number of replications are conducted and the observations in these replications are grouped into batches. This paper also introduces and compares methods for selecting the initial state of each replication. More specifically, we show that confidence intervals constructed by the replicated batch means method are valid for large batch sizes and derive expressions for the expected values and variances of the steady‐state mean and variance estimators for stationary processes and large sample sizes. We then use these expressions, analytical examples, and numerical experiments to compare the replicated batch means method with the standard batch means and multiple replications methods. The numerical results, which are obtained from an AR(1) process and a small, nearly‐decomposable Markov chain, show that the multiple replications method often gives confidence intervals with poorer coverage than the standard and replicated batch means methods and that the replicated batch means method, implemented with good choices of initialization method and number of replications, provides confidence interval coverages that range from being comparable with to being noticeably better than coverages obtained by the standard batch means method. © 2006 Wiley Periodicals, Inc. Naval Research Logistics, 2006     

Inventory control under substitutable demand: A stochastic game application

Substitutable product inventory problem is analyzed using the concepts of stochastic game theory. It is assumed that there are two substitutable products that are sold by different retailers and the demand for each product is random. Game theoretic nature of this problem is the result of substitution between products. Since retailers compete for the substitutable demand, ordering decision of each retailer depends on the ordering decision of the other retailer. Under the discounted payoff criterion, this problem is formulated as a two‐person nonzero‐sum stochastic game. In the case of linear ordering cost, it is shown that there exists a Nash equilibrium characterized by a pair of stationary base stock strategies for the infinite horizon problem. This is the unique Nash equilibrium within the class of stationary base stock strategies. © 2002 Wiley Periodicals, Inc. Naval Research Logistics 49: 359–375, 2002; Published online in Wiley InterScience (www.interscience.wiley.com). DOI 10.1002/nav.10018     

On the availability of R out of N repairable systems

An R out of N repairable system consisting of N components and operates if at least R components are functioning. Repairable means that failed components are repaired, and upon repair completion they are as good as new. We derive formulas for the expected up‐time, expected down‐time, and the availability of the system, using Markov renewal processes. We assume that either the repair times of the components are generally distributed and the components' lifetimes are exponential or vice versa. The analysis is done for systems with either cold or warm stand‐by. Numerical examples are given for several life time and repair time distributions. © 2002 Wiley Periodicals, Inc. Naval Research Logistics 49: 483–498, 2002; Published online in Wiley InterScience (www.interscience.wiley.com). DOI 10.1002/nav.10025     

On the reduction of total‐cost and average‐cost MDPs to discounted MDPs

This article provides conditions under which total‐cost and average‐cost Markov decision processes (MDPs) can be reduced to discounted ones. Results are given for transient total‐cost MDPs with transition rates whose values may be greater than one, as well as for average‐cost MDPs with transition probabilities satisfying the condition that there is a state such that the expected time to reach it is uniformly bounded for all initial states and stationary policies. In particular, these reductions imply sufficient conditions for the validity of optimality equations and the existence of stationary optimal policies for MDPs with undiscounted total cost and average‐cost criteria. When the state and action sets are finite, these reductions lead to linear programming formulations and complexity estimates for MDPs under the aforementioned criteria.© 2017 Wiley Periodicals, Inc. Naval Research Logistics 66:38–56, 2019     

A new importance sampling Monte Carlo method for a flow network reliability problem

The exact evaluation of the probability that the maximum st‐flow is greater than or equal to a fixed demand in a stochastic flow network is an NP‐hard problem. This limitation leads one to consider Monte Carlo alternatives. In this paper, we propose a new importance sampling Monte Carlo method. It is based on a recursive use of the state space decomposition methodology of Doulliez and Jamoulle during the simulation process. We show theoretically that the resulting estimator belongs to the variance‐reduction family and we give an upper bound on its variance. As shown by experimental tests, the new sampling principle offers, in many cases, substantial speedups with respect to a previous importance sampling based on the same decomposition procedure and its best performances are obtained when highly reliable networks are analyzed. © 2002 Wiley Periodicals, Inc. Naval Research Logistics 49: 204–228, 2002; DOI 10.1002/nav.10004     

Efficient generation of cycle time‐throughput curves through simulation and metamodeling

A cycle time‐throughput (CT‐TH) curve, which quantifies the relationship of long‐run average cycle time to throughput rate, plays an important role in strategic planning for manufacturing systems. In this paper, a nonlinear regression metamodel supported by queueing theory is developed to represent the underlying CT‐TH curve implied by a manufacturing simulation model. To estimate the model efficiently, simulation experiments are built up sequentially using a multistage procedure. Extensive numerical experiments are presented to demonstrate the effectiveness of the proposed procedure. © 2006 Wiley Periodicals, Inc. Naval Research Logistics, 2007     

Dynamic service rate control for a single‐server queue with Markov‐modulated arrivals

We consider the problem of service rate control of a single‐server queueing system with a finite‐state Markov‐modulated Poisson arrival process. We show that the optimal service rate is nondecreasing in the number of customers in the system; higher congestion levels warrant higher service rates. On the contrary, however, we show that the optimal service rate is not necessarily monotone in the current arrival rate. If the modulating process satisfies a stochastic monotonicity property, the monotonicity is recovered. We examine several heuristics and show where heuristics are reasonable substitutes for the optimal control. None of the heuristics perform well in all the regimes and the fluctuation rate of the modulating process plays an important role in deciding the right heuristic. Second, we discuss when the Markov‐modulated Poisson process with service rate control can act as a heuristic itself to approximate the control of a system with a periodic nonhomogeneous Poisson arrival process. Not only is the current model of interest in the control of Internet or mobile networks with bursty traffic, but it is also useful in providing a tractable alternative for the control of service centers with nonstationary arrival rates. © 2013 Wiley Periodicals, Inc. Naval Research Logistics 60: 661–677, 2013     

Sojourn times in G/M/1 fork‐join networks

We consider a processing network in which jobs arrive at a fork‐node according to a renewal process. Each job requires the completion of m tasks, which are instantaneously assigned by the fork‐node to m task‐processing nodes that operate like G/M/1 queueing stations. The job is completed when all of its m tasks are finished. The sojourn time (or response time) of a job in this G/M/1 fork‐join network is the total time it takes to complete the m tasks. Our main result is a closed‐form approximation of the sojourn‐time distribution of a job that arrives in equilibrium. This is obtained by the use of bounds, properties of D/M/1 and M/M/1 fork‐join networks, and exploratory simulations. Statistical tests show that our approximation distributions are good fits for the sojourn‐time distributions obtained from simulations. © 2008 Wiley Periodicals, Inc. Naval Research Logistics, 2008     

Analysis of the finite‐source multiclass priority queue with an unreliable server and setup time

In this article, we study a queueing system serving multiple classes of customers. Each class has a finite‐calling population. The customers are served according to the preemptive‐resume priority policy. We assume general distributions for the service times. For each priority class, we derive the steady‐state system size distributions at departure/arrival and arbitrary time epochs. We introduce the residual augmented process completion times conditioned on the number of customers in the system to obtain the system time distribution. We then extend the model by assuming that the server is subject to operation‐independent failures upon which a repair process with random duration starts immediately. We also demonstrate how setup times, which may be required before resuming interrupted service or picking up a new customer, can be incorporated in the model. © 2013 Wiley Periodicals, Inc. Naval Research Logistics, 2013     

Optimal pricing and scheduling control of product shipping

In this article, we seek to understand how a capacity‐constrained seller optimally prices and schedules product shipping to customers who are heterogeneous on willingness to pay (WTP) and willingness to wait (WTW). The capacity‐constrained seller does not observe each customer's WTP and WTW and knows only the aggregate distributions of WTP and WTW. The seller's problem is modeled as an M/M/N_s queueing model with multiclass customers and multidimensional information screening. We contribute to the literature by providing an optimal and efficient algorithm. Furthermore, we numerically find that customers with a larger waiting cost enjoys a higher scheduling priority, but customers with higher valuation do not necessarily get a higher scheduling priority. © 2015 Wiley Periodicals, Inc. Naval Research Logistics 62: 215–227, 2015     

A note on optimal pricing for finite capacity queueing systems with multiple customer classes

This article investigates optimal static prices for a finite capacity queueing system serving customers from different classes. We first show that the original multi‐class formulation in which the price for each class is a decision variable can be reformulated as a single dimensional problem with the total load as the decision variable. Using this alternative formulation, we prove an upper bound for the optimal arrival rates for a fairly large class of queueing systems and provide sufficient conditions that ensure the existence of a unique optimal arrival rate vector. We show that these conditions hold for M/M/1/m and M/G/s/s systems and prove structural results on the relationships between the optimal arrival rates and system capacity. © 2008 Wiley Periodicals, Inc. Naval Research Logistics, 2008     

Waiting time analysis for a queueing system with time‐limited service and exponential timer

We consider a single‐queue with exhaustive or gated time‐limited services and server vacations, in which the length of each service period at the queue is controlled by a timer, i.e., the server serves customers until the timer expires or the queue becomes empty, whichever occurs first, and then takes vacations. The customer whose service is interrupted due to the timer expiration may be attended according to nonpreemptive or preemptive service disciplines. For the M/G/1 exhaustive/gated time‐limited service queueing system with an exponential timer and four typical preemptive/nonpreemptive service disciplines, we derive the Laplace—Stieltjes transforms and the moment formulas for waiting times and sojourn times through a unified approach, and provide some new results for these time‐limited service disciplines. © John Wiley & Sons, Inc. Naval Research Logistics 48: 638–651, 2001.