We consider a markovian multiserver queue with a finite waiting line in which a customer may decide to leave and give up service if its waiting time in queue exceeds its random deadline. We focus on the performance measure in terms of the probability of being served under both transient and stationary regimes. We investigate monotonicity properties of first and second order of this performance with respect to the buffer size, say k. Under the stationary regime, we prove that our service level is strictly increasing and concave in k, whereas we prove under the transient regime that it is only increasing in k.

We consider a class of stochastic models for systems subject to random regulation. We derive expressions for the distribution of the intervals between regulating instants and for the transient and equilibrium properties of the process. Some of these are evaluated explicitly for some models of interest.

In this article, we consider deterministic (both fluid and discrete) polling systems with N queues with infinite buffers and we show how to compute the best polling sequence (minimizing the average total workload). With two queues, we show that the best polling sequence is always periodic when the system is stable and forms a regular sequence. The fraction of time spent by the server in the first queue is highly noncontinuous in the parameters of the system (arrival rate and service rate) and shows a fractal behavior. Moreover, convexity properties are shown and are used in a generalization of the computation of the optimal control policy (in open loop) for the stochastic exponential case.

Consider a system of queuing stations in tandem having both flexible servers (who are capable of working at multiple stations) and dedicated servers (who can only work at the station to which they are dedicated). We study the dynamic assignment of servers to stations in such systems with the goal of maximizing the long-run average throughput. We also investigate how the number of flexible servers influences the throughput and compare the improvement that is obtained by cross-training another server (i.e., increasing flexibility) with the improvement obtained by adding a resource (i.e., a new server or a buffer space). Finally, we show that having only one flexible server is sufficient for achieving near-optimal throughput in certain systems with moderate to large buffer sizes (the optimal throughput is attained by having all servers flexible). Our focus is on systems with generalist servers who are equally skilled at all tasks, but we also consider systems with arbitrary service rates.

This article deals with the effect of information and uncertainty on profits in an unobservable single-server queuing system. We consider scenarios in which the service rate, the service quality, or the waiting conditions are random variables that are known to the server but not to the customers. We ask whether the server is motivated to reveal these parameters. We investigate the structure of the profit function and its sensitivity to the variance of the random variable. We consider and compare variations of the model according to whether the server can modify the service price after observing the realization of the random variable.

We study the optimal admission of arriving customers to a Markovian finite-capacity queue (e.g., M/M/c/N queue) with several customer types. The system managers are paid for serving customers and penalized for rejecting them. The rewards and penalties depend on customer types. The penalties are modeled by a K-dimensional cost vector, K ≥ 1. The goal is to maximize the average rewards per unit time subject to the K constraints on the average costs per unit time. Let Km denote min{K,m − 1}, where m is the number of customer types. For a feasible problem, we show the existence of a Km-randomized trunk reservation optimal policy, where the acceptance thresholds for different customer types are ordered according to a linear combination of the service rewards and rejection costs. Additionally, we prove that any Km-randomized stationary optimal policy has this structure.

We consider the problem of admission control to a multiserver finite buffer queue under partial information. The controller cannot see the queue but is informed immediately if an admitted customer is lost due to buffer overflow. Turning away (i.e., blocking) customers is costly and so is losing an admitted customer. The latter cost is greater than that of blocking. The controller's objective is to minimize the average cost of blocking and rejection per incoming customer. Lin and Ross [11] studied this problem for multiserver loss systems. We extend their work by allowing a finite buffer and the arrival process to be of the renewal type. We propose a control policy based on a novel state aggregation approach that exploits the regenerative structure of the system, performs well, and gives a lower bound on the optimal cost. The control policy is inspired by a simulation technique that reduces the variance of the estimators by not simulating the customer service process. Numerical experiments show that our bound varies with the load offered to the system and is typically within 1% and 10% of the optimal cost. Also, our bound is tight in the important case when the cost of blocking is low compared to the cost of rejection and the load offered to the system is high. The quality of the bound degrades with the degree of state aggregation, but the computational effort is comparatively small. Moreover, the control policies that we obtain perform better compared to a heuristic suggested by Lin and Ross. The state aggregation technique developed in this article can be used more generally to solve problems in which the objective is to control the time to the end of a cycle and the quality of the information available to the controller degrades with the length of the cycle.

We study a cumulative storage system that is totally cleared sporadically at stationary renewal times and whenever a finite-capacity threshold is exceeded. The independent and identically distributed inputs occur at time epochs that also form a stationary renewal process. We determine the distribution of the interoverflow times. Although this distribution is quite intricate when both underlying renewal processes are general, in the special case of Poisson sporadic clearings we obtain a neat formula for its Laplace transform.

