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.     

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     

Level crossing analysis of priority queues and a conservation identity for vacation models

The two purposes of this article are to illustrate the power and simplicity of level crossing analysis and to present a conservation identity for M/G/1 priority queues with server vacations. To illustrate the use of level crossing analysis we apply it to preemptive (resume) priority M/G/1 queues with single- and multiple-server vacations considered by Kella and Yechiali (1986) and to non-preemptive priority M/M/c queues considered by Kella and Yechiali (1985). The conservation identity presented here states that the ratios of mean waiting times in an M/G/1 queue with and without server vacation policies are independent of the service discipline for first come first served, shortest processing time, shortest processing time within generations and non-preemptive priority service disciplines.     

Priorities in M/G/1 queue with server vacations

The M/G/1 queue with single and multiple server vacations is studied under both the preemptive and non-preemptive priority regimes. A unified methodology is developed to derive the Laplace-Stieltjes transform and first two moments of the waiting time W_k of a class-k customer for each of the four models analyzed. The results are given a probabilistic representation involving mean residual lifetimes.     

Arrival and departure state distributions in the general bulk‐service queue

In this paper, we give an explicit relation between steady‐state probability distributions of the buffer occupancy at customer entrance and departure epochs, for the classical single‐server system G/G^[N]/1 with batch services and for the finite capacity case. The method relies on level‐crossing arguments. For the particular case of Poisson input, we also express the loss probability in terms of state probabilities at departure epochs, yielding probabilities observed by arriving customers. This work provides the “bulk queue” version of a result established by Burke, who stated the equality between probabilities at arrival and departure epochs for systems with “unit jumps.” © 1999 John Wiley & Sons, Inc. Naval Research Logistics 46: 107–118, 1999     

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     

The NBUL class of life distribution and replacement policy comparisons

Let X and X_τ denote the lifetime and the residual life at age τ of a system, respectively. X is said to be a NBUL random variable if X_τ is smaller than X in Laplace order, i.e., X_τ ≤_L X. We obtain some characterizations for this class of life distribution by means of the lifetime of a series system and the residual life at random time. We also discuss preservation properties for this class of life distribution under shock models. Finally, under the assumption that the lifetimes have the NBUL property, we make stochastic comparisons between some basic replacement policies. © 2001 John Wiley & Sons, Inc. Naval Research Logistics 48: 578–591, 2001.     

The threshold policy in the M/G/1 queue with server vacations

This article deals with the M/G/1 queue with server vacations in which the return of the server to service depends on the number of customers present in the system. The main goal is optimization, which is done under the average cost criterion in the multiple- and single-vacation models as well as for the “total cost for one busy cycle” criterion in the multiple-vacation case. Expressions that characterize the optimal number of customers, below which the server should not start a new service period, are exhibited for the various cases. It is found that under the average cost criterion, the expression may be universal in the sense that it may hold for a general class of problems including such that arise in production planning and inventory theory (for the particular cost structure discussed).     

A queueing system with vacations after N services

This article is devoted to the study of an M/G/1 queue with a particular vacation discipline. The server is due to take a vacation as soon as it has served exactly N customers since the end of the previous vacation. N may be either a constant or a random variable. If the system becomes empty before the server has served N customers, then it stays idle until the next customer arrival. Such a vacation discipline arises, for example, in production systems and in order picking in warehouses. We determine the joint transform of the length of a visit period and the number of customers in the system at the end of that period. We also derive the generating function of the number of customers at a random instant, and the Laplace–Stieltjes transform of the delay of a customer. © 2015 Wiley Periodicals, Inc. Naval Research Logistics 62: 646–658, 2015     

Approximations for heavily loaded G/GI/n + GI queues

