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     

Dual‐ascent and primal heuristics for production‐assembly‐distribution system design

This article proposes two dual‐ascent algorithms and uses each in combination with a primal drop heuristic embedded within a branch and bound framework to solve the uncapacitated production assembly distribution system (i.e., supply chain) design problem, which is formulated as a mixed integer program. Computational results indicate that one approach, which combines primal drop and dual‐ascent heuristics, can solve instances within reasonable time and prescribes solutions with gaps between the primal and dual solution values that are less than 0.15%, an efficacy suiting it for actual large‐scale applications. © 2012 Wiley Periodicals, Inc. Naval Research Logistics, 2013     

A concave‐cost production planning problem with remanufacturing options

We focus on the concave‐cost version of a production planning problem where a manufacturer can meet demand by either producing new items or by remanufacturing used items. Unprocessed used items are disposed. We show the NP‐hardness of the problem even when all the costs are stationary. Utilizing the special structure of the extreme‐point optimal solutions for the minimum concave‐cost problem with a network flow type feasible region, we develop a polynomial‐time heuristic for the problem. Our computational study indicates that the heuristic is a very efficient way to solve the problem as far as solution speed and quality are concerned. © 2005 Wiley Periodicals, Inc. Naval Research Logistics, 2005     

The continuous‐time single‐sourcing problem with capacity expansion opportunities

This paper develops a new model for allocating demand from retailers (or customers) to a set of production/storage facilities. A producer manufactures a product in multiple production facilities, and faces demand from a set of retailers. The objective is to decide which of the production facilities should satisfy each retailer's demand, in order minimize total production, inventory holding, and assignment costs (where the latter may include, for instance, variable production costs and transportation costs). Demand occurs continuously in time at a deterministic rate at each retailer, while each production facility faces fixed‐charge production costs and linear holding costs. We first consider an uncapacitated model, which we generalize to allow for production or storage capacities. We then explore situations with capacity expansion opportunities. Our solution approach employs a column generation procedure, as well as greedy and local improvement heuristic approaches. A broad class of randomly generated test problems demonstrates that these heuristics find high quality solutions for this large‐scale cross‐facility planning problem using a modest amount of computation time. © 2005 Wiley Periodicals, Inc. Naval Research Logistics, 2005.     

A branch‐and‐price algorithm for a 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, but it can be transformed into a linear integer programming model. We present a branch‐and‐price algorithm for the problem employing the disaggregated formulation, which has exponentially many columns denoting the feasible allocations of weapon systems to each target. A greedy‐style heuristic is used to get some initial columns to start the column generation. A branching strategy compatible with the pricing problem is also proposed. Computational results using randomly generated data show this approach is promising for the targeting problem. © 2007 Wiley Periodicals, Inc. Naval Research Logistics, 2007     

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     

Capacitated lot‐sizing and scheduling with parallel machines,back‐orders,and setup carry‐over

We address the capacitated lot‐sizing and scheduling problem with setup times, setup carry‐over, back‐orders, and parallel machines as it appears in a semiconductor assembly facility. The problem can be formulated as an extension of the capacitated lot‐sizing problem with linked lot‐sizes (CLSPL). We present a mixed integer (MIP) formulation of the problem and a new solution procedure. The solution procedure is based on a novel “aggregate model,” which uses integer instead of binary variables. The model is embedded in a period‐by‐period heuristic and is solved to optimality or near‐optimality in each iteration using standard procedures (CPLEX). A subsequent scheduling routine loads and sequences the products on the parallel machines. Six variants of the heuristic are presented and tested in an extensive computational study. © 2009 Wiley Periodicals, Inc. Naval Research Logistics 2009     

An exact network flow formulation for cell‐based evacuation in urban areas

In the literature two common macroscopic evacuation planning approaches exist: The dynamic network flow approach and the Cell–Transmission–Based approach. Both approaches have advantages and disadvantages. Many efficient solution approaches for the dynamic network flow approach exist so that realistic problem instances can be considered. However, the consideration of (more) realistic aspects (eg, density dependent travel times) results in non‐linear model formulations. The Cell‐Transmission‐Based approach on the other hand considers realistic traffic phenomena like shock waves and traffic congestion, but this approach leads to long computational times for realistic problem instances. In this article, we combine the advantages of both approaches: We consider a Cell‐Transmission‐Based Evacuation Planning Model (CTEPM) and present a network flow formulation that is equivalent to the cell‐based model. Thus, the computational costs of the CTEPM are enormously reduced due to the reformulation and the detailed representation of the traffic flow dynamics is maintained. We investigate the impacts of various evacuation scenario parameters on the evacuation performance and on the computational times in a computational study including 90 realistic instances.     

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     

