An assignment problem for a parallel queueing system with two heterogeneous servers

In this paper, we consider an optimization problem for a parallel queueing system with two heterogeneous servers. Each server has its own queue and customers arrive at each queue according to independent Poisson processes. Each service time is independent and exponentially distributed. When a customer arrives at queue 1, the customers in queue 1 can be transferred to queue 2 by paying an assignment cost which is proportional to the number of moved customers. Holding cost is a function of the pair of queue lengths of the two servers. Our objective is to minimize the expected total discounted cost. We use the dynamic programming approach for this problem. Considering the pair of queue lengths as a state space, we show that the optimal policy has a switch over structure under some conditions on the holding cost.     

On optimal polling policies

In a single-server polling system, the server visits the queues according to a routing policy and while at a queue, serves some or all of the customers there according to a service policy. A polling (or scheduling) policy is a sequence of decisions on whether to serve a customer, idle the server, or switch the server to another queue. The goal of this paper is to find polling policies that stochastically minimize the unfinished work and the number of customers in the system at all times. This optimization problem is decomposed into three subproblems: determine the optimal action (i.e., serve, switch, idle) when the server is at a nonempty queue; determine the optimal action (i.e., switch, idle) when the server empties a queue; determine the optimal routing (i.e., choice of the queue) when the server decides to switch. Under fairly general assumptions, we show for the first subproblem that optimal policies are greedy and exhaustive, i.e., the server should neither idle nor switch when it is at a nonempty queue. For the second subproblem, we prove that in symmetric polling systems patient policies are optimal, i.e., the server should stay idling at the last visited queue whenever the system is empty. When the system is slotted, we further prove that non-idling and impatient policies are optimal. For the third subproblem, we establish that in symmetric polling systems optimal policies belong to the class of Stochastically Largest Queue (SLQ) policies. An SLQ policy is one that never routes the server to a queue known to have a queue length that is stochastically smaller than that of another queue. This result implies, in particular, that the policy that routes the server to the queue with the largest queue length is optimal when all queue lengths are known and that the cyclic routing policy is optimal in the case that the only information available is the previous decisions.This work was supported in part by NSF under Contract ASC-8802764.     

Resource Allocation to Minimize Delay in a Dual-Purpose Service Facility

This paper considers in a deterministic way the problem of dividing a general set of service stations into two groups in order to satisfy two types of service at minimum delay to the customers. The optimum decision depends on the combined effect of initial queue lengths and arrival rates relative to available service capacity. Various conditions are considered and a model is employed to derive theoretical results for optimization in each case.     

Optimal Policies for Multi-server Non-preemptive Priority Queues

We consider a multi-server non-preemptive queue with high and low priority customers, and a decision maker who decides when waiting customers may enter service. The goal is to minimize the mean waiting time for high-priority customers while keeping the queue stable. We use a linear programming approach to find and evaluate the performance of an asymptotically optimal policy in the setting of exponential service and inter-arrival times.     

Asymptotic analysis for closed multiclass queueing networks in critical usage

We consider a class of closed multiclass queueing networks containing First-Come-First-Serve (FCFS) and Infinite Server (IS) stations. These networks have a productform solution for their equilibrium probabilities. We study these networks in an asymptotic regime for which the number of customers and the service rates at the FCFS stations go to infinity with the same order. We assume that the regime is in critical usage, whereby the utilizations of the FCFS servers slowly approach one. The asymptotic distribution of the normalized queue lengths is shown to be in many cases a truncated multivariate normal distribution. Traffic conditions for which the normalized queue lengths arealmost asymptotically independent are determined. Asymptotic expansions of utilizations and expected queue lengths are presented. We show through an example how to obtain asymptotic expansions of performance measures when the networks are in mixed usage and how to apply the results to networks with finite data.Supported partially by NSF grant NCR93-04601.     

Optimal control of polling models for transportation applications

We formulate and analyze a dynamic scheduling problem for a class of transportation systems in a Markov Decision Process (MDP) framework. A transportation system is represented by a polling model consisting of a number of stations and a server with switch-over costs and constraints on its movement (the model we have analyzed is intended to emulate key features of an elevator system). Customers request service in order to be transported by the server from various arrival stations to a common destination station. The objective is to minimize a cost criterion that incorporates waiting costs at the arrival stations. Two versions of the basic problem are considered and structural properties of the optimal policy in each case are derived. It is shown that optimal scheduling policies are characterized by switching functions dependent on state information consisting of queue lengths formed at the arrival stations.     

