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     

Heuristic procedure for a multiproduct dynamic lot-sizing problem with coordinated replenishments

In this article we develop a heuristic procedure for a multiproduct dynamic lot-sizing problem. In this problem a joint setup cost is incurred when at least one product is ordered in a period. In addition to the joint setup cost a separate setup cost for each product ordered is also incurred. The objective is to determine the product lot sizes, over a finite planning horizon, that will minimize the total relevant cost such that the demand in each period for each product is satisfied without backlogging. In this article we present an effective heuristic procedure for this problem. Computational results for the heuristic procedure are also reported. Our computational experience leads us to conclude that the heuristic procedure may be of considerable value as a decision-making aid to production planners in a real-world setting. © 1994 John Wiley & Sons, Inc.     

Resource allocation with lumpy demand: To speed or not to speed?

In the classical EPQ model with continuous and constant demand, holding and setup costs are minimized when the production rate is no larger than the demand rate. However, the situation may change when demand is lumpy. We consider a firm that produces multiple products, each having a unique lumpy demand pattern. The decision involves determining both the lot size for each product and the allocation of resources for production rate improvements among the products. We find that each product's optimal production policy will take on only one of two forms: either continuous production or lot‐for‐lot production. The problem is then formulated as a nonlinear nonsmooth knapsack problem among products determined to be candidates for resource allocation. A heuristic procedure is developed to determine allocation amounts. The procedure decomposes the problem into a mixed integer program and a nonlinear convex resource allocation problem. Numerical tests suggest that the heuristic performs very well on average compared to the optimal solution. Both the model and the heuristic procedure can be extended to allow the company to simultaneously alter both the production rates and the incoming demand lot sizes through quantity discounts. Extensions can also be made to address the case where a single investment increases the production rate of multiple products. © 2004 Wiley Periodicals, Inc. Naval Research Logistics, 2004.     

On locally optimal independent sets and vertex covers

In this paper, we introduce a new notion of local optimality and demonstrate its application to the problem of finding optimal independent sets and vertex covers in k-claw free graphs. The maximum independent set problem in k-claw free graphs has interesting applications in the design of electronic testing fixtures for printed circuit boards [13]. For this problem, our concept of local optimality enabled us to devise an efficient heuristic algorithm which outperforms the currently best approximation algorithm by nearly a factor of two in terms of worst case bound. We believe that the idea of local optimality suggested in this paper can also be applied to other combinatorial problems such as the clique problem, the dominating set problem and the graph coloring problem. © 1996 John Wiley & Sons, Inc.     

Lot sizing when yields increase during the production run

We investigate the problem of determining lot sizes for multiple items when the expected percentage of acceptable output increases with the duration of the production run, usually due to adjustments made during the early part of the production run. Such problems arise in metal stamping, textile finishing processes, and a variety of other industries. The goal is to minimize the total cost of production, inventory holding costs, and setup costs (where applicable). We develop a heuristic procedure based on a Lagrangian relaxation that differs from relaxations used in earlier studies. We use various properties of the objective function to guide the adjustment of the initial solution from the relaxation toward feasibility. Computational results indicate that, on the average, the heuristic produces solutions within 4.9% of the lower bound obtained from the Lagrangian relaxation. © 1996 John Wiley & Sons, Inc.     

Heuristic procedures for scheduling job families with setups and due dates

This paper examines heuristic solution procedures for scheduling jobs on a single machine to minimize the maximum lateness in the presence of setup times between different job families. It reviews the state of knowledge about the solution of this problem, which is known to be difficult to solve in general, and examines natural solution approaches derived from some of the underlying theory. The emphasis is on the design and computational evaluation of new heuristic procedures. © 1999 John Wiley & Sons, Inc. Naval Research Logistics 46: 978–991, 1999     

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     

Short-term retrenchment planning in hierarchical manpower systems

