On the optimal detection of an underwater intruder in a channel using unmanned underwater vehicles

Given a number of patrollers that are required to detect an intruder in a channel, the channel patrol problem consists of determining the periodic trajectories that the patrollers must trace out so as to maximized the probability of detection of the intruder. We formulate this problem as an optimal control problem. We assume that the patrollers' sensors are imperfect and that their motions are subject to turn‐rate constraints, and that the intruder travels straight down a channel with constant speed. Using discretization of time and space, we approximate the optimal control problem with a large‐scale nonlinear programming problem which we solve to obtain an approximately stationary solution and a corresponding optimized trajectory for each patroller. In numerical tests for one, two, and three underwater patrollers, an underwater intruder, different trajectory constraints, several intruder speeds and other specific parameter choices, we obtain new insight—not easily obtained using simply geometric calculations—into efficient patrol trajectory design under certain conditions for multiple patrollers in a narrow channel where interaction between the patrollers is unavoidable due to their limited turn rate.© 2011 Wiley Periodicals, Inc. Naval Research Logistics, 2011     

Double Mover–Stayer model on customer switching in telecommunications industry

Customer acquisition and customer retention are the most important challenges in the increasingly competitive telecommunications industry. Traditional studies of customer switching always assume that customers are homogeneous, and thus that model customer switching behavior follows a Markov formulation. However, this postulation is obviously inappropriate in most instances. Blumen et al. (Cornell Studies of Industrial and Labor Relations, Cornell University Press, Ithaca, NY, 1955) developed the Mover–Stayer (MS) model, a generalization of the Markov chain model, to relax the requirement of homogeneity and allow the presence of heterogeneity with two different types of individuals—“stayers,” who purchase the same kinds of products or services throughout the entire observation period; and “movers,” who look for variety in products or services over time. There are two purpose of this article. First, we extend the MS model to a Double Mover‐Stayer (DMS) model by assuming the existence of three types of individuals in the market: (1) stable and loyal customers, who have stable usage within the same company; (2) instable but loyal customers, whose usage varies within the same company over time; and (3) disloyal customers, who switch from one company to another to seek for new experiences or/and benefits. We also propose an estimation method for the DMS model. Second, we apply the DMS model to telecommunications data and demonstrate how it can be used for pattern identification, hidden knowledge discovery, and decision making. © 2012 Wiley Periodicals, Inc. Naval Research Logistics, 2012     

Inventory competition with yield reliability improvement

This article studies the inventory competition under yield uncertainty. Two firms with random yield compete for substitutable demand: If one firm suffers a stockout, which can be caused by yield failure, its unsatisfied customers may switch to its competitor. We first study the case in which two competing firms decide order quantities based on the exogenous reliability levels. The results from the traditional inventory competition are generalized to the case with yield uncertainty and we find that quantity and reliability can be complementary instruments in the competition. Furthermore, we allow the firms to endogenously improve their yield reliability before competing in quantity. We show that the reliability game is submodular under some assumptions. The results indicate that the competition in quantity can discourage the reliability improvement. With an extensive numerical study, we also demonstrate the robustness of our analytical results in more general settings. © 2015 Wiley Periodicals, Inc. Naval Research Logistics 62: 107–126, 2015     

Heuristic procedure for a multiproduct dynamic lot-sizing problem with coordinated replenishments

In this article we develop a heuristic procedure for a multiproduct dynamic lot-sizing problem. In this problem a joint setup cost is incurred when at least one product is ordered in a period. In addition to the joint setup cost a separate setup cost for each product ordered is also incurred. The objective is to determine the product lot sizes, over a finite planning horizon, that will minimize the total relevant cost such that the demand in each period for each product is satisfied without backlogging. In this article we present an effective heuristic procedure for this problem. Computational results for the heuristic procedure are also reported. Our computational experience leads us to conclude that the heuristic procedure may be of considerable value as a decision-making aid to production planners in a real-world setting. © 1994 John Wiley & Sons, Inc.     

Optimal control of a capacitated inventory system with multiple demand classes

This article studies the optimal control of a periodic‐review make‐to‐stock system with limited production capacity and multiple demand classes. In this system, a single product is produced to fulfill several classes of demands. The manager has to make the production and inventory allocation decisions. His objective is to minimize the expected total discounted cost. The production decision is made at the beginning of each period and determines the amount of products to be produced. The inventory allocation decision is made after receiving the random demands and determines the amount of demands to be satisfied. A modified base stock policy is shown to be optimal for production, and a multi‐level rationing policy is shown to be optimal for inventory allocation. Then a heuristic algorithm is proposed to approximate the optimal policy. The numerical studies show that the heuristic algorithm is very effective. © 2011 Wiley Periodicals, Inc. Naval Research Logistics 58: 43–58, 2011     

