A facility reliability problem: Formulation,properties, and algorithm

Having a robustly designed supply chain network is one of the most effective ways to hedge against network disruptions because contingency plans in the event of a disruption are often significantly limited. In this article, we study the facility reliability problem: how to design a reliable supply chain network in the presence of random facility disruptions with the option of hardening selected facilities. We consider a facility location problem incorporating two types of facilities, one that is unreliable and another that is reliable (which is not subject to disruption, but is more expensive). We formulate this as a mixed integer programming model and develop a Lagrangian Relaxation‐based solution algorithm. We derive structural properties of the problem and show that for some values of the disruption probability, the problem reduces to the classical uncapacitated fixed charge location problem. In addition, we show that the proposed solution algorithm is not only capable of solving large‐scale problems, but is also computationally effective. © 2009 Wiley Periodicals, Inc. Naval Research Logistics, 2010     

A supply chain design model with unreliable supply

Uncertainties abound within a supply chain and have big impacts on its performance. We propose an integrated model for a three‐tiered supply chain network with one supplier, one or more facilities and retailers. This model takes into consideration the unreliable aspects of a supply chain. The properties of the optimal solution to the model are analyzed to reveal the impacts of supply uncertainty on supply chain design decisions. We also propose a general solution algorithm for this model. Computational experience is presented and discussed. © 2007 Wiley Periodicals, Inc. Naval Research Logistics, 2007     

不确定条件下装备器材供应网规划模型

装备器材供应网是装备器材供应保障工作的重要基石,其规划问题是我军装备器材保障过程的重要战略决策之一。针对节点、边和需求的不确定性,对不确定条件下由多个区域供应子网构成的装备器材供应网的规划问题展开研究。针对问题的特点,用区间分析理论对供应网规划中的不确定性因素进行度量和运算,得到不确定性规划模型,通过区间运算转化,将不确定性模型转化为确定性混合整数规划模型,并设计采用基于禁忌搜索算法的两阶段算法进行求解,分别得到了不同参数设置下的模型求解结果,并将所用算法与模糊规划和随机规划算法的求解结果进行了比较分析。实例分析结果表明所建立的模型和算法具有较强的实用性。     

Benders decomposition with alternative multiple cuts for a multi‐product closed‐loop supply chain network design model

In this article, we consider a multi‐product closed‐loop supply chain network design problem where we locate collection centers and remanufacturing facilities while coordinating the forward and reverse flows in the network so as to minimize the processing, transportation, and fixed location costs. The problem of interest is motivated by the practice of an original equipment manufacturer in the automotive industry that provides service parts for vehicle maintenance and repair. We provide an effective problem formulation that is amenable to efficient Benders reformulation and an exact solution approach. More specifically, we develop an efficient dual solution approach to generate strong Benders cuts, and, in addition to the classical single Benders cut approach, we propose three different approaches for adding multiple Benders cuts. These cuts are obtained via dual problem disaggregation based either on the forward and reverse flows, or the products, or both. We present computational results which illustrate the superior performance of the proposed solution methodology with multiple Benders cuts in comparison to the branch‐and‐cut approach as well as the traditional Benders decomposition approach with a single cut. In particular, we observe that the use of multiple Benders cuts generates stronger lower bounds and promotes faster convergence to optimality. We also observe that if the model parameters are such that the different costs are not balanced, but, rather, are biased towards one of the major cost categories (processing, transportation or fixed location costs), the time required to obtain the optimal solution decreases considerably when using the proposed solution methodology as well as the branch‐and‐cut approach. © 2007 Wiley Periodicals, Inc. Naval Research Logistics, 2007     

Coordinating independent buyers with integer‐ratio time coordination and quantity discounts

Supply chain members can gain substantial benefits by coordinating their activities. However, a remaining challenge is to create useful coordination mechanisms when channel members are independent. This paper develops a coordination strategy with which a supplier uses quantity discounts to entice independent buyers to comply with an integer‐ratio time coordination scheme. The problem is analyzed as a Stackelberg game in which the supplier acts as the leader by announcing its coordination policy in advance and buyers act as followers by deciding their ordering decisions with this information. The strategy is compared to a coordination mechanism with quantity discounts and power‐of‐two time coordination. While both strategies are able to produce substantial benefits over simple quantity discounts, integer‐ratio time coordination provides a better coordination mechanism for a decentralized supply chain. It is shown that power‐of‐two time coordination may not be able to provide a stable equilibrium coordination strategy when buyers act independently and opportunistically. Furthermore, if this is not the case, integer‐ratio time coordination is at least equally effective. Unlike a centralized solution, under which the improvement by integer‐ratio over power‐of‐two time coordination is limited to 2% of optimality, system cost reduction from a decentralized coordination strategy could be much more significant. © 2003 Wiley Periodicals, Inc. Naval Research Logistics, 2004.     

