We consider several independent decision makers who stock expensive, low-demand spare parts for their high-tech machines. They can collaborate by full pooling of their inventories via free transshipments. We examine the stability of such pooling arrangements, and we address the issue of fairly distributing the collective holding and downtime costs over the participants, by applying concepts from cooperative game theory. We consider two settings: one where each party maintains a predetermined stocking level and one where base stock levels are optimized. For the setting with fixed stocking levels, we unravel the possibly conflicting effects of implementing a full pooling arrangement and study these effects separately to establish intuitive conditions for existence of a stable cost allocation. For the setting with optimized stocking levels, we provide a simple proportional rule that accomplishes a population monotonic allocation scheme if downtime costs are symmetric among participants. Although our whole analysis is motivated by spare parts applications, all results are also applicable to other pooled resource systems of which the steady-state behavior is equivalent to that of an Erlang loss system. © 2012 Wiley Periodicals, Inc. Naval Research Logistics, 2012

This article develops a new approximate dynamic programming (DP) algorithm for Markov decision problems and applies it to a vehicle dispatching problem arising in warehouse management. The algorithm is of the actor-critic type and uses a least squares temporal difference learning method. It operates on a sample-path of the system and optimizes the policy within a prespecified class parameterized by a parsimonious set of parameters. The method is applicable to a partially observable Markov decision process setting where the measurements of state variables are potentially corrupted, and the cost is only observed through the imperfect state observations. We show that under reasonable assumptions, the algorithm converges to a locally optimal parameter set. We also show that the imperfect cost observations do not affect the policy and the algorithm minimizes the true expected cost. In the warehouse application, the problem is to dispatch sensor-equipped forklifts in order to minimize operating costs involving product movement delays and forklift maintenance. We consider instances where standard DP is computationally intractable. Simulation results confirm the theoretical claims of the article and show that our algorithm converges more smoothly than earlier actor–critic algorithms while substantially outperforming heuristics used in practice. © 2012 Wiley Periodicals, Inc. Naval Research Logistics, 2012

We address the problem of generating a joint flight and maintenance plan for a unit of mission aircraft. The objective is to establish a balanced allocation of the flight load and the maintenance capacity to the individual aircraft of the unit, so that its long-term availability is kept at a high and steady level. We propose a mixed integer nonlinear model to formulate the problem, the objective function of which minimizes a least squares index expressing the total deviation of the individual aircraft flight and maintenance times from their corresponding target values. Using the model's special structure and properties, we develop an exact search algorithm for its solution. We analyze the computational complexity of this algorithm, and we present computational results comparing its performance against that of a commercial optimization package. Besides demonstrating the superiority of the proposed algorithm, these results reveal that the total computational effort required for the solution of the problem depends mainly on two crucial parameters: the size of the unit (i.e., the number of aircraft that comprise it) and the space capacity of the maintenance station. © 2012 Wiley Periodicals, Inc. Naval Research Logistics, 2012

We consider a single-product dynamic lot-sizing model with an all-units quantity discount pricing scheme available to the buyer, where the discount price breakpoints are stationary. To capture the real-life behavior of a typical buyer who often takes advantage of quantity discounts through purchasing in excess of the anticipated demand, our model allows the buyer to resell or dispose of any leftover inventory that he/she does not need. We show that the general problem with an arbitrary number of discount price breakpoints is NP-hard. We then develop a polynomial algorithm for the problem with an O(T^m+3) running time when the number of price breakpoints, m, is fixed, where T is the number of time periods in the planning horizon. We further develop an O(T²) algorithm for the special case with a single price breakpoint. © 2012 Wiley Periodicals, Inc. Naval Research Logistics, 2012

This article considers a dynamic lot-sizing problem with storage capacity limitation in which backlogging is allowed. For general concave procurement and inventory costs, we present an O(T²) dynamic programming algorithm where T is the length of the planning horizon. Furthermore, in case of a fixed-charge cost structure without speculative motives, we show that the problem can be solved in O(T) time. By carefully choosing decompositions of the problems, we can use classical results like an efficient matrix searching algorithm and geometric techniques to achieve the results. © 2012 Wiley Periodicals, Inc. Naval Research Logistics, 2012