We address the issue of short-term retrenchment planning required of organizations that are phasing down their manpower levels at rates faster than are allowed by natural attrition. Specifically, the problem we study is as follows: given the initial and target grade populations in a hierarchical manpower system at the end of a finite time horizon and the per-period rate of natural attrition for each grade, find a stationary manpower policy that minimizes the maximum per-period rate of retrenchment across all the grades over all stationary policies that yield the target grade populations at the end of the horizon. Because the problem is a nonconvex, nonseparable, nonlinear program, we develop a heuristic in which the promotion proportions of all the grades are successively fixed, starting from the lowest grade. We prove optimality of the heuristic policy in three nontrivial situations. In a computational experiment, in 135 out of 150 randomly generated instances (i.e., in 90% of the cases), the heuristic yielded a solution that was as good or better than that yielded by a benchmark computer program that solves the present problem as a nonlinear program. Further, the average computational time under the heuristic was an order of magnitude less than that under the program. © 1995 John Wiley & Sons, Inc.     

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 partial characterization of the optimal ordering/rationing policy for a periodic review system with two demand classes and backordering

We consider a finite horizon periodic review, single product inventory system with a fixed setup cost and two stochastic demand classes that differ in their backordering costs. In each period, one must decide whether and how much to order, and how much demand of the lower class should be satisfied. We show that the optimal ordering policy can be characterized as a state dependent (s,S) policy, and the rationing structure is partially obtained based on the subconvexity of the cost function. We then propose a simple heuristic rationing policy, which is easy to implement and close to optimal for intensive numerical examples. We further study the case when the first demand class is deterministic and must be satisfied immediately. We show the optimality of the state dependent (s,S) ordering policy, and obtain additional rationing structural properties. Based on these properties, the optimal ordering and rationing policy for any state can be generated by finding the optimal policy of only a finite set of states, and for each state in this set, the optimal policy is obtained simply by choosing a policy from at most two alternatives. An efficient algorithm is then proposed. © 2010 Wiley Periodicals, Inc. Naval Research Logistics, 2010     

Exact algorithms for scheduling multiple families of jobs on parallel machines

In many practical manufacturing environments, jobs to be processed can be divided into different families such that a setup is required whenever there is a switch from processing a job of one family to another job of a different family. The time for setup could be sequence independent or sequence dependent. We consider two particular scheduling problems relevant to such situations. In both problems, we are given a set of jobs to be processed on a set of identical parallel machines. The objective of the first problem is to minimize total weighted completion time of jobs, and that of the second problem is to minimize weighted number of tardy jobs. We propose column generation based branch and bound exact solution algorithms for the problems. Computational experiments show that the algorithms are capable of solving both problems of medium size to optimality within reasonable computational time. © 2003 Wiley Periodicals, Inc. Naval Research Logistics 50: 823–840, 2003.     

A branch-and-bound algorithm to minimize total flow time with unequal release dates

This article examines the single-machine scheduling problem to minimize total flow time with unequal release dates. This problem has been proven to be NP-hard. We present a necessary and sufficient condition for local optimality which can also be considered as a priority rule. On the basis of this condition, we then define a class of schedules which contains all optimal solutions. We present some efficient heuristic algorithms using the previous condition to build a schedule belonging to this subset. We also prove some new dominance theorems, discuss the results found in the literature for this problem, and propose a branch-and-bound algorithm in which the heuristics are used to provide good upper bounds. We compare this new algorithm with existing algorithms found in the literature. Computational results on problems with up to 100 jobs indicate that the proposed branch-and-bound algorithm is superior to previously published algorithms. © 1992 John Wiley & Sons. Inc.     

A single-machine replacement model with learning

