Heuristic algorithms for routing yard‐side equipment for minimizing loading times in container terminals

This paper discusses a method of routing yard‐side equipment during loading operations in container terminals. Both the route of yard‐side equipment (such as transfer cranes or straddle carriers) and the number of containers picked up at each yard‐bay is determined simultaneously. The objective of the problem in this paper is to minimize the total container‐handling time in a yard. The size of the search space can be greatly reduced by utilizing inherent properties of the optimal solution. An encoding method is introduced to represent solutions in the search space. A genetic algorithm and a beam search algorithm are suggested to solve the above problem. Numerical experiments have been conducted to compare the performances of the proposed heuristic algorithms against each other and against that of the optimal solution. © 2003 Wiley Periodicals, Inc. Naval Research Logistics 50: 498–514, 2003     

Analysis of a new vehicle scheduling and location problem

We consider a container terminal discharging containers from a ship and locating them in the terminal yard. Each container has a number of potential locations in the yard where it can be stored. Containers are moved from the ship to the yard using a fleet of vehicles, each of which can carry one container at a time. The problem is to assign each container to a yard location and dispatch vehicles to the containers so as to minimize the time it takes to download all the containers from the ship. We show that the problem is NP‐hard and develop a heuristic algorithm based on formulating the problem as an assignment problem. The effectiveness of the heuristic is analyzed from both worst‐case and computational points of view. © 2001 John Wiley & Sons, Inc. Naval Research Logistics 48: 363–385, 2001     

A mathematical formulation and efficient heuristics for the dynamic container relocation problem

The container relocation problem (CRP) is concerned with emptying a single yard‐bay which contains J containers each following a given pickup order so as to minimize the total number of relocations made during their retrieval process. The CRP can be modeled as a binary integer programming (IP) problem and is known to be NP‐hard. In this work, we focus on an extension of the CRP to the case where containers are both received and retrieved from a single yard‐bay, and call it the dynamic container relocation problem. The arrival (departure) sequences of containers to (from) the yard‐bay is assumed to be known a priori. A binary IP formulation is presented for the problem. Then, we propose three types of heuristic methods: index based heuristics, heuristics using the binary IP formulation, and a beam search heuristic. Computational experiments are performed on an extensive set of randomly generated test instances. Our results show that beam search heuristic is very efficient and performs better than the other heuristic methods.Copyright © 2014 Wiley Periodicals, Inc. Naval Research Logistics 61: 101–118, 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.     

The assignment of storage locations to containers for a container stack

Assigning storage locations to incoming or reshuffled containers is a fundamental problem essential to the operations efficiency of container terminals. The problem is notoriously hard for its combinatorial and dynamic nature. In this article, we minimize the number of reshuffles in assigning storage locations for incoming and reshuffled export containers. For the static problem to empty a given stack without any new container arrival, the optimum reshuffle sequence is identified by an integer program (IP). The integer program captures the evolution of stack configurations as a function of decisions and is of interest by itself. Heuristics based on the integer program are then derived. Their competitiveness in accuracy and time are established by extensive numerical runs comparing them with existing heuristics in literature and in practice as well as with extensions of the existing heuristics. Variants of the IP‐based heuristics are then applied to the dynamic problem with continual retrievals and arrivals of containers. Again, numerical runs confirm that the IP‐based heuristic is competitive. © 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     

Mathematical formulation and heuristic algorithm for the block relocation and loading problem

This study considers the block relocation and loading problem in container terminals. The optimal loading sequence and relocation location are simultaneously decided on the basis of the desired ship‐bay and initial yard space configuration. An integer linear programming model is developed to minimize the number of relocations in the yard space on the basis of no shifts in the ship bay. The accuracy of the model is tested on small‐scale scenarios by using CPLEX. Considering the problem size in the real world, we present a rule‐based heuristic method that is combined with a mathematical model for the removal, loading, and relocation operations. The influence of rules on algorithm performance is also analyzed, and the heuristic algorithm is compared with different types of algorithms in the literature. The extensive numerical experiments show the efficiency of the proposed heuristic algorithm.     

Capacity allocation with machine duplication in semiconductor manufacturing

