Two competing discrete-time queues with priority

This paper considers a class of two discrete-time queues with infinite buffers that compete for a single server. Tasks requiring a deterministic amount of service time, arrive randomly to the queues and have to be served by the server. One of the queues has priority over the other in the sense that it always attempts to get the server, while the other queue attempts only randomly according to a rule that depends on how long the task at the head of the queue has been waiting in that position. The class considered is characterized by the fact that if both queues compete and attempt to get the server simultaneously, then they both fail and the server remains idle for a deterministic amount of time. For this class we derive the steady-state joint generating function of the state probabilities. The queueing system considered exhibits interesting behavior, as we demonstrate by an example.     

Retrial queues with server subject to breakdowns and repairs

In this paper we consider a single server retrial queue where the server is subject to breakdowns and repairs. New customers arrive at the service station according to a Poisson process and demand i.i.d. service times. If the server is idle, the incoming customer starts getting served immediately. If the server is busy, the incoming customer conducts a retrial after an exponential amount of time. The retrial customers behave independently of each other. The server stays up for an exponential time and then fails. Repair times have a general distribution. The failure/repair behavior when the server is idle is different from when it is busy. Two different models are considered. In model I, the failed server cannot be occupied and the customer whose service is interrupted has to either leave the system or rejoin the retrial group. In model II, the customer whose service is interrupted by a failure stays at the server and restarts the service when repair is completed. Model II can be handled as a special case of model I. For model I, we derive the stability condition and study the limiting behavior of the system by using the tools of Markov regenerative processes.Visiting from Department of Applied Mathematics, Korea Advanced Institute of Science and Technology, Cheongryang, Seoul, Korea.     

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.     

有启动失败和可选服务的M/G/1重试排队系统

考虑具有可选服务的M/G/1重试排队模型,其中服务台有可能启动失败.系统外新到达的顾客服从参数为λ的泊松过程.重试区域只允许队首顾客重试,重试时间服务一般分布.所有的顾客都必须接受必选服务,然而只有其中部分接受可选服务.通过嵌入马尔可夫链法证明了系统稳态的充要条件.利用补充变量的方法得到了稳态时系统和重试区域中队长分布.我们还得到重试期间服务台处于空闲的概率,重试区域为空的概率以及其他各种指标.并证出在把系统中服务台空闲和修理的时间定义为广义休假情况下也具有随机分解特征.     

有Bernoulli休假和可选服务的M/G/1重试反馈排队模型

考虑具有可选服务的M/G/1重试反馈排队模型,其中服务台有Bernoulli休假策略.系统外新到达的顾客服从参数为λ的泊松过程.重试区域只允许队首顾客重试,重试时间服从一般分布.所有的顾客都必须接受必选服务,然而只有其中部分接受可选服务.每个顾客每次被服务完成后可以离开系统或者返回到重试区域.服务台完成一次服务以后,可以休假也可以继续为顾客服务.通过嵌入马尔可夫链法证明了系统稳态的充要条件.利用补充变量的方法得到了稳态时系统和重试区域中队长分布.我们还得到了重试期间服务台处于空闲的概率,重试区域为空的概率以及其他各种指标.并证出在系统中服务员休假和服务台空闲的时间定义为广义休假情况下也具有随机分解特征.     

Response times in gated M/G/1 queues: The processor-sharing case

A class of single server queues with Poisson arrivals and a gated server is considered. Whenever the server becomes idle the gate separating it from the waiting line opens, admitting all the waiting customers into service, and then closes again. The batch admitted into service may be served according to some arbitrary scheme. The equilibrium waiting time distribution is provided for the subclass of conservative schemes with arbitrary service times and the processor-sharing case is treated in some detail to produce the equilibrium time-in-service and response time distributions, conditional on the length of required service. The LIFO and random order of service schemes and the case of compound Poisson arrivals are treated briefly as examples of the effectiveness of the proposed method of analysis. All distributions are provided in terms of their Laplace transforms except for the case of exponential service times where the L.T. of the waiting time distribution is inverted. The first two moments of the equilibrium waiting and response times are provided for most treated cases and in the exponential service times case the batch size distribution is also presented.     