A m‐parallel crane scheduling problem with a non‐crossing constraint

In this paper, we study a m‐parallel machine scheduling problem with a non‐crossing constraint motivated by crane scheduling in ports. We decompose the problem to allow time allocations to be determined once crane assignments are known and construct a backtracking search scheme that manipulates domain reduction and pruning strategies. Simple approximation heuristics are developed, one of which guarantees solutions to be at most two times the optimum. For large‐scale problems, a simulated annealing heuristic that uses random neighborhood generation is provided. Computational experiments are conducted to test the algorithms. © 2006 Wiley Periodicals, Inc. Naval Research Logistics, 2007.     

Short‐term capacity allocation problem with tool and setup constraints

We consider a short‐term capacity allocation problem with tool and setup constraints that arises in the context of operational planning in a semiconductor wafer fabrication facility. The problem is that of allocating the available capacity of parallel nonidentical machines to available work‐in‐process (WIP) inventory of operations. Each machine can process a subset of the operations and a tool setup is required on a machine to change processing from one operation to another. Both the number of tools available for an operation and the number of setups that can be performed on a machine during a specified time horizon are limited. We formulate this problem as a degree‐constrained network flow problem on a bipartite graph, show that the problem is NP‐hard, and propose constant factor approximation algorithms. We also develop constructive heuristics and a greedy randomized adaptive search procedure for the problem. Our computational experiments demonstrate that our solution procedures solve the problem efficiently, rendering the use of our algorithms in real environment feasible. © 2005 Wiley Periodicals, Inc. Naval Research Logistics, 2005     

Dynamic service rate control for a single‐server queue with Markov‐modulated arrivals

We consider the problem of service rate control of a single‐server queueing system with a finite‐state Markov‐modulated Poisson arrival process. We show that the optimal service rate is nondecreasing in the number of customers in the system; higher congestion levels warrant higher service rates. On the contrary, however, we show that the optimal service rate is not necessarily monotone in the current arrival rate. If the modulating process satisfies a stochastic monotonicity property, the monotonicity is recovered. We examine several heuristics and show where heuristics are reasonable substitutes for the optimal control. None of the heuristics perform well in all the regimes and the fluctuation rate of the modulating process plays an important role in deciding the right heuristic. Second, we discuss when the Markov‐modulated Poisson process with service rate control can act as a heuristic itself to approximate the control of a system with a periodic nonhomogeneous Poisson arrival process. Not only is the current model of interest in the control of Internet or mobile networks with bursty traffic, but it is also useful in providing a tractable alternative for the control of service centers with nonstationary arrival rates. © 2013 Wiley Periodicals, Inc. Naval Research Logistics 60: 661–677, 2013     

Strategic capacity decision‐making in a stochastic manufacturing environment using real‐time approximate dynamic programming

In this study, we illustrate a real‐time approximate dynamic programming (RTADP) method for solving multistage capacity decision problems in a stochastic manufacturing environment, by using an exemplary three‐stage manufacturing system with recycle. The system is a moderate size queuing network, which experiences stochastic variations in demand and product yield. The dynamic capacity decision problem is formulated as a Markov decision process (MDP). The proposed RTADP method starts with a set of heuristics and learns a superior quality solution by interacting with the stochastic system via simulation. The curse‐of‐dimensionality associated with DP methods is alleviated by the adoption of several notions including “evolving set of relevant states,” for which the value function table is built and updated, “adaptive action set” for keeping track of attractive action candidates, and “nonparametric k nearest neighbor averager” for value function approximation. The performance of the learned solution is evaluated against (1) an “ideal” solution derived using a mixed integer programming (MIP) formulation, which assumes full knowledge of future realized values of the stochastic variables (2) a myopic heuristic solution, and (3) a sample path based rolling horizon MIP solution. The policy learned through the RTADP method turned out to be superior to polices of 2 and 3. © 2010 Wiley Periodicals, Inc. Naval Research Logistics 2010     

An asymptotically optimal greedy heuristic for the multiperiod single‐sourcing problem: The cyclic case