Optimal assignment policy of a single server attended by two queues

A single server attends to two separate queues. Each queue has Poisson arrivals and exponential service. There is a switching cost whenever the server switches from one queue to another. The objective is to minimize the discounted or average holding and switching costs over a finite or an infinite horizon. We show numerically that the optimal assignment policy is characterized by a switching curve. We also show that the optimal policy is monotonic in the following senses: If it is optimal to switch from queue one to queue two, then it is optimal to continue serve queue two whenever the number of customers in queue one or in queue two decreases or increases, respectively.     

A simple policy for multiple queues with size-independent service times

We consider a service system with two Poisson arrival queues. A server chooses which queue to serve at each moment. Once a queue is served, all the customers will be served within a fixed amount of time. This model is useful in studying airport shuttling or certain online computing systems. We propose a simple yet optimal state-independent policy for this problem which is not only easy to implement, but also performs very well.     

Admission control of a service station when the arrivals are internal

All studies in the admission control of a service station make decisions at arrival epochs. When arrivals are internal and are rejected from a queue, the rejected jobs have to be routed to other stations in the system. However the system will not know whether a job will be admitted to a queue or not until its arrival epoch to that queue. Thus, the system has to react dynamically and agilely to the decisions made at a specific queue and may try several queues before finding a queue that admits the job. This paper remedies these difficulties by changing the decision epochs of the admission control from arrival epochs to departure epochs with the actions of switching (keeping) the arrival stream on or off. Thus upstream stations will have information on the admission status of their downstream stations all the time. It is proved that the optimal policy for this revised admission control system is of control limit type for an M/G/1 queue. Comparisons of the optimal values and optimal policies for the admission controls made at arrival epochs and at departure epochs are included in the paper.     

Generalised ‘join the shortest queue’ policies for the dynamic routing of jobs to multi-class queues

Jobs or customers arrive and require service that may be provided at one of several different stations. The associated routing problems concern how customers may be assigned to stations in an optimal manner. Much of the classical literature concerns a single class of customers seeking service from a collection of homogeneous stations. We argue that many contemporary application areas call for the analysis of routing problems in which many classes of customer seek service provided at a collection of diverse stations. This paper is the first to consider routing policies in such complex environments which take appropriate account of the degree of congestion at each service station. A simple and intuitive class of policies emerges from a policy improvement approach. In a numerical study, the policies were close to optimal in all cases.     

On the average optimality of circular assignment policy

We consider a parallel queueing system with identical exponential servers. Customers arrive according to a renewal process and upon arrival are immediately assigned to those queues. The problem is to find an optimal assignment policy minimizing the longrun average expected cost, without information about the current queue lengths, but with the initial queue-length distributions and information about the past arrival process and assignment of customers. In this paper, it is shown that the so-called circular assignment policy is optimal under mild conditions on the initial queue-length distributions and the holding cost.     

Dynamic load balancing in parallel queueing systems: Stability and optimal control

We consider a system of parallel queues with dedicated arrival streams. At each decision epoch a decision-maker can move customers from one queue to another. The cost for moving customers consists of a fixed cost and a linear, variable cost dependent on the number of customers moved. There are also linear holding costs that may depend on the queue in which customers are stored. Under very mild assumptions, we develop stability (and instability) conditions for this system via a fluid model. Under the assumption of stability, we consider minimizing the long-run average cost. In the case of two-servers the optimal control policy is shown to prefer to store customers in the lowest cost queue. When the inter-arrival and service times are assumed to be exponential, we use a Markov decision process formulation to show that for a fixed number of customers in the system, there exists a level S such that whenever customers are moved from the high cost queue to the low cost queue, the number of customers moved brings the number of customers in the low cost queue to S. These results lead to the development of a heuristic for the model with more than two servers.     

Analysis of a two-phase queueing system with a fixed-size batch policy

We consider a single-server, two-phase queueing system with a fixed-size batch policy. Customers arrive at the system according to a Poisson process and receive batch service in the first-phase followed by individual services in the second-phase. The batch service in the first-phase is applied for a fixed number (k) of customers. If the number of customers waiting for the first-phase service is less than k when the server completes individual services, the system stays idle until the queue length reaches k. We derive the steady state distribution for the system’s queue length. We also show that the stochastic decomposition property can be applied to our model. Finally, we illustrate the process of finding the optimal batch size that minimizes the long-run average cost under a linear cost structure.     

