Quay crane scheduling at container terminals to minimize the maximum relative tardiness of vessel departures

In this paper, we study the problem of scheduling quay cranes (QCs) at container terminals where incoming vessels have different ready times. The objective is to minimize the maximum relative tardiness of vessel departures. The problem can be formulated as a mixed integer linear programming (MILP) model of large size that is difficult to solve directly. We propose a heuristic decomposition approach to breakdown the problem into two smaller, linked models, the vessel‐level and the berth‐level models. With the same berth‐level model, two heuristic methods are developed using different vessel‐level models. Computational experiments show that the proposed approach is effective and efficient. © 2005 Wiley Periodicals, Inc. Naval Research Logistics, 2006     

Lagrangian solution of maximum dispersion problems

We address the so‐called maximum dispersion problems where the objective is to maximize the sum or the minimum of interelement distances amongst a subset chosen from a given set. The problems arise in a variety of contexts including the location of obnoxious facilities, the selection of diverse groups, and the identification of dense subgraphs. They are known to be computationally difficult. In this paper, we propose a Lagrangian approach toward their solution and report the results of an extensive computational experimentation. Our results show that our Lagrangian approach is reasonably fast, that it yields heuristic solutions which provide good lower bounds on the optimum solution values for both the sum and the minimum problems, and further that it produces decent upper bounds in the case of the sum problem. For the sum problem, the results also show that the Lagrangian heuristic compares favorably against several existing heuristics. © 2000 John Wiley & Sons, Inc. Naval Research Logistics 47: 97–114, 2000     

Facility location models for immobile servers with stochastic demand

This paper presents several models for the location of facilities subject to congestion. Motivated by applications to locating servers in communication networks and automatic teller machines in bank systems, these models are developed for situations in which immobile service facilities are congested by stochastic demand originating from nearby customer locations. We consider this problem from three different perspectives, that of (i) the service provider (wishing to limit costs of setup and operating servers), (ii) the customers (wishing to limit costs of accessing and waiting for service), and (iii) both the service provider and the customers combined. In all cases, a minimum level of service quality is ensured by imposing an upper bound on the server utilization rate at a service facility. The latter two perspectives also incorporate queueing delay costs as part of the objective. Some cases are amenable to an optimal solution. For those cases that are more challenging, we either propose heuristic procedures to find good solutions or establish equivalence to other well‐studied facility location problems. © 2003 Wiley Periodicals, Inc. Naval Research Logistics, 2004.     

Outbound supply chain network design with mode selection and lead time considerations

We present a large‐scale network design model for the outbound supply chain of an automotive company that considers transportation mode selection (road vs. rail) and explicitly models the relationship between lead times and the volume of flow through the nodes of the network. We formulate the problem as a nonlinear zero‐one integer program, reformulate it to obtain a linear integer model, and develop a Lagrangian heuristic for its solution that gives near‐optimal results in reasonable time. We also present scenario analyses that examine the behavior of the supply chain under different parameter settings and the performance of the solution procedures under different experimental conditions. © 2006 Wiley Periodicals, Inc. Naval Research Logistics, 2007     

Expansion planning for waste‐to‐energy systems using waste forecast prediction sets

We consider an expansion planning problem for Waste‐to‐Energy (WtE) systems facing uncertainty in future waste supplies. The WtE expansion plans are regarded as strategic, long term decisions, while the waste distribution and treatment are medium to short term operational decisions which can adapt to the actual waste collected. We propose a prediction set uncertainty model which integrates a set of waste generation forecasts and is constructed based on user‐specified levels of forecasting errors. Next, we use the prediction sets for WtE expansion scenario analysis. More specifically, for a given WtE expansion plan, the guaranteed net present value (NPV) is evaluated by computing an extreme value forecast trajectory of future waste generation from the prediction set that minimizes the maximum NPV of the WtE project. This problem is essentially a multiple stage min‐max dynamic optimization problem. By exploiting the structure of the WtE problem, we show this is equivalent to a simpler min‐max optimization problem, which can be further transformed into a single mixed‐integer linear program. Furthermore, we extend the model to optimize the guaranteed NPV by searching over the set of all feasible expansion scenarios, and show that this can be solved by an exact cutting plane approach. We also propose a heuristic based on a constant proportion distribution rule for the WtE expansion optimization model, which reduces the problem into a moderate size mixed‐integer program. Finally, our computational studies demonstrate that our proposed expansion model solutions are very stable and competitive in performance compared to scenario tree approaches. © 2016 Wiley Periodicals, Inc. Naval Research Logistics 63: 47–70, 2016     

