The M/G/1 retrial queue with Bernoulli schedules and general retrial times

This paper is concerned with the analysis of a single-server queue with Bernoulli vacation schedules and general retrial times. We assume that the customers who find the server busy are queued in the orbit in accordance with an FCFS (first-come-first-served) discipline and only the customer at the head of the queue is allowed access to the server. We first present the necessary and sufficient condition for the system to be stable and derive analytical results for the queue length distribution, as well as some performance measures of the system under steady-state condition. We show that the general stochastic decomposition law for M/G/1 vacation models holds for the present system also. Some special cases are also studied.     

On a batch arrival Poisson queue with a random setup time and vacation period

The single server queue with vacation has been extended to include several types of extensions and generalisations, to which attention has been paid by several researchers (e.g. see Doshi, B. T., Single server queues with vacations — a servey. Queueing Systems, 1986, 1, 29–66; Takagi, H., Queueing Analysis: A Foundation of Performance evaluation, Vol. 1, Vacation and Priority systems, Part. 1. North Holland, Amsterdam, 1991; Medhi, J., Extensions and generalizations of the classical single server queueing system with Poisson input. J. Ass. Sci. Soc., 1994, 36, 35–41, etc.). The interest in such types of queues have been further enhanced in resent years because of their theoretical structures as well as their application in many real life situations such as computer, telecommunication, airline scheduling as well as production/inventory systems. This paper concerns the model building of such a production/inventory system, where machine undergoes extra operation (such as machine repair, preventive maintenance, gearing up machinery, etc.) before the processing of raw material is to be started. To be realistic, we also assume that raw materials arrive in batch. This production system can be formulated as an M^x/M/1 queues with a setup time. Further, from the utility point of view of idle time this model can also be formulated as a case of multiple vacation model, where vacation begins at the end of each busy period. Besides, the production/inventory systems, such a model is generally fitted to airline scheduling problems also. In this paper an attempt has been made to study the steady state behavior of such an M^x/M/1 queueing system with a view to provide some system performance measures, which lead to remarkable simplification when solving other similar types of queueing models.This paper deals with the steady state behaviour of a single server batch arrival Poisson queue with a random setup time and a vacation period. The service of the first customer in each busy period is preceded by a random setup period, on completion of which service starts. As soon as the system becomes empty the server goes on vacation for a random length of time. On return from vacation, if he finds customer(s) waiting, the server starts servicing the first customer in the queue. Otherwise it takes another vacation and so on. We study the steady state behaviour of the queue size distribution at random (stationary) point of time as well as at departure point of time and try to show that departure point queue size distribution can be decomposed into three independent random variables, one of which is the queue size of the standard M^x/M/1 queue. The interpretation of the other two random variables will also be provided. Further, we derive analytically explicit expressions for the system state (number of customers in the system) probabilities and provide their appropriate interpretations. Also, we derive some system performance measures. Finally, we develop a procedure to find mean waiting time of an arbitrary customer.     

The interdeparture time distribution for each class in the ∑Mi/Gi/1 queue with set-up times and repeated server vacations

This paper studies the interdeparture time distribution of one class of customers who arrive at a single server queue where customers of several classes are served and where the server takes a vacation whenever the system becomes empty or is empty when the server returns from a vacation. Furthermore, the first customer in the busy period is allowed to have an exceptional service time (set-up time), depending on the class to which this customer belongs. Batches of customers of each class arrive according to independent Poisson processes and compete with each other on a FIFO basis. All customers who belong to the same class are served according to a common generally distributed service time. Service times, batch sizes and the arrival process are all assumed to be mutually independent. Successive vacation times of the server form independent and identically distributed sequences with a general distribution.For this queueing model we obtain the Laplace transform of the interdeparture time distribution for each class of customers whose batch size is geometrically distributed. No explicit assumptions of the batch size distributions of the other classes of customers are necessary to obtain the results.The paper ends by showing how the mathematical results can be used to evaluate a protocol that controls access to a shared medium of an ATM passive optical network. The numerical results presented in the last section of this paper show that the bundle spacing principle that is used by the permit distribution algorithm of this protocol introduces high delays and in many cases also more variable interdeparture times for the ATM cells of individual connections. An alternative algorithm is proposed that does not cope with these performance short comings and at the same time conserves the good properties of the protocol.     

Analysis of the discrete-time Geo/G/1 working vacation queue and its application to network scheduling

