Comparing two queueing models for nonhomogeneous nonreliable terminal systems

This paper deals with two nonhomogeneous queueing models to describe the performance of finite, multiterminal systems subject to random breakdowns. The difference between the two models is relatively small, but we will see that the differences between some system performance characteristics are very large (100% or more). The other contribution of this paper is to introduce some new terminologies to queueing theory, which are necessary for the second model. All random variables involved here are independent and exponentially distributed. The models described here are generalizations of the homogeneous model treated earlier by different authors. At the end of this paper some numerical results illustrate the problem in question. Proceedings of the XVI Seminar on Stability Problems for Stochastic Models, Part I, Eger, Hungary, 1994.     

A discrete model of a large polling system

For a network with Poisson incoming flow of customers (particles) and unit time of the motion of servers (annihilators), we obtain the limit distribution of the number of customers at the node for a fixed general number of nodes.     

A polling model with smart customers

In this paper we consider a single-server, cyclic polling system with switch-over times. A distinguishing feature of the model is that the rates of the Poisson arrival processes at the various queues depend on the server location. For this model we study the joint queue length distribution at polling epochs and at the server’s departure epochs. We also study the marginal queue length distribution at arrival epochs, as well as at arbitrary epochs (which is not the same in general, since we cannot use the PASTA property). A generalised version of the distributional form of Little’s law is applied to the joint queue length distribution at customer’s departure epochs in order to find the waiting time distribution for each customer type. We also provide an alternative, more efficient way to determine the mean queue lengths and mean waiting times, using Mean Value Analysis. Furthermore, we show that under certain conditions a Pseudo-Conservation Law for the total amount of work in the system holds. Finally, typical features of the model under consideration are demonstrated in several numerical examples.     

Dynamic pricing and scheduling in a multi-class single-server queueing system

This paper investigates an optimal sequencing and dynamic pricing problem for a two-class queueing system. Using a Markov Decision Process based model, we obtain structural characterizations of optimal policies. In particular, it is shown that the optimal pricing policy depends on the entire queue length vector but some monotonicity results prevail as the composition of this vector changes. A numerical study finds that static pricing policies may have significant suboptimality but simple dynamic pricing policies perform well in most situations.     

A polling model with an autonomous server

This paper considers polling systems with an autonomous server that remains at a queue for an exponential amount of time before moving to a next queue incurring a generally distributed switch-over time. The server remains at a queue until the exponential visit time expires, also when the queue becomes empty. If the queue is not empty when the visit time expires, service is preempted upon server departure, and repeated when the server returns to the queue. The paper first presents a necessary and sufficient condition for stability, and subsequently analyzes the joint queue-length distribution via an embedded Markov chain approach. As the autonomous exponential visit times may seem to result in a system that closely resembles a system of independent queues, we explicitly investigate the approximation of our system via a system of independent vacation queues. This approximation is accurate for short visit times only.      

Stochastic bounds for a polling system

In this note we consider two queueing systems: a symmetric polling system with gated service at allN queues and with switchover times, and a single-server single-queue model with one arrival stream of ordinary customers andN additional permanently present customers. It is assumed that the combined arrival process at the queues of the polling system coincides with the arrival process of the ordinary customers in the single-queue model, and that the service time and switchover time distributions of the polling model coincide with the service time distributions of the ordinary and permanent customers, respectively, in the single-queue model. A complete equivalence between both models is accomplished by the following queue insertion of arriving customers. In the single-queue model, an arriving ordinary customer occupies with probabilityp _i a position at the end of the queue section behind theith permanent customer,i = l, ...,N. In the cyclic polling model, an arriving customer with probabilityp _i joins the end of theith queue to be visited by the server, measured from its present position.For the single-queue model we prove that, if two queue insertion distributions {p _{i, i} = l, ...,N} and {q _{i, i} = l, ...,N} are stochastically ordered, then also the workload and queue length distributions in the corresponding two single-queue versions are stochastically ordered. This immediately leads to equivalent stochastic orderings in polling models.Finally, the single-queue model with Poisson arrivals andp ₁ = 1 is studied in detail.Part of the research of the first author has been supported by the Esprit BRA project QMIPS.     

