In This Issue

Expanding Nurse Staffing Paradigms

Nurse-to-patient ratios constitute a commonly used framework for discussing and implementing staffing policies. Indeed, the discourse on quality of care as it is affected by staffing levels is usually couched in terms of magnitude of the ratio. In “Nurse Staffing in Medical Units: A Queueing Perspective,” F. de Véricourt and O. B. Jennings illustrate that such thinking is unnecessarily restrictive and often misleading. The authors promote a queueing model of health-care unit dynamics and a family of performance metrics intended to help evaluate staffing choices. They perform asymptotic analysis of the performance metrics, which is then applied to propose more effective staffing paradigms.

Generation Capacity Expansion in a Risky Environment

Generation capacity expansion problems were cast in optimization form more than 50 years ago. Companies operated under an obligation to serve, and in compensation were guaranteed a certain rate of return on investment. Optimization ensured demand satisfaction at minimal investment and operation cost computed over a certain horizon. Capacity expansion is quite different today, at least in restructured systems. The industry operates in a competitive environment, even though it remains subject to various regulatory interventions, particularly on the environmental side. In “Generation Capacity Expansion in a Risky Environment: A Stochastic Equilibrium Analysis,” A. Ehrenmann and Y. Smeers examine the question of investment in generation capacity in a competitive system operating in a risky environment and subject to regulatory interventions. They present a computational approach that remains close to the mathematical programming framework used in former capacity expansion models while accommodating some of the features of today's restructured industry. Therefore, it departs from alternative approaches that view power plants as financial assets and value them as such.

Optimal Energy Commitments

In “Optimal Energy Commitments with Storage and Intermittent Supply,” J. H. Kim and W. B. Powell study how wind and solar energy generators should make commitments to deliver electricity to the grid when their sources of energy are unpredictable but they can store their energy using a battery, albeit with a conversion loss and a capacity limit.

The Peak-End Rule in Pricing

When making purchase decisions, people perceive transactions as good or bad deals relative to what they have paid in the past. Yet only few past prices are remembered, typically the lowest and most recent ones—as the peak-end rule in psychology suggests. Given such patterns of consumer behavior, what are the implications on the firm's demand and pricing policies over time? How should firms weigh, for example, the sale-boosting benefits of a low introductory price against its eroding effect on future demand? In “Dynamic Pricing with Loss-Averse Consumers and Peak-End Anchoring,” J. Nasiry and I. Popescu investigate how profit maximizing firms should set prices in a repeated interaction setting, when customers remember the lowest and most recent prices. They find that behavioral regularities such as peak-end anchoring and loss aversion limit the benefits of varying prices, and they caution that the adverse effects of deep discounts on the firm's optimal prices and profits may be more enduring than previous models predict.

Optimizing Commodity Operations

Managing commodity processing operations requires decisions regarding procurement, processing, and trade of multiple commodities. Because of uncertainty in both input and output commodity prices, it is important for processing firms to understand the relationship between procurement, processing, and trade decisions for multiple commodities and coordinate decisions across commodities and periods. Operational constraints such as procurement and processing capacities make this task more complex. While different aspects of the problem—procurement, processing, and trade—have been studied earlier, the integrated problem itself has not received much attention in the literature. In “Integrated Optimization of Procurement, Processing, and Trade of Commodities,” S. K. Devalkar, R. Anupindi, and A. Sinha consider a multiperiod optimization problem for a firm that procures an input commodity and has processing capacity to convert the input into a processed commodity. They show that it is optimal for the firm to postpone trade of the output commodities using forward contracts to the last possible period; i.e., to just before the maturity of the forward contract and the optimal trade policy is similar to the exercise of a compound exchange option on forward contracts maturing over the planning horizon. They also show that the optimal procurement and processing decisions for the input commodity are governed by “procure up to” and “process down to” inventory thresholds, with these thresholds dependent on the realized prices and remaining horizon length. Most importantly, using commodity markets data for the soybean complex, they find that a dynamic programming policy provides significant benefits compared to myopic heuristics used in practice under conditions of tight processing capacities and high price volatilities.

