The resource constrained project scheduling problem with multiple crashable modes: An exact solution method

We introduce a formulation and an exact solution method for a nonpreemptive resource constrained project scheduling problem in which the duration/cost of an activity is determined by the mode selection and the duration reduction (crashing) within the mode. This problem is a natural combination of the time/cost tradeoff problem and the resource constrained project scheduling problem. It involves the determination, for each activity, of its resource requirements, the extent of crashing, and its start time so that the total project cost is minimized. We present a branch and bound procedure and report computational results with a set of 160 problems. Computational results demonstrate the effectiveness of our procedure. © 2001 John Wiley & Sons, Inc. Naval Research Logistics 48: 107–127, 2001     

Replacing continuous demand with discrete demand in a competitive location model

Location models commonly represent demand as discrete points rather than as continuously spread over an area. This modeling technique introduces inaccuracies to the objective function and consequently to the optimal location solution. In this article this inaccuracy is investigated by the study of a particular competitive facility location problem. First, the location problem is formulated over a continuous demand area. The optimal location for a new facility that optimizes the objective function is obtained. This optimal location solution is then compared with the optimal location obtained for a discrete set of demand points. Second, a simple approximation approach to the continuous demand formulation is proposed. The location problem can be solved by using the discrete demand algorithm while significantly reducing the inaccuracies. This way the simplicity of the discrete approach is combined with the approximated accuracy of the continuous-demand location solution. Extensive analysis and computations of the test problem are reported. It is recommended that this approximation approach be considered for implementation in other location models. © 1997 John Wiley & Sons, Inc.     

OPTIMAL FACILITY LOCATION UNDER RANDOM DEMAND WITH GENERAL COST STRUCTURE

This paper investigates the problem of determining the optimal location of plants, and their respective production and distribution levels, in order to meet demand at a finite number of centers. The possible locations of plants are restricted to a finite set of sites, and the demands are allowed to be random. The cost structure of operating a plant is dependent on its location and is assumed to be a piecewise linear function of the production level, though not necessarily concave or convex. The paper is organized in three parts. In the first part, a branch and bound procedure for the general piecewise linear cost problem is presented, assuming that the demand is known. In the second part, a solution procedure is presented for the case when the demand is random, assuming a linear cost of production. Finally, in the third part, a solution procedure is presented for the general problem utilizing the results of the earlier parts. Certain extensions, such as capacity expansion or reduction at existing plants, and geopolitical configuration constraints can be easily incorporated within this framework.     

A cover based competitive facility location model with continuous demand

In this paper we propose and solve a competitive facility location model when demand is continuously distributed in an area and each facility attracts customers within a given distance. This distance is a measure of the facility's attractiveness level which may be different for different facilities. The market share captured by each facility is calculated by two numerical integration methods. These approaches can be used for evaluating functional values in other operations research models as well. The single facility location problem is optimally solved by the big triangle small triangle global optimization algorithm and the multiple facility problem is heuristically solved by the Nelder‐Mead algorithm. Extensive computational experiments demonstrate the effectiveness of the solution approaches.     

Algorithms for solving the conditional covering problem on paths

Consider the conditional covering problem on an undirected graph, where each node represents a site that must be covered by a facility, and facilities may only be established at these nodes. Each facility can cover all sites that lie within some common covering radius, except the site at which it is located. Although this problem is difficult to solve on general graphs, there exist special structures on which the problem is easily solvable. In this paper, we consider the special case in which the graph is a simple path. For the case in which facility location costs do not vary based on the site, we derive characteristics of the problem that lead to a linear‐time shortest path algorithm for solving the problem. When the facility location costs vary according to the site, we provide a more complex, but still polynomial‐time, dynamic programming algorithm to find the optimal solution. © 2005 Wiley Periodicals, Inc. Naval Research Logistics, 2005.     

Locating facilities in three-dimensional space by convex programming

