Profit maximization in flexible serial queueing networks

We analyze the tradeoff between efficiency and service quality in tandem systems with flexible servers and finite buffers. We reward efficiency by assuming that a revenue is earned each time a job is completed, and penalize poor service quality by incorporating positive holding costs. We study the dynamic assignment of servers to tasks with the objective of maximizing the long-run average profit. For systems of arbitrary size, structured service rates, and linear or nonlinear holding costs, we determine the server assignment policy that maximizes the profit. For systems with two stations, two servers with arbitrary service rates, and linear holding costs, we show that the optimal server assignment policy is of threshold type and determine the value of this threshold as a function of the revenue and holding cost. The threshold can be interpreted as the best possible buffer size, and hence our results prove the equivalence of addressing service quality via a holding cost and via limiting the buffer size. Furthermore, we identify the optimal buffer size when each buffer space comes at a cost. We provide numerical results that suggest that the optimal policy also has a threshold structure for nonlinear holding costs. Finally, for larger systems with arbitrary service rates, we propose effective server assignment heuristics.     

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.     

Allocating flexible servers in serial systems with switching costs

Consider a firm that operates a make-to-order serial production system and employs a cross-trained workforce. We model such a firm as a tandem queuing system in which flexible servers can be allocated across stations, and assume that a switching cost is charged when servers move between stations. We show that even in the two-station two-server case the optimal policy follows a complex state-dependent structure that may be difficult to implement in practice. We propose three alternate heuristic policies and assess their performance. We show that a simpler policy which only moves one server can achieve close to optimal results.     

Pooling in tandem queueing networks with non-collaborative servers

This paper considers pooling several adjacent stations in a tandem network of single-server stations with finite buffers. When stations are pooled, we assume that the tasks at those stations are pooled but the servers are not. More specifically, each server at the pooled station picks a job from the incoming buffer of the pooled station and conducts all tasks required for that job at the pooled station before that job is placed in the outgoing buffer. For such a system, we provide sufficient conditions on the buffer capacities and service times under which pooling increases the system throughput by means of sample-path comparisons. Our numerical results suggest that pooling in a tandem line generally improves the system throughput—substantially in many cases. Finally, our analytical and numerical results suggest that pooling servers in addition to tasks results in even larger throughput when service rates are additive and the two systems have the same total number of storage spaces.     

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.     

Round robin scheduling of heterogeneous parallel servers in heavy traffic

We consider scheduling for heterogeneous server systems, where tasks arrive according to a Poisson process, with their processing requirements following a discrete distribution with finite support. For a system with a dispatcher and several heterogeneous servers, we propose an optimized multi-layered round robin routing policy followed by shortest remaining processing time scheduling at each server. Using a heavy traffic approximation, we show that the proposed policy performs as well as the optimal scheduling policy for a heterogeneous servers system with a single queue (no routing) in heavy traffic. Additional simulation results suggest that such policies will be effective in more general settings.     

Throughput maximization for two station tandem systems: a proof of the Andradóttir–Ayhan conjecture

We study a tandem queueing network with two stations, M heterogeneous flexible servers, and a finite intermediate buffer. The objective is to dynamically assign the servers to the stations in order to maximize the throughput of the system. The form of the optimal policy for M≤3 was derived in two previous papers. In one of those papers, Andradóttir and Ayhan (Operations Research 53:516–531, 2005) provide a conjecture on the form of the optimal policy for M≥4. We prove their conjecture in this paper, showing that the optimal policy is defined by monotone thresholds and the ratios of the service rates among the servers. For M>1, we also prove that the optimal policy always uses the entire intermediate buffer.     

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.     

Asymptotically optimal open-loop load balancing

