The minmax multidimensional knapsack problem with application to a chance‐constrained problem

In this paper we present a new combinatorial problem, called minmax multidimensional knapsack problem (MKP), motivated by a military logistics problem. The logistics problem is a two‐period, two‐level, chance‐constrained problem with recourse. We show that the MKP is NP‐hard and develop a practically efficient combinatorial algorithm for solving it. We also show that under some reasonable assumptions regarding the operational setting of the logistics problem, the chance‐constrained optimization problem is decomposable into a series of MKPs that are solved separately. © 2007 Wiley Periodicals, Inc. Naval Research Logistics, 2007     

OF HAWKS AND DOVES

The policies toward countries aspiring to acquire nuclear weapons continue to be heavily contested, differing even among countries that consider nuclear proliferation as one of the main threats to international security. This article maps the actual policies of liberal democracies toward Iran and North Korea along a continuum from confrontation to accommodation. Using data from an expert survey, the authors outline four main findings. First, policies toward both Iran and North Korea have become increasingly confrontational over time. Second, no policy convergence was observed among the states studied; that is, notwithstanding the adoption of joint sanctions, differences remained between states preferring confrontation and those opting for accommodation. Third, states maintained remarkably stable policy profiles over time. Finally, despite obvious differences between the norm violations of North Korea and Iran, states generally followed remarkably similar policies toward both countries. The authors’ findings indicate that states exhibit stable preferences for either confrontation or accommodation toward nuclear aspirants. Although a comprehensive examination of the causes of these policy differences is beyond the scope of this article, the authors present evidence that a major cleavage exists between members and non-members of the Non-Aligned Movement, indicating that the degree to which nuclear aspirants’ sovereignty should be respected is a main issue of contention.     

Optimizing the quality control station configuration

We study unreliable serial production lines with known failure probabilities for each operation. Such a production line consists of a series of stations, existing machines, and optional quality control stations (QCSs). Our aim is to decide on the allocation of the QCSs within the assembly line, so as to maximize the expected profit of the system. In such a problem, the designer has to determine the QCS configuration and the production rate simultaneously. The profit maximization problem is approximated assuming exponentially distributed processing times, Poisson arrival process of jobs into the system, and the existing of holding costs. The novel feature of our model is the incorporation of holding costs that significantly complicated the problem. Our approximation approach uses a branch and bound strategy that employs our fast dynamic programming algorithm for minimizing the expected operational costs for a given production rate as a subroutine. Extensive numerical experiments are conducted to demonstrate the efficiency of the branch and bound procedure for solving large scale instances of the problem and for obtaining some qualitative insights.

相似文献   

Lot sizing with learning and forgetting in setups: Analytical results and insights

This article considers the dynamic lot sizing problem when there is learning and forgetting in setups. Learning in setups takes place with repetition when additional setups are made and forgetting takes place when there is a break between two successive setups. We allow the amount forgotten over a break to depend both on the length of the break and the amount of learning at the beginning of the break. The learning and forgetting functions we use are realistic. We present several analytical results and use these in developing computationally efficient algorithms for solving the problem. Some decision/forecast horizon results are also developed, and finally we present managerial insights based on our computational results. © 2016 Wiley Periodicals, Inc. Naval Research Logistics 63: 93–108, 2016     

Flexibility and complexity in periodic distribution problems

In this paper, we explore trade‐offs between operational flexibility and operational complexity in periodic distribution problems. We consider the gains from operational flexibility in terms of vehicle routing costs and customer service benefits, as well as the costs of operational complexity in terms of modeling, solution methods, and implementation challenges for drivers and customers. The period vehicle routing problem (PVRP) is a variation of the classic vehicle routing problem in which delivery routes are constructed for a period of time; the PVRP with service choice (PVRP‐SC) extends the PVRP to allow service (visit) frequency to become a decision of the model. For the periodic distribution problems represented by PVRP and PVRP‐SC, we introduce operational flexibility levers and a set of quantitative measures to evaluate the trade‐offs between flexibility and complexity. We develop a Tabu Search heuristic to incorporate a range of operational flexibility options. We analyze the potential value and the increased operational complexity of the flexibility levers. © 2006 Wiley Periodicals, Inc. Naval Research Logistics, 2007     