A queueing model for crowdsourcing

Crowdsourcing is getting popular after a number of industries such as food, consumer products, hotels, electronics, and other large retailers bought into this idea of serving customers. In this paper, we introduce a multi-server queueing model in the context of crowdsourcing. We assume that two types, say, Type 1 and Type 2, of customers arrive to a c-server queueing system. A Type 1 customer has to receive service by one of c servers while a Type 2 customer may be served by a Type 1 customer who is available to act as a server soon after getting a service or by one of c servers. We assume that a Type 1 customer will be available for serving a Type 2 customer (provided there is at least one Type 2 customer waiting in the queue at the time of the service completion of that Type 1 customer) with probability \(p, 0 \le p \le 1\). With probability \(q = 1 - p\), a Type 1 customer will opt out of serving a Type 2 customer provided there is at least one Type 2 customer waiting in the system. Upon completion of a service a free server will offer service to a Type 1 customer on an FCFS basis; however, if there are no Type 1 customers waiting in the system, the server will serve a Type 2 customer if there is one present in the queue. If a Type 1 customer decides to serve a Type 2 customer, for our analysis purposes that Type 2 customer will be removed from the system as Type 1 customer will leave the system with that Type 2 customer. Under the assumption of exponential services for both types of customers we study the model in steady state using matrix analytic methods and establish some results including explicit ones for the waiting time distributions. Some illustrative numerical examples are presented.     

Optimal stochastic scheduling in a single server biclass retrial queueing system

The paper deals with the assignment of a single server to two retrial queues. Each customer reapplies for service after an exponentially distributed amount of time. The server operates at customer dependent exponential rates. There are holding costs and costs during service per customer and per unit of time. We provide conditions on which it is optimal to allocate the server to queue 1 or 2 in order to minimize the expected total costs until the system is cleared.     

A new look at a smart polling model

We analyze a Markovian smart polling model, which is a special case of the smart polling models studied in the work of Boon et al. (Queueing Syst 66:239–274, 2010), as well as a generalization of the gated M / M / 1 queue considered in Resing and Rietman (Stat Neerlandica 58:97–110, 2004). We first derive tractable expressions for the stationary distribution (when it exists) as well as the Laplace transforms of the transition functions of this polling model—while further assuming the system is empty at time zero—and we also present simple necessary and sufficient conditions for ergodicity of the smart polling model. Finally, we conclude the paper by briefly explaining how these techniques can be used to study other interesting variants of this smart polling model.     

The polling system with a stopping server

This paper analyzes the polling system in which, unlike nearly all previous studies, the server comes to a stop when the system is empty rather than continuing to cycle. The possibility of server stopping permits a rich variety of alternatives for server behavior; we consider threestopping rules, governing server behavior when the system is emptied, and twostarting rules, governing server behavior when an arrival occurs to an idle system. The Laplace-Stieltjes Transforms and means for the waiting time andserver return time (the interval from an arrival at an unserved queue until the server returns to that queue) are determined. For the special case of zero changeover times and strictly cyclic service, explicit results are obtained.     

A geometric process model for M/M/1 queueing system with a repairable service station

In this paper, we study a geometric process model for M/M/1 queueing system with a repairable service station. By introducing a supplementary variable, some queueing characteristics of the system and reliability indices of the service station are derived. Then a replacement policy N for the service station by which the service station will be replaced following the Nth failure is applied. An optimal replacement policy N¹ for minimizing the long-run average cost per unit time for the service station is then determined.     

A queueing model with bonus service for certain customers

