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.     

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.     

Optimal control of parallel queues with impatient customers

We consider a queueing system with a number of identical exponential servers. Each server has its own queue with unlimited capacity. The service discipline in each queue is first-come-first-served (FCFS). Customers arrive according to a state-dependent Poisson process with an arrival rate which is a non-increasing function of the number of customers in the system. Upon arrival, a customer must join a server’s queue according to a stationary state-dependent policy, where the state is taken to be the number of customers in servers’ queues. No jockeying among queues is allowed. Each arriving customer is limited to a generally distributed patience time after which it must depart the system and is considered lost. Two models of customer behavior are considered: deadlines until the beginning of service and deadlines until the end of service. We seek an optimal policy to assign an arriving customer to a server’s queue. We show that, when the distribution of customer impatience satisfies certain property, the policy of joining shortest queue (SQ) stochastically minimizes the number of lost customers during any finite interval in the long run. This property is shown to always hold for the case of deterministic customer impatience.     

Optimal NT policies for M/G/1 system with a startup and unreliable server

This paper studies the control policies of an M/G/1 queueing system with a startup and unreliable server, in which the length of the vacation period is controlled either by the number of arrivals during the idle period, or by a timer. After all the customers are served in the queue exhaustively, the server immediately takes a vacation and operates two different policies: (i) the server reactivates as soon as the number of arrivals in the queue reaches to a predetermined threshold N or the waiting time of the leading customer reaches T units; and (ii) the server reactivates as soon as the number of arrivals in the queue reaches to a predetermined threshold N or T time units have elapsed since the end of the completion period. If the timer expires or the number of arrivals exceeds the threshold N, then the server reactivates and requires a startup time before providing the service until the system is empty. Furthermore, it is assumed that the server breaks down according to a Poisson process and his repair time has a general distribution. We analyze the system characteristics for each scheme. The total expected cost function per unit time is developed to determine the optimal thresholds of N and T at a minimum cost.     

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

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

The effect of workers with different capabilities on customer delay

Many service facilities operate seven days per week. The operations managers of these facilities face the problem of allocating personnel of varying skills and work speed to satisfy the demand for services. Furthermore, for practical reasons, periodic staffing schedule is implemented regularly. We introduce a novel approach for modeling periodic staffing schedule and analyzing the impact of employee variability on customer delay. The problem is formulated as a multiple server vacation queueing system with Bernoulli feedback of customers. At any point in time, at most one server can serve the customers. Each server incur a durations of set-up time before they can serve the customers. The customer service time and server set-up time may depend on the server. The service process is unreliable in the sense that it is possible for the customer at service completion to rejoin the queue and request for more service. The customer arrival process is assumed to satisfy a linear–quadratic model of uncertainty. We will present transient and steady-state analysis on the queueing model. The transient analysis provides a stability condition for the system to reach steady state. The steady-state analysis provides explicit expressions for several performance measures of the system. For the special case of M^X/G/1 vacation queue with a gated or exhaustive service policy and Bernoulli feedback, our result reduces to a previously known result. Lastly, we show that a variant of our periodic staffing schedule model can be used to analyze queues with permanent customers. For the special case of M/G/1 queue with permanent customers and Bernoulli feedback of ordinary customers, we obtain results previously given by Boxma and Cohen (IEEE J. Select. Areas Commun. 9 (1991) 179) and van den Berg (Sojourn Times in Feedback and Processor Sharing Queues, CWI Tracts, vol. 97, Amsterdam, Netherlands, 1993).Scope and purposeWorkforce scheduling is a classical problem and has been studied by many researchers. The problem is usually formulated with homogeneous workforce as part of the assumption. Clearly, non-homogeneous workforce is a fact of life for many organizations. Operations manager would prefer to have skills and experience worker as it would improve the quality of the services provided. Ignoring the effect of employees with varying skills and work speed would seriously undermine the effectiveness of the services provided and lead to significant undesirable outcomes for the organization. This paper aims as a first step to fill the gap of past research. We present a novel approach to analyze the issue of non-homogeneous workforce on stability of work flows and the effect of workers with different capabilities on customers’ waiting time. We believe that the results are useful for operations manager dealing with non-homogeneous workforce.     

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.     

Comparison of stability and queueing times for reader-writer queues

A reader-writer queue manages two classes of customers: readers and writers. An unlimited number of readers can be processed in parallel; writers are processed serially. Both classes arrive according to a Poisson process. Reader and writer service times are general iid random variables. There is infinite room in the queue for waiting customers.

In this paper, a reader-writer queue is considered under the following priority disciplines: strong reader preference (SRP), reader preference (RP), alternating exhaustive priority (AEP), writer preference (WP), and strong writer preference (SWP). Preemptive priority is given to readers under the SRP discipline, or to writers under the SWP discipline. Non-preemptive priority is accorded to readers with the RP discipline, or to writers with the WP discipline. For the AEP discipline, customers of a given class are served exhaustively in an alternating fashion.

For the five priority disciplines, a stability condition and first moments for the steady-state reader and writer queueing times are given. Using these analytical results, each of the five priority disciplines is seen to be optimal (among the five) in some region of the parameter space. Simulation results are also presented.     

A Two-Queue Polling Model with Two Priority Levels in the First Queue

In this paper we consider a single-server cyclic polling system consisting of two queues. Between visits to successive queues, the server is delayed by a random switch-over time. Two types of customers arrive at the first queue: high and low priority customers. For this situation the following service disciplines are considered: gated, globally gated, and exhaustive. We study the cycle time distribution, the waiting times for each customer type, the joint queue length distribution at polling epochs, and the steady-state marginal queue length distributions for each customer type.     

Sojourn times in polling systems with various service disciplines

We consider a polling system of N queues Q₁,…,Q_N, cyclically visited by a single server. Customers arrive at these queues according to independent Poisson processes, requiring generally distributed service times. When the server visits Q_i, i=1,…,N, it serves a number of customers according to a certain polling discipline. This discipline is assumed to belong to the class of branching-type disciplines, which includes the gated and exhaustive disciplines. The special feature of our study is that, within each queue, we do not restrict ourselves to service in order of arrival (FCFS); we are interested in the effect of different service disciplines, like Last-Come–First-Served, Processor Sharing, Random Order of Service, and Shortest Job First, on the sojourn time distribution of a typical customer that arrives to the system during steady-state. After a discussion of the joint distribution of the numbers of customers at each queue at visit epochs of the server to a particular queue, we determine the Laplace–Stieltjes transform of the cycle-time distribution, viz., the time between two successive visits of the server to, say, Q₁. This yields the transform of the joint distribution of past and residual cycle time, w.r.t. the arrival of a tagged customer at Q₁. Subsequently concentrating on the case of gated service at Q₁, we use that cycle-time result to determine the (Laplace–Stieltjes transform of the) sojourn-time distribution at Q₁, for each of the scheduling disciplines mentioned above.Next to locally gated polling disciplines, we also consider the globally gated discipline. Again, we consider various non-FCFS service disciplines at the queues, and we determine the (Laplace–Stieltjes transform of the) sojourn-time distribution at an arbitrary queue.