Scheduling arrivals to a stochastic service mechanism

We consider the problem of scheduling the arrivals of a fixed number of customers to a stochastic service mechanism to minimize an expected cost associated with operating the system. We consider the special case of exponentially distributed service times and the problems in general associated with obtaining exact analytic solutions. For general service time distributions we obtain approximate numerical solutions using a stochastic version of gradient search employing Infinitesimal Perturbation Analysis estimates of the objective function gradient obtained via simulation.     

Staffing a service system with appointment-based customer arrivals

Appointment systems are widely used to facilitate customers’ access to services in many industries such as healthcare. A number of studies have taken a queueing approach to analyse service systems and facilitate managerial decisions on staffing requirements by assuming independent and stationary customer arrivals. This paper is motivated by the observation that the queueing-based method shows relatively poor performance when customers arrive according to their appointment times. Because customer arrivals are dependent on their appointment times, this study, unlike queueing-based methods, conducts a detailed analysis of appointment-based customer arrivals instead of making steady-state assumptions. We develop a new model that captures the characteristics of appointment-based customer arrivals and computes the probability of transient system states. Through the use of this model, which relaxes stationary and independent assumptions, we propose a heuristic algorithm that determines staffing requirements with aims to minimizing staff-hours while satisfying a target service level. The simulation results show that the proposed method outperforms the queueing-based method.     

Modeling teletraffic arrivals by a Poisson cluster process

In this paper we consider a Poisson cluster process N as a generating process for the arrivals of packets to a server. This process generalizes in a more realistic way the infinite source Poisson model which has been used for modeling teletraffic for a long time. At each Poisson point Γ _j , a flow of packets is initiated which is modeled as a partial iid sum process , with a random limit K _j which is independent of (X _ji ) and the underlying Poisson points (Γ _j ). We study the covariance structure of the increment process of N. In particular, the covariance function of the increment process is not summable if the right tail P(K _j > x) is regularly varying with index α∊ (1, 2), the distribution of the X _ji ’s being irrelevant. This means that the increment process exhibits long-range dependence. If var(K _j ) < ∞ long-range dependence is excluded. We study the asymptotic behavior of the process (N(t)) _{t≥ 0} and give conditions on the distribution of K _j and X _ji under which the random sums have a regularly varying tail. Using the form of the distribution of the interarrival times of the process N under the Palm distribution, we also conduct an exploratory statistical analysis of simulated data and of Internet packet arrivals to a server. We illustrate how the theoretical results can be used to detect distribution al characteristics of K _j , X _ji , and of the Poisson process. AMS Subject Classifications Primary—60K30; Secondary—60K25 A large part of this research was done with support of Institut Mittag-Leffler of the Royal Swedish Academy of Sciences when the authors participated in the Fall 2004 program on Queuing Theory and Teletraffic Theory. Mikosch’s research is also partially supported by MaPhySto, the Danish research network for mathematical physics and stochastics and the Danish Research Council (SNF) Grant No 21-04-0400. Samorodnitsky’s research is also partially supported by NSF grant DMS-0303493 and NSA grant MSPF-02G-183 at Cornell University. González-Arévalo’s research is partially supported by BoRSF grant LEQSF(2004-2007)-RD-A-31 at the University of Louisiana at Lafayette.     

Scheduling arrivals to a production system in a fuzzy environment

A frequently encountered scheduling problem is to determine a material and job ready time while simultaneously finding a production sequence given customer-specified due dates. Often the production times and due dates are vague. This paper presents an investigation of scheduling ready times for a set of jobs with fuzzy service times and due dates. The ready time is constrained in that the possibility that a job is late must not exceed a predefined value. The objective in such an instance is to maximize the ready time without violating these constraints. The steps necessary to determine the maximum ready time and cases in which this effort may be significantly reduced are presented for single machine and flow shop production systems. Finally, a branch and bound technique is developed for cases in which the optimal job sequence cannot be determined a priori.     

On a risk model with Markovian arrivals and tax

A risk model with Markovian arrivals and tax payments is considered.When the insurer is in a profitable situation,the insurer may pay a certain proportion of the premium income as tax payments. First,t...     

Two queues with non-stochastic arrivals

This article presents a paradigm where no stochastic assumptions are made on a queue’s arrival process. To this end, we study two queueing systems which exhibit a form of stability under an arbitrary arrival process. The first queueing system applies Blackwell’s Approachability Theorem and the second analyzes the Vacuum Cleaner Problem.     

Synchronized queues with deterministic arrivals

We consider m independent exponential servers in parallel, driven by the same deterministic input. This is a modification of the Flatto-Hahn-Wright model which turns out to be easily tractable. We focus on the time-stationary distribution of the number of customers which is obtained using the Palm inversion formula.     

Optimal admission policies for a finite queue with bursty arrivals

We consider a service system with a single server, a finite waiting room and two classes of customers with deterministic service time. Primary jobs arrive at random and are admitted whenever there is room in the system. At the beginning of each period, secondary jobs can be admitted from an infinite pool. A revenue is earned upon admission of each job, with the primary jobs bringing a higher contribution than the secondary jobs, the objective being to maximize the total discounted revenue over an infinite horizon. We model the system as a discrete time Markov decision process and show that a monotone admission policy is optimal when the number of primary arrivals has a fixed distribution. Moreover, when the primary arrival distribution varies with time according to a finite state Markov chain, we show that the optimal policy is conditionally monotone and that the numerical computation of an optimal policy, in this case, is substantially more difficult than in the case of stationary arrivals.This research was supported in part by the National Science Foundation, under grant ECS-8803061, while the author was at the University of Arizona.     

Admission control with batch arrivals