This article examines the capacity allocation decisions in a supply chain in which a supplier sells a common product to two retailers at a fixed wholesale price. The retailers order the supplier's product subject to an allocation mechanism preannounced by the supplier, and compete for the customer demand. We perform an equilibrium analysis of the retailers' ordering decisions under uniform and individually responsive allocations. Uniform allocation guarantees equilibrium orders, but is not necessarily truth inducing in the presence of demand competition. Further, we find that (1) neither the supplier nor either one of the retailers sees its profits necessarily increasing with the supplier's capacity, and the supplier may sell more with a lower capacity level, and (2) capacity allocation may not only affect the supply chain members' profits but also change the supply chain structure by driving a retailer out of the market. This article provides managerial insights on the capacity and ordering decisions for the supplier, the retailers, and the supply chain. © 2012 Wiley Periodicals, Inc. Naval Research Logistics, 2012

We consider the problem of transporting containers from one port to another using a fleet of ships. Each ship has a capacity constraint that limits the total number of containers it can carry; each ship calls on a specific set of ports that is referred to as its route and each ship follows a fixed route with a fixed departure time at each port. Each container has a release date, that is, the date when it becomes available for shipping at its origination port; it cannot be loaded onto a ship before its release date. Also, each container has an importance factor referred to as its weight. The delivery time of a container is defined as the time when the container is delivered by a ship at its destination port. We consider the problem of minimizing the total weighted delivery times over all containers. We consider three scenarios with regard to the routes of the ships, namely, (i) identical routes, (ii) nested routes, and (iii) arbitrary routes. We determine the computational complexity of the problems and provide heuristics with their worst-case analyses. © 2012 Wiley Periodicals, Inc. Naval Research Logistics, 2012

This article considers the problem of determining the optimal size allocation and optimal number of experimental conditions for a second elementary symmetric function with different coefficients. Analytical solutions for several practical applications are derived and the general formulation is used to elucidate the foundation between different parametric models found in recent studies. A geometrical interpretation of the structure of some theoretical results is also provided. This approach renders some complex problems more tractable than what numerical search algorithms would allow. © 2012 Wiley Periodicals, Inc. Naval Research Logistics, 2012

In this article, we deal with the inventory control of one single product in a distribution network consisting of one warehouse and n retailers where the retailers face continuous demands with constant rates. We study two policies for this problem that are derived from the application of the classical economical ordering quantity formula at each location: the first policy is purely single-echelon, whereas the second synchronizes the reorder intervals between the different installations and thus constitutes a first step toward a multiechelon perspective. We show that those policies are, respectively, - and 1.275-optimal. We then conduct computational experiments and demonstrate that our second policy exhibits excellent average performance and improves substantially over the pure single-echelon policy: in particular it deviates from Roundy's celebrated algorithm by less than 5%. This result indicates that in this simple setting, a great part of the benefit of shifting to a multiechelon perspective can be obtained by the most natural synchronization scheme between the different installations, and adapting single-echelon policies can be efficient at managing the inventory in simple distribution networks, confirming observations of practitioners. © 2012 Wiley Periodicals, Inc. Naval Research Logistics, 2012

The split pickup split delivery crude oil tanker routing and scheduling problem is a difficult combinatorial optimization problem, both theoretically and practically. However, because of the large expenses in crude oil shipping it is attractive to make use of optimization that exploits as many degrees of freedom as possible to save transportation cost. We propose a nested column generation algorithm for this particular split pickup split delivery problem which bears several complexities such as a heterogeneous fleet, multiple commodities, many-to-many relations for pickup and delivery of each commodity, sequence dependent vehicle capacities, and cargo quantity dependent pickup and delivery times. Our approach builds on a branch-and-price algorithm in which the column generation subproblems are solved by branch-and-price themselves. We describe our implementation in the branch-cut-and-price framework SCIP and give computational results for realistic test instances. The high quality schedules we obtain for these instances improve on those in previous studies. © 2012 Wiley Periodicals, Inc. Naval Research Logistics, 2012