Social forecasting for company planning: Brian C. TWISS (Ed.) Macmillan,London, 1982, xxv + 310 pages, £25.00

The transportation system considered in this paper has a number of vehicles with no capacity constraint, which take passengers from a source terminal to various destinations and return to the terminal. The trip times are considered to be independent and identically distributed random variables with a common exponential distribution. Passengers arrive at the terminal in accordance with a Poisson process. The system is operated under the following policy: when a vehicle is available and there are at least α passengers waiting for service, then a vehicle is dispatched immediately. The passenger queue length and waiting time distributions are obtained under steady-state conditions. System performance measures such as average passenger queue length and waiting time are then derived. A minimum average cost criterion is then used to determine the optimal fleet size and dispatching policy. This is a generalization of the results of Weiss for a single-vehicle system.     

Further results for the M/M(a, ∞)/N batch-service system

A multi-server Markovian queueing system is considered such that an idle server will take the entire batch of waiting customers into service as soon as their number is as large as some control limit. Some new results are derived. These include the distribution of the time interval between two consecutive commencements of service (including itsrth moment) and the actual service batch size distribution. In addition, the average customer waiting time in the queue is derived by a simple combinatorial approach. This is an expanded version of “Combinatorial analysis of batch-service queues” which was presented at the ORSA/TIMS meeting, Orlando, Florida, November 1983.     

Sojourn time distributions for the M/M/1 queue in a Markovian environment

In this paper, we study a single server queue in which both the arrival rate and service rate depend on the state of an external Markov process (called the environment) with a finite state space. Given that the environment is in state j, the mean arrival and service rates are λ_j and μ_j respectively. For such a queue, the queue length distribution is known to be matrix geometric. In this paper, we characterize the Laplace-Stieltjes transform of the sojourn time distribution under four disciplines - last come first served preemptive resume, last come first served, processor sharing and round robin. We also discuss a potential application of this queue in the are of data communication.     

Analysis of a two-phase queueing system with a fixed-size batch policy

We consider a single-server, two-phase queueing system with a fixed-size batch policy. Customers arrive at the system according to a Poisson process and receive batch service in the first-phase followed by individual services in the second-phase. The batch service in the first-phase is applied for a fixed number (k) of customers. If the number of customers waiting for the first-phase service is less than k when the server completes individual services, the system stays idle until the queue length reaches k. We derive the steady state distribution for the system’s queue length. We also show that the stochastic decomposition property can be applied to our model. Finally, we illustrate the process of finding the optimal batch size that minimizes the long-run average cost under a linear cost structure.     

A single server queue with gated processor-sharing discipline

In this paper we consider a single server queue in which arrivals occur according to a Poisson process and each customer's service time is exponentially distributed. The server works according to the gated process-sharing discipline. In this discipline, the server provides service to a batch of at mostm customers at a time. Once a batch of customers begins service, no other waiting customer can receive service until all members of the batch have completed their service. For this queue, we derive performance characteristics, such as waiting time distribution, queue length distribution etc. For this queue, it is possible to obtain the mean conditional response time for a customer whose service time is known. This conditional response time is a nonlinear function (as opposed to the linear case for the ordinary processor-sharing queue). A special case of the queue (wherem=) has an interesting and unusual solution. For this special case, the size of the batch for service is a Markov chain whose steady state distribution can be explicitly written down. Apart from the contribution to the theory of Markov chains and queues, the model may be applicable to scheduling of computer and communication systems.     

The shuttle dispatch problem with compound Poisson arrivals: Controls at two terminals

We consider the control of an infinite capacity shuttle which transports passengers between two terminals. The passengers arrive at each terminal according to a compound Poisson process and the travel time from one terminal to the other is a random variable following an arbitrary distribution. The following control limit policy is considered: dispatch the shuttle at terminali, at the instant that the total number of passengers waiting at terminali reaches or exceeds a predetermined control limitm _i . The objective of this paper is to obtain the mean waiting time of an arbitrary passenger at each terminal for given control valuesm ₁ andm ₂. We also discuss a search procedure to obtain the optimal control values which minimize the total expected cost per unit time under a linear cost structure.     

Performance analysis of an elevator system during up-peak

We model and analyze an elevator system during up-peak. We study the round-trip time, whose distribution depends strongly on the number of passengers waiting at the lobby, as well as the number of stops and the highest reversal floor. The distribution functions of the passenger queue length in the lobby, the round-trip time, the waiting time, the ride time and the journey time are derived.     