Cheap Talk in Operations

We are all familiar with delay announcements provided by service systems. In many settings, customers dial a customer service number and wait as the automated message begins: “We are currently assisting other customers. Your call will be answered in the order it was received.” Recorded delay announcements such as these are nothing new, but their strategic use is proving to be a surprisingly complex game played between customers and service providers. In “ ‘We Will Be Right with You’: Managing Customer Expectations with Vague Promises and Cheap Talk,” G. Allon, A. Bassamboo, and I. Gurvich are interested in how delay announcements can be used more efficiently by service providers when the customers are strategic in the manner that customers interpret these. The theoretical research shows that strategic use of wait messages can ultimately improve both firms' profits and utility to customers.

Efficient Simulation of Value at Risk

Simulation of small probabilities has important applications in many disciplines. The probabilities considered in value at risk (VaR) are moderately small. The variance reduction techniques developed in the literature for VaR computation are based on large deviations methods, which are effective for very small probabilities. In “Efficient Simulation of Value at Risk with Heavy-Tailed Risk Factors,” C.-D. Fuh, I. Hu, Y.-H. Hsu, and R.-H. Wang describe heavy-tailed risk factors using multivariate t distributions and develop a new method for VaR computation. The proposed method minimizes the variance of the importance sampling estimator exactly, while previous methods produce approximations to the exact solution. This method consistently outperforms existing methods derived from large deviations theory under various settings.

Optimization of Runway Use at Airports

As the airspace becomes more and more congested, the efficient management of air traffic is becoming crucial for ensuring the smooth operation of the air traffic system. Safety, passenger delays, as well as fuel burn and associated emissions are all at stake. A particular source of delay in the air traffic system is at the airports themselves, where controllers are faced with many decisions. One particular problem they face is how to use different combinations of runways at different times, for which types of aircraft, and in which directions. These decisions greatly influence an airport's capacity to process arrivals and departures. In “Optimal Selection of Airport Runway Configurations,” D. Bertsimas, M. Frankovich, and A. Odoni present tractable integer programming models to optimally coordinate runway use at airports. This optimization is shown to have the potential to result in significant reductions in aircraft delays and their associated costs. Another key contribution is the modeling of this problem for a group of airports that are situated close to one another, where airspace is shared, and hence decisions need to be coordinated.

Economy of Scale in Multiserver Queueing Systems

The Erlang delay and loss formulae are true probability classics and arguably the most basic formulae in queueing theory. The Erlang delay formula gives the steady-state probability of delay in the M/M/s system, and the Erlang loss formula gives the steady-state probability that the M/G/s/s system is full. The applications of these formulae are in diverse systems where queueing phenomena arise, including telecommunications, production, and service systems. In “Convexity Results for the Erlang Delay and Loss Formulae When the Server Utilization Is Held Constant,” A. Harel shows that when the server utilization is held constant the Erlang delay and loss formulae are convex functions of the number of servers. In addition, the expected number of customers in the queue and in the system, as well as the expected waiting time and sojourn in the M/M/s queue, are convex functions of the number of servers.

Efficient Adaptive Control of Large Flexible Service Systems

In large-scale service systems, such as large contact centers, with multiskilled servers and multitype customers, devising an efficient request routing and server scheduling strategy is a challenging problem, especially if such a strategy needs to be simple and robust. In “Shadow-Routing Based Control of Flexible Multiserver Pools in Overload,” A. L. Stolyar and T. Tezcan propose a simple routing/scheduling scheme, which is optimal when system load exceeds its capacity: it correctly identifies requests that need to be blocked and correctly routes the accepted requests. The optimality is established in the asymptotic sense as the system size becomes very large. The scheme employs a virtual (shadow) queueing system as the key device. In addition, the authors demonstrate that this strategy can be easily combined with another scheme (introduced in their previous work), to produce a single simple algorithm that automatically and seamlessly “switches” between optimal revenue maximization in overload and optimal load balancing, depending on the prevalent conditions.

