A note on comparing response times in the M/GI/1/FB and M/GI/1/PS queues

We compare the overall mean response time (a.k.a. sojourn time) of the processor sharing (PS) and feedback (FB) queues under an M/GI/1 system. We show that FB outperforms PS under service distributions having decreasing failure rates; whereas PS outperforms FB under service distributions having increasing failure rates.     

The GI/M/1 queue with exponential vacations

In this paper, we give a detailed analysis of the GI/M/1 queue with exhaustive service and multiple exponential vacation. We express the transition matrix of the imbedded Markov chain as a block-Jacobi form and give a matrix-geometric solution. The probability distribution of the queue length at arrival epochs is derived and is shown to decompose into the distribution of the sum of two independent random variables. In addition, we discuss the limiting behavior of the continuous time queue length processes and obtain the probability distributions for the waiting time and the busy period.     

服务台可修的GI／M（M／PH）／1排队系统

本文首次讨论一个到达间隔为一般分布的可修排队系统。假定服务时间、忙期服务台寿命都服从指疏分布，修复时间是ＰＨ变量。首先证明该系统可转化为一个经典的ＧＩ／￣ＰＨ／１排队模型，然后给出系统在稳态下的各种排队论指标和可靠性指标。     

Controlling the GI/M/1 queue by conditional acceptance of customers

In this paper we consider the problem of controlling the arrival of customers into a GI/M/1 service station. It is known that when the decisions controlling the system are made only at arrival epochs, the optimal acceptance strategy is of a control-limit type, i.e., an arrival is accepted if and only if fewer than n customers are present in the system. The question is whether exercising conditional acceptance can further increase the expected long run average profit of a firm which operates the system. To reveal the relevance of conditional acceptance we consider an extension of the control-limit rule in which the nth customer is conditionally admitted to the queue. This customer may later be rejected if neither service completion nor arrival has occurred within a given time period since the last arrival epoch. We model the system as a semi-Markov decision process, and develop conditions under which such a policy is preferable to the simple control-limit rule.     

Workload and busy period for M/GI/1 with a general impatience mechanism

The paper deals with the workload and busy period for the $M/GI/1$ M / G I / 1 system with impatience under FCFS discipline. The customers may become impatient during their waiting for service with generally distributed maximal waiting times and also during their service with generally distributed maximal service times depending on the time waited for service. This general impatience mechanism was originally introduced by Kovalenko (1961) and considered by Daley (1965), too. It covers the special cases of impatience on waiting times as well as impatience on sojourn times, for which Boxma et al. (2010, 2011) gave new results and outlined special cases recently. Our unified approach bases on the vector process of workload and busy time. Explicit representations for the LSTs of workload and busy period are given in case of phase-type distributed impatience.     

Performance Analysis of the GI/M/1 Queue with Single Working Vacation and Vacations

In this paper, we consider a new class of the GI/M/1 queue with single working vacation and vacations. When the system become empty at the end of each regular service period, the server first enters a working vacation during which the server continues to serve the possible arriving customers with a slower rate, after that, the server may resume to the regular service rate if there are customers left in the system, or enter a vacation during which the server stops the service completely if the system is empty. Using matrix geometric solution method, we derive the stationary distribution of the system size at arrival epochs. The stochastic decompositions of system size and conditional system size given that the server is in the regular service period are also obtained. Moreover, using the method of semi-Markov process (SMP), we gain the stationary distribution of system size at arbitrary epochs. We acquire the waiting time and sojourn time of an arbitrary customer by the first-passage time analysis. Furthermore, we analyze the busy period by the theory of limiting theorem of alternative renewal process. Finally, some numerical results are presented.     

A sample path analysis of M/GI/1 queues with workload restrictions

A simple random time change is used to analyze M/GI/1 queues with workload restrictions. The types of restrictions considered include workload bounds and rejection of jobs whose waiting times exceed a (possibly random) threshold. Load dependent service rates and vacations are also allowed and in each case the steady state distribution of the workload process for the system with workload restrictions is obtained in terms of that of the corresponding M/ GI/1 queue without restrictions. The novel sample path arguments used simplify and generalize previous results.     

