A multi-class discrete-time queueing system under the FCFS service discipline

The problem with the FCFS server discipline in discrete-time queueing systems is that it doesn’t actually determine what happens if multiple customers enter the system at the same time, which in the discrete-time paradigm translates into ‘during the same time-slot’. In other words, it doesn’t specify in which order such customers are served. When we consider multiple types of customers, each requiring different service time distributions, the precise order of service even starts to affect quantities such as queue content and delays of arbitrary customers, so specifying this order will be prime. In this paper we study a multi-class discrete-time queueing system with a general independent arrival process and generally distributed service times. The service discipline is FCFS and customers entering during the same time-slot are served in random order. It will be our goal to search for the steady-state distribution of queue content and delays of certain types of customers. If one thinks of the time-slot as a continuous but bounded time period, the random order of service is equivalent to FCFS if different customers have different arrival epochs within this time-slot and if the arrival epochs are independent of customer class. For this reason we propose two distinct ways of analysing; one utilizing permutations, the other considering a slot as a bounded continuous time frame.     

A discrete-time queueing system with optional LCFS discipline

We consider a discrete-time queueing system in which the arriving customers decide with a certain probability to be served under a LCFS-PR discipline and with complementary probability to join the queue. The arrivals are assumed to be geometrical and the service times are arbitrarily distributed. The service times of the expelled customers are independent of their previous ones. We carry out an extensive analysis of the system developing recursive formulae and generating functions for the steady-state distribution of the number of customers in the system and obtaining also recursive formulae and generating functions for the stationary distribution of the busy period and sojourn time as well as some performance measures.     

An M/G/1 queue with cyclic service times

In this paper we consider a single server queue with Poisson arrivals and general service distributions in which the service distributions are changed cyclically according to customer sequence number. This model extends a previous study that used cyclic exponential service times to the treatment of general service distributions. First, the stationary probability generating function and the average number of customers in the system are found. Then, a single vacation queueing system with aN-limited service policy, in which the server goes on vacation after servingN consecutive customers is analyzed as a particular case of our model. Also, to increase the flexibility of using theM/G/1 model with cyclic service times in optimization problems, an approximation approach is introduced in order to obtain the average number of customers in the system. Finally, using this approximation, the optimalN-limited service policy for a single vacation queueing system is obtained.On leave from the Department of Industrial Engineering, Iran University of Science and Technology, Narmak, Tehran 16844, Iran.     

On the stability of queueing systems under precedence restrictions for the service of customers

We consider queueing systems under precedence-based queueing disciplines and derive conditions for the stability of the system. The precedence restrictions are posed on customers' service in a way that a service can start only if some previous customers are served completely and some later customers arrived already. The stability depends on the interarrival times only through their means and the stability condition splits into two terms: with respect to a typical customer, one is representing the influences of future arrivals and one is representing the influences of past arrivals.     

The discrete-time preemptive repeat identical priority queue

Priority queueing systems come natural when customers with diversified delay requirements have to wait to get service. The customers that cannot tolerate but small delays get service priority over customers which are less delay-sensitive. In this contribution, we analyze a discrete-time two-class preemptive repeat identical priority queue with infinite buffer space and generally distributed service times. Newly arriving high-priority customers interrupt the on-going service of a low-priority customer. After all high-priority customers have left the system, the interrupted service of the low-priority customer has to be repeated completely. By means of a probability generating functions approach, we analyze the system content and the delay of both types of customers. Performance measures (such as means and variances) are calculated and the impact of the priority scheduling is discussed by means of some numerical examples.     

Workload in queues having priorities assigned according to service time

System designers often implement priority queueing disciplines in order to improve overall system performance; however, improvement is often gained at the expense of lower priority cystomers. Shortest Processing Time is an example of a priority discipline wherein lower priority customers may suffer very long waiting times when compared to their waiting times under a democratic service discipline. In what follows, we shall investigate a queueing system where customers are divided into a finitie number of priority classes according to their service times.We develop the multivariate generating function characterizing the joint workload among the priority classes. First moments obtained from the generating function yield traffic intensities for each priority class. Second moments address expected workloads, in particular, we obtain simple Pollaczek-Khinchine type formulae for the classes. Higher moments address variance and covariance among the workloads of the priority classes.This work was supported in part by National Science Foundation Grant DDM-8913658.     

Single line queue with repeated demands