Strategic Decisions in Integers: New Game-Theoretic Frameworks and Algorithms

Integer programming has proven to be a powerful framework for modeling and analyzing a variety of operations problems faced by a single decision maker. In “Rational Generating Functions and Integer Programming Games,” M. Köppe, C. T. Ryan, and M. Queyranne introduce a novel framework for analyzing settings where multiple decision makers make integer decisions simultaneously. In other words, they extend the paradigm of integer programming to a strategic setting, termed integer programming games, and explore the properties of equilibria in this expanded framework. In particular, they explore computational complexity issues and apply a theory of rational generating functions to provide algorithms for counting and enumerating pure strategy Nash equilibria. They extend Lenstra's (1983) well-known result that integer programming can be solved in polynomial time, when the number of variables is fixed, to the setting of integer programming games, by demonstrating that a pure Nash equilibria can be found in polynomial time when the total number of variables is fixed and a certain structure on the utility functions is imposed. Using their methodology they further demonstrate how other computations of interest (finding social-welfare maximizing equlibria and threat points) can be performed using rational generating functions. Finally, they extend their approach to a more general Stackelberg-Nash setting that combines both sequential and simultaneous decision making in integers.

Interactions in Operational Decision Making and Risk Assessment

Risk managers of complex systems are routinely called to evaluate the risk significance of policies and programs. When operational policies impact two or more components simultaneously, the issue of informing risk managers with the relevance of interactions arises. While the need for a formal and quantitative approach to the assessment of interactions is called for in several recent works, a systematic approach has not been proposed yet. The methodology offered in “A Study of Interactions in the Risk Assessment of Complex Engineering Systems: An Application to Space PSA” by E. Borgonovo and C. L. Smith provides risk managers with a way for detecting the presence and assessing the relevance of interactions. It exploits the multilinearity of the PSA (probabilistic safety assessment) risk metric to introduce sensitivity measures that dissect the exact portion of the change in system risk associated with a component into its individual and interaction contributions. The methodology is tested through quantitative experiments performed on a space mission initial-design risk assessment model developed for NASA.

Optimal Hub Location in Transportation, Telecommunications, and Computer Networks

Transportation, telecommunications, and computer networks frequently employ hub-and-spoke architectures to efficiently route commodities between many origins and destinations. Their key feature lies in the use of consolidation or transshipment points, called hub facilities, to connect a large number of origin and destination pairs by using a small number of links. Hub location problems constitute a challenging class of NP-hard combinatorial optimization problems combining location and network design decisions. In “Benders Decomposition for Large-Scale Uncapacitated Hub Location,” I. Contreras, J.-F. Cordeau, and G. Laporte propose an exact algorithm to solve large-scale instances of the well-known uncapacitated hub location problem with multiple assignments. The algorithm is based on a Benders decomposition, which is enhanced through the inclusion of several features such as the use of a multicut reformulation, the generation of strong optimality cuts, the integration of reduction tests, and the execution of a heuristic procedure. Extensive computational experiments on a large set of existing and new instances with up to 500 nodes and 250,000 commodities confirm the efficiency of the algorithm by clearly outperforming all exact methods previously proposed in the literature.

The Impact of Cost Sharing Methods on the Efficiency of Selfish Resource Usage

Resource allocation games are frequently used to model the interaction of strategic agents competing for a finite set of congestible resources. Examples include strategic driving behavior in traffic networks and packet routing in telecommunication networks. An important issue in such applications is the degree of suboptimality caused by selfish resource allocation. In “The Worst-Case Efficiency of Cost Sharing Methods in Resource Allocation Games,” T. Harks and K. Miller study the worst-case inefficiency of corresponding equilibria with respect to different classes of cost sharing methods that determine for each resource and player the respective cost shares. The paper contains new results for quantifying the worst-case inefficiency for a broad class of cost sharing methods including well-known methods used in practice, such as marginal cost pricing and average cost sharing.