In this paper we present an exact steady-state analysis of a discrete-time Geo/G/1 queueing system with working vacations, where the server can keep on working, but at a slower speed during the vacation period. The transition probability matrix describing this queuing model can be seen as an M/G/1-type matrix form. This allows us to derive the probability generating function (PGF) of the stationary queue length at the departure epochs by the M/G/1-type matrix analytic approach. To understand the stationary queue length better, by applying the stochastic decomposition theory of the standard M/G/1 queue with general vacations, another equivalent expression for the PGF is derived. We also show the different cases of the customer waiting to obtain the PGF of the waiting time, and the normal busy period and busy cycle analysis is provided. Finally, we discuss various performance measures and numerical results, and an application to network scheduling in the wavelength division-multiplexed (WDM) system illustrates the benefit of this model in real problems.     

The analysis of the M/M/1 queue with two vacation policies (M/M/1/SWV+MV)

We consider an M/M/1 queue with two vacation policies which comprise single working vacation and multiple vacations, denoted by M/M/1/SMV+MV. Using two methods (called R-matrix method and G-matrix method), we obtain the stationary distribution of queue length (including the customer being in service) and make further analysis on the stationary numbers of customers in the working vacation and vacation period, respectively. The stochastic decomposition results of stationary queue length and the sojourn time of a customer are also derived. Meanwhile, we show that a simple and direct method of decomposition developed in Liu et al. [Stochastic decompositions in the M/M/1 queue with working vacations, Oper. Res. Lett. 35 (2007), pp. 595–600] is also applicable to our model. Furthermore, busy period is analysed by the limiting theorem of alternative renewal process. Finally, some boundary properties and numerical analysis on performance measures are presented.     

Equilibrium balking strategies in renewal input batch arrival queues with multiple and single working vacation

This paper investigates equilibrium threshold balking strategies of customers in a renewal input batch arrival queue with multiple and single working vacation of the server. The vacation period, service period during normal service and vacation period are considered to be independent and exponentially distributed. Upon arriving, the customers decide whether to join or balk the queue based on observation of the system-length and status of the server. The waiting time in the system is associated with a linear cost–reward structure for estimating the net benefit if a customer wishes to participate in the system. Equilibrium customer strategy is studied under four cases: fully observable, almost observable, almost unobservable and fully unobservable. Using embedded Markov chain approach and system cost analysis, we obtain the equilibrium threshold. The analysis of unobservable cases is based on the roots of the characteristics equations formed using the probability generating function of embedded pre-arrival epoch probabilities. Equilibrium balking strategy may be useful in quality of service for EPON (ethernet passive optical network) as a multiple working vacation model and accounting through gatekeeper based H.323 protocols as a single working vacation model.     

A discrete-time single-server queue with a modified N -policy

We consider a discrete-time single-server queue where the idle server waits for reaching a level N in the queue size to start a batch service of N messages, although the following arrivals during the busy period receive single services. We find the stationary distributions of the queue and system lengths as well as some performance measures. The vacation and busy periods of the system and the number of messages served during a busy period are also analyzed. The stationary distributions of the time spent waiting in the queue and in the system are studied too. Finally, a total expected cost function is developed to determine the optimal operating N-policy at minimum cost.     

An M/G/1 retrial G-queue with non-exhaustive random vacations and an unreliable server

This paper deals with an M/G/1 retrial queue with negative customers and non-exhaustive random vacations subject to the server breakdowns and repairs. Arrivals of both positive customers and negative customers are two independent Poisson processes. A breakdown at the busy server is represented by the arrival of a negative customer which causes the customer being in service to be lost. The server takes a vacation of random length after an exponential time when the server is up. We develop a new method to discuss the stable condition by finding absorb distribution and using the stable condition of a classical M/G/1 queue. By applying the supplementary variable method, we obtain the steady-state solutions for both queueing measures and reliability quantities. Moreover, we investigate the stochastic decomposition law. We also analyse the busy period of the system. Some special cases of interest are discussed and some known results have been derived. Finally, an application to cellular mobile networks is provided and the effects of various parameters on the system performance are analysed numerically.     

A pseudoconservation law for a time-limited service polling system with structured batch poisson arrivals