Single‐commodity stochastic network design under demand and topological uncertainties with insufficient data

Stochastic network design is fundamental to transportation and logistic problems in practice, yet faces new modeling and computational challenges resulted from heterogeneous sources of uncertainties and their unknown distributions given limited data. In this article, we design arcs in a network to optimize the cost of single‐commodity flows under random demand and arc disruptions. We minimize the network design cost plus cost associated with network performance under uncertainty evaluated by two schemes. The first scheme restricts demand and arc capacities in budgeted uncertainty sets and minimizes the worst‐case cost of supply generation and network flows for any possible realizations. The second scheme generates a finite set of samples from statistical information (e.g., moments) of data and minimizes the expected cost of supplies and flows, for which we bound the worst‐case cost using budgeted uncertainty sets. We develop cutting‐plane algorithms for solving the mixed‐integer nonlinear programming reformulations of the problem under the two schemes. We compare the computational efficacy of different approaches and analyze the results by testing diverse instances of random and real‐world networks. © 2017 Wiley Periodicals, Inc. Naval Research Logistics 64: 154–173, 2017     

An integrated electric power supply chain and fuel market network framework: Theoretical modeling with empirical analysis for New England

In this article, we develop a novel electric power supply chain network model with fuel supply markets that captures both the economic network transactions in energy supply markets and the physical network transmission constraints in the electric power network. The theoretical derivation and analysis are done using the theory of variational inequalities. We then apply the model to a specific case, the New England electric power supply chain, consisting of six states, five fuel types, 82 power generators, with a total of 573 generating units, and 10 demand market regions. The empirical case study demonstrates that the regional electric power prices simulated by our model match the actual electricity prices in New England very well. We also compute the electric power prices and the spark spread, an important measure of the power plant profitability, under natural gas and oil price variations. The empirical examples illustrate that in New England, the market/grid‐level fuel competition has become the major factor that affects the influence of the oil price on the natural gas price. Finally, we utilize the model to quantitatively investigate how changes in the demand for electricity influence the electric power and the fuel markets from a regional perspective. The theoretical model can be applied to other regions and multiple electricity markets under deregulation to quantify the interactions in electric power/energy supply chains and their effects on flows and prices. © 2009 Wiley Periodicals, Inc. Naval Research Logistics, 2009     

Vertically restrictive pricing in supply chains with price‐dependent demand

We examine the behavior of a manufacturer and a retailer in a decentralized supply chain under price‐dependent, stochastic demand. We model a retail fixed markup (RFM) policy, which can arise as a form of vertically restrictive pricing in a supply chain, and we examine its effect on supply chain performance. We prove the existence of the optimal pricing and replenishment policies when demand has a linear additive form and the distribution of the uncertainty component has a nondecreasing failure rate. We numerically compare the relative performance of RFM to a price‐only contract and we find that RFM results in greater profit for the supply chain than the price‐only contract in a variety of scenarios. We find that RFM can lead to Pareto‐improving solutions where both the supplier and the retailer earn more profit than under a price‐only contract. Finally, we compare RFM to a buyback contract and explore the implications of allowing the fixed markup parameter to be endogenous to the model. © 2006 Wiley Periodicals, Inc. Naval Research Logistics, 2006.     

Generation and storage dispatch in electricity networks with generator disruptions