Motivated by applications to service systems, we develop simple engineering approximation formulas for the steady‐state performance of heavily loaded G/GI/n+GI multiserver queues, which can have non‐Poisson and nonrenewal arrivals and non‐exponential service‐time and patience‐time distributions. The formulas are based on recently established Gaussian many‐server heavy‐traffic limits in the efficiency‐driven (ED) regime, where the traffic intensity is fixed at ρ > 1, but the approximations also apply to systems in the quality‐and‐ED regime, where ρ > 1 but ρ is close to 1. Good performance across a wide range of parameters is obtained by making heuristic refinements, the main one being truncation of the queue length and waiting time approximations to nonnegative values. Simulation experiments show that the proposed approximations are effective for large‐scale queuing systems for a significant range of the traffic intensity ρ and the abandonment rate θ, roughly for ρ > 1.02 and θ > 2.0. © 2016 Wiley Periodicals, Inc. Naval Research Logistics 63: 187–217, 2016     

Single batch machine scheduling with deliveries

We consider the problem of scheduling a set of n jobs on a single batch machine, where several jobs can be processed simultaneously. Each job j has a processing time p_j and a size s_j. All jobs are available for processing at time 0. The batch machine has a capacity D. Several jobs can be batched together and processed simultaneously, provided that the total size of the jobs in the batch does not exceed D. The processing time of a batch is the largest processing time among all jobs in the batch. There is a single vehicle available for delivery of the finished products to the customer, and the vehicle has capacity K. We assume that K = rD, where and r is an integer. The travel time of the vehicle is T; that is, T is the time from the manufacturer to the customer. Our goal is to find a schedule of the jobs and a delivery plan so that the service span is minimized, where the service span is the time that the last job is delivered to the customer. We show that if the jobs have identical sizes, then we can find a schedule and delivery plan in time such that the service span is minimum. If the jobs have identical processing times, then we can find a schedule and delivery plan in time such that the service span is asymptotically at most 11/9 times the optimal service span. When the jobs have arbitrary processing times and arbitrary sizes, then we can find a schedule and delivery plan in time such that the service span is asymptotically at most twice the optimal service span. We also derive upper bounds of the absolute worst‐case ratios in both cases. © 2015 Wiley Periodicals, Inc. Naval Research Logistics 62: 470–482, 2015     

Sojourn times in a two‐stage queueing network with blocking

The model considered in this paper involves a tandem queue consisting of a sequence of two waiting lines. The main feature of our model is blocking, i.e., as soon as the second waiting line reaches a certain upper limit, the first line is blocked. The input of units to the tandem queue is the MAP (Markovian arrival process), and service requirements are of phase type. Our objective is to study the sojourn time distribution under the first‐come‐first‐serve discipline by analyzing the sojourn time through times until absorption in appropriately defined quasi‐birth‐and‐death processes and continuous‐time Markov chains. © 2004 Wiley Periodicals, Inc. Naval Research Logistics, 2004     

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     

A note on sojourn times in M/G/1 queues with instantaneous,bernoulli feedback

Queueing systems which include the possibility for a customer to return to the same server for additional service are called queueing systems with feedback. Such systems occur in computer networks for example. In these systems a chosen customer will wait in the queue, be serviced and then, with probability p, return to wait again, be serviced again and continue this process until, with probability (1 – p) = q, it departs the system never to return. The time of waiting plus service time, the nth time the customer goes through, we will call his nth sojourn time. The (random) sum of these sojourn times we will call the total sojourn time (abbreviated, sojourn time when there is no confusion which sojourn time we are talking about). In this paper we study the total sojourn time in a queueing system with feedback. We give the details for M/G/1 queues in which the decision to feedback or not is a Bernoulli process. While the details of the computations can be more difficult, the structure of the sojourn time process is unchanged for the M/G/1 queue with a more general decision process as will be shown. We assume the reader is familiar with Disney, McNickle and Simon [1].     

On‐line algorithms for minimizing makespan on batch processing machines