We consider a cyclic-service queueing system (polling system) with time-limited service, in which the length of a service period for each queue is controlled by a timer, i.e., the server serves customers until the timer expires or the queue becomes empty, whichever occurs first, and then proceeds to the next queue. The customer whose service is interrupted due to the timer expiration is attended according to the nonpreemptive service discipline. For the cyclic-service system with structured batch Poisson arrivals (M^x/G/1) and an exponential timer, we derive a pseudoconservation law and an exact mean waiting time formula for the symmetric system.     

Optimal Measurement-based Pricing for an M/M/1 Queue

In this paper, we consider a system modelled as an M/M/1 queue. Jobs corresponding to different classes are sent to the queue and are characterized by a delay cost per unit of time and a demand function. Our goal is to design an optimal pricing scheme for the queue, where the total charge depends on both the mean delay at the queue and arrival rate of each customer. We also assume that those two values have to be (statistically) measured, introducing errors on the total charge that might avert jobs from using the system, and then decrease demand. This model can be applied in telecommunication networks, where pricing can be used to control congestion, and the network can be characterized by a single bottleneck queue; the throughput of each class would be determined through passive measurements while the delay would be determined through active measurements.     

Stationary distributions and optimal control of queues with batch Markovian arrival process under multiple adaptive vacations

We consider an infinite-buffer single server queue with batch Markovian arrival process (BMAP) and exhaustive service discipline under multiple adaptive vacation policy. That is, the server serves until system emptied and after that server takes a random maximum number H different vacations until either he finds at least one customer in queue or the server have exhaustively taken all the vacations. The maximum number H of vacations taken by the server is a discrete random variable. We obtain queue-length distributions at various epochs such as, service completion/vacation termination, pre-arrival, arbitrary, post-departure and pre-service. The proposed analysis is based on the use of matrix-analytic procedure to obtain queue-length distribution at a post-departure epoch. Later we use supplementary variable method and simple algebraic manipulations to obtain the queue-length distribution at other epochs using queue-length distribution at post-departure epoch. Some important performance measures, like mean queue lengths and mean waiting times have been obtained. Several other vacation queueing models can be obtained as a special case of our model, e.g., single-, multiple-vacation model and queues with exceptional first vacation time. Finally, the total expected cost function per unit time is considered to determine a locally optimal multiple adaptive vacation policy at a minimum cost.     

Impatient customers in an M/M/1 queue with single and multiple working vacations

We consider an M/M/1 queue with impatient customers and two different types of working vacations. The working vacation policy is the one in which the server serves at a lower rate during a vacation period rather than completely stop serving. The customer’s impatience is due to its arrival during a working vacation period, in which the customer service rate is lower than the normal busy period. We analyze the queue for two different working vacation termination policies, a multiple working vacation policy and a single working vacation policy. Closed-form solutions and various performance measures like, the mean queue lengths and the mean waiting times are derived. The stochastic decomposition properties are verified for both multiple and single working vacation cases. A comparison of both the models is carried out to capture their performances with the change in system parameters.     

Queueing analysis and optimal control of and systems

We first consider a finite-buffer single server queue where arrivals occur according to batch Markovian arrival process (BMAP). The server serves customers in batches of maximum size ‘b’ with a minimum threshold size ‘a’. The service time of each batch follows general distribution independent of each other as well as the arrival process. We obtain queue length distributions at various epochs such as, pre-arrival, arbitrary, departure, etc. Some important performance measures, like mean queue length, mean waiting time, probability of blocking, etc. have been obtained. Total expected cost function per unit time is also derived to determine the optimal value N^* of N at a minimum cost for given values of a and b. Secondly, we consider a finite-buffer single server queue where arrivals occur according to BMAP and service process in this case follows a non-renewal one, namely, Markovian service process (MSP). Server serves customers according to general bulk service rule as described above. We derive queue length distributions and important performance measures as above. Such queueing systems find applications in the performance analysis of communication, manufacturing and transportation systems.     

On the multi-server retrial queue with geometric loss and feedback: computational algorithm and parameter optimization

We consider an M/M/c retrial queue with geometric loss and feedback. An arriving customer finding a free server enters into service immediately; otherwise the customer either enters into an orbit to try again after a random amount of time or leave the system without service. After the completion of service, he decides either to join the retrial orbit or to leave the system. The retrial system is modelled by a quasi-birth-and-death process, and some system performance measures are derived. The useful formulae for computing the rate matrix and stationary probabilities are derived by means of matrix-analytical approach. A cost model is derived to determine the optimal values of the number of servers and service rate simultaneously at the minimal total expected cost per unit time. Illustrative numerical examples demonstrate the optimization approach as well as the effect of various parameters on system performance measures.     