The manufacturing process for a computer chip is complex in that it involves a large number of distinct operations requiring a substantial lead‐time for completion. Our observations of such a manufacturing process at a large plant in the United States led us to identify several tactical and operational problems that were being addressed by the production planners on a recurring basis. This paper focuses on one such problem. At a tactical level, given a demand forecast of wafers to be manufactured, one specific problem deals with specifying which machine or machine groups will process different batches of wafers. We address this problem by recognizing the capacity limitations of the individual machines as well as the requirement for reducing operating and investment costs related to the machines. A mathematical model, which is a variation of the well‐known capacitated facility location problem, is proposed to solve this problem. Given the intractability of the model, we first develop problem specific lower bounding procedures based on Lagrangean relaxation. We also propose a heuristic method to obtain “good” solutions with reasonable computational effort. Computational tests, using hypothetical and industry‐based data, indicate that our heuristic approach provides optimal/near optimal solutions fairly quickly. © 2005 Wiley Periodicals, Inc. Naval Research Logistics, 2005     

Scheduling of depalletizing and truck loading operations in a food distribution system

This paper studies a scheduling problem arising in a beef distribution system where pallets of various types of beef products in the warehouse are first depalletized and then individual cases are loaded via conveyors to the trucks which deliver beef products to various customers. Given each customer's demand for each type of beef, the problem is to find a depalletizing and truck loading schedule that fills all the demands at a minimum total cost. We first show that the general problem where there are multiple trucks and each truck covers multiple customers is strongly NP‐hard. Then we propose polynomial‐time algorithms for the case where there are multiple trucks, each covering only one customer, and the case where there is only one truck covering multiple customers. We also develop an optimal dynamic programming algorithm and a heuristic for solving the general problem. By comparing to the optimal solutions generated by the dynamic programming algorithm, the heuristic is shown to be capable of generating near optimal solutions quickly. © 2003 Wiley Periodicals, Inc. Naval Research Logistics, 2003     

Bicriteria scheduling on a single batching machine with job transportation and deterioration considerations

We study a single batching machine scheduling problem with transportation and deterioration considerations arising from steel production. A set of jobs are transported, one at a time, by a vehicle from a holding area to the single batching machine. The machine can process several jobs simultaneously as a batch. The processing time of a job will increase if the duration from the time leaving the holding area to the start of its processing exceeds a given threshold. The time needed to process a batch is the longest of the job processing times in the batch. The problem is to determine the job sequence for transportation and the job batching for processing so as to minimize the makespan and the number of batches. We study four variations (P1, P2, P3, P4) of the problem with different treatments of the two criteria. We prove that all the four variations are strongly NP‐hard and further develop polynomial time algorithms for their special cases. For each of the first three variations, we propose a heuristic algorithm and analyze its worst‐case performance. For P4, which is to find the Pareto frontier, we provide a heuristic algorithm and an exact algorithm based on branch and bound. Computational experiments show that all the heuristic algorithms perform well on randomly generated problem instances, and the exact algorithm for P4 can obtain Pareto optimal schedules for small‐scale instances. © 2014 Wiley Periodicals, Inc. Naval Research Logistics 61: 269–285, 2014     

Parallel machine scheduling with batch deliveries to minimize total flow time and delivery cost

Motivated by the flow of products in the iron and steel industry, we study an identical and parallel machine scheduling problem with batch deliveries, where jobs finished on the parallel machines are delivered to customers in batches. Each delivery batch has a capacity and incurs a cost. The objective is to find a coordinated production and delivery schedule that minimizes the total flow time of jobs plus the total delivery cost. This problem is an extension of the problem considered by Hall and Potts, Ann Oper Res 135 (2005) 41–64, who studied a two‐machine problem with an unbounded number of transporters and unbounded delivery capacity. We first provide a dynamic programming algorithm to solve a special case with a given job assignment to the machines. A heuristic algorithm is then presented for the general problem, and its worst‐case performance ratio is analyzed. The computational results show that the heuristic algorithm can generate near‐optimal solutions. Finally, we offer a fully polynomial‐time approximation scheme for a fixed number of machines. © 2016 Wiley Periodicals, Inc. Naval Research Logistics 63: 492–502, 2016     

A generalization of the weighted set covering problem

