A branch and bound algorithm for sector allocation of a naval task group

A naval task group (TG) is a collection of naval combatants and auxiliaries that are grouped together for the accomplishment of one or more missions. Ships forming a TG are located in predefined sectors. We define determination of ship sector locations to provide a robust air defense formation as the sector allocation problem (SAP). A robust formation is one that is very effective against a variety of attack scenarios but not necessarily the most effective against any scenario. We propose a 0‐1 integer linear programming formulation for SAP. The model takes the size and the direction of threat into account as well as the defensive weapons of the naval TG. We develop tight lower and upper bounds by incorporating some valid inequalities and use a branch and bound algorithm to exactly solve SAP. We report computational results that demonstrate the effectiveness of the proposed solution approach. © 2011 Wiley Periodicals, Inc. Naval Research Logistics, 2011     

A note on the optimality of index priority rules for search and sequencing problems

We show that the linear objective function of a search problem can be generalized to a power function and/or a logarithmic function and still be minimized by an index priority rule. We prove our result by solving the differential equation resulting from the required invariance condition, therefore, we also prove that any other generalization of this linear objective function will not lead to an index priority rule. We also demonstrate the full equivalence between two related search problems in the sense that a solution to either one can be used to solve the other one and vice versa. Finally, we show that the linear function is the only function leading to an index priority rule for the single‐machine makespan minimization problem with deteriorating jobs and an additive job deterioration function. © 2011 Wiley Periodicals, Inc. Naval Research Logistics, 2011     

Production‐inventory systems with imperfect advance demand information and updating

We consider a supplier with finite production capacity and stochastic production times. Customers provide advance demand information (ADI) to the supplier by announcing orders ahead of their due dates. However, this information is not perfect, and customers may request an order be fulfilled prior to or later than the expected due date. Customers update the status of their orders, but the time between consecutive updates is random. We formulate the production‐control problem as a continuous‐time Markov decision process and prove there is an optimal state‐dependent base‐stock policy, where the base‐stock levels depend upon the numbers of orders at various stages of update. In addition, we derive results on the sensitivity of the state‐dependent base‐stock levels to the number of orders in each stage of update. In a numerical study, we examine the benefit of ADI, and find that it is most valuable to the supplier when the time between updates is moderate. We also consider the impact of holding and backorder costs, numbers of updates, and the fraction of customers that provide ADI. In addition, we find that while ADI is always beneficial to the supplier, this may not be the case for the customers who provide the ADI. © 2011 Wiley Periodicals, Inc. Naval Research Logistics, 2011     

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     

A combination of Lagrangian relaxation and column generation for order batching in steelmaking and continuous‐casting production

This article considers the order batching problem in steelmaking and continuous‐casting production. The problem is to jointly specify the slabs needed to satisfy each customer order and group all the slabs of different customer orders into production batches. A novel mixed integer programming model is formulated for the problem. Through relaxing the order assignment constraints, a Lagrangian relaxation model is then obtained. By exploiting the relationship between Lagrangian relaxation and column generation, we develop a combined algorithm that contains nested double loops. At the inner loop, the subgradient method is applied for approximating the Lagrangian dual problem and pricing out columns of the master problem corresponding to the linear dual form of the Lagrangian dual problem. At the outer loop, column generation is employed to solve the master problem exactly and adjust Lagrangian multipliers. Computational experiments are carried out using real data collected from a large steel company, as well as on large‐scaled problem instances randomly generated. The results demonstrate that the combined algorithm can obtain tighter lower bound and higher quality solution within an acceptable computation time as compared to the conventional Lagrangian relaxation algorithm. © 2011 Wiley Periodicals, Inc. Naval Research Logistics, 2011     

Fashion products with asymmetric sales horizons

In this study, we explore an inventory model for a wholesaler who sells a fashion product through two channels with asymmetric sales horizons. The wholesaler can improve profitability by employing joint procurement and inventory reallocation as a recourse action in response to the dynamics of sales. In this research, a simple stochastic programming model is analyzed to specify the properties of the optimal inventory decisions. © 2011 Wiley Periodicals, Inc. Naval Research Logistics, 2011     

Aircraft routing under the risk of detection

The deterministic problem for finding an aircraft's optimal risk trajectory in a threat environment has been formulated. The threat is associated with the risk of aircraft detection by radars or similar sensors. The model considers an aircraft's trajectory in three‐dimensional (3‐D) space and represents the aircraft by a symmetrical ellipsoid with the axis of symmetry directing the trajectory. Analytical and discrete optimization approaches for routing an aircraft with variable radar cross‐section (RCS) subject to a constraint on the trajectory length have been developed. Through techniques of Calculus of Variations, the analytical approach reduces the original risk optimization problem to a vectorial nonlinear differential equation. In the case of a single detecting installation, a solution to this equation is expressed by a quadrature. A network optimization approach reduces the original problem to the Constrained Shortest Path Problem (CSPP) for a 3‐D network. The CSPP has been solved for various ellipsoid shapes and different length constraints in cases with several radars. The impact of ellipsoid shape on the geometry of an optimal trajectory as well as the impact of variable RCS on the performance of a network optimization algorithm have been analyzed and illustrated by several numerical examples. © 2006 Wiley Periodicals, Inc. Naval Research Logistics, 2006     

An inspection game: Taking account of fulfillment probabilities of players' aims

This paper deals with an inspection game of customs and a smuggler. The customs can take two options of assigning a patrol or not. The smuggler has two strategies of shipping its cargo of contraband or not. Two players have several opportunities to take actions during a limited number of days. When both players do, there are some possibilities that the customs captures the smuggler and, simultaneously, the smuggler possibly makes a success of the smuggling. If the smuggler is captured or there remain no days for playing the game, the game ends. In this paper, we formulate the problem into a multi‐stage two‐person zero‐sum stochastic game and investigate some characteristics of the equilibrium solution, some of which are given in a closed form in a special case. There have been some studies so far on the inspection game. However, some consider the case that the smuggler has only one opportunity of smuggling or the perfect‐capture case that the customs can certainly arrest the smuggler on patrol, and others think of a recursive game without the probabilities of fulfilling the players' purposes. In this paper, we consider the inspection game taking account of the fulfillment probabilities of the players' aims. © 2006 Wiley Periodicals, Inc. Naval Research Logistics, 2006     

A new reformulation approach for the generalized partial covering problem

In this paper, we consider a situation in which a group of facilities must be constructed in order to serve a given set of customers, where the facilities might not be able to guarantee an absolute coverage to the different customers. We examine the problem of maximizing the total service reliability of the system subject to a budgetary constraint. We propose a new reformulation of this problem that facilitates the generation of tight lower and upper bounds. These bounding mechanisms are embedded within the framework of a branch‐and‐bound procedure. Computational results on problem instances ranging in size up to 100 facilities and 200 customers reveal the efficacy of the proposed exact and heuristic approaches. © 2005 Wiley Periodicals, Inc. Naval Research Logistics, 2006     

The Banzhaf value and communication situations

Myerson 3 and 4 proposed and characterized a modification of the Shapley value in the context of communication situations. In this paper we propose several characterizations of the extension of the Banzhaf value proposed by Owen 7 to communication situations. In particular we characterize this value with the properties of fairness, isolation, and pairwise merging. © 2006 Wiley Periodicals, Inc. Naval Research Logistics, 2006