We consider problem of scheduling jobs on‐line on batch processing machines with dynamic job arrivals to minimize makespan. A batch machine can handle up to B jobs simultaneously. The jobs that are processed together from a batch, and all jobs in a batch start and complete at the same time. The processing time of a batch is given by the longest processing time of any job in the batch. Each job becomes available at its arrival time, which is unknown in advance, and its processing time becomes known upon its arrival. In the first part of this paper, we address the single batch processing machine scheduling problem. First we deal with two variants: the unbounded model where B is sufficiently large and the bounded model where jobs have two distinct arrival times. For both variants, we provide on‐line algorithms with worst‐case ratio (the inverse of the Golden ratio) and prove that these results are the best possible. Furthermore, we generalize our algorithms to the general case and show a worst‐case ratio of 2. We then consider the unbounded case for parallel batch processing machine scheduling. Lower bound are given, and two on‐line algorithms are presented. © 2001 John Wiley & Sons, Inc. Naval Research Logistics 48: 241–258, 2001     

On the (S-1, S) inventory model under compound poisson demands and i.i.d. unit resupply times

We analyze an (S-1, S) inventory model with compound Poisson demands. Resupply times for individual units are independent and identically distributed. Such a model can also be characterized as an M^X/G/∞ queue. We derive expressions of performance measure such as the steady-state distribution and the expectation of the number of backlogged units. In addition, numerical examples are included to reflect the effects of i.i.d. unit resupply times. © 1996 John Wiley & Sons, Inc.     

Estimating a survival curve when new is better than used in expectation

Let X be a positive random variable. The distribution F of X is said to be “new better than used in expectation,” or “NBUE,” if E(X) ⩾ E(X – t|X > t) for all t ⩾ 0. Suppose X₁, …, X_n, is a random sample from an NBUE distribution F. The problem of estimating F by a distribution which is itself NBUE is considered. The estimator G_n, defined as the NBUE distribution supported on the sample which minimizes the (sup norm) distance between the NBUE class and the empirical distribution function, is studied. The strong uniform consistency of G_n, is proven, and a numerical algorithm for obtaining G_n, is given. Our approach is applied to provide an estimate of the distribution of lifetime following the diagnosis of chronic granulocytic leukemia based on data from a National Cancer Institute study.     

Waiting times for M/G/1 queues with service-time or delay-dependent server vacations

This article shows how to determine the stationary distribution of the virtual wait in M/G/1 queues with either one-at-a-time or exhaustive server vacations, depending on either service times or accrued workload. For the first type of dependence, each vacation time is a function of the immediately preceding service time or of whether the server finds the system empty after returning from vacation. In this way, it is possible to model situations such as long service times followed by short vacations, and vice versa. For the second type of dependence, the vacation time assigned to an arrival to follow its service is a function of the level of virtual wait reached. By this device, we can model situations in which vacations may be shortened whenever virtual delays have gotten excessive. The method of analysis employs level-crossing theory, and examples are given for various cases of service and vacation-time distributions. A closing discussion relates the new model class to standard M/G/1 queues where the service time is a sum of variables having complex dependencies. © 1992 John Wiley & Sons, Inc.     

Exact expected values of variance estimators for simulation

We formulate exact expressions for the expected values of selected estimators of the variance parameter (that is, the sum of covariances at all lags) of a steady‐state simulation output process. Given in terms of the autocovariance function of the process, these expressions are derived for variance estimators based on the simulation analysis methods of nonoverlapping batch means, overlapping batch means, and standardized time series. Comparing estimator performance in a first‐order autoregressive process and the M/M/1 queue‐waiting‐time process, we find that certain standardized time series estimators outperform their competitors as the sample size becomes large. © 2007 Wiley Periodicals, Inc. Naval Research Logistics, 2007     

On the behavior of the batch arrival queue Mx/M/1 during a busy period

The queue size process (^t)⁰≤^t≤^t0 of the batch arrival queue M^X/M/1 is studied under the condition that the duration of its busy period is larger than t⁰. Explicit formulas for the transition probabilities are given and the limiting Markov process for t⁰ → ∞ is investigated. Several properties of this process are considered. Its transition probabilities and moments and the distribution of its minimum are derived and a functional limit theorem for the rescaled process is proved. © 1994 John Wiley & Sons, Inc.