服务台不可靠的重试排队系统均衡分析

本文研究服务台不可靠的M/M/1常数率重试排队系统中顾客的均衡进队策略, 其中服务台在正常工作和空闲状态下以不同的速率发生故障。在该系统中, 服务台前没有等待空间, 如果到达的顾客发现服务台处于空闲状态, 该顾客可占用服务台开始服务。否则, 如果服务台处于忙碌状态, 顾客可以选择留下信息, 使得服务台在空闲时可以按顺序在重试空间中寻找之前留下信息的顾客进行服务。当服务台发生故障时, 正在被服务的顾客会发生丢失, 且系统拒绝新的顾客进入系统。根据系统提供给顾客的不同程度的信息, 研究队长可见和不可见两种信息情形下系统的稳态指标, 以及顾客基于收入-支出函数的均衡进队策略, 并建立单位时间内服务商的收益和社会福利函数。比较发现, 披露队长信息不一定能提高服务商收益和社会福利。     

A single-server discrete-time retrial <Emphasis Type="Italic">G</Emphasis>-queue with server breakdowns and repairs

This paper concerns a discrete-time Geo/Geo/1 retrial queue with both positive and negative customers where the server is subject to breakdowns and repairs due to negative arrivals. The arrival of a negative customer causes one positive customer to be killed if any is present, and simultaneously breaks the server down. The server is sent to repair immediately and after repair it is as good as new. The negative customer also causes the server breakdown if the server is found idle, but has no effect on the system if the server is under repair. We analyze the Markov chain underlying the queueing system and obtain its ergodicity condition. The generating function of the number of customers in the orbit and in the system are also obtained, along with the marginal distributions of the orbit size when the server is idle, busy or down. Finally, we present some numerical examples to illustrate the influence of the parameters on several performance characteristics of the system.     

A Discrete-Time Geo/G/1 retrial queue with the server subject to starting failures

This paper studies a discrete-time Geo/G/1 retrial queue where the server is subject to starting failures. We analyse the Markov chain underlying the regarded queueing system and present some performance measures of the system in steady-state. Then, we give two stochastic decomposition laws and find a measure of the proximity between the system size distributions of our model and the corresponding model without retrials. We also develop a procedure for calculating the distributions of the orbit and system size as well as the marginal distributions of the orbit size when the server is idle, busy or down. Besides, we prove that the M/G/1 retrial queue with starting failures can be approximated by its discrete-time counterpart. Finally, some numerical examples show the influence of the parameters on several performance characteristics. This work is supported by the DGINV through the project BFM2002-02189.     

Single server retrial queues with two way communication

The main aim of this paper is to study the steady state behavior of an M/G/1-type retrial queue in which there are two flows of arrivals namely ingoing calls made by regular customers and outgoing calls made by the server when it is idle. We carry out an extensive stationary analysis of the system, including stability condition, embedded Markov chain, steady state joint distribution of the server state and the number of customers in the orbit (i.e., the retrial group) and calculation of the first moments. We also obtain light-tailed asymptotic results for the number of customers in the orbit. We further formulate a more complicate but realistic model where the arrivals and the service time distributions are modeled in terms of the Markovian arrival process (MAP) and the phase (PH) type distribution.     

On the stability of retrial queues

We consider the following Type of problems. Calls arrive at a queue of capacity K (which is called the primary queue), and attempt to get served by a single server. If upon arrival, the queue is full and the server is busy, the new arriving call moves into an infinite capacity orbit, from which it makes new attempts to reach the primary queue, until it finds it non-full (or it finds the server idle). If the queue is not full upon arrival, then the call (customer) waits in line, and will be served according to the FIFO order. If λ is the arrival rate (average number per time unit) of calls and μ is one over the expected service time in the facility, it is well known that μ > λ is not always sufficient for stability. The aim of this paper is to provide general conditions under which it is a sufficient condition. In particular, (i) we derive conditions for Harris ergodicity and obtain bounds for the rate of convergence to the steady state and large deviations results, in the case that the inter-arrival times, retrial times and service times are independent i.i.d. sequences and the retrial times are exponentially distributed; (ii) we establish conditions for strong coupling convergence to a stationary regime when either service times are general stationary ergodic (no independence assumption), and inter-arrival and retrial times are i.i.d. exponentially distributed; or when inter-arrival times are general stationary ergodic, and service and retrial times are i.i.d. exponentially distributed; (iii) we obtain conditions for the existence of uniform exponential bounds of the queue length process under some rather broad conditions on the retrial process. We finally present conditions for boundedness in distribution for the case of nonpatient (or non persistent) customers. This revised version was published online in June 2006 with corrections to the Cover Date.     