The dynamics of the environment in which supply chains evolve requires that companies frequently redesign their logistics distribution networks. In this paper we address a multiperiod single‐sourcing problem that can be used as a strategic tool for evaluating the costs of logistics network designs in a dynamic environment. The distribution networks that we consider consist of a set of production and storage facilities, and a set of customers who do not hold inventories. The facilities face production capacities, and each customer's demand needs to be delivered by a single facility in each period. We deal with the assignment of customers to facilities, as well as the location, timing, and size of inventories. In addition, to mitigate start and end‐of‐study effects, we view the planning period as a typical future one, which will repeat itself. This leads to a cyclic model, in which starting and ending inventories are equal. Based on an assignment formulation of the problem, we propose a greedy heuristic, and prove that this greedy heuristic is asymptotically feasible and optimal in a probabilistic sense. We illustrate the behavior of the greedy heuristic, as well as some improvements where the greedy heuristic is used as the starting point of a local interchange procedure, on a set of randomly generated test problems. © 2003 Wiley Periodicals, Inc. Naval Research Logistics 50: 412–437, 2003     

A branch‐and‐price algorithm for parallel machine scheduling with time windows and job priorities

This paper presents a branch‐and‐price algorithm for scheduling n jobs on m nonhomogeneous parallel machines with multiple time windows. An additional feature of the problem is that each job falls into one of ρ priority classes and may require two operations. The objective is to maximize the weighted number of jobs scheduled, where a job in a higher priority class has “infinitely” more weight or value than a job in a lower priority class. The methodology makes use of a greedy randomized adaptive search procedure (GRASP) to find feasible solutions during implicit enumeration and a two‐cycle elimination heuristic when solving the pricing subproblems. Extensive computational results are presented based on data from an application involving the use of communications relay satellites. Many 100‐job instances that were believed to be beyond the capability of exact methods, were solved within minutes. © 2005 Wiley Periodicals, Inc. Naval Research Logistics, 2006     

Manpower allocation with time windows and job‐teaming constraints

In this work, we study manpower allocation with time windows and job‐teaming constraints. A set of jobs at dispersed locations requires teams of different types of workers where each job must be carried out in a preestablished time window and requires a specific length of time for completion. A job is satisfied if the required composite team can be brought together at the job's location for the required duration within the job's time window. The objective is to minimize a weighted sum of the total number of workers and the total traveling time. We show that construction heuristics used with simulated annealing is a good approach to solving this NP‐hard problem. In experiments, this approach is compared with solutions found using CPLEX and with lower bounds obtained from a network flow model. © 2005 Wiley Periodicals, Inc. Naval Research Logistics, 2005.     

Balancing perfectly periodic service schedules: An application from recycling and waste management

A national recycling and waste management company provides periodic services to its customers from over 160 service centers. The services are performed periodically in units of weeks over a planning horizon. The number of truck‐hours allocated to this effort is determined by the maximum weekly workload during the planning horizon. Therefore, minimizing the maximum weekly workload results in minimum operating expenses. The perfectly periodic service scheduling (PPSS) problem is defined based on the practices of the company. It is shown that the PPSS problem is strongly NP‐hard. Attempts to solve large instances by using an integer programming formulation are unsuccessful. Therefore, greedy BestFit heuristics with three different sorting schemes are designed and tested for six real‐world PPSS instances and 80 randomly generated data files. The heuristics provide effective solutions that are within 2% of optimality on average. When the best found BestFit schedules are compared with the existing schedules, it is shown that operational costs are reduced by 18% on average. © 2012 Wiley Periodicals, Inc. Naval Research Logistics 59: 160–171, 2012     

On the asymptotic optimality of algorithms for the flow shop problem with release dates

We consider the nonpermutation flow shop problem with release dates, with the objective of minimizing the sum of the weighted completion times on the final machine. Since the problem is NP‐hard, we focus on the analysis of the performance of several approximation algorithms, all of which are related to the classical Weighted Shortest Processing Time Among Available Jobs heuristic. In particular, we perform a probabilistic analysis and prove that two online heuristics and one offline heuristic are asymptotically optimal. © 2005 Wiley Periodicals, Inc. Naval Research Logistics, 2005.     

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     

Optimal job splitting on a multi‐slot machine with applications in the printing industry

In this article, we define a scheduling/packing problem called the Job Splitting Problem, motivated by the practices in the printing industry. There are n types of items to be produced on an m‐slot machine. A particular assignment of the types to the slots is called a “run” configuration and requires a setup cost. Once a run begins, the production continues according to that configuration and the “length” of the run represents the quantity produced in each slot during that run. For each unit of production in excess of demand, there is a waste cost. Our goal is to construct a production plan, i.e., a set of runs, such that the total setup and waste cost is minimized. We show that the problem is strongly NP‐hard and propose two integer programming formulations, several preprocessing steps, and two heuristics. We also provide a worst‐case bound for one of the heuristics. Extensive tests on real‐world and randomly generated instances show that the heuristics are both fast and effective, finding near‐optimal solutions. © 2010 Wiley Periodicals, Inc. Naval Research Logistics, 2010