Analysis of Queues under Batch Service in an M/G/1 System in a Random Environment

A queue system with batch service is investigated. The batch size depends on the state both of the system and the state of some random environment. The server state changes under the action of the random environment. When the system is empty, a birth-death process acts as the random environment, whereas when the system is busy the random environment is disregarded and affects only the initial service probabilistic characteristics (in this sense, the random environment in the busy state can be regarded as arbitrary). An analytical model of the system is constructed and studied in terms Laplace (Laplace–Stieltjes) images. The generating function of the queue length is derived.     

Mean value analysis of re-entrant line with batch machines and multi-class jobs

We propose an approximate approach for estimating the performance measures of the re-entrant line with single-job machines and batch machines based on the mean value analysis (MVA) technique. Multi-class jobs are assumed to be processed in predetermined routings, in which some processes may utilize the same machines in the re-entrant fashion. The performance measures of interest are the steady-state averages of the cycle time of each job class, the queue length of each buffer, and the throughput of the system. The system may not be modeled by a product form queueing network due to the inclusion of the batch machines and the multi-class jobs with different processing times. Thus, we present a methodology for approximately analyzing such a re-entrant line using the iterative procedures based upon the MVA and some heuristic adjustments. Numerical experiments show that the relative errors of the proposed method are within 5% as compared against the simulation results.Scope and purposeWe consider a re-entrant shop with multi-class jobs, in which jobs may visit some machines more than once at different stages of processing, as observed in the wafer fabrication process of semiconductor manufacturing. The re-entrant line also consists of both the single-job machine and the batch machine. The former refers to the ordinary machine processing one job at a time, and the latter means the machine processing several jobs together as a batch at a time. In this paper, we propose an approximation method based on the mean value analysis for estimating the mean cycle time of each class of jobs, the mean queue length of each buffer, and the throughput of the system.     

Analysis of the M/G/1 queue with discriminatory random order service policy

We consider an M/G/1 queue with different classes of customers and discriminatory random order service (DROS) discipline. The DROS discipline generalizes the random order service (ROS) discipline: when the server selects a customer to serve, all customers waiting in the system have the same selection probability under ROS discipline, whereas customers belonging to different classes may have different selection probabilities under DROS discipline. For the M/G/1 queue with DROS discipline, we derive equations for the joint queue length distributions and for the waiting time distributions of each class. We also obtain the moments of the queue lengths and the waiting time of each class. Numerical results are given to illustrate our results.     

具有优先权的M/G/1重试可修排队系统

在服务台忙的情况下, 到达服务台的顾客以概率 q 进入无限位置的优先队列而以概率 p 进入无限位置的重试轨道 (orbit), 并且按照先到先服务 (FCFS) 规则排队, 假定只有队首的顾客允许重试, 同时考虑服务台可修的因素, 证明了系统稳态解存在的充要条件. 利用补充变量法求得稳态时两个队列与系统的平均队长、顾客等待时间、服务台的各种状态概率以及可靠性指标.     

M/M/1 retrial queue with working vacations

In this paper we introduce the new M/M/1 retrial queue with working vacations which is motivated by the performance analysis of a Media Access Control function in wireless systems. We give a condition for the stability of the model, which has an important impact on setting the retrial rate for such systems. We derive the closed form solution in equilibrium for the retrial M/M/1 queue with working vacations, and we also show that the conditional stochastic decomposition holds for this model as well.     

Grids with multiple batch systems for performance enhancement of multi-component and parameter sweep parallel applications

In this work, we evaluate the benefits of using Grids with multiple batch systems to improve the performance of multi-component and parameter sweep parallel applications by reduction in queue waiting times. Using different job traces of different loads, job distributions and queue waiting times corresponding to three different queuing policies (FCFS, conservative and EASY backfilling), we conducted a large number of experiments using simulators of two important classes of applications. The first simulator models Community Climate System Model (CCSM), a prominent multi-component application and the second simulator models parameter sweep applications. We compare the performance of the applications when executed on multiple batch systems and on a single batch system for different system and application configurations. We show that there are a large number of configurations for which application execution using multiple batch systems can give improved performance over execution on a single system.