Delivery-Time Quotation with Delays

There are many situations in supply chain scheduling when the supplier finds it impossible to meet the promised due dates for some orders (for example, the airline industry). In “Revised Delivery-Time Quotation in Scheduling with Tardiness Penalties,” G. Steiner and R. Zhang present a model for the rescheduling of orders with simultaneous assignment of attainable revised due dates to minimize due date escalation and tardiness penalties for the supplier. They prove that the problem is computationally hard and present a pseudopolynomial algorithm for it. They also present a fully polynomial time approximation scheme for the problem. Finally, they discuss the implications of their solution for setting fair tardiness penalties when due dates have to be renegotiated because of the delays.

A Celebrated Rule of Thumb to Staff Agents in Call Centers in the Square Root Staffing Rule

In “Refining Square Root Safety Staffing by Expanding Erlang C,” A. J. E. M. Janssen, J. S. H. van Leeuwaarden, and B. Zwart provide analytic insights into the accuracy of the square root staffing rule by developing corrected diffusion approximations for the Erlang C model. These corrected approximations allow for refinements of the square root staffing rule. The computational complexity of these refinements is not more complicated than the conventional square root staffing rule.

Strategic Rules for Joint Dynamic Pricing and Lead-Time Decision

When price sensitive customers also demand exact delivery lead-times before committing their orders, companies need a policy to guide the frontline managers in their real time price and lead-time decisions. This is particularly important when companies with limited capacities want to maintain good fulfillment service to their customers. In “An Optimal Policy for Joint Dynamic Price and Lead-Time Quotation,” J. Feng, L. Liu, and X. Liu develop a semi-Markov dynamic programming model to study this joint dynamic decision problem. By capturing customers' ordering behavior in fairly general demand function, they show that a unique profit maximizing policy exists for this two-dimensional dynamic programming problem. In this policy, the optimal lead-time and price are determined sequentially. In particular, the optimal lead-time follows a simple threshold rule and can be expressed analytically by maximizing the reward from the current order. The determination of the optimal price is accomplished next by single-variable policy iterations of unimodal value functions and will maximize the global objective function.

Information and Coordination in a System with Inventory Sharing

Inventory sharing among retailers has drawn increased attention from retailers and manufacturers as they seek to increase profitability and reduce risk. As the practice of inventory sharing between retailers prevails in many industries (e.g., automotive, machine tool, fashion, electronics), issues related to information and information sharing between the collaborating retailers also surface. In “Decentralized Inventory Sharing with Asymmetric Information,” X. Yan and H. Zhao show that demand information shared between retailers may be distorted due to decentralization. However, they develop a coordination mechanism that not only leads to an all-win situation for the retailers as well as their supplier, but also results in a situation where each retailer obtains a profit very close to what he can obtain under a centralized system even if retailers do not share information, hence, indirectly solving the information issues.

Can Bucket Brigades Be More Productive?

Bucket brigades are used in industries as a way to coordinate workers along an assembly line with more work stations than workers. All workers in a bucket brigade follow a simple rule: Assemble a product along the line until either your colleague downstream takes over it or you complete it; then you walk back to get more work, either from your colleague upstream or from the beginning of the line. Bucket brigades are effective because they constantly balance work for workers and spontaneously adapt to disruptions and seasonality. In “Cellular Bucket Brigades,” Y. F. Lim presents a novel design alternative that may provide significant improvement to the performance of a bucket brigade. Under the new design, each worker works on one side of an aisle when he proceeds in one direction and works on the other side when he proceeds in the reverse direction. Lim proposes rules for workers to share work under the new design and finds a sufficient condition for the system to self-balance. His numerical examples suggest that the improvement in throughput by the new design can be as large as 30%.