Computational analysis of MMAP[K]/PH[K]/1 queues with a mixed FCFS and LCFS service discipline

This paper studies a queueing system with a Markov arrival process with marked arrivals and PH‐distribution service times for each type of customer. Customers (regardless of their types) are served on a mixed first‐come‐first‐served (FCFS) and last‐come‐first‐served (LCFS) nonpreemptive basis. That is, when the queue length is N (a positive integer) or less, customers are served on an FCFS basis; otherwise, customers are served on an LCFS basis. The focus is on the stationary distribution of queue strings, busy periods, and waiting times of individual types of customers. A computational approach is developed for computing the stationary distribution of queue strings, the mean of busy period, and the means and variances of waiting times. The relationship between these performance measures and the threshold number N is analyzed in depth numerically. It is found that the variance of the virtual (actual) waiting time of an arbitrary customer can be reduced by increasing N. © 2000 John Wiley & Sons, Inc. Naval Research Logistics 47: 399–421, 2000     

Queues with stochastic service rates

The purpose of this paper is to explore an extension of the output discipline for the Poisson input, general output, single channel, first-come, first-served queueing system. The service time parameter, μ, is instead considered a random variable, M. In other words, the service time random variable, T, is to be conditioned by a parameter random variable, M. Therefore, if the distribution function of M is denoted by F_M(μ) and the known conditional service time distribution as B(t |_μ), then the unconditional service distribution is given by B(t) = Pr {T ≤ t}. = ∫_-∞^∞ B(t |_μ) dF_M(μ). Results are obtained that characterize queue size and waiting time using the imbedded Markov chain approach. Expressions are derived for the expected queue length and Laplace-Stieltjes transforms of the steady-state waiting time when conditional service times are exponential. More specific results are found for three special distributions of M: (1) uniform on [1.2]; (2) two-point; and (3) gamma.     

Estimation in single server queues

Moment and maximum likelihood estimates (m.l.e.'s) arc investigated for nonparametric and parametric models for a single server queue observed over a random time horizon, namely, up to the nth departure epoch. Also. m.l.e's of the mean interarrival time and mean service time in anM/M/1 queue observed over a fixed time-interval are studied Limit distributions of these estimates are obtained Without imposing steady state assumptions on the queue-size or waiting time processes.     

Markov chain analyses of multiprogrammed computer systems

Most operating systems for large computing facilities involve service disciplines which base, to some extent, the sequencing of object program executions on the amount of running time they require. It is the object of this paper to study mathematical models of such service disciplines applicable to both batch and time-shared processing systems. In particular, Markov queueing models are defined and analyzed for round-robin and foreground-background service disciplines. With the round-robin discipline, the service facility processes each program or job for a maximum of q seconds; if the program's service is completed during this quantum, it leaves the system, otherwise it returns to the end of the waiting line to await another quantum of service. With the foreground-background discipline each new arrival joins the end of the foreground queue and awaits a single quantum of service. If it requires more it is subsequently placed at the end of the background queue which is allocated service only when the foreground queue is empty. The analysis focuses on the efficiency of the above systems by assuming a swap or set-up time (overhead cost) associated with the switching of programs on and off the processor. The analysis leads to generating functions for the equilibrium queue length probabilities, the moments of this latter distribution, and measures of mean waiting times. The paper concludes with a discussion of the results along with several examples.     

The queue G/M/m/N: Busy period and cycle,waiting time under reverse and random order service

The busy period, busy cycle, and the numbers of customers served and lost therein, of the G/M/m queue with balking is studied via the embedded Markov chain approach. It is shown that the expectations of the two discrete variables give the loss probability. For the special case G/M/1/N a closed expression in terms of contour integrals is obtained for the Laplace transform of these four variables. This yields as a byproduct the LIFO waiting time distribution for the G/M/m/N queue. The waiting time under random order service for this queue is also studied.     

Stochastic analysis of a single server retrial queue with general retrial times

Retrial queueing systems are widely used in teletraffic theory and computer and communication networks. Although there has been a rapid growth in the literature on retrial queueing systems, the research on retrial queues with nonexponential retrial times is very limited. This paper is concerned with the analytical treatment of an M/G/1 retrial queue with general retrial times. Our queueing model is different from most single server retrial queueing models in several respectives. First, customers who find the server busy are queued in the orbit in accordance with an FCFS (first‐come‐first‐served) discipline and only the customer at the head of the queue is allowed for access to the server. Besides, a retrial time begins (if applicable) only when the server completes a service rather upon a service attempt failure. We carry out an extensive analysis of the queue, including a necessary and sufficient condition for the system to be stable, the steady state distribution of the server state and the orbit length, the waiting time distribution, the busy period, and other related quantities. Finally, we study the joint distribution of the server state and the orbit length in non‐stationary regime. © 1999 John Wiley & Sons, Inc. Naval Research Logistics 46: 561–581, 1999     

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.     

Algorithms for computing waiting time distributions under different queue disciplines for the D-BMAP/PH/1

A queueing system characterized by the discrete batch Markovian arrival process (D-BMAP) and a probability of phase type distribution for the service time is one that arises frequently in the area of telecommunications. Under this arrival process and service time distribution we derive the waiting time distribution for three queue disciplines: first in first out (FIFO), last in first out (LIFO), and service in random order (SIRO). We also outline efficient algorithmic procedures for computing the waiting time distributions under each discipline. © 1997 John Wiley & Sons, Inc. Naval Research Logistics 44: 559–576, 1997     

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     

随机环境中的M/MY/1排队系统

文献［４］讨论了随机环境中的Ｍ／Ｍ／１排队模型，本文提出和讨论随机环境中的Ｍ／Ｍｙ／１排队模型，在统计平衡条件下给出了队长和等待队长的平稳分布以及平均队长和平均等待队长，得到了等待时间和逗留时间分布以及平均等待时间和平均逗留时间。     

Matrix-geometric solution of discrete time MAP/PH/1 priority queue

We use the matrix-geometric method to study the discrete time MAP/PH/1 priority queue with two types of jobs. Both preemptive and non-preemptive cases are considered. We show that the structure of the R matrix obtained by Miller for the Birth-Death system can be extended to our Quasi-Birth-Death case. For both preemptive and non-preemptive cases the distributions of the number of jobs of each type in the system are obtained and their waiting times are obtained for the non-preemptive. For the preemptive case we obtain the waiting time distribution for the high priority job and the distribution of the lower priority job's wait before it becomes the leading job of its priority class. © 1998 John Wiley & Sons, Inc. Naval Research Logistics 45: 23–50, 1998     

Managing waiting times of backordered demands in single‐stage (Q,r) inventory systems

We present a service constrained (Q, r) model that minimizes expected holding and ordering costs subject to an upper bound on the expected waiting time of demands that are actually backordered. We show that, after optimizing over r, the average cost is quasiconvex in Q for logconcave continuous lead time demand distributions. For logconcave discrete lead time demand distributions we find a single‐pass efficient algorithm based on a novel search stopping criterion. The algorithm also allows for bounds on the variability of the service measure. A brief numerical study indicates how the bounds on service impact the optimal average cost and the optimal (Q, r) choice. The discrete case algorithm can be readily adapted to provide a single pass algorithm for the traditional model that bounds the expected waiting time of all demands (backordered or not). © 2002 Wiley Periodicals, Inc. Naval Research Logistics 49: 557–573, 2002; Published online in Wiley InterScience (www.interscience.wiley.com). DOI 10.1002/nav.10028     

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].     