We consider the problem of dynamic admission control in a multi-class Markovian loss system receiving random batches, where each admitted class-i job demands an exponential service with rate μ, and brings a reward r_i. We show that the optimal admission policy is a sequential threshold policy with monotone thresholds.     

Infinite-server systems with Coxian arrivals

We consider a network of infinite-server queues where the input process is a Cox process of the following form: The arrival rate is a vector-valued linear transform of a multivariate generalized (i.e., being driven by a subordinator rather than a compound Poisson process) shot-noise process. We first derive some distributional properties of the multivariate generalized shot-noise process. Then these are exploited to obtain the joint transform of the numbers of customers, at various time epochs, in a single infinite-server queue fed by the above-mentioned Cox process. We also obtain transforms pertaining to the joint stationary arrival rate and queue length processes (thus facilitating the analysis of the corresponding departure process), as well as their means and covariance structure. Finally, we extend to the setting of a network of infinite-server queues.

     

Admission control and pricing in a queue with batch arrivals

We investigate a problem of admission control in a queue with batch arrivals. We consider a single server with exponential service times and a compound Poisson arrival process. Each arriving batch computes its expected benefit and decides whether or not to enter the system. The controller’s problem is to set state dependent prices for arriving batches. Once prices have been set we formulate the admission control problem, derive properties of the value function, and obtain the optimal admission policy.     

Control of arrivals in a finite buffered queue with setup costs

We consider finite buffered queues where the arrival process is controlled by shutting down and restarting the arrival stream. In the absence of holding costs for items in the queue, the optimal (s,?S) policy can be characterised by relating the arrival control problem to a corresponding service control problem. With the inclusion of holding costs however, this characterisation is not valid and efficient numerical computation of the queue length probability distribution is necessary. We perform this computation by using a duality property which relates queue lengths in the controlled arrival system to a controlled service system. Numerical results which analyse the effect of setup and holding costs and the variability of the arrival process on the performance of the system are included.     

Asymptotics for the late arrivals problem

We study a discrete time queueing system where deterministic arrivals have i.i.d. exponential delays \(\xi _{i}\). We describe the model as a bivariate Markov chain, prove its ergodicity and study the joint equilibrium distribution. We write a functional equation for the bivariate generating function, finding the solution on a subset of its domain. This solution allows us to prove that the equilibrium distribution of the chain decays super-exponentially fast in the quarter plane. We exploit the latter result and discuss the numerical computation of the solution through a simple yet effective approximation scheme in a wide region of the parameters. Finally, we compare the features of this queueing model with the standard M / D / 1 system, showing that the congestion turns out to be very different when the traffic intensity is close to 1.     

Erlang arrivals joining the shorter queue

We consider a system in which customers join upon arrival the shortest of two single-server queues. The interarrival times between customers are Erlang distributed and the service times of both servers are exponentially distributed. Under these assumptions, this system gives rise to a Markov chain on a multi-layered quarter plane. For this Markov chain we derive the equilibrium distribution using the compensation approach. The expression for the equilibrium distribution matches and refines tail asymptotics obtained earlier in the literature.     

Admission control of a service station when the arrivals are internal

All studies in the admission control of a service station make decisions at arrival epochs. When arrivals are internal and are rejected from a queue, the rejected jobs have to be routed to other stations in the system. However the system will not know whether a job will be admitted to a queue or not until its arrival epoch to that queue. Thus, the system has to react dynamically and agilely to the decisions made at a specific queue and may try several queues before finding a queue that admits the job. This paper remedies these difficulties by changing the decision epochs of the admission control from arrival epochs to departure epochs with the actions of switching (keeping) the arrival stream on or off. Thus upstream stations will have information on the admission status of their downstream stations all the time. It is proved that the optimal policy for this revised admission control system is of control limit type for an M/G/1 queue. Comparisons of the optimal values and optimal policies for the admission controls made at arrival epochs and at departure epochs are included in the paper.     

Single-server queues with spatially distributed arrivals

Consider a queueing system where customers arrive at a circle according to a homogeneous Poisson process. After choosing their positions on the circle, according to a uniform distribution, they wait for a single server who travels on the circle. The server's movement is modelled by a Brownian motion with drift. Whenever the server encounters a customer, he stops and serves this customer. The service times are independent, but arbitrarily distributed. The model generalizes the continuous cyclic polling system (the diffusion coefficient of the Brownian motion is zero in this case) and can be interpreted as a continuous version of a Markov polling system. Using Tweedie's lemma for positive recurrence of Markov chains with general state space, we show that the system is stable if and only if the traffic intensity is less than one. Moreover, we derive a stochastic decomposition result which leads to equilibrium equations for the stationary configuration of customers on the circle. Steady-state performance characteristics are determined, in particular the expected number of customers in the system as seen by a travelling server and at an arbitrary point in time.     

Discrete-time analysis of a classified multi-server queue with burst arrivals and a shared buffer

We study a discrete-time, classified multi-server queue with a shared buffer. There arem servers and each server belongs to one ofk classes (mk), so thatk kinds of jobs can be served in the system. We characterize a bursty arrival process using bursts which consist of the same kind of jobs. Once the first job of a burst arrives at the queue, the successive jobs will arrive on every time slot until the last job of the burst arrives. The numbers of jobs of a burst and the inter-arrival times of bursts are assumed to be i.i.d., respectively, and the service time is assumed to be equal to one slot. We propose an efficient numerical method to exactly obtain the job loss probability, the waiting time distribution and the mean queue length. We apply this model to the ATM switch with a shared buffer and obtain the performance measures. Numerical results show the advantage of the ATM switch with a shared buffer compared to the one with output buffers.