Flexible servers in tandem lines with setup costs

We study the dynamic assignment of flexible servers to stations in the presence of setup costs that are incurred when servers move between stations. The goal is to maximize the long-run average profit. We provide a general problem formulation and some structural results, and then concentrate on tandem lines with two stations, two servers, and a finite buffer between the stations. We investigate how the optimal server assignment policy for such systems depends on the magnitude of the setup costs, as well as on the homogeneity of servers and tasks. More specifically, for systems with either homogeneous servers or homogeneous tasks, small buffer sizes, and constant setup cost, we prove the optimality of “multiple threshold” policies (where servers’ movement between stations depends on both the number of jobs in the system and the locations of the servers) and determine the values of the thresholds. For systems with heterogeneous servers and tasks, small buffers, and constant setup cost, we provide results that partially characterize the optimal server assignment policy. Finally, for systems with larger buffer sizes and various service rate and setup cost configurations, we present structural results for the optimal policy and provide numerical results that strongly support the optimality of multiple threshold policies.     

Expulsion and scheduling control for multiclass queues with heterogeneous servers

We consider an M/M/2 system with nonidentical servers and multiple classes of customers. Each customer class has its own reward rate and holding cost. We may assign priorities so that high priority customers may preempt lower priority customers on the servers. We give two models for which the optimal admission and scheduling policy for maximizing expected discounted profit is determined by a threshold structure on the number of customers of each type in the system. Surprisingly, the optimal thresholds do not depend on the specific numerical values of the reward rates and holding costs, making them relatively easy to determine in practice. Our results also hold when there is a finite buffer and when customers have independent random deadlines for service completion.     

A server backup model with Markovian arrivals and phase type services

We consider a finite capacity queueing system with one main server who is supported by a backup server. We assume Markovian arrivals, phase type services, and a threshold-type server backup policy with two pre-determined lower and upper thresholds. A request for a backup server is made whenever the buffer size (number of customers in the queue) hits the upper threshold and the backup server is released from the system when the buffer size drops to the lower threshold or fewer at a service completion of the backup server. The request time for the backup server is assumed to be exponentially distributed. For this queuing model we perform the steady state analysis and derive a number of performance measures. We show that the busy periods of the main and backup servers, the waiting times in the queue and in the system, are of phase type. We develop a cost model to obtain the optimal threshold values and study the impact of fixed and variable costs for the backup server on the optimal server backup decisions. We show that the impact of standard deviations of the interarrival and service time distributions on the server backup decisions is quite different for small and large values of the arrival rates. In addition, the pattern of use of the backup server is very different when the arrivals are positively correlated compared to mutually independent arrivals.     

Optimal pricing for tandem queues with finite buffers

We consider optimal pricing for a two-station tandem queueing system with finite buffers, communication blocking, and price-sensitive customers whose arrivals form a homogeneous Poisson process. The service provider quotes prices to incoming customers using either a static or dynamic pricing scheme. There may also be a holding cost for each customer in the system. The objective is to maximize either the discounted profit over an infinite planning horizon or the long-run average profit of the provider. We show that there exists an optimal dynamic policy that exhibits a monotone structure, in which the quoted price is non-decreasing in the queue length at either station and is non-increasing if a customer moves from station 1 to 2, for both the discounted and long-run average problems under certain conditions on the holding costs. We then focus on the long-run average problem and show that the optimal static policy performs as well as the optimal dynamic policy when the buffer size at station 1 becomes large, there are no holding costs, and the arrival rate is either small or large. We learn from numerical results that for systems with small arrival rates and no holding cost, the optimal static policy produces a gain quite close to the optimal gain even when the buffer at station 1 is small. On the other hand, for systems with arrival rates that are not small, there are cases where the optimal dynamic policy performs much better than the optimal static policy.

     

Optimal server assignment in a two-stage tandem queueing system

We study Markovian queueing systems consisting of two stations in tandem. There is a dedicated server in each station and an additional server that can be assigned to any station. Assuming that linear holding costs are incurred by jobs in the system and two servers can collaborate to work on the same job, we determine structural properties of optimal server assignment policies under the discounted and the average cost criteria.     

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.     

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.     