The GI/M/1 queue with phase-type working vacations and vacation interruption

Consider a GI/M/1 queue with phase-type working vacations and vacation interruption where the vacation time follows a phase-type distribution. The server takes the original work at the lower rate during the vacation period. And, the server can come back to the normal working level at a service completion instant if there are customers at this instant, and not accomplish a complete vacation. From the PH renewal process theory, we obtain the transition probability matrix. Using the matrix-analytic method, we obtain the steady-state distributions for the queue length at arrival epochs, and waiting time of an arbitrary customer. Meanwhile, we obtain the stochastic decomposition structures of the queue length and waiting time. Two numerical examples are presented lastly.     

Performance analysis of GI/M/1 queue with working vacations and vacation interruption

In this paper, we analyze a single-server vacation queue with a general arrival process. Two policies, working vacation and vacation interruption, are connected to model some practical problems. The GI/M/1 queue with such two policies is described and by the matrix analysis method, we obtain various performance measures such as mean queue length and waiting time. Finally, using some numerical examples, we present the parameter effect on the performance measures and establish the cost and profit functions to analyze the optimal service rate η during the vacation period.     

Dynamic scheduling of a GI/GI/1+GI queue with multiple customer classes

We consider a dynamic control problem for a GI/GI/1+GI queue with multiclass customers. The customer classes are distinguished by their interarrival time, service time, and abandonment time distributions. There is a cost c _k >0 for every class k∈{1,2,…,N} customer that abandons the queue before receiving service. The objective is to minimize average cost by dynamically choosing which customer class the server should next serve each time the server becomes available (and there are waiting customers from at least two classes). It is not possible to solve this control problem exactly, and so we formulate an approximating Brownian control problem. The Brownian control problem incorporates the entire abandonment distribution of each customer class. We solve the Brownian control problem under the assumption that the abandonment distribution for each customer class has an increasing failure rate. We then interpret the solution to the Brownian control problem as a control for the original dynamic scheduling problem. Finally, we perform a simulation study to demonstrate the effectiveness of our proposed control.     

Vacations in GI X/M Y/1 systems and Riemann boundary value problems

We consider systems of GI/M/1 type with bulk arrivals, bulk service and exponential server vacations. The generating functions of the steady-state probabilities of the embedded Markov chain are found in terms of Riemann boundary value problems, a necessary and sufficient condition of ergodicity is proved. Explicit formulas are obtained for the case where the generating function of the arrival group size is rational. Resonance between the vacation rate and the system is studied. Complete formulas are given for the cases of single and geometric arrivals. This revised version was published online in June 2006 with corrections to the Cover Date.     

服务台可修的GI/PH/1排队系统

本文讨论服务台可修的GI/PH/1排队,其中服务台寿命和修复时间也是PH变量。首先证明系统在稳态下可转化为一个等价的经典GI/PH/1模型,然后给出系统的各种稳态指标。此外,对修复后重新服务和累积服务两种不同模型,我们给出了统一的处理。     

The conditional sojourn time distribution in the GI/M/1 processor-sharing queue in heavy traffic

We treat the GI/M/1 queue with a processor-sharing server, in the heavy traffic case. Using perturbation methods, we construct asymptotic expansions for the conditional sojourn time distribution of a tagged customer conditioned on the tagged customer's service time. The resulting approximation is simple in form and involves only the first three moments of the interarrival time distribution.     

GI/M/1 Queue with Server Vacations

A queueing model with server vacations is studied in which it is assumed that the interarrival time has a general distribution, the service-time distribution is exponential and vacations are independently and indentically distributed with a general distribution. Using the embedded Markov chain technique, the equilibrium probability distributions of system size have been obtained at pre-arrival and at random epochs separately. Finally, the distribution of waiting time of a customer in the queue (excluding service) has been derived.     

A large-deviations analysis of the GI/GI/1 SRPT queue