We consider the problem of simultaneously locating any number of facilities in three-dimensional Euclidean space. The criterion to be satisfied is that of minimizing the total cost of some activity between the facilities to be located and any number of fixed locations. Any amount of activity may be present between any pair of the facilities themselves. The total cost is assumed to be a linear function of the inter-facility and facility-to-fixed locations distances. Since the total cost function for this problem is convex, a unique optimal solution exists. Certain discontinuities are shown to exist in the derivatives of the total cost function which previously has prevented the successful use of gradient computing methods for locating optimal solutions. This article demonstrates the use of a created function which possesses all the necessary properties for ensuring the convergence of first order gradient techniques and is itself uniformly convergent to the actual objective function. Use of the fitted function and the dual problem in the case of constrained problems enables solutions to be determined within any predetermined degree of accuracy. Some computation results are given for both constrained and unconstrained problems.     

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     

Optimal location of public facilities

Location of both public and private facilities has become an important consideration in today's society. Progress in solution of location problems has been impeded by difficulty of the fixed charge problem and the lack of an efficient algorithm for large problems. In this paper a method is developed for solving large-scale public location problems. An implicit enumeration scheme with an imbedded transportation algorithm forms the basis of the solution technique.     

Due‐window assignment with unit processing‐time jobs

In due‐window assignment problems, jobs completed within a designated time interval are regarded as being on time, whereas early and tardy jobs are penalized. The objective is to determine the location and size of the due‐window, as well as the job schedule. We address a common due‐window assignment problem on parallel identical machines with unit processing time jobs. We show that the number of candidate values for the optimal due‐window starting time and for the optimal due‐window completion time are bounded by 2. We also prove that the starting time of the first job on each of the machines is either 0 or 1, thus introducing a fairly simple, constant‐time solution for the problem. © 2004 Wiley Periodicals, Inc. Naval Research Logistics, 2004     

An efficient heuristic procedure for the capacitated warehouse location problem

This paper introduces an efficient heuristic procedure for solving a special class of mixed integer programming problem called the capacitated warehouse (plant) location problem. This procedure parallels the work reported earlier in [9] on the uncapacitated warehouse location problem. The procedure can be viewed as tracing a judiciously selected path of the branch and bound tree (from the initial node to the terminal node) to arrive at a candidate solution. A simple backtracking scheme is also incorporated in the procedure to investigate possible improvement in the solution. Computational results on problems found in the literature look quite encouraging.     

A stochastic gradual cover location problem

Covering models assume that a point is covered if it is within a certain distance from a facility and not covered beyond that distance. In gradual cover models it is assumed that a point is fully covered within a given distance from a facility, then cover gradually declines, and the point is not covered beyond a larger distance. Gradual cover models address the discontinuity in cover which may not be the correct approach in many situations. In the stochastic gradual cover model presented in this article it is assumed that the short and long distances employed in gradual cover models are random variables. This refinement of gradual cover models provides yet a more realistic depiction of actual behavior in many situations. The maximal cover model based on the new concept is analyzed and the single facility location cover problem in the plane is solved. Computational results illustrating the effectiveness of the solution procedures are presented. © 2010 Wiley Periodicals, Inc. Naval Research Logistics, 2010     

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     

A note on solving multifacility location problems involving euclidean distances

This note considers a recently proposed solution method for a multifacility location problem. It is shown that the method does not always produce an optimal solution.     

Client‐contractor bargaining on net present value in project scheduling with limited resources

The client‐contractor bargaining problem addressed here is in the context of a multi‐mode resource constrained project scheduling problem with discounted cash flows, which is formulated as a progress payments model. In this model, the contractor receives payments from the client at predetermined regular time intervals. The last payment is paid at the first predetermined payment point right after project completion. The second payment model considered in this paper is the one with payments at activity completions. The project is represented on an Activity‐on‐Node (AON) project network. Activity durations are assumed to be deterministic. The project duration is bounded from above by a deadline imposed by the client, which constitutes a hard constraint. The bargaining objective is to maximize the bargaining objective function comprised of the objectives of both the client and the contractor. The bargaining objective function is expected to reflect the two‐party nature of the problem environment and seeks a compromise between the client and the contractor. The bargaining power concept is introduced into the problem by the bargaining power weights used in the bargaining objective function. Simulated annealing algorithm and genetic algorithm approaches are proposed as solution procedures. The proposed solution methods are tested with respect to solution quality and solution times. Sensitivity analyses are conducted among different parameters used in the model, namely the profit margin, the discount rate, and the bargaining power weights. © 2009 Wiley Periodicals, Inc. Naval Research Logistics, 2009     

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     