The replacement or upgrade of productive resources over time is an important decision for a manufacturing organization. The type of technology used in the productive resources determines how effectively the manufacturing operations can support the product and marketing strategy of the organization. Increasing operating costs (cost of maintenance, labor, and depreciation) over time force manufacturing organizations to periodically consider replacement or upgrade of their existing productive resources. We assume that there is a setup cost associated with the replacement of a machine, and that the setup cost is a nonincreasing function of the number of replacements made so far due to learning in setups. The operating cost of a newer machine is assumed to be lower than the operating cost of an older machine in any given period, except perhaps in the first period of operation of the new machine when the cost could be unusually high due to higher initial depreciation. A forward dynamic programming algorithm is developed which can be used to solve finite-horizon problems. We develop procedures to find decision and forecast horizons such that choices made during the decision horizon based only on information over the forecast horizon are also optimal for any longer horizon problem. Thus, we are able to obtain optimal results for what is effectively an infinite-horizon problem while only requiring data over a finite period of time. We present a numerical example to illustrate the decision/forecast horizon procedure, as well as a study of the effects of considering learning in making a series of machine replacement decisions. © 1993 John Wiley & Sons. Inc.     

Algorithm to solve a chance‐constrained network capacity design problem with stochastic demands and finite support

We consider the problem of determining the capacity to assign to each arc in a given network, subject to uncertainty in the supply and/or demand of each node. This design problem underlies many real‐world applications, such as the design of power transmission and telecommunications networks. We first consider the case where a set of supply/demand scenarios are provided, and we must determine the minimum‐cost set of arc capacities such that a feasible flow exists for each scenario. We briefly review existing theoretical approaches to solving this problem and explore implementation strategies to reduce run times. With this as a foundation, our primary focus is on a chance‐constrained version of the problem in which α% of the scenarios must be feasible under the chosen capacity, where α is a user‐defined parameter and the specific scenarios to be satisfied are not predetermined. We describe an algorithm which utilizes a separation routine for identifying violated cut‐sets which can solve the problem to optimality, and we present computational results. We also present a novel greedy algorithm, our primary contribution, which can be used to solve for a high quality heuristic solution. We present computational analysis to evaluate the performance of our proposed approaches. © 2016 Wiley Periodicals, Inc. Naval Research Logistics 63: 236–246, 2016     

A parametric-based heuristic program for the quadratic assignment problem

In this article we study the quadratic assignment problem by embedding the actual data in a data space which satisfies an extension of the metric triangle property. This leads to simpler computations for the determination of heuristic solutions. Bounds are given for the loss of optimality which such heuristic solutions would involve in any specific instance. © 1993 John Wiley & Sons, Inc.     

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.     

Strategic investment to reduce setup times in the economic lot scheduling problem

This article considers the Economic Lot Scheduling Problem where setup times and costs can be reduced by an initial investment that is amortized over time. The objective is to determine a multiple-item single facility cyclic schedule to minimize the long run average holding and setup costs plus the amortized investment. We develop a lower bound on the long run average inventory carrying and setup costs as a function of the setup times, and show that this lower bound is increasing concave on the setup times when the out-of-pocket setup costs are zero or proportional to the setup times. We then develop a model that may be helpful in deciding the magnitude and the distribution of a one-time investment in reducing the setup times when the investment is amortized over time. Numerical results based on randomly generated problems, and on Bomberger's ten item problem indicate that significant overall savings are possible for highly utilized facilities. Most of the savings are due to a significant reduction in the long run average holding cost. © 1995 John Wiley & Sons, Inc.     

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     

Generation and storage dispatch in electricity networks with generator disruptions

We present methods for optimizing generation and storage decisions in an electricity network with multiple unreliable generators, each colocated with one energy storage unit (e.g., battery), and multiple loads under power flow constraints. Our model chooses the amount of energy produced by each generator and the amount of energy stored in each battery in every time period in order to minimize power generation and storage costs when each generator faces stochastic Markovian supply disruptions. This problem cannot be optimized easily using stochastic programming and/or dynamic programming approaches. Therefore, in this study, we present several heuristic methods to find an approximate optimal solution for this system. Each heuristic involves decomposing the network into several single‐generator, single‐battery, multiload systems and solving them optimally using dynamic programming, then obtaining a solution for the original problem by recombining. We discuss the computational performance of the proposed heuristics as well as insights gained from the models. © 2015 Wiley Periodicals, Inc. Naval Research Logistics 62: 493–511, 2015