Operating characteristic analysis on the M/G/1 system with a variant vacation policy and balking

This paper studies the operating characteristics of an M^[x]/G/1 queueing system under a variant vacation policy, where the server leaves for a vacation as soon as the system is empty. The server takes at most J vacations repeatedly until at least one customer is found waiting in the queue when the server returns from a vacation. If the server is busy or on vacation, an arriving batch balks (refuses to join) the system with probability 1 − b. We derive the system size distribution at different points in time, as well as the waiting time distribution in the queue. Finally, important system characteristics are derived along with some numerical illustration.     

Efficient computational analysis of non-exhaustive service vacation queues: BMAP/R/1/N(∞) under gated-limited discipline

This paper analyzes the finite-buffer single server queue with vacation(s). It is assumed that the arrivals follow a batch Markovian arrival process (BMAP) and the server serves customers according to a non-exhaustive type gated-limited service discipline. It has been also considered that the service and vacation distributions possess rational Laplace-Stieltjes transformation (LST) as these types of distributions may approximate many other distributions appeared in queueing literature. Among several batch acceptance/rejection strategies, the partial batch acceptance strategy is discussed in this paper. The service limit L (1 ≤ L ≤ N) is considered to be fixed, where N is the buffer-capacity excluding the one in service. It is assumed that in each busy period the server continues to serve until either L customers out of those that were waiting at the start of the busy period are served or the queue empties, whichever occurs first. The queue-length distribution at vacation termination/service completion epochs is determined by solving a set of linear simultaneous equations. The successive substitution method is used in the steady-state equations embedded at vacation termination/service completion epochs. The distribution of the queue-length at an arbitrary epoch has been obtained using the supplementary variable technique. The queue-length distributions at pre-arrival and post-departure epoch are also obtained. The results of the corresponding infinite-buffer queueing model have been analyzed briefly and matched with the previous model. Net profit function per unit of time is derived and an optimal service limit and buffer-capacity are obtained from a maximal expected profit. Some numerical results are presented in tabular and graphical forms.     

Selecting batch size in discrete-time two-phase queuing system

This paper discusses the modeling and analysis of a discrete-time two-phase queuing system. Packets arrive at the system according to a Bernoulli process and receive batch service in the first queue and individual service in the second queue. We study the queue length, average waiting time of packets in the first queue and the effect of batch size on the waiting time.     

Analysis of the queue-length distribution for the discrete-time batch-service Geo/G/1/K queue

In this paper, we consider a discrete-time finite-capacity queue with Bernoulli arrivals and batch services. In this queue, the single server has a variable service capacity and serves the customers only when the number of customers in system is at least a certain threshold value. For this queue, we first obtain the queue-length distribution just after a service completion, using the embedded Markov chain technique. Then we establish a relationship between the queue-length distribution just after a service completion and that at a random epoch, using elementary ‘rate-in = rate-out’ arguments. Based on this relationship, we obtain the queue-length distribution at a random (as well as at an arrival) epoch, from which important performance measures of practical interest, such as the mean queue length, the mean waiting time, and the loss probability, are also obtained. Sample numerical examples are presented at the end.     

Fluid polling systems

We study N-queues single-server fluid polling systems, where a fluid is continuously flowing into the queues at queue-dependent rates. When visiting and serving a queue, the server reduces the amount of fluid in the queue at a queue-dependent rate. Switching from queue i to queue j requires two random-duration steps: (i) departing queue i, and (ii) reaching queue j. The length of time the server resides in a queue depends on the service regime. We consider three main regimes: Exhaustive, Gated, and Globally-Gated. Two polling procedures are analyzed: (i) cyclic and (ii) probabilistic. Under steady-state, we derive the Laplace–Stieltjes transform (LST), mean, and second moment of the amount of flow at each queue at polling instants, as well as at an arbitrary moment. We further calculate the LST and mean of the “waiting time” of a drop at each queue and derive expressions for the mean total load in the system for the various service regimes. Finally, we explore optimal switching procedures.     

Bayesian prediction inM/M/1 queues

Simple queues with Poisson input and exponential service times are considered to illustrate how well-suited Bayesian methods are used to handle the common inferential aims that appear when dealing with queue problems. The emphasis will mainly be placed on prediction; in particular, we study the predictive distribution of usual measures of effectiveness in anM/M/1 queue system, such as the number of customers in the queue and in the system, the waiting time in the queue and in the system, the length of an idle period and the length of a busy period.     