In many distributed computing systems, stochastically arriving jobs need to be assigned to servers with the objective of minimizing waiting times. Many existing dispatching algorithms are basically included in the SQ(d) framework: Upon arrival of a job, \(d\ge 2\) servers are contacted uniformly at random to retrieve their state and then the job is routed to a server in the best observed state. One practical issue in this type of algorithm is that server states may not be observable, depending on the underlying architecture. In this paper, we investigate the assignment problem in the open-loop setting where no feedback information can flow dynamically from the queues back to the controller, i.e., the queues are unobservable. This is an intractable problem, and unless particular cases are considered, the structure of an optimal policy is not known. Under mild assumptions and in a heavy-traffic many-server limiting regime, our main result proves the optimality of a subset of deterministic and periodic policies within a wide set of (open-loop) policies that can be randomized or deterministic and can be dependent on the arrival process at the controller. The limiting value of the scaled stationary mean waiting time achieved by any policy in our subset provides a simple approximation for the optimal system performance.     

Dynamic control of a flexible server in an assembly-type queue with setup costs

We consider a queueing system with multiple stations attended by a single flexible server. An order arriving at this system needs to go through each station only once but there is no particular precedence relationship among these stations. One can also think of this system as an assembly system where each station processes a different component of an order and once all the components associated with an order are processed they are assembled instantaneously. A holding cost is charged for keeping the orders in the system and there is a penalty associated with the switches of the server between stations. Our objective is to minimize the long-run average costs by dynamically assigning the server to stations based on the system state. Using sample-path arguments, we provide partial characterizations of the optimal policy and provide sufficient conditions under which a simple state-independent policy that works on one order at a time is optimal. We also propose three simple threshold policies and present a numerical study that provides supporting evidence for the superior performance of our double-threshold heuristic.     

Throughput and delay optimality of power-of-d choices in inhomogeneous load balancing systems

It is well-known that the power-of-d choices routing algorithm maximizes throughput and is heavy-traffic optimal in load balancing systems with homogeneous servers. However, if the servers are heterogeneous, throughput optimality does not hold in general. We find necessary and sufficient conditions for throughput optimality of power-of-d choices when the servers are heterogeneous, and we prove that almost the same conditions are sufficient to show heavy-traffic optimality. Additionally, we generalize the sufficient condition for throughput optimality to a larger class of routing policies.     

Static and dynamic server allocation in systems with on/off sources

A system consisting of a number of servers, where demands of different types arrive in bursts (modelled by interrupted Poisson processes), is examined in the steady state. The problem is to decide how many servers to allocate to each job type, so as to minimize a cost function expressed in terms of average queue sizes. First, an exact analysis is provided for an isolated IPP/M/n queue. The results are used to compute the optimal static server allocation policy. The latter is then compared to four heuristic policies which employ dynamic switching of servers from one queue to another (such switches take time and hence incur costs). This work was carried out in the framework of the collaborative project DOPCHE (Dynamic Operative Policies for Commercial Hosting Environments), funded by the UK Engineering and Physical Sciences Research Council under its E-Science programme. The support of the Network of Excellence EuroNGI, funded by the EU, is also acknowledged.     

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.     

Dynamic repositioning for vehicle sharing with setup costs

This study considers a multi-period two-region repositioning problem with setup repositioning costs involved for vehicle sharing systems. We find that incorporating such costs can influence the total cost significantly and complicate the structure of the optimal policy. Moreover, we manage to partially characterize the optimal policy, and then develop an easy-to-implement heuristic policy. The performance of the heuristic policy and the influence of setup repositioning costs on policies are assessed numerically.     

Age-dependent production planning and maintenance strategies in unreliable manufacturing systems with lost sale