We present methods for optimizing generation and storage decisions in an electricity network with multiple unreliable generators, each colocated with one energy storage unit (e.g., battery), and multiple loads under power flow constraints. Our model chooses the amount of energy produced by each generator and the amount of energy stored in each battery in every time period in order to minimize power generation and storage costs when each generator faces stochastic Markovian supply disruptions. This problem cannot be optimized easily using stochastic programming and/or dynamic programming approaches. Therefore, in this study, we present several heuristic methods to find an approximate optimal solution for this system. Each heuristic involves decomposing the network into several single‐generator, single‐battery, multiload systems and solving them optimally using dynamic programming, then obtaining a solution for the original problem by recombining. We discuss the computational performance of the proposed heuristics as well as insights gained from the models. © 2015 Wiley Periodicals, Inc. Naval Research Logistics 62: 493–511, 2015     

Interdiction models for delaying adversarial attacks against critical information technology infrastructure

Information technology (IT) infrastructure relies on a globalized supply chain that is vulnerable to numerous risks from adversarial attacks. It is important to protect IT infrastructure from these dynamic, persistent risks by delaying adversarial exploits. In this paper, we propose max‐min interdiction models for critical infrastructure protection that prioritizes cost‐effective security mitigations to maximally delay adversarial attacks. We consider attacks originating from multiple adversaries, each of which aims to find a “critical path” through the attack surface to complete the corresponding attack as soon as possible. Decision‐makers can deploy mitigations to delay attack exploits, however, mitigation effectiveness is sometimes uncertain. We propose a stochastic model variant to address this uncertainty by incorporating random delay times. The proposed models can be reformulated as a nested max‐max problem using dualization. We propose a Lagrangian heuristic approach that decomposes the max‐max problem into a number of smaller subproblems, and updates upper and lower bounds to the original problem via subgradient optimization. We evaluate the perfect information solution value as an alternative method for updating the upper bound. Computational results demonstrate that the Lagrangian heuristic identifies near‐optimal solutions efficiently, which outperforms a general purpose mixed‐integer programming solver on medium and large instances.     

Stability of information‐sharing alliances in a three‐level supply chain

In their recent article, Leng and Parlar (L&P) (2009) analyze information‐sharing alliances in a three‐level supply chain (consisting of a manufacturer, a distributor, and a retailer) that faces a nonstationary end demand. Supply chain members can share demand information, which reduces information distortion and thus decreases their inventory holding and shortage costs. We expand the results from L&P by considering dynamic (farsighted) stability concepts. We use two different allocation rules and show that under some reasonable assumptions there should always be some information sharing in this supply chain. We also identify conditions under which the retailer in a stable outcome shares his demand information with the distributor, with the manufacturer, or with both remaining supply chain members. © 2010 Wiley Periodicals, Inc. Naval Research Logistics, 2010     

Assessing the value of demand sharing in supply chains

We consider the problem of assessing the value of demand sharing in a multistage supply chain in which the retailer observes stationary autoregressive moving average demand with Gaussian white noise (shocks). Similar to previous research, we assume each supply chain player constructs its best linear forecast of the leadtime demand and uses it to determine the order quantity via a periodic review myopic order‐up‐to policy. We demonstrate how a typical supply chain player can determine the extent of its available information in the presence of demand sharing by studying the properties of the moving average polynomials of adjacent supply chain players. The retailer's demand is driven by the random shocks appearing in the autoregressive moving average representation for its demand. Under the assumptions we will make in this article, to the retailer, knowing the shock information is equivalent to knowing the demand process (assuming that the model parameters are also known). Thus (in the event of sharing) the retailer's demand sequence and shock sequence would contain the same information to the retailer's supplier. We will show that, once we consider the dynamics of demand propagation further up the chain, it may be that a player's demand and shock sequences will contain different levels of information for an upstream player. Hence, we study how a player can determine its available information under demand sharing, and use this information to forecast leadtime demand. We characterize the value of demand sharing for a typical supply chain player. Furthermore, we show conditions under which (i) it is equivalent to no sharing, (ii) it is equivalent to full information shock sharing, and (iii) it is intermediate in value to the two previously described arrangements. Although it follows from existing literature that demand sharing is equivalent to full information shock sharing between a retailer and supplier, we demonstrate and characterize when this result does not generalize to upstream supply chain players. We then show that demand propagates through a supply chain where any player may share nothing, its demand, or its full information shocks (FIS) with an adjacent upstream player as quasi‐ARMA in—quasi‐ARMA out. We also provide a convenient form for the propagation of demand in a supply chain that will lend itself to future research applications. © 2014 Wiley Periodicals, Inc. Naval Research Logistics 61: 515–531, 2014     