We study a generalization of the weighted set covering problem where every element needs to be covered multiple times. When no set contains more than two elements, we can solve the problem in polynomial time by solving a corresponding weighted perfect b‐matching problem. In general, we may use a polynomial‐time greedy heuristic similar to the one for the classical weighted set covering problem studied by D.S. Johnson [Approximation algorithms for combinatorial problems, J Comput Syst Sci 9 (1974), 256–278], L. Lovasz [On the ratio of optimal integral and fractional covers, Discrete Math 13 (1975), 383–390], and V. Chvatal [A greedy heuristic for the set‐covering problem, Math Oper Res 4(3) (1979), 233–235] to get an approximate solution for the problem. We find a worst‐case bound for the heuristic similar to that for the classical problem. In addition, we introduce a general type of probability distribution for the population of the problem instances and prove that the greedy heuristic is asymptotically optimal for instances drawn from such a distribution. We also conduct computational studies to compare solutions resulting from running the heuristic and from running the commercial integer programming solver CPLEX on problem instances drawn from a more specific type of distribution. The results clearly exemplify benefits of using the greedy heuristic when problem instances are large. © 2003 Wiley Periodicals, Inc. Naval Research Logistics, 2005     

Scheduling a production–distribution system to optimize the tradeoff between delivery tardiness and distribution cost

We consider a make‐to‐order production–distribution system with one supplier and one or more customers. A set of orders with due dates needs to be processed by the supplier and delivered to the customers upon completion. The supplier can process one order at a time without preemption. Each customer is at a distinct location and only orders from the same customer can be batched together for delivery. Each delivery shipment has a capacity limit and incurs a distribution cost. The problem is to find a joint schedule of order processing at the supplier and order delivery from the supplier to the customers that optimizes an objective function involving the maximum delivery tardiness and the total distribution cost. We first study the solvability of various cases of the problem by either providing an efficient algorithm or proving the intractability of the problem. We then develop a fast heuristic for the general problem. We show that the heuristic is asymptotically optimal as the number of orders goes to infinity. We also evaluate the performance of the heuristic computationally by using lower bounds obtained by a column generation approach. Our results indicate that the heuristic is capable of generating near optimal solutions quickly. Finally, we study the value of production–distribution integration by comparing our integrated approach with two sequential approaches where scheduling decisions for order processing are made first, followed by order delivery decisions, with no or only partial integration of the two decisions. We show that in many cases, the integrated approach performs significantly better than the sequential approaches. © 2005 Wiley Periodicals, Inc. Naval Research Logistics, 2005     

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     

A selective newsvendor approach to order management

Consider a supplier offering a product to several potential demand sources, each with a unique revenue, size, and probability that it will materialize. Given a long procurement lead time, the supplier must choose the orders to pursue and the total quantity to procure prior to the selling season. We model this as a selective newsvendor problem of maximizing profits where the total (random) demand is given by the set of pursued orders. Given that the dimensionality of a mixed‐integer linear programming formulation of the problem increases exponentially with the number of potential orders, we develop both a tailored exact algorithm based on the L‐shaped method for two‐stage stochastic programming as well as a heuristic method. We also extend our solution approach to account for piecewise‐linear cost and revenue functions as well as a multiperiod setting. Extensive experimentation indicates that our exact approach rapidly finds optimal solutions with three times as many orders as a state‐of‐the‐art commercial solver. In addition, our heuristic approach provides average gaps of less than 1% for the largest problems that can be solved exactly. Observing that the gaps decrease as problem size grows, we expect the heuristic approach to work well for large problem instances. © 2008 Wiley Periodicals, Inc. Naval Research Logistics 2008     

An approximative algorithm for the fixed charge problem

This paper describes an approximate solution method for solving the fixed charge problem. This heuristic approach is applied to a set of test problems to explore the margin of error. The results indicate that the proposed fixed charge simplex algorithm is capable of finding optimal or near optimal solutions to moderate sized fixed charge problems. In the absence of an exact method, this heuristic should prove useful in solving this fundamental nonlinear programming problem.     

Optimal FCFS allocation rules for periodic‐review assemble‐to‐order systems