In this paper, we formulate an analytical model for the joint determination of an optimal age-dependent buffer inventory and preventive maintenance policy in a production environment that is subject to random machine breakdowns. Traditional preventive maintenance policies, such as age and periodic replacements, are usually studied based on simplified and non-realistic assumptions, as well as on the expected costs criterion. Finished goods inventories and the age-dependent likelihood of machine breakdowns are usually not considered. As a result, these policies could significantly extend beyond the anticipated financial incomes of the system, and lead to crises. In order to solve this problem, a more realistic analysis model is proposed in this paper to consider the effects of both preventive maintenance policies and machine age on optimal safety stock levels. Hence, a unified framework is developed, allowing production and preventive maintenance to be jointly considered. We use an age-dependent optimization model based on the minimization of an overall cost function, including inventory holdings, lost sales, preventive and corrective maintenance costs. We provide optimality conditions for the manufacturing systems considered, and use numerical methods to obtain an optimal preventive maintenance policy and the relevant age-dependent threshold level production policy. In this work, this policy is called the multiple threshold levels hedging point policy. We include numerical examples and sensitivity analyses to illustrate the importance and the effectiveness of the proposed methodology. Compared with other available optimal production and maintenance policies, the numerical solution obtained shows that the proposed age-dependent optimal production and maintenance policies significantly reduce the overall cost incurred.     

Optimal control of an M/G/1 queuing system with removable server via diffusion approximation

In this paper, applying the technique of diffusion approximation to an M/G/1 queuing system with removable server, we provide a robust approximation model for determining an optimal operating policy of the system. The following costs are incurred to the system: costs per hour for keeping the server on or off, fixed costs for turning the server on or off, and a holding cost per customer per hour. The expected discounted cost is used as a criterion for optimality. Using a couple of independent diffusion processes approximating the number of customers in the system, we derive approximation formulae of the expected discounted cost that do not depend on the service time distribution but its first two moments. Some new results on the characterization of the optimal operating policy are provided from these results. Moreover, in order to examine the accuracy of the approximation, they are numerically compared with the exact results.     

Towards minimum loss job routing to parallel heterogeneous multiserver queues via index policies

This paper considers a Markovian model for the optimal dynamic routing of homogeneous traffic to parallel heterogeneous queues, each having its own finite input buffer and server pool, where buffer and server-pool sizes, as well as service rates, may differ across queues. The main goal is to identify a heuristic index-based routing policy with low complexity that consistently attains a nearly minimum average loss rate (or, equivalently, maximum throughput rate). A second goal is to compare alternative policies, with respect to computational demands and empirical performance. A novel routing policy that can be efficiently computed is developed based on a second-order extension to Whittle’s restless bandit (RB) index, since the latter is constant for this model. New results are also given for the more computationally demanding index policy obtained via policy improvement (PI), including that it reduces to shortest queue routing under symmetric buffer and server-pool sizes. A numerical study shows that the proposed RB index policy is nearly optimal across the instances considered, and substantially outperforms several previously proposed index policies.     

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.     

Admission control for a multi-server queue with abandonment

In a M/M/N+M queue, when there are many customers waiting, it may be preferable to reject a new arrival rather than risk that arrival later abandoning without receiving service. On the other hand, rejecting new arrivals increases the percentage of time servers are idle, which also may not be desirable. We address these trade-offs by considering an admission control problem for a M/M/N+M queue when there are costs associated with customer abandonment, server idleness, and turning away customers. First, we formulate the relevant Markov decision process (MDP), show that the optimal policy is of threshold form, and provide a simple and efficient iterative algorithm that does not presuppose a bounded state space to compute the minimum infinite horizon expected average cost and associated threshold level. Under certain conditions we can guarantee that the algorithm provides an exact optimal solution when it stops; otherwise, the algorithm stops when a provided bound on the optimality gap is reached. Next, we solve the approximating diffusion control problem (DCP) that arises in the Halfin–Whitt many-server limit regime. This allows us to establish that the parameter space has a sharp division. Specifically, there is an optimal solution with a finite threshold level when the cost of an abandonment exceeds the cost of rejecting a customer; otherwise, there is an optimal solution that exercises no control. This analysis also yields a convenient analytic expression for the infinite horizon expected average cost as a function of the threshold level. Finally, we propose a policy for the original system that is based on the DCP solution, and show that this policy is asymptotically optimal. Our extensive numerical study shows that the control that arises from solving the DCP achieves a very similar cost to the control that arises from solving the MDP, even when the number of servers is small.     

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.