Allocating capacity in parallel queues to improve their resilience to deliberate attack

We develop models that lend insight into how to design systems that enjoy economies of scale in their operating costs, when those systems will subsequently face disruptions from accidents, acts of nature, or an intentional attack from a well‐informed attacker. The systems are modeled as parallel M/M/1 queues, and the key question is how to allocate service capacity among the queues to make the system resilient to worst‐case disruptions. We formulate this problem as a three‐level sequential game of perfect information between a defender and a hypothetical attacker. The optimal allocation of service capacity to queues depends on the type of attack one is facing. We distinguish between deterministic incremental attacks, where some, but not all, of the capacity of each attacked queue is knocked out, and zero‐one random‐outcome (ZORO) attacks, where the outcome is random and either all capacity at an attacked queue is knocked out or none is. There are differences in the way one should design systems in the face of incremental or ZORO attacks. For incremental attacks it is best to concentrate capacity. For ZORO attacks the optimal allocation is more complex, typically, but not always, involving spreading the service capacity out somewhat among the servers. © 2011 Wiley Periodicals, Inc. Naval Research Logistics, 2011     

A generalized assignment model for dynamic supply chain capacity planning

We consider a generalization of the well‐known generalized assignment problem (GAP) over discrete time periods encompassed within a finite planning horizon. The resulting model, MultiGAP, addresses the assignment of tasks to agents within each time period, with the attendant single‐period assignment costs and agent‐capacity constraint requirements, in conjunction with transition costs arising between any two consecutive periods in which a task is reassigned to a different agent. As is the case for its single‐period antecedent, MultiGAP offers a robust tool for modeling a wide range of capacity planning problems occurring within supply chain management. We provide two formulations for MultiGAP and establish that the second (alternative) formulation provides a tighter bound. We define a Lagrangian relaxation‐based heuristic as well as a branch‐and‐bound algorithm for MultiGAP. Computational experience with the heuristic and branch‐and‐bound algorithm on over 2500 test problems is reported. The Lagrangian heuristic consistently generates high‐quality and in many cases near‐optimal solutions. The branch‐and‐bound algorithm is also seen to constitute an effective means for solving to optimality MultiGAP problems of reasonable size. © 2012 Wiley Periodicals, Inc. Naval Research Logistics, 2012     

Scheduling policies for an antiterrorist surveillance system

This article concerns scheduling policies in a surveillance system aimed at detecting a terrorist attack in time. Terrorist suspects arriving at a public area are subject to continuous monitoring, while a surveillance team takes their biometric signatures and compares them with records stored in a terrorist database. Because the surveillance team can screen only one terrorist suspect at a time, the team faces a dynamic scheduling problem among the suspects. We build a model consisting of an M/G/1 queue with two types of customers—red and white—to study this problem. Both types of customers are impatient but the reneging time distributions are different. The server only receives a reward by serving a red customer and can use the time a customer has spent in the queue to deduce its likely type. In a few special cases, a simple service rule—such as first‐come‐first‐serve—is optimal. We explain why the problem is in general difficult and we develop a heuristic policy motivated by the fact that terrorist attacks tend to be rare events. © 2009 Wiley Periodicals, Inc. Naval Research Logistics, 2009     

Evasion policies for a vessel being chased by pirate skiffs

Piracy attack is a serious safety problem for maritime transport worldwide. Whilst various strategic actions can be taken, such as rerouting vessels and strengthening navy patrols, this still cannot completely eliminate the possibility of a piracy attack. It is therefore important for a commercial vessel to be equipped with operational solutions in case of piracy attacks. In particular, the choice of a direction for rapidly fleeing is a critical decision for the vessel. In this article, we formulate such a problem as a nonlinear optimal control problem. We consider various policies, such as maintaining a straight direction or making turns, develop algorithms to optimize the policies, and derive conditions under which these policies are effective and safe. Our work can be used as a real‐time decision making tool that enables a vessel master to evaluate different scenarios and quickly make decisions.     

Lagrangian relaxation approach to the targeting problem

In this paper, we consider a new weapon–target allocation problem with the objective of minimizing the overall firing cost. The problem is formulated as a nonlinear integer programming model. We applied Lagrangian relaxation and a branch‐and‐bound method to the problem after transforming the nonlinear constraints into linear ones. An efficient primal heuristic is developed to find a feasible solution to the problem to facilitate the procedure. In the branch‐and‐bound method, three different branching rules are considered and the performances are evaluated. Computational results using randomly generated data are presented. © 1999 John Wiley & Sons, Inc. Naval Research Logistics 46: 640–653, 1999     

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     

