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     

Non‐greedy heuristics and augmented neural networks for the open‐shop scheduling problem

In this paper we propose some non‐greedy heuristics and develop an Augmented‐Neural‐Network (AugNN) formulation for solving the classical open‐shop scheduling problem (OSSP). AugNN is a neural network based meta‐heuristic approach that allows integration of domain‐specific knowledge. The OSSP is framed as a neural network with multiple layers of jobs and machines. Input, output and activation functions are designed to enforce the problem constraints and embed known heuristics to generate a good feasible solution fast. Suitable learning strategies are applied to obtain better neighborhood solutions iteratively. The new heuristics and the AugNN formulation are tested on several benchmark problem instances in the literature and on some new problem instances generated in this study. The results are very competitive with other meta‐heuristic approaches, both in terms of solution quality and computational times. © 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     

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     

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     

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     

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     

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     

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     

Machine scheduling with pickup and delivery

The coordination of production, supply, and distribution is an important issue in logistics and operations management. This paper develops and analyzes a single‐machine scheduling model that incorporates the scheduling of jobs and the pickup and delivery arrangements of the materials and finished jobs. In this model, there is a capacitated pickup and delivery vehicle that travels between the machine and the storage area, and the objective is to minimize the makespan of the schedule. The problem is strongly NP‐hard in general but is solvable in polynomial time when the job processing sequence is predetermined. An efficient heuristic is developed for the general problem. The effectiveness of the heuristic is studied both analytically and computationally. © 2005 Wiley Periodicals, Inc. Naval Research Logistics, 2005.     

Scheduling and lot streaming in two‐machine open shops with no‐wait in process

We study the problem of minimizing the makespan in no‐wait two‐machine open shops producing multiple products using lot streaming. In no‐wait open shop scheduling, sublot sizes are necessarily consistent; i.e., they remain the same over all machines. This intractable problem requires finding sublot sizes, a product sequence for each machine, and a machine sequence for each product. We develop a dynamic programming algorithm to generate all the dominant schedule profiles for each product that are required to formulate the open shop problem as a generalized traveling salesman problem. This problem is equivalent to a classical traveling salesman problem with a pseudopolynomial number of cities. We develop and test a computationally efficient heuristic for the open shop problem. Our results indicate that solutions can quickly be found for two machine open shops with up to 50 products. © 2005 Wiley Periodicals, Inc. Naval Research Logistics, 2005     

Coordinated scheduling of customer orders for quick response

The scheduling problem addressed in this paper concerns a manufacturer who produces a variety of product types and operates in a make‐to‐order environment. Each customer order consists of known quantities of the different product types, and must be delivered as a single shipment. Periodically the manufacturer schedules the accumulated and unscheduled customer orders. Instances of this problem occur across industries in manufacturing as well as in service environments. In this paper we show that the problem of minimizing the weighted sum of customer order delivery times is unary NP‐hard. We characterize the optimal schedule, solve several special cases of the problem, derive tight lower bounds, and propose several heuristic solutions. We report the results of a set of computational experiments to evaluate the lower bounding procedures and the heuristics, and to determine optimal solutions. © 2005 Wiley Periodicals, Inc. Naval Research Logistics, 2005.     

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.     

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 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     

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     

Robust capacity planning in semiconductor manufacturing

We present a stochastic programming approach to capacity planning under demand uncertainty in semiconductor manufacturing. Given multiple demand scenarios together with associated probabilities, our aim is to identify a set of tools that is a good compromise for all these scenarios. More precisely, we formulate a mixed‐integer program in which expected value of the unmet demand is minimized subject to capacity and budget constraints. This is a difficult two‐stage stochastic mixed‐integer program which cannot be solved to optimality in a reasonable amount of time. We instead propose a heuristic that can produce near‐optimal solutions. Our heuristic strengthens the linear programming relaxation of the formulation with cutting planes and performs limited enumeration. Analyses of the results in some real‐life situations are also presented. © 2005 Wiley Periodicals, Inc. Naval Research Logistics, 2005.     

A dynamic allocation heuristic for centralized safety stock

An inventory system that consists of a depot (central warehouse) and retailers (regional warehouses) is considered. The system is replenished regularly on a fixed cycle by an outside supplier. Most of the stock is direct shipped to the retailer locations but some stock is sent to the central warehouse. At the beginning of any one of the periods during the cycle, the central stock can then be completely allocated out to the retailers. In this paper we propose a heuristic method to dynamically (as retailer inventory levels change with time) determine the appropriate period in which to do the allocation. As the optimal method is not tractable, the heuristic's performance is compared against two other approaches. One presets the allocation period, while the other provides a lower bound on the expected shortages of the optimal solution, obtained by assuming that we know ahead of time all of the demands, period by period, in the cycle. The results from extensive simulation experiments show that the dynamic heuristic significantly outperforms the “preset” approach and its performance is reasonably close to the lower bound. Moreover, the logic of the heuristic is appealing and the calculations, associated with using it, are easy to carry out. Sensitivities to various system parameters (such as the safety factor, coefficient of variation of demand, number of regional warehouses, external lead time, and the cycle length) are presented. © 2005 Wiley Periodicals, Inc. Naval Research Logistics, 2005.     

Models and algorithms for shuffling problems in steel plants

In this article, we study item shuffling (IS) problems arising in the logistics system of steel production. An IS problem here is to optimize shuffling operations needed in retrieving a sequence of steel items from a warehouse served by a crane. There are two types of such problems, plate shuffling problems (PSP) and coil shuffling problems (CSP), considering the item shapes. The PSP is modeled as a container storage location assignment problem. For CSP, a novel linear integer programming model is formulated considering the practical stacking and shuffling features. Several valid inequalities are constructed to accelerate the solving of the models. Some properties of optimal solutions of PSP and CSP are also derived. Because of the strong NP‐hardness of the problems, we consider some special cases of them and propose polynomial time algorithms to obtain optimal solutions for these cases. A greedy heuristic is proposed to solve the general problems and its worst‐case performances on both PSP and CSP are analyzed. A tabu search (TS) method with a tabu list of variable length is proposed to further improve the heuristic solutions. Without considering the crane traveling distance, we then construct a rolling variable horizon heuristic for the problems. Numerical experiments show that the proposed heuristic algorithms and the TS method are effective. © 2012 Wiley Periodicals, Inc. Naval Research Logistics, 2012     

On finding spanning eulerian subgraphs

In this article, we examine the problem of producing a spanning Eulerian subgraph in an undirected graph. After the ?-completeness of the general problem is established, we present polynomial-time algorithms for both the maximization and minimization versions where instances are defined on a restricted class of graphs referred to as series-parallel. Some novelties in the minimization case are discussed, as are heuristic ideas.