A queueing model is introduced in which the management has a policy, because of economic reasons, of not operating the service counter unless a certain number, R + 1, of customers are available during each busy period. Thus, the first R customers who arrive must wait until the service counter is opened. Such a policy may cause the management to provide or render additional services to the first R customers. Assuming Poisson arrivals and that both regular and additional services follow exponential distributions, explicit expressions are derived for the stationary queue length and busy period distributions and their expected values. In the special case where R = 1, an explicit expression is presented for the stationary distribution of the waiting time.     

A queueing model of a production system with two machines,one operator and priorities

This paper studies a priority queueing model of a production system in which one operator serves two types of units with overlapping service times. The two types of units arrive in independent Poisson processes. There are two machines in the system. Units of type 1 receive two consecutive types of services at machine #1: the handwork performed by the operator and the automatic machining without the operator. Units of type 2 receive only the handwork performed by the operator at machine #2. The operator attends the two machines according to a strict-priority discipline which always gives units of type 2 higher priority than units of type 1. At each machine the handwork times have a general distribution, and at machine #1 the machining times have an exponential distribution. The Laplace-Stieltjes transform of the queue-size distributions and the waiting time distributions for a stationary process are obtained.     

A multi-server queueing model with server consultations

We consider a multi-server queueing model in which the arrivals occur according to a Markovian arrival process. One of the servers, henceforth referred to as the main server, offers consultation to fellow servers (referred to as regular servers) apart from serving the customers. A regular server may request a consultation only when serving a customer and is offered consultation on a first-come-first-served basis by the main server. The main server gives a preemptive priority to regular servers (for consulting) over customers. Thus, the main server can undergo interruptions during his/her servicing the customers. Under the assumptions of exponential services and consultations, the model is analyzed in steady-state using the well-known matrix-analytic methods. Illustrative numerical examples to bring out the qualitative nature of the model under study are presented.     

A tandem queueing model with coupled processors

We consider a tandem queue with coupled processors and analyze the two-dimensional Markov process representing the numbers of jobs in the two stations. A functional equation for the generating function of the stationary distribution of this two-dimensional process is derived and solved through the theory of Riemann-Hilbert boundary value problems.     

A catastrophic queueing model with delayed action

A queueing model with catastrophes and delayed action is studied in this paper. This delayed action could be in the form of protecting or removing all the customers that are in the system based on the outcome of two random clocks which are simultaneously activated upon the occurrence of a catastrophic event. Assuming the customers to arrive according to a versatile Markovian point process to a single server system, the service times to be of phase type, and all other underlying random variables to be exponentially distributed, we use matrix-analytic methods to study the delayed catastrophic model in steady-state. Needed expressions for the number in the system as well as the waiting time distributions are derived along with a discussion on some special cases of this model. Detailed illustrative examples are presented.     

A market-based multi-agent system model for decentralized multi-project scheduling

We consider a multi-project scheduling problem, where each project is composed of a set of activities, with precedence relations, requiring specific amounts of local and shared (among projects) resources. The aim is to complete all the project activities, satisfying precedence and resource constraints, and minimizing each project schedule length. The decision making process is supposed to be decentralized, with as many local decision makers as the projects. A multi-agent system model, and an iterative combinatorial auction mechanism for the agent coordination are proposed. We provide a dynamic programming formulation for the combinatorial auction problem, and heuristic algorithms for both the combinatorial auction and the bidding process. An experimental analysis on the whole multi-agent system model is discussed.     

A transient queueing model for Business Office with standby servers

Customers call Business Offices of a telephone company for services and billing information. We have considered a Business Office in which customers are usually serviced by scheduled servers. These scheduled servers are backed up by some standby servers who will answer a call only when the number of calls waiting to be answered is big. Impatient customers may renege. In this paper, we present a transient solution to a queueing model that can be used to help a Business Office manager efficiently determine the optimal numbers of scheduled and standby servers for achieving the designated service objective cost effectively. We have estimated that our model would save each of the 108 Business Office managers 20 minutes per day. Our tests of the model, using real data from randomly selected days, reveal that the model is about 93% accurate.