We analyze a model of a queueing system in which customers can only call in to request service: if the server is free, the customer enters service immediately, but if the service system is occupied, the unsatisfied customer must break contact and reinitiate his request later. Such a customer is said to be in “orbit”. In this paper we consider three models characterized by the discipline governing the order of re-request of service from orbit. First, all customers in orbit can reapply, but are discouraged and reduce their rate of demand as more customers join the orbit. Secondly, the FCFS discipline operates for the unsatisfied customers in orbit. Finally, the LCFS discipline governs the customers in orbit and the server takes an exponentially distributed vacation after each service is completed. We calculate several characteristics quantities of such systems, assuming a general service-time distribution and different exponential distributions for the times between arrivals of first and repeat requests.     

Optimal static pricing for a service facility with holding costs

We study a service facility modelled as a single-server queueing system with Poisson arrivals and limited or unlimited buffer size. In systems with unlimited buffer size, the service times have general distributions, whereas in finite buffered systems service times are exponentially distributed. Arriving customers enter if there is room in the facility and if they are willing to pay the posted price. The same price is charged to all customers at all times (static pricing). The service provider is charged a holding cost proportional to the time that the customers spend in the system. We demonstrate that there is a unique optimal price that maximizes the long-run average profit per unit time. We also investigate how optimal prices vary as system parameters change. Finally, we consider buffer size as an additional decision variable and show that there is an optimal buffer size level that maximizes profit.     

Limit theorems for queueing systems with infinite number of servers and group arrival of requests

We consider an infinite-server queueing system where customers come by groups of random size at random i.d. intervals of time. The number of requests in a group and intervals between their arrivals can be dependent. We assume that service times have a regularly varying distribution with infinite mean. We obtain limit theorems for the number of customers in the system and prove limit theorems under appropriate normalizations.     

Assembly-like queues with finite capacity: Bounds,asymptotics and approximations

In this paper we study a queueing model of assembly-like manufacturing operations. This study was motivated by an examination of a circuit pack testing procedure in an AT & T factory. However, the model may be representative of many manufacturing assembly operations. We assume that customers fromn classes arrive according to independent Poisson processes with the same arrival rate into a single-server queueing station where the service times are exponentially distributed. The service discipline requires that service be rendered simultaneously to a group of customers consisting of exactly one member from each class. The server is idle if there are not enough customers to form a group. There is a separate waiting area for customers belonging to the same class and the size of the waiting area is the same for all classes. Customers who arrive to find the waiting area for their class full, are lost. Performance measures of interest include blocking probability, throughput, mean queue length and mean sojourn time. Since the state space for this queueing system could be large, exact answers for even reasonable values of the parameters may not be easy to obtain. We have therefore focused on two approaches. First, we find upper and lower bounds for the mean sojourn time. From these bounds we obtain the asymptotic solutions as the arrival rate (waiting room, service rate) approaches zero (infinity). Second, for moderate values of these parameters we suggest an approximate solution method. We compare the results of our approximation against simulation results and report good correspondence.     

Randomly Interrupted GI-G-1 Queues: Service Strategies and Stability Issues

We consider a discrete-time queueing system subjected to random server interruptions. As customers arriving in the queue require generally distributed service times, the server can be interrupted during a customer's service. Therefore, nine different service strategies are proposed and analyzed using a probability generating functions approach. Performance measures under investigation include moments of steady-state buffer contents at random slot boundaries in equilibrium and moments of the customer delay. In particular we focus on the stability requirements for the strategies under consideration.     

具有位相型修理的离散时间可修排队系统

本文研究了具有一般独立输入，位相型修理的离散时间可修排队系统，假定服务台对顾客的服务时间和服务台寿命服从几何分布，运用矩阵解析方法我们给出系统嵌入在到达时刻的稳态队长分布和等待时间分布，并证明这些分布均为离散位相型分布．我们也得到在广义服务时间内服务台发生故障次数的分布，证明它服从一个修正的几何分布．我们对离散时间可修排队与连续时间可修排队进行了比较，说明这两种排队系统在一些性能指标方面的区别之处．最后我们通过一些数值例子说明在这类系统中顾客的到达过程、服务时间和服务台的故障率之间的关系．     

M/G/1 queue with event-dependent arrival rates

Motivated by experiments on customers’ behavior in service systems, we consider a queueing model with event-dependent arrival rates. Customers’ arrival rates depend on the last event, which may either be a service departure or an arrival. We derive explicitly the performance measures and analyze the impact of the event-dependency. In particular, we show that this queueing model, in which a service completion generates a higher arrival rate than an arrival, performs better than a system in which customers are insensitive to the last event. Moreover, contrary to the M/G/1 queue, we show that the coefficient of variation of the service does not necessarily deteriorate the system performance. Next, we show that this queueing model may be the result of customers’ strategic behavior when only the last event is known. Finally, we investigate the historical admission control problem. We show that, under certain conditions, a deterministic policy with two thresholds may be optimal. This new policy is easy to implement and provides an improvement compared to the classical one-threshold policy.     