We consider a GI/GI/1 queue with the shortest remaining processing time discipline (SRPT) and light-tailed service times. Our interest is focused on the tail behavior of the sojourn-time distribution. We obtain a general expression for its large-deviations decay rate. The value of this decay rate critically depends on whether there is mass in the endpoint of the service-time distribution or not. An auxiliary priority queue, for which we obtain some new results, plays an important role in our analysis. We apply our SRPT results to compare SRPT with FIFO from a large-deviations point of view. 2000 Mathematics Subject Classification: Primary—60K25; Secondary—60F10; 90B22     

A Recursive Algorithm for State Dependent GI/M/1/N Queue with Bernoulli-Schedule Vacation

In this paper, we study a renewal input working vacations queue with state dependent services and Bernoulli-schedule vacations. The model is analyzed with single and multiple working vacations. The server goes for exponential working vacation whenever the queue is empty and the vacation rate is state dependent. At the instant of a service completion, the vacation is interrupted and the server resumes a regular busy period with probability 1???q (if there are customers in the queue), or continues the vacation with probability q (0?≤?q?≤?1). We provide a recursive algorithm using the supplementary variable technique to numerically compute the stationary queue length distribution of the system. Finally, using some numerical results, we present the parameter effect on the various performance measures.     

两类负顾客M/GI/1系统的统计平衡条件

负顾客排队模型由于其灵活模拟各种复杂随机现象的广阔的应用前景，当前正越来越受到各类高性能通讯网络研究多方面的广泛关注．由于负顾客的抵消作用这类系统可以容许在顾客到达率大于服务率的情况下，进入平稳状态．本文用马尔可夫更新理论和Foster负偏移准则，研究了两类M／GI／1负顾客排队模型进入平稳状态的充要条件，首次得到了负顾客更新到达情况下，带负顾客抵消队列头部正顾客和队列尾部正顾客两种策略下的M／GI／1（FCFS）系统的统计平衡条件．当负顾客到达取更新过程的特例一泊松过程时，这一结果与Harrison＆Pital（1996）中所得结果完全一致．     

TheM/GI/1 Bernoulli feedback queue with vacations

Feedback may be introduced as a mechanism for scheduling customer service (for example in systems in which customers bring work that is divided into a random number of stages). A model is developed that characterizes the queue length distribution as seen following vacations and service stage completions. We demonstrate the relationship that exists between these distributions. The ergodic waiting time distribution is formulated in such a way as to reveal the effects of server vacations when feedback is introduced.This work was supported in part by NSF Grant No. DDM-8913658.     

The GI/M/1 queue with start-up period and single working vacation and Bernoulli vacation interruption

Consider a GI/M/1 queue with start-up period and single working vacation. When the system is in a closed state, an arriving customer leading to a start-up period, after the start-up period, the system becomes a normal service state. And during the working vacation period, if there are customers at a service completion instant, the vacation can be interrupted and the server will come back to the normal working level with probability p (0 ? p ? 1) or continue the vacation with probability 1 − p. Meanwhile, if there is no customer when a vacation ends, the system is closed. Using the matrix-analytic method, we obtain the steady-state distributions for the queue length at both arrival epochs and arbitrary epochs, the waiting time and sojourn time.     

The GI/M/1 queue with Bernoulli-schedule-controlled vacation and vacation interruption

Consider a GI/M/1 queue with multiple vacations. As soon as the system becomes empty, the server either begins an ordinary vacation with probability q  (0?q?1)$(0?q?1)$ or takes a working vacation with probability 1-q$1-q$. We assume the vacation interruption is controlled by Bernoulli. If the system is non-empty at a service completion instant in a working vacation period, the server can come back to the normal busy period with probability p  (0?p?1)$(0?p?1)$ or continue the vacation with probability 1-p$1-p$. Using the matrix-analytic method, we obtain the steady-state distributions for the queue length both at arrival and arbitrary epochs. The waiting time and sojourn time are also derived by different methods. Finally, some numerical examples are presented.