In Assemble‐To‐Order (ATO) systems, situations may arise in which customer demand must be backlogged due to a shortage of some components, leaving available stock of other components unused. Such unused component stock is called remnant stock. Remnant stock is a consequence of both component ordering decisions and decisions regarding allocation of components to end‐product demand. In this article, we examine periodic‐review ATO systems under linear holding and backlogging costs with a component installation stock policy and a First‐Come‐First‐Served (FCFS) allocation policy. We show that the FCFS allocation policy decouples the problem of optimal component allocation over time into deterministic period‐by‐period optimal component allocation problems. We denote the optimal allocation of components to end‐product demand as multimatching. We solve the multi‐matching problem by an iterative algorithm. In addition, an approximation scheme for the joint replenishment and allocation optimization problem with both upper and lower bounds is proposed. Numerical experiments for base‐stock component replenishment policies show that under optimal base‐stock policies and optimal allocation, remnant stock holding costs must be taken into account. Finally, joint optimization incorporating optimal FCFS component allocation is valuable because it provides a benchmark against which heuristic methods can be compared. © 2015 Wiley Periodicals, Inc. Naval Research Logistics 62: 158–169, 2015     

A multifacility capacity expansion model with joint expansion set-up costs

This article describes a multifacility capacity expansion model in which the different facility types represent different quality levels. These facility types are used to satisfy a variety of deterministic demands over a finite number of discrete time periods. Applications for the model can be found in cable sizing problems associated with the planning of communication networks. It is assumed that the cost function associated with expanding the capacity of any facility type is concave, and that a joint set-up cost is incurred in any period in which one or more facilities are expanded. The model is formulated as a network flow problem from which properties associated with optimal solutions are derived. Using these properties, we develop a dynamic programming algorithm that finds optimal solutions for problems with a few facilities, and a heuristic algorithm that finds near-optimal solutions for larger problems. Numerical examples for both algorithms are discussed.     

Integrated scheduling of loading and transportation with tractors and semitrailers separated

Motivated by some practical applications, we study a new integrated loading and transportation scheduling problem. Given a set of jobs, a single crane is available to load jobs, one by one, onto semitrailers with a given capacity. Loaded semitrailers are assigned to tractors for transportation tasks. Subject to limited resources (crane, semitrailers, and tractors), the problem is to determine (1) an assignment of jobs to semitrailers for loading tasks, (2) a sequence for the crane to load jobs onto semitrailers, (3) an assignment of loaded semitrailers to tractors for transportation tasks, and (4) a transportation schedule of assigned tractors such that the completion time of the last transportation task is minimized. We first formulate the problem as a mixed integer linear programming model (MILPM) and prove that the problem is strongly NP‐hard. Then, optimality properties are provided which are useful in establishing an improved MILPM and designing solution algorithms. We develop a constructive heuristic, two LP‐based heuristics, and a recovering beam search heuristic to solve this problem. An improved procedure for solutions by heuristics is also presented. Furthermore, two branch‐and‐bound (B&B) algorithms with two different lower bounds are developed to solve the problem to optimality. Finally, computational experiments using both real data and randomly generated data demonstrate that our heuristics are highly efficient and effective. In terms of computational time and the number of instances solved to optimality in a time limit, the B&B algorithms are better than solving the MILPM. © 2015 Wiley Periodicals, Inc. Naval Research Logistics 62: 416–433, 2015     

Interdiction models for delaying adversarial attacks against critical information technology infrastructure

Information technology (IT) infrastructure relies on a globalized supply chain that is vulnerable to numerous risks from adversarial attacks. It is important to protect IT infrastructure from these dynamic, persistent risks by delaying adversarial exploits. In this paper, we propose max‐min interdiction models for critical infrastructure protection that prioritizes cost‐effective security mitigations to maximally delay adversarial attacks. We consider attacks originating from multiple adversaries, each of which aims to find a “critical path” through the attack surface to complete the corresponding attack as soon as possible. Decision‐makers can deploy mitigations to delay attack exploits, however, mitigation effectiveness is sometimes uncertain. We propose a stochastic model variant to address this uncertainty by incorporating random delay times. The proposed models can be reformulated as a nested max‐max problem using dualization. We propose a Lagrangian heuristic approach that decomposes the max‐max problem into a number of smaller subproblems, and updates upper and lower bounds to the original problem via subgradient optimization. We evaluate the perfect information solution value as an alternative method for updating the upper bound. Computational results demonstrate that the Lagrangian heuristic identifies near‐optimal solutions efficiently, which outperforms a general purpose mixed‐integer programming solver on medium and large instances.