Transient analysis of an M/G/1 retrial queue subject to disasters and server failures

An M/G/1 retrial queueing system with disasters and unreliable server is investigated in this paper. Primary customers arrive in the system according to a Poisson process, and they receive service immediately if the server is available upon their arrivals. Otherwise, they will enter a retrial orbit and try their luck after a random time interval. We assume the catastrophes occur following a Poisson stream, and if a catastrophe occurs, all customers in the system are deleted immediately and it also causes the server’s breakdown. Besides, the server has an exponential lifetime in addition to the catastrophe process. Whenever the server breaks down, it is sent for repair immediately. It is assumed that the service time and two kinds of repair time of the server are all arbitrarily distributed. By applying the supplementary variables method, we obtain the Laplace transforms of the transient solutions and also the steady-state solutions for both queueing measures and reliability quantities of interest. Finally, numerical inversion of Laplace transforms is carried out for the blocking probability of the system, and the effects of several system parameters on the blocking probability are illustrated by numerical inversion results.     

An M|G|1 Retrial Queue with Nonpersistent Customers and Orbital Search

Abstract

The M|G|1 retrial queue with nonpersistent customers and orbital search is considered. If the server is busy at the time of arrival of a primary customer, then with probability 1 ? H ₁ it leaves the system without service, and with probability H ₁ > 0, it enters into an orbit. Similarly, if the server is occupied at the time of arrival of an orbital customer, with probability 1 ? H ₂, it leaves the system without service, and with probability H ₂ > 0, it goes back to the orbit. Immediately after the completion of each service, the server searches for customers in the orbit with probability p > 0, and remains idle with probability 1 ? p. Search time is assumed to be negligible. In the case H ₂ = 1, the model is analyzed in full detail using the supplementary variable method. The joint distribution of the server state and the orbit length in steady state is studied. The structure of the busy period and its analysis in terms of Laplace transform is discussed. We also provide a direct method of calculation for the first and second moment of the busy period. In the case H ₂ < 1, closed form solution is obtained for exponentially distributed service time, in terms of hypergeometric series.     

Insensitivity in discrete time queues with a moving server

Queues in which customers request service consisting of an integral number of segments and in which the server moves from service station to service station are of considerable interest to practitioners working on digital communications networks. In this paper, we present insensitivity theorems and thereby equilibrium distributions for two discrete time queueing models in which the server may change from one customer to another after completion of each segment of service. In the first model, exactly one segment of service is provided at each time point whether or not an arrival occurs, while in the second model, at most one arrival or service occurs at each time point. In each model, customers of typet request a service time which consists ofl segments in succession with probabilityb _t(l). Examples are given which illustrate the application of the theorems to round robin queues, to queues with a persistent server, and to queues in which server transition probabilities do not depend on the server's previous position. In addition, for models in which the probability that the server moves from one position to another depends only on the distance between the positions, an amalgamation procedure is proposed which gives an insensitive model on a coarse state space even though a queue may not be insensitive on the original state space. A model of Daduna and Schassberger is discussed in this context.This work was supported by the Australian Research Council.     

Optimal control of a removable and non-reliable server in an M/M/1 queueing system with exponential startup time