Waiting time analysis of the M/G/1 queue with finite retrial group

We consider an M/G/1 retrial queue with finite capacity of the retrial group. First, we obtain equations governing the dynamic of the waiting time. Then, we focus on the numerical inversion of the density function and the computation of moments. These results are used to approximate the waiting time of the M/G/1 queue with infinite retrial group for which direct analysis seems intractable. © 2007 Wiley Periodicals, Inc. Naval Research Logistics, 2007     

Customer delays in M/M/c repair systems with spares

A service center to which customers bring failed items for repair is considered. The items are exchangeable in the sense that a customer is ready to take in return for the failed item he brought to the center any good item of the same kind. This exchangeability feature makes it possible for the service center to possess spares. The focus of the article is on customer delay in the system—the time that elapses since the arrival of a customer with a failed item and his departure with a good one—when repaired items are given to waiting customers on a FIFO basis. An algorithm is developed for the computation of the delay distribution when the item repair system operates as an M/M/c queue.     

MAD: Mathematical analysis of downtime

The MAD model presents a mathematic treatment of the relationship between aircraft reliability and maintainability, system manning and inspection policies, scheduling and sortie length, and aircraft downtime. Log normal distributions are postulated for subsystem repair times and simultaneous repair of malfunctions is assumed. The aircraft downtime for maintenance is computed with the distribution of the largest of k log normal distributions. Waiting time for maintenance men is calculated either by using a multiple-channel queuing model or by generating the distribution of the number of maintenance men required and comparing this to the number of men available to determine the probability of waiting at each inspection.     

A sequential scheduling problem with impatient jobs

There are n customers that need to be served. Customer i will only wait in queue for an exponentially distributed time with rate λ_i before departing the system. The service time of customer i has distribution F_i, and on completion of service of customer i a positive reward r_i is earned. There is a single server and the problem is to choose, after each service completion, which currently in queue customer to serve next so as to maximize the expected total return. © 2015 Wiley Periodicals, Inc. Naval Research Logistics 62: 659–663, 2015     

Optimal admission pricing policies for M/Ek/1 queues

This paper extends the Low-Lippman M/M/1 model to the case of Gamma service times. Specifically, we have a queue in which arrivals are Poisson, service time is Gamma-distributed, and the arrival rate to the system is subject to setting an admission fee p. The arrival rate λ(p) is non-increasing in p. We prove that the optimal admission fee p^* is a non-decreasing function of the customer work load on the server. The proof is for an infinite capacity queue and holds for the infinite horizon continuous time Markov decision process. In the special case of exponential service time, we extend the Low-Lippman model to include a state-dependent service rate and service cost structure (for finite or infinite time horizon and queue capacity). Relatively recent dynamic programming techniques are employed throughout the paper. Due to the large class of functions represented by the Gamma family, the extension is of interest and utility.     

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     

On queues with dependent interarrival and service times

AnM/G/1 queueing system is studied in which the service time required by a customer is dependent on the interarrival time between his arrival and that of his predecessor Assuming the two variables are “associated,” we prove that the expected delay in this system is less than or equal to than of a conventional M/G/1 queue This conclusion has been verified via simulation by Mitchell and Paulson [9] for a special class of dependent M/M/1 queue. Their model is a special case of the one we consider here. We also study another modified GI/G/1 queue. where the arrival process and/or the service process are individually “associated”.