Multiple subset sum with inclusive assignment set restrictions

In a traditional multiple subset sum problem (MSSP), there is a given set of items and a given set of bins (or knapsacks) with identical capacities. The objective is to select a subset of the items and pack them into the bins such that the total weight of the selected items is maximized. However, in many applications of the MSSP, the bins have assignment restrictions. In this article, we study the subset sum problem with inclusive assignment set restrictions, in which the assignment set of one item (i.e., the set of bins that the item may be assigned to) must be either a subset or a superset of the assignment set of another item. We develop an efficient 0.6492‐approximation algorithm and test its effectiveness via computational experiments. We also develop a polynomial time approximation scheme for this problem. © 2011 Wiley Periodicals, Inc. Naval Research Logistics, 2011     

Scheduling parallel machines with inclusive processing set restrictions

We consider the problem of assigning a set of jobs to different parallel machines of the same processing speed, where each job is compatible to only a subset of those machines. The machines can be linearly ordered such that a higher‐indexed machine can process all those jobs that a lower‐indexed machine can process. The objective is to minimize the makespan of the schedule. This problem is motivated by industrial applications such as cargo handling by cranes with nonidentical weight capacities, computer processor scheduling with memory constraints, and grades of service provision by parallel servers. We develop an efficient algorithm for this problem with a worst‐case performance ratio of + ε, where ε is a positive constant which may be set arbitrarily close to zero. We also present a polynomial time approximation scheme for this problem, which answers an open question in the literature. © 2008 Wiley Periodicals, Inc. Naval Research Logistics, 2008     

Approximation algorithms for general one‐warehouse multi‐retailer systems

Logistical planning problems are complicated in practice because planners have to deal with the challenges of demand planning and supply replenishment, while taking into account the issues of (i) inventory perishability and storage charges, (ii) management of backlog and/or lost sales, and (iii) cost saving opportunities due to economies of scale in order replenishment and transportation. It is therefore not surprising that many logistical planning problems are computationally difficult, and finding a good solution to these problems necessitates the development of many ad hoc algorithmic procedures to address various features of the planning problems. In this article, we identify simple conditions and structural properties associated with these logistical planning problems in which the warehouse is managed as a cross‐docking facility. Despite the nonlinear cost structures in the problems, we show that a solution that is within ε‐optimality can be obtained by solving a related piece‐wise linear concave cost multi‐commodity network flow problem. An immediate consequence of this result is that certain classes of logistical planning problems can be approximated by a factor of (1 + ε) in polynomial time. This significantly improves upon the results found in literature for these classes of problems. We also show that the piece‐wise linear concave cost network flow problem can be approximated to within a logarithmic factor via a large scale linear programming relaxation. We use polymatroidal constraints to capture the piece‐wise concavity feature of the cost functions. This gives rise to a unified and generic LP‐based approach for a large class of complicated logistical planning problems. © 2009 Wiley Periodicals, Inc. Naval Research Logistics, 2009     

An optimal procedure for the coordinated replenishment dynamic lot‐sizing problem with quantity discounts

We consider in this paper the coordinated replenishment dynamic lot‐sizing problem when quantity discounts are offered. In addition to the coordination required due to the presence of major and minor setup costs, a separate element of coordination made possible by the offer of quantity discounts needs to be considered as well. The mathematical programming formulation for the incremental discount version of the extended problem and a tighter reformulation of the problem based on variable redefinition are provided. These then serve as the basis for the development of a primal‐dual based approach that yields a strong lower bound for our problem. This lower bound is then used in a branch and bound scheme to find an optimal solution to the problem. Computational results for this optimal solution procedure are reported in the paper. © 2000 John Wiley & Sons, Inc. Naval Research Logistics 47: 686–695, 2000     

A single‐period inventory placement problem for a serial supply chain

This article addresses the inventory placement problem in a serial supply chain facing a stochastic demand for a single planning period. All customer demand is served from stage 1, where the product is stored in its final form. If the demand exceeds the supply at stage 1, then stage 1 is resupplied from stocks held at the upstream stages 2 through N, where the product may be stored in finished form or as raw materials or subassemblies. All stocking decisions are made before the demand occurs. The demand is nonnegative and continuous with a known probability distribution, and the purchasing, holding, shipping, processing, and shortage costs are proportional. There are no fixed costs. All unsatisfied demand is lost. The objective is to select the stock quantities that should be placed different stages so as to maximize the expected profit. Under reasonable cost assumptions, this leads to a convex constrained optimization problem. We characterize the properties of the optimal solution and propose an effective algorithm for its computation. For the case of normal demands, the calculations can be done on a spreadsheet. © 2001 John Wiley & Sons, Inc. Naval Research Logistics 48:506–517, 2001