On the M/G/1 queue with feedback and optional server vacations based on a single vacation policy

We study a single server queue with batch arrivals and general (arbitrary) service time distribution. The server provides service to customers, one by one, on a first come, first served basis. Just after completion of his service, a customer may leave the system or may opt to repeat his service, in which case this customer rejoins the queue. Further, just after completion of a customer's service the server may take a vacation of random length or may opt to continue staying in the system to serve the next customer. We obtain steady state results in explicit and closed form in terms of the probability generating functions for the number of customers in the queue, the average number of customers and the average waiting time in the queue. Some special cases of interest are discussed and some known results have been derived. A numerical illustration is provided.     

Asymptotic expansions for waiting time probabilities in an M/G/1 queue with long-tailed service time

We consider anM/G/1 queue with FCFS queue discipline. We present asymptotic expansions for tail probabilities of the stationary waiting time when the service time distribution is longtailed and we discuss an extension of our methods to theM ^[x]/G/1 queue with batch arrivals.     

An M/G/1 Queueing Model with Gated Random Order of Service

We analyse an M/G/1 queueing model with gated random order of service. In this service discipline there are a waiting room, in which arriving customers are collected, and a service queue. Each time the service queue becomes empty, all customers in the waiting room are put instantaneously and in random order into the service queue. The service times of customers are generally distributed with finite mean. We derive various bivariate steady-state probabilities and the bivariate Laplace–Stieltjes transform (LST) of the joint distribution of the sojourn times in the waiting room and the service queue. The derivation follows the line of reasoning of Avi-Itzhak and Halfin [4]. As a by-product, we obtain the joint sojourn times LST for several other gated service disciplines.     

Equilibrium properties of the M/G/1 queue

Summary Various aspects of the equilibrium M/G/1 queue at large values are studied subject to a condition on the service time distribution closely related to the tail to decrease exponentially fast. A simple case considered is the supplementary variables (age and residual life of the current service period), the distribution of which conditioned upon queue length n is shown to have a limit as n. Similar results hold when conditioning upon large virtual waiting times. More generally, a number of results are given which describe the input and output streams prior to large values e.g. in the sense of weak convergence of the associated point processes and incremental processes. Typically, the behaviour is shown to be that of a different transient M/G/1 queueing model with a certain stochastically larger service time distribution and a larger arrival intensity. The basis of the asymptotic results is a geometrical approximation for the tail of the equilibrium queue length distribution, pointed out here for the GI/G/1 queue as well.     

On the M/G/2 queeing model

The M/G/2 queueing model with service time distribution a mixture of m negative exponential distributions is analysed. The starting point is the functional relation for the Laplace–Stieltjes transform of the stationary joint distribution of the workloads of the two servers. By means of Wiener–Hopf decompositions the solution is constructed and reduced to the solution of m linear equations of which the coefficients depend on the zeros of a polynome. Once this set of equations has been solved the moments of the waiting time distribution can be easily obtained. The Laplace–Stieltjes transform of the stationary waiting time distribution has been derived, it is an intricate expression.     

The infinite-buffer single server queue with a variant of multiple vacation policy and batch Markovian arrival process

We consider an infinite-buffer single server queue where arrivals occur according to a batch Markovian arrival process (BMAP). The server serves until system emptied and after that server takes a vacation. The server will take a maximum number H of vacations until either he finds at least one customer in the queue or the server has exhaustively taken all the vacations. We obtain queue length distributions at various epochs such as, service completion/vacation termination, pre-arrival, arbitrary, departure, etc. Some important performance measures, like mean queue lengths and mean waiting times, etc. have been obtained. Several other vacation queueing models like, single and multiple vacation model, queues with exceptional first vacation time, etc. can be considered as special cases of our model.     

Analysis of $$\hbox {M}^{\mathrm {x}}/\hbox {G}/1$$ queues with impatient customers

This paper considers a batch arrival \(\hbox {M}^{\mathrm {x}}/\hbox {G}/1\) queue with impatient customers. We consider two different model variants. In the first variant, customers in the same batch are assumed to have the same patience time, and patience times associated with batches are i.i.d. according to a general distribution. In the second variant, patience times of customers in the same batch are independent, and they follow a general distribution. Both variants are related to an M/G/1 queue in which the service time of a customer depends on its waiting time. Our main focus is on the virtual and actual waiting times, and on the loss probability of customers.