Workload and Waiting Time Analyses of MAP/G/1 Queue under D-policy

We study the workload (unfinished work) and the waiting time of the queueing system with MAP arrivals under D-policy. The D-policy stipulates that the idle server begin to serve the customers only when the sum of the service times of all waiting customers exceeds some fixed threshold D. We first set up the system equations for workload and obtain the steady-state distributions of workloads at an arbitrary idle and busy points of time. We then proceed to obtain the waiting time distribution of an arbitrary customer based on the workload results. The M/G/1/D-policy queue will be investigated as a special case.     

Decomposition of an M/D/r·k queue with FIFO into k Ek/D/r queues with FIFO

It is observed that the queuing system M/D/r·k with FIFO has the same waiting time distribution as the queuing system E_k/D/r with FIFO. Using this simple equivalence we can apply numerical methods and tables for M/Dn to solve E_k/D/r.     

A simple approach for analyzing feedback vacation queues with levy input process

We introduce a simple approach for modeling and analyzing a SII/G/I queue where the server may take repeated vacations. Whenever a busy period ends the server takes a vacation of random duration. At the end of each vacation the server may either take a new vacation or resume service; if the queue is found empty the server always takes a new vacation. Furthermore, the queuing system allows Bernoulli feedback of customers. Three classes of service disciplines, random gated, 1-limited and exhaustive, are considered. The random gated service discipline generalizes several known service disciplines. The customers arrival process is assumed to be a Levy process (i.e., satisfies the stationary and independent increments (SII property). We obtain explicit expressions for several performance measures of the system. These performance measures include the mean and second moment of the cycle time, the mean queue length at the beginning of a cycle of service and the expected delay observed by a customer. Furthermore, our analysis provides a uniform method to get several results previously obtained by Baba, Chiarawongse and Sriniwasan, and Takine, Takagi and Hasegawa.     

Parametric nonlinear programming approach to fuzzy queues with bulk service

This paper proposes a procedure to construct the membership functions of the performance measures in bulk service queuing systems with the arrival rate and service rate are fuzzy numbers. The basic idea is to transform a fuzzy queue with bulk service to a family of conventional crisp queues with bulk service by applying the α-cut approach. On the basis of α-cut representation and the extension principle, a pair of parametric nonlinear programs is formulated to describe that family of crisp bulk service queues, via which the membership functions of the performance measures are derived. To demonstrate the validity of the proposed procedure, two fuzzy queues often encountered in transportation management are exemplified. Since the performance measures are expressed by membership functions rather than by crisp values, they completely conserve the fuzziness of input information when some data of bulk-service queuing systems are ambiguous. Thus the proposed approach for vague systems can represent the system more accurately, and more information is provided for designing queuing systems in real life. By extending to fuzzy environment, the bulk service queuing models would have wider applications.     

Simulation of a random fuzzy queuing system with multiple servers

The paper considers a queuing system that has k servers and its interarrival times and service times are random fuzzy variables.We obtain a theorem concerning the average chance of the event “r servers (r ≤ k) are busy at time t”, provided that all the servers work independently. We simulate the average chance using fuzzy simulation method and obtain some results on the number of servers that are busy. Some examples to illustrate the simulation procedure are also presented.     

?/M/1: On the equilibrium distribution of customer arrivals

Each day a facility commences service at time zero. All customers arriving prior to time T are served during that day. The queuing discipline is First-Come First-Served. Each day, each person in the population chooses whether or not to visit the facility that day. If he decides to visit, he arrives at an instant of time such that his expected waiting time in the queue is minimal. We investigate the arrival rate of customers in equilibrium, where each customer is fully aware of the characteristics of the system. We show that the arrival rate is constant before opening time, but that in general it is not constant between opening and closing time. For the case of exponential distribution of service time, we develop a set of equations from which the equilibrium queue size distribution and expected waiting time can be numerically computed as functions of time.     

Tables for M/G/c queuing systems with phase-type service

Currently much research is done on the development of simple approximations for complex queuing systems. This practically important research is usually hampered by the fact that no exact results are available for a thorough testing of the approximations. In this paper we give for several M/G/c queuing systems with phase-type service the exact values for both the delay probability and the first two moments of the queuing time. These tables considerably extend the widely used Hillier-Lo tables which only consider Erlangian service and small values for the number of servers. The aim of the publication of our tables is to supply much needed test material to the research community and in this way to contribute to further progress in the research on queuing approximations. We present the result of the testing of several existing approximations. Also, the tables provide the practitioner with numerical results useful to design queuing systems.     

On optimal serving policies when customer payment is random

This paper deals with whether or not to let in an arriving customer to a N-server queuing system with no room for waiting customers, depending on how much he will pay for service and the number of customers already in the system, on the assumption that we want to maximize expected income per unit of time.     

Asymptotic independence of queues under randomized load balancing

Randomized load balancing greatly improves the sharing of resources while being simple to implement. In one such model, jobs arrive according to a rate-??N Poisson process, with ??<1, in a system of N rate-1 exponential server queues. In Vvedenskaya et al. (Probl. Inf. Transm. 32:15?C29, 1996), it was shown that when each arriving job is assigned to the shortest of D, D??2, randomly chosen queues, the equilibrium queue sizes decay doubly exponentially in the limit as N????. This is a substantial improvement over the case D=1, where queue sizes decay exponentially. The reasoning in Vvedenskaya et al. (Probl. Inf. Transm. 32:15?C29, 1996) does not easily generalize to jobs with nonexponential service time distributions. A?modularized program for treating randomized load balancing problems with general service time distributions was introduced in Bramson et al. (Proc. ACM SIGMETRICS, pp.?275?C286, 2010). The program relies on an ansatz that asserts that, for a randomized load balancing scheme in equilibrium, any fixed number of queues become independent of one another as N????. This allows computation of queue size distributions and other performance measures of interest. In this article, we demonstrate the ansatz in several settings. We consider the least loaded balancing problem, where an arriving job is assigned to the queue with the smallest workload. We also consider the more difficult problem, where an arriving job is assigned to the queue with the fewest jobs, and demonstrate the ansatz when the service discipline is FIFO and the service time distribution has a decreasing hazard rate. Last, we show the ansatz always holds for a sufficiently small arrival rate, as long as the service distribution has 2 moments.     

System G|Gκ|1 with Batch Service of Calls

For the queuing system G|G |1 with batch service of calls, we determine the distributions of the following characteristics: the length of a busy period, the queue length in transient and stationary modes of the queuing system, the total idle time of the queuing system, the output stream of served calls, etc.     

Main Probability Characteristics of the Queuing System Gκ|G|1

For the queuing system G |G|1 with batch arrivals of calls, we present the distributions of the following characteristics: the length of a busy period, queue length in transient and stationary modes of the queuing system, total idle time of the queuing system, virtual waiting time to the beginning of the service, input stream of calls, output stream of served calls, etc.     

Stochastically minimizing the number of customers in exponential queuing systems

This paper deals with the problem of controlling an exponential queuing system (that is, a system with exponential service times and Poisson arrivals) so as to stochastically minimize the number of customers in the system at any time t > 0. Sufficient (simple) conditions are developed for a policy to be optimal. Similar conditions are sufficient for a policy to stochastically minimize (maximize) any function of the state of the system. Two models are considered to illustrate the results. In both cases, optimal policies are shown to satisfy these conditions by a simple inductive procedure.     

Unslotted CSMA/CD protocol with the threshold control policy

We consider a single channelCSM A/CD system withD homogeneous stations and impeded buffer of infinite size. We find a sufficient condition for the model to be stable under the threshold control policy and derive the limiting distribution of the number of messages in the system at the moment of service completion. We also derive the limiting distribution of the number of messages in the system size at arbitrary time by using Markov regenerative processes. Some numerical examples and special cases are also treated.     

The two-machine open shop problem: To fit or not to fit, that is the question

We consider the open shop scheduling problem with two machines. Each job consists of two operations, and it is prescribed that the first (second) operation has to be executed by the first (second) machine. The order in which the two operations are scheduled is not fixed, but their execution intervals cannot overlap. We are interested in the question whether, for two given values D₁ and D₂, there exists a feasible schedule such that the first and second machine process all jobs during the intervals [0,D₁] and [0,D₂], respectively.We formulate four simple conditions on D₁ and D₂, which can be verified in linear time. These conditions are necessary and sufficient for the existence of a feasible schedule. The proof of sufficiency is algorithmical, and yields a feasible schedule in linear time. Furthermore, we show that there are at most two non-dominated points (D₁,D₂) for which there exists a feasible schedule.     

Parallel queuing systems with and without decentralized server reallocation — A simulation study

This paper describes the results of an initial exploratory research effort on the subject of the dynamic reallocation of servers in a group of parallel queuing systems under decentralized control. Each queuing system is described as being (M/E_k/c_i,t): (FCFS/∞/∞) where t = 1,.., ∞ and i = 1,..., I. Server reallocation is handled by a (G^(b)/G/C): (FCS/C/K) system — where C = Σ_t=1^∞Σ_i=1^Ic_i,t and K is an unknown constant — located at a higher level than the group members. The customers of the latter system are requests for servers independently generated by identical heuristic event-triggered operating policies at each of the lower level systems. These local policies are of the stochastic review, relative control number type. Performance is measured by means of a variety of criteria from the viewpoint of the group as a whole (global) as well as an individual queuing system (local). Results of experiments using a simulation model confirmed the null hypothesis that the customer service behaviour of a group that shared servers was significantly different from the behaviour of a control group that did not share servers.     

The optimal strategy structure of an intermittently operated service channel

An analysis is made of the policy space structure for an intermittently operated M/M/1 queuing system. When the queue length builds up to limit N, the service channel is opened and service rendered until the queue length is reduced to some lower number, v, whereupon the channel is closed. Certain costs, namely these of lost customers, of giving service and of opening and closing the channel are imposed. A technique for dividing the policy space into regions of optimal {v, N} is developed so that the best strategy for any combination of costs is immediately visible to the decision maker.     

Some related paradoxes of queuing theory: new cases and a unifying explanation

In this paper, we study a number of closely related paradoxes of queuing theory, each of which is based on the intuitive notion that the level of congestion in a queuing system should be directly related to the stochastic variability of the arrival process and the service times. In contrast to such an expectation, it has previously been shown that, in all H _k /G/1 queues, PW (the steady-state probability that a customer has to wait for service) decreases when the service-time becomes more variable. An analagous result has also been proved for p_loss (the steady-state probability that a customer is lost) in all H_k/G/1 loss systems. Such theoretical results can be seen, in this paper, to be part of a much broader scheme of paradoxical behaviour which covers a wide range of queuing systems. The main aim of this paper is to provide a unifying explanation for these kinds of behaviour. Using an analysis based on a simple, approximate model, we show that, for an arbitrary set of n GI/G_k/1 loss systems (k=1,..., n), if the interarrival-time distribution is fixed and ‘does not differ too greatly’ from the exponential distribution, and if the n systems are ordered in terms of their p_loss values, then the order that results whenever c_A<1 is the exact reverse of the order that results whenever c_A>1, where c_A is the coefficient of variation of the interarrival time. An important part of the analysis is the insensitivity of the p_loss value in an M/G/1 loss system to the choice of service-time distribution, for a given traffic intensity. The analysis is easily generalised to other queuing systems for which similar insensitivity results hold. Numerical results are presented for paradoxical behaviour of the following quantities in the steady state: p_loss in the GI/G/1 loss system; PW and W _q (the expected queuing time of customers) in the GI/G/1 queue; and p_K (the probability that all K machines are in the failed state) in the GI/G/r machine interference model. Two of these examples of paradoxical behaviour have not previously been reported in the literature. Additional cases are also discussed.     

A note on the allocation of queuing facilities using a minisum criterion

This paper suggests a formulation and a solution procedure for resource allocation problems which consider a central planner, m static queuing facilities providing a homogeneous service at their locations, and a known set of demand points or customers. It is assumed that upon a request for service the customer is routed to a facility by a probabilistic assignment. The objective is to determine how to allocate a limited number of servers to the facilities, and to specify demand rates from customers to facilities in order to minimize a weighted sum of response times. This sum measures the total time lost in the system due to two sources: travel time from customer to facility locations and waiting time for service at the facilities. The setting does not allow for cooperation between the facilities.     

The throughput performance of a prioritized LIFO service discipline

The LIFO service discipline maximizes throughput for certain queuing systems with delay-dependent customer behavior. To study the effects of priorities in such a system, we obtain delay distributions for each customer class of a K-class, single server system with nonpreemptive priorities and LIFO within each queue.     

Capacity and price setting for dispersed,time-sensitive customer segments

We consider joint pricing and capacity decisions for a facility serving heterogeneous consumers that span a continuous range of locations, and are sensitive to time delays. Within this context, we analyze two contrasting service strategies: segmentation and pooling. Consumer segments differ with respect to their reservation prices and time sensitivities, and are dispersed over a single distance dimension. The firm serves these consumers using a process that we initially model as an M/M/1 queuing system. We analyze profit-maximizing price and capacity levels for a monopolist, and contrast the optimal segmentation and pooling policies. We find that when consumers are time sensitive, and can expect queuing delays at the firm’s facility (due to random arrival and service times), then scale economies from pooling can outweigh segmentation benefits. Yet, segmentation outperforms pooling when consumer segments differ substantively, in which case the firm can use capacity as a lever to price discriminate between the segments. Moreover, by contrasting a dedicated-services strategy, which directly targets specific segments and serves them separately, with the alternative of allowing consumers to self-select, we find that self-selection has a moderate negative influence on profits. We also examine the profit impact of employing alternative queuing systems, and find that a hybrid strategy based on a prioritized queuing discipline, that combines elements of segmentation (by offering different waiting times) and pooling (by sharing capacity across consumer segments), can outperform both the pure segmentation and pooling strategies.