A two-stage tandem queue attended by a moving server with holding and switching costs

We consider a two-stage tandem queue attended by a moving server, with homogeneous Poisson arrivals and general service times. Two different holding costs for stages 1 and 2 and different switching costs from one stage to the other are considered. We show that the optimal policy in the second stage is greedy; and if the holding cost rate in the second stage is greater or equal to the rate in the first stage, then the optimal policy in the second stage is also exhaustive. Then, the optimality condition for sequential service policy in systems with zero switchover times is introduced. Considering some properties of the optimal policy, we then define a Triple-Threshold (TT) policy to approximate the optimal policy in the first stage. Finally, a model is introduced to find the optimal TT policy, and using numerical results, it is shown that the TT policy accurately approximates the optimal policy. This revised version was published online in June 2006 with corrections to the Cover Date.     

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.     

Optimal batch service of a polling system under partial information

We consider the optimal scheduling of an infinite-capacity batch server in aN-node ring queueing network, where the controller observes only the length of the queue at which the server is located. For a cost criterion that includes linear holding costs, fixed dispatching costs, and linear service rewards, we prove optimality and monotonicity of threshold scheduling policies.     

Optimal stochastic scheduling of two interconnected queues with varying service rates

We consider two-stage tandem queueing systems attended by two specialized and one flexible server, where all servers have time varying rates. Assuming exponential processing times and linear holding costs, we derive properties of server allocation policies that minimize expected costs over an infinite time horizon.     

Optimal stochastic scheduling in a single server biclass retrial queueing system

The paper deals with the assignment of a single server to two retrial queues. Each customer reapplies for service after an exponentially distributed amount of time. The server operates at customer dependent exponential rates. There are holding costs and costs during service per customer and per unit of time. We provide conditions on which it is optimal to allocate the server to queue 1 or 2 in order to minimize the expected total costs until the system is cleared.     

On the optimality of threshold control in queues with model uncertainty

We consider a single-stage queuing system where arrivals and departures are modeled by point processes with stochastic intensities. An arrival incurs a cost, while a departure earns a revenue. The objective is to maximize the profit by controlling the intensities subject to capacity limits and holding costs. When the stochastic model for arrival and departure processes are completely known, then a threshold policy is known to be optimal. Many times arrival and departure processes can not be accurately modeled and controlled due to lack of sufficient calibration data or inaccurate assumptions. We prove that a threshold policy is optimal under a max–min robust model when the uncertainty in the processes is characterized by relative entropy. Our model generalizes the standard notion of relative entropy to account for different levels of model uncertainty in arrival and departure processes. We also study the impact of uncertainty levels on the optimal threshold control.     

Heavy traffic resource pooling in parallel‐server systems

We consider a queueing system with r non‐identical servers working in parallel, exogenous arrivals into m different job classes, and linear holding costs for each class. Each arrival requires a single service, which may be provided by any of several different servers in our general formulation; the service time distribution depends on both the job class being processed and the server selected. The system manager seeks to minimize holding costs by dynamically scheduling waiting jobs onto available servers. A linear program involving only first‐moment data (average arrival rates and mean service times) is used to define heavy traffic for a system of this form, and also to articulate a condition of overlapping server capabilities which leads to resource pooling in the heavy traffic limit. Assuming that the latter condition holds, we rescale time and state space in standard fashion, then identify a Brownian control problem that is the formal heavy traffic limit of our rescaled scheduling problem. Because of the assumed overlap in server capabilities, the limiting Brownian control problem is effectively one‐dimensional, and it admits a pathwise optimal solution. That is, in the limiting Brownian control problem the multiple servers of our original model merge to form a single pool of service capacity, and there exists a dynamic control policy which minimizes cumulative cost incurred up to any time t with probability one. Interpreted in our original problem context, the Brownian solution suggests the following: virtually all backlogged work should be held in one particular job class, and all servers can and should be productively employed except when the total backlog is small. It is conjectured that such ideal system behavior can be approached using a family of relatively simple scheduling policies related to the cμ rule. This revised version was published online in June 2006 with corrections to the Cover Date.     