In the present article, we consider a class of reliability structures that can be efficiently described through a finite Markov chain (Markov chain imbeddable systems) and investigate its closeness with respect to the increasing failure rate (IFR) property. More specifically we derive a sufficient condition for the system's lifetime to have increasing failure rate when the identical and independent components comprising it own this property. As an application of the general theory, we establish an alternative proof of the IFR property preservation for the k-out-of-n system and derive some related results for the family of weighted k-out-of-n systems.

In this article we investigate conditions on the underlying distribution functions on which the sequential order statistics are based, to obtain stochastic comparisons of sequential order statistics in the multivariate likelihood ratio, the multivariate hazard rate, and the usual multivariate stochastic orders. Some applications of the main results are also given.

The embedded Markov chain approach is widely used in queuing theory, in particular in M/G/1 and GI/M/c queues. In these cases, one has to relate the embedded equilibrium probablities to the corresponding random-time probabilities. The classical method to do this is based on Markov renewal theory, a rather complex approach, especially if the population is finite or if there is balking. In this article we present a much simpler method to derive the random-time probabilities from the embedded Markov chain probabilities. The method is based on conditional probability. Our approach might also be applicable in such situations.

This article provides series expansions of the stationary distribution of a finite Markov chain. This leads to an efficient numerical algorithm for computing the stationary distribution of a finite Markov chain. Numerical examples are given to illustrate the performance of the algorithm.

In this article we investigate conditions by a unified method under which the covariances of functions of two adjacent ordered random variables are nonnegative. The main structural results are applied to several kinds of ordered random variable, such as delayed record values, continuous and discrete ℓ∞⩽-spherical order statistics, epoch times of mixed Poisson processes, generalized order statistics, discrete weak record values, and epoch times of modified geometric processes. These applications extend the main results for ordinary order statistics in Qi [28] and for usual record values in Nagaraja and Nevzorov [25].

We consider the problem of estimating passage times in stochastic simulations of Markov chains. Two types of estimator are considered for this purpose: the “simple” and the “overlapping” estimator; they are compared in terms of their asymptotic variance. The analysis is based on the regenerative structure of the process and it is shown that when estimating the mean passage time, the simple estimator is always asymptotically superior. However, when the object is to estimate the expectation of a nonlinear function of the passage time, such as the probability that the passage time exceeds a given threshold, then it is shown that the overlapping estimator can be superior in some cases. Related results in the Reinforcement Learning literature are discussed.

This article derives amazingly accurate approximations to the state probabilities and waiting-time probabilities in the M/D/1 queue using a two-phase process with negative probabilities to approximate the deterministic service time. The approximations are in the form of explicit expressions involving geometric and exponential terms. The approximations extend to the finite-capacity M/D/1/N + 1 queue.

The concept of generalized order statistics was introduced as a unified approach to a variety of models of ordered random variables. The purpose of this article is to establish the usual stochastic and the likelihood ratio orderings of conditional distributions of generalized order statistics from one sample or two samples, strengthening and generalizing the main results in Khaledi and Shaked [15], and Li and Zhao [17]. Some applications of the main results are also given.

Consider a single machine that can process multiple jobs in batch mode. We have n jobs and the processing time of job j is a random variable Xj with distribution Fj. Up to b jobs can be processed simultaneously by the machine. The jobs in a batch all have to start at the same time and the batch is completed when all jobs have finished their processing (i.e., at the maximum of the processing times of the jobs in that batch). We are interested in two objective functions, namely the minimization of the expected makespan and the minimization of the total expected completion time. We first show that under certain fairly general conditions, the minimization of the expected makespan is equivalent to specific deterministic combinatorial problems, namely the Weighted Matching problem and the Set Partitioning problem. We then consider the case when all jobs have the same mean processing time but different variances. We show that for certain special classes of processing time distributions the Smallest Variance First rule minimizes the expected makespan as well as the total expected completion time. In our conclusions we present various general rules that are suitable for the minimization of the expected makespan and the total expected completion time in batch scheduling.

We consider an M/G/1 retrial queue with finite capacity of the retrial group. We derive the Laplace transform of the busy period using the catastrophe method. This is the key point for the numerical inversion of the density function and the computation of moments. Our results can be used to approach the corresponding descriptors of the M/G/1 queue with infinite retrial group, for which direct analysis seems intractable.

In this article we first give a characterization of a class of probability transition matrices having closed-form solutions for transient distributions and the steady-state distribution. We propose to apply the stochastic comparison approach to construct bounding chains belonging to this class. Therefore, bounding chains can be analyzed efficiently through closed-form solutions in order to provide bounds on the distributions of the considered Markov chain. We present algorithms to construct upper-bounding matrices in the sense of the ≤st and ≤icx order.

We study weighted path lengths (depths) and distances for increasing tree families. For those subclasses of increasing tree families, which can be constructed via an insertion process (e.g., recursive trees, plane-oriented recursive trees, and binary increasing trees), we can determine the limiting distribution that can be characterized as a generalized Dickman's infinitely divisible distribution.