Dynamic pricing and replenishment: Optimality,bounds, and asymptotics

In many applications, managers face the problem of replenishing and selling products during a finite time horizon. We investigate the problem of making dynamic and joint decisions on product replenishment and selling in order to improve profit. We consider a backlog scenario in which penalty cost (resulting from fulfillment delay) and accommodation cost (resulting from shortage at the end of the selling horizon) are incurred. Based on continuous‐time and discrete‐state dynamic programming, we study the optimal joint decisions and characterize their structural properties. We establish an upper bound for the optimal expected profit and develop a fluid policy by resorting to the deterministic version of the problem (ie, the fluid problem). The fluid policy is shown to be asymptotically optimal for the original stochastic problem when the problem size is sufficiently large. The static nature of the fluid policy and its lack of flexibility in matching supply with demand motivate us to develop a “target‐inventory” heuristic, which is shown, numerically, to be a significant improvement over the fluid policy. Scenarios with discrete feasible sets and lost‐sales are also discussed in this article.     

Machine scheduling with an availability constraint and job delivery coordination

In this paper we study the scheduling problem that considers both production and job delivery at the same time with machine availability considerations. Only one vehicle is available to deliver jobs in a fixed transportation time to a distribution center. The vehicle can load at most K jobs as a delivery batch in one shipment due to the vehicle capacity constraint. The objective is to minimize the arrival time of the last delivery batch to the distribution center. Since machines may not always be available over the production period in real life due to preventive maintenance, we incorporate machine availability into the models. Three scenarios of the problem are studied. For the problem in which the jobs are processed on a single machine and the jobs interrupted by the unavailable machine interval are resumable, we provide a polynomial algorithm to solve the problem optimally. For the problem in which the jobs are processed on a single machine and the interrupted jobs are nonresumable, we first show that the problem is NP‐hard. We then propose a heuristic with a worst‐case error bound of 1/2 and show that the bound is tight. For the problem in which the jobs are processed on either one of two parallel machines, where only one machine has an unavailable interval and the interrupted jobs are resumable, we propose a heuristic with a worst‐case error bound of 2/3. © 2006 Wiley Periodicals, Inc. Naval Research Logistics, 2007     

A two‐echelon inventory‐location problem with service considerations

We study the problem of designing a two‐echelon spare parts inventory system consisting of a central plant and a number of service centers each serving a set of customers with stochastic demand. Processing and storage capacities at both levels of facilities are limited. The manufacturing process is modeled as a queuing system at the plant. The goal is to optimize the base‐stock levels at both echelons, the location of service centers, and the allocation of customers to centers simultaneously, subject to service constraints. A mixed integer nonlinear programming model (MINLP) is formulated to minimize the total expected cost of the system. The problem is NP‐hard and a Lagrangian heuristic is proposed. We present computational results and discuss the trade‐off between cost and service. © 2009 Wiley Periodicals, Inc. Naval Research Logistics 2009     

Heuristics for the multi‐resource generalized assignment problem

The well‐known generalized assignment problem (GAP) involves the identification of a minimum‐cost assignment of tasks to agents when each agent is constrained by a resource in limited supply. The multi‐resource generalized assignment problem (MRGAP) is the generalization of the GAP in which there are a number of different potentially constraining resources associated with each agent. This paper explores heuristic procedures for the MRGAP. We first define a three‐phase heuristic which seeks to construct a feasible solution to MRGAP and then systematically attempts to improve the solution. We then propose a modification of the heuristic for the MRGAP defined previously by Gavish and Pirkul. The third procedure is a hybrid heuristic that combines the first two heuristics, thus capturing their relative strengths. We discuss extensive computational experience with the heuristics. The hybrid procedure is seen to be extremely effective in solving MRGAPs, generating feasible solutions to more than 99% of the test problems and consistently producing near‐optimal solutions. © 2001 John Wiley & Sons, Inc. Naval Research Logistics 48: 468–483, 2001     

The graph association problem: Mathematical models and a lagrangian heuristic