Resource allocation in an asymmetric technology race with temporary advantages

We consider two opponents that compete in developing asymmetric technologies where each party's technology is aimed at damaging (or neutralizing) the other's technology. The situation we consider is different than the classical problem of commercial R&D races in two ways: First, while in commercial R&D races the competitors compete over the control of market share, in our case the competition is about the effectiveness of technologies with respect to certain capabilities. Second, in contrast with the “winner‐takes‐all” assumption that characterizes much of the literature on this field in the commercial world, we assume that the party that wins the race gains a temporary advantage that expires when the other party develops a superior technology. We formulate a variety of models that apply to a one‐sided situation, where one of the two parties has to determine how much to invest in developing a technology to counter another technology employed by the other party. The decision problems are expressed as (convex) nonlinear optimization problems. We present an application that provides some operational insights regarding optimal resource allocation. We also consider a two‐sided situation and develop a Nash equilibrium solution that sets investment values, so that both parties have no incentive to change their investments. © 2012 Wiley Periodicals, Inc. Naval Research Logistics 59: 128–145, 2012     

The transshipment fund mechanism: Coordinating the decentralized multilocation transshipment problem

The multilocation replenishment and transshipment problem is concerned with several retailers facing random demand for the same item at distinct markets, that may use transshipments to eliminate excess inventory/shortages after demand realization. When the system is decentralized so that each retailer operates to maximize their own profit, there are incentive problems that prevent coordination. These problems arise even with two retailers who may pay each other for transshipped units. We propose a new mechanism based on a transshipment fund, which is the first to coordinate the system, in a fully noncooperative setting, for all instances of two retailers as well as all instances of any number of retailers. Moreover, our mechanism strongly coordinates the system, i.e., achieves coordination as the unique equilibrium. The computation and information requirements of this mechanism are realistic and relatively modest. We also present necessary and sufficient conditions for coordination and prove they are always satisfied with our mechanism. Numerical examples illustrate some of the properties underlying this mechanism for two retailers. © 2010 Wiley Periodicals, Inc. Naval Research Logistics, 2010     

The single and multi‐item transshipment problem with fixed transshipment costs

This article deals with supply chain systems in which lateral transshipments are allowed. For a system with two retailers facing stochastic demand, we relax the assumption of negligible fixed transshipment costs, thus, extending existing results for the single‐item case and introducing a new model with multiple items. The goal is to determine optimal transshipment and replenishment policies, such that the total centralized expected profit of both retailers is maximized. For the single‐item problem with fixed transshipment costs, we develop optimality conditions, analyze the expected profit function, and identify the optimal solution. We extend our analysis to multiple items with joint fixed transshipment costs, a problem that has not been investigated previously in the literature, and show how the optimality conditions may be extended for any number of items. Due to the complexity involved in solving these conditions, we suggest a simple heuristic based on the single‐item results. Finally, we conduct a numerical study that provides managerial insights on the solutions obtained in various settings and demonstrates that the suggested heuristic performs very well. © 2014 Wiley Periodicals, Inc. Naval Research Logistics, 61: 637–664, 2014     

Algorithms for the multi‐item multi‐vehicles dynamic lot sizing problem

We consider a two‐stage supply chain, in which multi‐items are shipped from a manufacturing facility or a central warehouse to a downstream retailer that faces deterministic external demand for each of the items over a finite planning horizon. The items are shipped through identical capacitated vehicles, each incurring a fixed cost per trip. In addition, there exist item‐dependent variable shipping costs and inventory holding costs at the retailer for items stored at the end of the period; these costs are constant over time. The sum of all costs must be minimized while satisfying the external demand without backlogging. In this paper we develop a search algorithm to solve the problem optimally. Our search algorithm, although exponential in the worst case, is very efficient empirically due to new properties of the optimal solution that we found, which allow us to restrict the number of solutions examined. Second, we perform a computational study that compares the empirical running time of our search methods to other available exact solution methods to the problem. Finally, we characterize the conditions under which each of the solution methods is likely to be faster than the others and suggest efficient heuristic solutions that we recommend using when the problem is large in all dimensions. © 2005 Wiley Periodicals, Inc. Naval Research Logistics, 2006.