An integer decomposition algorithm for solving a two‐stage facility location problem with second‐stage activation costs

We study a stochastic scenario‐based facility location problem arising in situations when facilities must first be located, then activated in a particular scenario before they can be used to satisfy scenario demands. Unlike typical facility location problems, fixed charges arise in the initial location of the facilities, and then in the activation of located facilities. The first‐stage variables in our problem are the traditional binary facility‐location variables, whereas the second‐stage variables involve a mix of binary facility‐activation variables and continuous flow variables. Benders decomposition is not applicable for these problems due to the presence of the second‐stage integer activation variables. Instead, we derive cutting planes tailored to the problem under investigation from recourse solution data. These cutting planes are derived by solving a series of specialized shortest path problems based on a modified residual graph from the recourse solution, and are tighter than the general cuts established by Laporte and Louveaux for two‐stage binary programming problems. We demonstrate the computational efficacy of our approach on a variety of randomly generated test problems. © 2010 Wiley Periodicals, Inc. Naval Research Logistics, 2010     

Column generation for stochastic green telecommunication network planning with switchable base stations

We present the green telecommunication network planning problem with switchable base stations, where the location and configuration of the base stations are optimized, while taking into account uncertainty and variability of demand. The problem is formulated as a two‐stage stochastic program under demand uncertainty with integers in both stages. Since solving the presented problem is computationally challenging, we develop the corresponding Dantzig‐Wolfe reformulation and propose a solution approach based on column generation. Comprehensive computational results are provided for instances of varying characteristics. The results show that the joint location and dynamic switching of base stations leads to significant savings in terms of energy cost. Up to 30% reduction in power consumption cost is achieved while still serving all users. In certain cases, allowing dynamic configurations leads to more installed base stations and higher user coverage, while having lower total energy consumption. The Dantzig‐Wolfe reformulation provides solutions with a tight LP‐gap eliminating the need for a full branch‐and‐price scheme. Furthermore, the proposed column generation solution approach is computationally efficient and outperforms CPLEX on the majority of the tested instances. © 2016 Wiley Periodicals, Inc. Naval Research Logistics 63: 351–366, 2016     

Route optimization for multiple searchers

We consider a discrete time‐and‐space route‐optimization problem across a finite time horizon in which multiple searchers seek to detect one or more probabilistically moving targets. This article formulates a novel convex mixed‐integer nonlinear program for this problem that generalizes earlier models to situations with multiple targets, searcher deconfliction, and target‐ and location‐dependent search effectiveness. We present two solution approaches, one based on the cutting‐plane method and the other on linearization. These approaches result in the first practical exact algorithms for solving this important problem, which arises broadly in military, rescue, law enforcement, and border patrol operations. The cutting‐plane approach solves many realistically sized problem instances in a few minutes, while existing branch‐and‐bound algorithms fail. A specialized cut improves solution time by 50[percnt] in difficult problem instances. The approach based on linearization, which is applicable in important special cases, may further reduce solution time with one or two orders of magnitude. The solution time for the cutting‐plane approach tends to remain constant as the number of searchers grows. In part, then, we overcome the difficulty that earlier solution methods have with many searchers. © 2010 Wiley Periodicals, Inc. Naval Research Logistics, 2010     

On a rational stopping rule for facilities location algorithms

In the multifacility location problem, a number of new facilities are to be located so as to minimize a sum of weighted distances. Recently, a lower bound on the optimal value was developed, for use in deciding when to stop an iterative solution procedure. We develop a stronger bound that allows some computational savings.     

An efficient primal approach to bottleneck transportation problems

This article addresses bottleneck linear programming problems and in particular capacitated and constrained bottleneck transportation problems. A pseudopricing procedure based on the poly-ω procedure is used to facilitate the primal simplex procedure. This process allows the recent computational developments such as the Extended Threaded Index Method to be applied to bottleneck transportation problems. The impact on problem solution times is illustrated by computational testing and comparison with other current methods.