Graph association is the problem of merging many graphs that collectively describe a set of possibly repetitive entities and relationships into a single graph that contains unique entities and relationships. As a form of data association, graph association can be used to identify when two sensors are observing the same object so information from both sensors can be combined and analyzed in a meaningful and consistent way. Graph association between two graphs is related to the problem of graph matching, and between multiple graphs it is related to the common labeling of a graph set (also known as multiple graph matching) problem. This article contribution is to formulate graph association as a binary linear program and introduce a heuristic for solving multiple graph association using a Lagrangian relaxation approach to address issues with between‐graph transitivity requirements. The algorithms are tested on a representative dataset. The developed model formulation was found to accurately solve the graph association problem. Furthermore, the Lagrangian heuristic was found to solve the developed model within 3% of optimal on many problem instances, and found better solutions to large problems than is possible by directly using CPLEX. © 2013 Wiley Periodicals, Inc. Naval Research Logistics, 2013     

Distribution free bounds for service constrained (Q,r) inventory systems

A classical and important problem in stochastic inventory theory is to determine the order quantity (Q) and the reorder level (r) to minimize inventory holding and backorder costs subject to a service constraint that the fill rate, i.e., the fraction of demand satisfied by inventory in stock, is at least equal to a desired value. This problem is often hard to solve because the fill rate constraint is not convex in (Q, r) unless additional assumptions are made about the distribution of demand during the lead‐time. As a consequence, there are no known algorithms, other than exhaustive search, that are available for solving this problem in its full generality. Our paper derives the first known bounds to the fill‐rate constrained (Q, r) inventory problem. We derive upper and lower bounds for the optimal values of the order quantity and the reorder level for this problem that are independent of the distribution of demand during the lead time and its variance. We show that the classical economic order quantity is a lower bound on the optimal ordering quantity. We present an efficient solution procedure that exploits these bounds and has a guaranteed bound on the error. When the Lagrangian of the fill rate constraint is convex or when the fill rate constraint does not exist, our bounds can be used to enhance the efficiency of existing algorithms. © 2000 John Wiley & Sons, Inc. Naval Research Logistics 47: 635–656, 2000     

Optimizing barge utilization in hinterland container transportation

In hinterland container transportation the use of barges is getting more and more important. We propose a real‐life operational planning problem model from an inland terminal operating company, in which the number of containers shipped per barge is maximized and the number of terminals visited per barge is minimized. This problem is solved with an integer linear program (ILP), yielding strong cost reductions, about 20%, compared to the method used currently in practice. Besides, we develop a heuristic that solves the ILP in two stages. First, it decides for each barge which terminals to visit and second it assigns containers to the barges. This heuristic produces almost always optimal solutions and otherwise near‐optimal solutions. Moreover, the heuristic runs much faster than the ILP, especially for large‐sized instances.     

Optimal patrol to uncover threats in time when detection is imperfect

Consider a patrol problem, where a patroller traverses a graph through edges to detect potential attacks at nodes. An attack takes a random amount of time to complete. The patroller takes one time unit to move to and inspect an adjacent node, and will detect an ongoing attack with some probability. If an attack completes before it is detected, a cost is incurred. The attack time distribution, the cost due to a successful attack, and the detection probability all depend on the attack node. The patroller seeks a patrol policy that minimizes the expected cost incurred when, and if, an attack eventually happens. We consider two cases. A random attacker chooses where to attack according to predetermined probabilities, while a strategic attacker chooses where to attack to incur the maximal expected cost. In each case, computing the optimal solution, although possible, quickly becomes intractable for problems of practical sizes. Our main contribution is to develop efficient index policies—based on Lagrangian relaxation methodology, and also on approximate dynamic programming—which typically achieve within 1% of optimality with computation time orders of magnitude less than what is required to compute the optimal policy for problems of practical sizes. © 2014 Wiley Periodicals, Inc. Naval Research Logistics, 61: 557–576, 2014     

Priority and dynamic scheduling in a make‐to‐stock queue with hyperexponential demand

We consider the scheduling problem in a make‐to‐stock queue with two demand classes that can be differentiated based on their variability. One class experiences Poisson arrivals and the other class experiences hyperexponential renewal arrivals. We provide an exact analysis of the case where the demand class with higher variability is given non‐preemptive priority. The results are then used to compare the inventory cost performance of three scheduling disciplines, first‐come first‐serve and priority to either class. We then build on an existing dynamic scheduling heuristic to propose a modification that works well for our system. Extensions of the heuristic to more than two classes and to the case where demand state is known are also discussed. © 2006 Wiley Periodicals, Inc. Naval Research Logistics, 2006.