Scheduling in Multiclass Networks with Deterministic Service Times

We consider general feed-forward networks of queues with deterministic service times and arbitrary arrival processes. There are holding costs at each queue, idling may or may not be permitted, and servers may fail. We partially characterize the optimal policy and give conditions under which lower priority should be given to jobs that would be delayed later in the network if they were processed now.     

Analysis of job assignment with batch arrivals among heterogeneous servers

We revisit the problem of job assignment to multiple heterogeneous servers in parallel. The system under consideration, however, has a few unique features. Specifically, repair jobs arrive to the queueing system in batches according to a Poisson process. In addition, servers are heterogeneous and the service time distributions of the individual servers are general. The objective is to optimally assign each job within a batch arrival to minimize the long-run average number of jobs in the entire system. We focus on the class of static assignment policies where jobs are routed to servers upon arrival according to pre-determined probabilities. We solve the model analytically and derive the structural properties of the optimal static assignment. We show that when the traffic is below a certain threshold, it is better to not assign any jobs to slower servers. As traffic increases (either due to an increase in job arrival rate or batch size), more slower servers will be utilized. We give an explicit formula for computing the threshold. Finally we compare and evaluate the performance of the static assignment policy to two dynamic policies, specifically the shortest expected completion policy and the shortest queue policy.     

Optimal assignment of servers to tasks when collaboration is inefficient

Consider a Markovian system of two stations in tandem with finite intermediate buffer and two servers. The servers are heterogeneous, flexible, and more efficient when they work on their own than when they collaborate. We determine how the servers should be assigned dynamically to the stations with the goal of maximizing the system throughput. We show that the optimal policy depends on whether or not one server is dominant (i.e., faster at both stations) and on the magnitude of the efficiency loss of collaborating servers. In particular, if one server is dominant then he must divide his time between the two stations, and we identify the threshold policy the dominant server should use; otherwise each server should focus on the station where he is the faster server. In all cases, servers only collaborate to avoid idleness when the first station is blocked or the second station is starved, and we determine when collaboration is preferable to idleness as a function of the efficiency loss of collaborating servers.     

Dynamic scheduling to minimize lost sales subject to set-up costs

We consider scheduling a shared server in a two-class, make-to-stock, closed queueing network. We include server switching costs and lost sales costs (equivalently, server starvation penalties) for lost jobs. If the switching costs are zero, the optimal policy has a monotonic threshold type of switching curve provided that the service times are identical. For completely symmetric systems without set-ups, it is optimal to serve the longer queue. Using simple analytical models as approximations, we derive a heuristic scheduling policy. Numerical results demonstrate the effectiveness of our heuristic, which is typically within 10% of optimal. We also develop and test a heuristic policy for a model in which the shared resource is part of a series network under a CONWIP release policy. This revised version was published online in June 2006 with corrections to the Cover Date.     

Optimal use of excess capacity in two interconnected queues

We consider a two-stage tandem queueing network where jobs from station 1 join station 2 with a certain probability. Each job incurs a linear holding cost, different for each station. Each station is attended by a dedicated server, and there is an additional server that is either constrained to serve in station 1 or can serve in both stations. Assuming no switching or other operating costs for the additional server, we seek an allocation strategy that minimizes expected holding costs. For a clearing system we show that the optimal policy is characterized by a switching curve for which we provide a lower bound on its slope. We also specify a subset of the state space where the optimal policy can be explicitly determined.     

Optimality of D-Policies for an M/G/1 Queue with a Removable Server

We consider an M/G/1 queue with a removable server. When a customer arrives, the workload becomes known. The cost structure consists of switching costs, running costs, and holding costs per unit time which is a nonnegative nondecreasing right-continuous function of a current workload in the system. We prove an old conjecture that D-policies are optimal for the average cost per unit time criterion. It means that for this criterion there is an optimal policy that either runs the server all the time or switches the server off when the system becomes empty and switches it on when the workload reaches or exceeds some threshold D.