We study a single removable and non-reliable server in the N policy M/M/1 queueing system. The server begins service only when the number of customers in the system reaches N (N1). After each idle period, the startup times of the server follow the negative exponential distribution. While the server is working, it is subject to breakdowns according to a Poisson process. When the server breaks down, it requires repair at a repair facility, where the repair times follow the negative exponential distribution. The steady-state results are derived and it is shown that the probability that the server is busy is equal to the traffic intensity. Cost model is developed to determine the optimal operating N policy at minimum cost.     

Mixed integer programming formulations for the Biomass Truck Scheduling problem

In this paper, we introduce the Biomass Truck Scheduling (BTS) problem that originated in a real-life herbaceous biomass supply chain (HBSC) around Pécs, Hungary. BTS can be considered as a Parallel Machine Scheduling with a Single Server problem, where identical trucks (parallel machines) deliver biomass from satellite storage locations to a central biorefinery operating a single unloader (single server). We make two particular assumptions regarding the server: the server operation has a unit time length for each trip and idle periods are not allowed for it (server no idle time constraint). We consider two objective functions associated with the revealed HBSC logistic cost structure. First, the number of trucks is minimized (resource availability cost) following which the total truck idle time is minimized. Three mixed integer programming formulations are constructed to solve BTS, and their efficiency is evaluated using a number of test cases. We found that, even if the number of trucks is locked at its minimum value, there is always a schedule with zero truck idle time—that is, there is no trade-off between these two objective functions.     

Equilibrium pricing in an M/G/1 retrial queue with reserved idle time and setup time

Power consumption is a ubiquitous and challenging problem in modern society. To save energy, one should turn off an idle device which still consumes about 60% of its peak consumption and switch it on again when some jobs arrive. However, it is not tolerate for delay sensitive applications. Therefore, there is a trade-off between power consumption and delay performance. In this paper we study an M/G/1 retrial queueing system with setup times in which the server keeps idle for a reserved idle time after completion of a service. If there are arrivals during this reserved idle time, these customers can be served immediately. Otherwise, the server will be turned off for saving energy until a new customer comes to activate the server. The setup time follows an exponential distribution. Based on the reward-cost function and the expected payoff, all customers will make decisions on whether to join or balk the system upon arrival. Given these strategic behaviors we study the optimal pricing strategies from the perspective of the server and social planner, respectively. The optimization of the reserved idle time for maximizing the server’s profit is also studied. Finally, numerical experiments are presented to illustrate the impact of system parameters on the customers’ equilibrium behavior and profit maximization solutions.     

Waiting times in queues with relative priorities

This paper determines the mean waiting times for a single server multi-class queueing model with Poisson arrivals and relative priorities. If the server becomes idle, the probability that the next job is from class-i is proportional to the product between the number of class-i jobs present and their priority parameter.     

Coordinated production and inspection in a tandem system

We study the coordination of production and quality control in a tandem-queue system. There are two stages, with a single server at stage one that can engage in processing an item, or inspecting the produced item, or staying idle; whereas the second stage represents the aggregate of the rest of the production facility. We focus on the optimal control of the first stage, where both the production and inspection times follow general distributions. We formulate a semi-Markov decision program with a long-run average objective, and derive the stationary optimal policy to control and coordinate the production, inspection, and idling processes. We show that there exists a threshold valuei ^–, such that under the optimal policy, once the threshold is reached, production should be suspended at the first stage; and this leads naturally toi ^–+1 being the required buffer capacity between the two stages.Supported in part by NSF Grant MDI-9523029.Supported in part by HKUST Grant DAG95/96.BM52.     

A Markovian single server with upstream job and downstream demand arrival stream

In this paper we consider a Markovian single server system which processes items arriving from an upstream region (as usual in queueing systems) and is controlled by a demand arrival stream for finished items from a downstream area. A finite storage is available at the server to store finished items not immediately needed in the downstream area. The system considered corresponds to an assembly-like queue with two input streams. The system is stable in a strict sense only if all queues are finite, i.e., both random processes are synchronized via blocking. This notion leads to a complementary system with a very similar state space which is a pair of Markovian single servers with synchronous arrivals. In the mathematical analysis the main focus is on the state probabilities and expectation of minimum and maximum of the two input queues. This revised version was published online in June 2006 with corrections to the Cover Date.