A discrete queue with double thresholds policy and its application to SVC systems

A discrete time Geo/Geo/1 queue with (m, N)-policy is considered in this paper. There are three operation periods being considered: high speed, low speed service periods and idle periods. With double thresholds policy, the server begins to take a working vacation when the number of customers is below m after a service and there is one customer in the system at least. What’s more, if the system becomes empty after a service, the server will take an ordinary vacation. Otherwise, high speed service continues if the number of customers still exceeds m after a service. At the vacation completion instant, servers resume their service if the quantity of customers exceeds N. Vacations can also be interrupted when the system accumulate customers more than the prefixed threshold. Using the quasi birth-death process and matrix-geometric solution methods, we derive the stationary queue length distribution and some system characteristics of interest. Based on these, we apply the queue to a virtual channel switching system and present various numerical experiments for the system. Finally, numerical results are offered to illustrate the optimal (m, N)-policy to minimize cost function and obtain practical consequence on the operation of double thresholds policy.     

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 tollbooth tandem queue with heterogeneous servers

We study a tandem queueing system with K servers and no waiting space in between. A customer needs service from one server but can leave the system only if all down-stream servers are unoccupied. Such a system is often observed in toll collection during rush hours in transportation networks, and we call it a tollbooth tandem queue. We apply matrix-analytic methods to study this queueing system, and obtain explicit results for various performance measures. Using these results, we can efficiently compute the mean and variance of the queue lengths, waiting time, sojourn time, and departure delays. Numerical examples are presented to gain insights into the performance and design of the tollbooth tandem queue. In particular, it reveals that the intuitive result of arranging servers in decreasing order of service speed (i.e., arrange faster servers at downstream stations) is not always optimal for minimizing the mean queue length or mean waiting time.     

Economies of scale,competitiveness, and trade patterns within the European community: Clarendon Press,Oxford, 1983, 193 pages, £20.00

We consider two queues in series with input to each queue, which can be controlled by accepting or rejecting arriving customers. The objective is to maximize the discounted or average expected net benefit over a finite or infinite horizon, where net benefit is composed of (random) rewards for entering customers minus holding costs assessed against the customers at each queue. Provided that it costs more to hold a customer at the first queue than at the second, we show that an optimal policy is monotonic in the following senses: Adding a customer to either queue makes it less likely that we will accept a new customer into either queue; moreover moving a customer from the first queue to the second makes it more (less) likely that we will accept a new customer into the first (second) queue. Our model has policy implications for flow control in communication systems, industrial job shops, and traffic-flow systems. We comment on the relation between the control policies implied by our model and those proposed in the communicationa literature.     

Scheduling service in tandem queues attended by a single server

Consider a tandem queue model with a single server who can switch instantaneously from one queue to another. Customers arrive according to a Poisson process with rate λ . The amount of service required by each customer at the i^th queue is an exponentially distributed random variable with rate μ_i. Whenever two or more customers are in the system, the decision as to which customer should be served first depends on the optimzation criterion. In this system all server allocation policies in the finite set of work conserving deterministic policies have the same expected first passage times (makespan) to empty the system of customers from any initial state. However, a unique policy maximizes the first passage probability of empty-ing the system before the number of customers exceeds K, for any value of K, and it stochastically minimizes (he number of customers in the system at any time t > 0 . This policy always assigns the server to the non empty queue closest to the exit     

带有负顾客且具有Bernoulli反馈的M/M/1工作休假排队

本文研究带反馈的具有正、负两类顾客的M/M/1工作休假排队模型.工作休假策略为空竭服务多重工作休假.负顾客一对一抵消队尾的正顾客(若有),若系统中无正顾客时,到达的负顾客自动消失,负顾客不接受服务.完成服务的正顾客以概率p(0相似文献   

Revenue-maximizing pricing and scheduling strategies in service systems with flexible customers

We propose a model of service operations systems in which customers are heterogeneous both in terms of their private delay sensitivity and flexibility. A service provider maximizes revenue through jointly optimal pricing and steady-state scheduling strategies. We provide a complete analysis for this generally intractable problem. Interestingly, when one queue accommodates a large population of impatient customers, it may be desirable to strategically idle the server in the other queue, which is a phenomenon new to the literature.