Impact of transfer pricing methods for tax purposes on supply chain performance under demand uncertainty

Transfer pricing refers to the pricing of an intermediate product or service within a firm. This product or service is transferred between two divisions of the firm. Thus, transfer pricing is closely related to the allocation of profits in a supply chain. Motivated by the significant impact of transfer pricing methods for tax purposes on operational decisions and the corresponding profits of a supply chain, in this article, we study a decentralized supply chain of a multinational firm consisting of two divisions: a manufacturing division and a retail division. These two divisions are located in different countries under demand uncertainty. The retail division orders an intermediate product from the upstream manufacturing division and sets the retail price under random customer demand. The manufacturing division accepts or rejects the retail division's order. We specifically consider two commonly used transfer pricing methods for tax purposes: the cost‐plus method and the resale‐price method. We compare the supply chain profits under these two methods. Based on the newsvendor framework, our analysis shows that the cost‐plus method tends to allocate a higher percentage of profit to the retail division, whereas the resale‐price method tends to achieve a higher firm‐wide profit. However, as the variability of demand increases, our numerical study suggests that the firm‐wide and divisional profits tend to be higher under the cost‐plus method than they are under the resale‐price method. © 2013 Wiley Periodicals, Inc. Naval Research Logistics, 2013     

Dual‐ascent and primal heuristics for production‐assembly‐distribution system design

This article proposes two dual‐ascent algorithms and uses each in combination with a primal drop heuristic embedded within a branch and bound framework to solve the uncapacitated production assembly distribution system (i.e., supply chain) design problem, which is formulated as a mixed integer program. Computational results indicate that one approach, which combines primal drop and dual‐ascent heuristics, can solve instances within reasonable time and prescribes solutions with gaps between the primal and dual solution values that are less than 0.15%, an efficacy suiting it for actual large‐scale applications. © 2012 Wiley Periodicals, Inc. Naval Research Logistics, 2013     

Capacitated lot‐sizing and scheduling with parallel machines,back‐orders,and setup carry‐over

We address the capacitated lot‐sizing and scheduling problem with setup times, setup carry‐over, back‐orders, and parallel machines as it appears in a semiconductor assembly facility. The problem can be formulated as an extension of the capacitated lot‐sizing problem with linked lot‐sizes (CLSPL). We present a mixed integer (MIP) formulation of the problem and a new solution procedure. The solution procedure is based on a novel “aggregate model,” which uses integer instead of binary variables. The model is embedded in a period‐by‐period heuristic and is solved to optimality or near‐optimality in each iteration using standard procedures (CPLEX). A subsequent scheduling routine loads and sequences the products on the parallel machines. Six variants of the heuristic are presented and tested in an extensive computational study. © 2009 Wiley Periodicals, Inc. Naval Research Logistics 2009     

Bicriteria product design optimization: An efficient solution procedure using AND/OR trees

Competitive imperatives are causing manufacturing firms to consider multiple criteria when designing products. However, current methods to deal with multiple criteria in product design are ad hoc in nature. In this paper we present a systematic procedure to efficiently solve bicriteria product design optimization problems. We first present a modeling framework, the AND/OR tree, which permits a simplified representation of product design optimization problems. We then show how product design optimization problems on AND/OR trees can be framed as network design problems on a special graph—a directed series‐parallel graph. We develop an enumerative solution algorithm for the bicriteria problem that requires as a subroutine the solution of the parametric shortest path problem. Although this parametric problem is hard on general graphs, we show that it is polynomially solvable on the series‐parallel graph. As a result we develop an efficient solution algorithm for the product design optimization problem that does not require the use of complex and expensive linear/integer programming solvers. As a byproduct of the solution algorithm, sensitivity analysis for product design optimization is also efficiently performed under this framework. © 2002 Wiley Periodicals, Inc. Naval Research Logistics 49: 574–592, 2002; Published online in Wiley InterScience (www.interscience.wiley.com). DOI 10.1002/nav.10031     

The network redesign problem for access telecommunications networks