A recursive method to the optimal control of an M/G/1 queueing system with finite capacity and infinite capacity

We study a single removable server in an infinite and a finite queueing systems with Poisson arrivals and general distribution service times. The server may be turned on at arrival epochs or off at service completion epochs. We present a recursive method, using the supplementary variable technique and treating the supplementary variable as the remaining service time, to obtain the steady state probability distribution of the number of customers in a finite system. The method is illustrated analytically for three different service time distributions: exponential, 3-stage Erlang, and deterministic. Cost models for infinite and finite queueing systems are respectively developed to determine the optimal operating policy at minimum cost.     

Order restoration in queues

We examine a class of problems in queueing networks which arise when customers enter a bank of parallel servers in a given order and lose their place in the sequence due to passing resulting from variations in service times. The original sequence is required before service can take place at the next station in the network. These problems arise naturally in flexible manufacturing systems. The result is that the next station beyond the parallel bank of servers can be approximated by a non-Markovian bulk arrival system. This station sees batch arrivals of customers that are eligible to receive service. The size of the arriving batches is shown to depend on the inter-arrival times. Several fundamental results are established for this class of problems including the distribution of batch inter-arrival times, batch sizes, and an approximate method for determining the distribution of the number of eligible and an exact method for determining the distribution of the number of ineligible customers in the system.     

带有负顾客的M/M/c多重工作休假排队

考虑服务台在休假期间不是完全停止工作,而是以相对于正常服务期低些的服务率服务顾客的M/M/c工作休假排队模型.在此模型基础上,针对现实的M/M/c排队模型中可能出现的外来干扰因素,提出了带有负顾客的M/M/c工作休假排队这一新的模型.服务规则为先到先服务.工作休假策略为空竭服务异步多重工作休假.抵消原则为负顾客一对一抵消处于正常服务期的正顾客,若系统中无处于正常服务期的正顾客时,到达的负顾客自动消失,负顾客不接受服务.首先,由该多重休假模型得到其拟生灭过程及生成元矩阵,然后运用矩阵几何方法给出系统队长的稳态分布表达式和若干系统指标.     

A queueing system with random server capacity and multiple control

The authors study queueing, input and output processes in a queueing system with bulk service and state dependent service delay. The input flow of customers, modulated by a semi-Markov process, is served by a single server that takes batches of a certain fixed size if available or waits until the queue accumulates enough customers for service. In the latter case, the batch taken for service is of random size dependent on the state of the system, while service duration depends both on the state of the system and on the batch size taken. The authors establish a necessary and sufficient condition for equilibrium of the system and obtain the following results: Explicit formulas for steady state distribution of the queueing process, intensity of the input and output processes, and mean values of idle and busy periods. They employ theory of semi-regenerative processes and illustrate the results by a number of examples. In one of them an optimization problem is discussed.     

Analysis of a finite-source customer assignment model with no state information

In this paper we analyse a closed queueing network in which customers have to be assigned to parallel queues. The routing decision may not depend on the numbers of customers in the queues. We present an algorithm and we show that it computes an average optimal policy in case of exponential service times. The algorithm also works for non-exponential service times, in which case periodic policies are found.The research of this author has been supported by the Netherlands Organization for Scientific Research (N.W.O.) and was carried out at the University of Leiden.     

Waiting time analysis of a two-stage queueing system with priorities

A two-stage queueing system with two types of customers and non-preemptive priorities is analyzed. There is no waiting space between stages and so the blocking phenomenon is observed. The arrivals follow a Poisson distribution for the high priority customers and a gamma distribution for the low priority customers, while all service times are arbitrarily distributed. We derive expressions for the Laplace transform of the waiting time density of a low priority customer both in the transient and the steady state.     

Analysis of queueing systems with customer interjections

In this paper we study queueing systems with customer interjections. Customers are distinguished into normal customers and interjecting customers. All customers join a single queue waiting for service. A normal customer joins the queue at the end and an interjecting customer tries to cut in the queue. The waiting times of normal customers and interjecting customers are studied. Two parameters are introduced to describe the interjection behavior: the percentage of customers interjecting and the tolerance level of interjection by individual customers. The relationship between the two parameters and the mean and variance of waiting times is characterized analytically and numerically.