The network redesign problem attempts to design an optimal network that serves both existing and new demands. In addition to using spare capacity on existing network facilities and deploying new facilities, the model allows for rearrangement of existing demand units. As rearrangements mean reassigning existing demand units, at a cost, to different facilities, they may lead to disconnecting of uneconomical existing facilities, resulting in significant savings. The model is applied to an access network, where the demands from many sources need to be routed to a single destination, using either low‐capacity or high‐capacity facilities. Demand from any location can be routed to the destination either directly or through one other demand location. Low‐capacity facilities can be used between any pair of locations, whereas high‐capacity facilities are used only between demand locations and the destination. We present a new modeling approach to such problems. The model is described as a network flow problem, where each demand location is represented by multiple nodes associated with demands, low‐capacity and high‐capacity facilities, and rearrangements. Each link has a capacity and a cost per unit flow parameters. Some of the links also have a fixed‐charge cost. The resulting network flow model is formulated as a mixed integer program, and solved by a heuristic and a commercially available software. © 1999 John Wiley & Sons, Inc. Naval Research Logistics 46: 487–506, 1999     

Algorithm to solve a chance‐constrained network capacity design problem with stochastic demands and finite support

We consider the problem of determining the capacity to assign to each arc in a given network, subject to uncertainty in the supply and/or demand of each node. This design problem underlies many real‐world applications, such as the design of power transmission and telecommunications networks. We first consider the case where a set of supply/demand scenarios are provided, and we must determine the minimum‐cost set of arc capacities such that a feasible flow exists for each scenario. We briefly review existing theoretical approaches to solving this problem and explore implementation strategies to reduce run times. With this as a foundation, our primary focus is on a chance‐constrained version of the problem in which α% of the scenarios must be feasible under the chosen capacity, where α is a user‐defined parameter and the specific scenarios to be satisfied are not predetermined. We describe an algorithm which utilizes a separation routine for identifying violated cut‐sets which can solve the problem to optimality, and we present computational results. We also present a novel greedy algorithm, our primary contribution, which can be used to solve for a high quality heuristic solution. We present computational analysis to evaluate the performance of our proposed approaches. © 2016 Wiley Periodicals, Inc. Naval Research Logistics 63: 236–246, 2016     

Subspace dynamic‐simplex linear interpolation search for mixed‐integer black‐box optimization problems

Design and management of complex systems with both integer and continuous decision variables can be guided using mixed‐integer optimization models and analysis. We propose a new mixed‐integer black‐box optimization (MIBO) method, subspace dynamic‐simplex linear interpolation search (SD‐SLIS), for decision making problems in which system performance can only be evaluated with a computer black‐box model. Through a sequence of gradient‐type local searches in subspaces of solution space, SD‐SLIS is particularly efficient for such MIBO problems with scaling issues. We discuss the convergence conditions and properties of SD‐SLIS algorithms for a class of MIBO problems. Under mild conditions, SD‐SLIS is proved to converge to a stationary solution asymptotically. We apply SD‐SLIS to six example problems including two MIBO problems associated with petroleum field development projects. The algorithm performance of SD‐SLIS is compared with that of a state‐of‐the‐art direct‐search method, NOMAD, and that of a full space simplex interpolation search, Full‐SLIS. The numerical results suggest that SD‐SLIS solves the example problems efficiently and outperforms the compared methods for most of the example cases. © 2017 Wiley Periodicals, Inc. Naval Research Logistics 64: 305–322, 2017     

Flow shop scheduling with earliness,tardiness, and intermediate inventory holding costs

We consider the problem of scheduling customer orders in a flow shop with the objective of minimizing the sum of tardiness, earliness (finished goods inventory holding), and intermediate (work‐in‐process) inventory holding costs. We formulate this problem as an integer program, and based on approximate solutions to two different, but closely related, Dantzig‐Wolfe reformulations, we develop heuristics to minimize the total cost. We exploit the duality between Dantzig‐Wolfe reformulation and Lagrangian relaxation to enhance our heuristics. This combined approach enables us to develop two different lower bounds on the optimal integer solution, together with intuitive approaches for obtaining near‐optimal feasible integer solutions. To the best of our knowledge, this is the first paper that applies column generation to a scheduling problem with different types of strongly ????‐hard pricing problems which are solved heuristically. The computational study demonstrates that our algorithms have a significant speed advantage over alternate methods, yield good lower bounds, and generate near‐optimal feasible integer solutions for problem instances with many machines and a realistically large number of jobs. © 2004 Wiley Periodicals, Inc. Naval Research Logistics, 2004.