An integer decomposition algorithm for solving a two‐stage facility location problem with second‐stage activation costs

We study a stochastic scenario‐based facility location problem arising in situations when facilities must first be located, then activated in a particular scenario before they can be used to satisfy scenario demands. Unlike typical facility location problems, fixed charges arise in the initial location of the facilities, and then in the activation of located facilities. The first‐stage variables in our problem are the traditional binary facility‐location variables, whereas the second‐stage variables involve a mix of binary facility‐activation variables and continuous flow variables. Benders decomposition is not applicable for these problems due to the presence of the second‐stage integer activation variables. Instead, we derive cutting planes tailored to the problem under investigation from recourse solution data. These cutting planes are derived by solving a series of specialized shortest path problems based on a modified residual graph from the recourse solution, and are tighter than the general cuts established by Laporte and Louveaux for two‐stage binary programming problems. We demonstrate the computational efficacy of our approach on a variety of randomly generated test problems. © 2010 Wiley Periodicals, Inc. Naval Research Logistics, 2010     

Makespan minimization in the two‐machine flowshop batch scheduling problem

In this paper we consider a practical scheduling problem commonly arising from batch production in a flexible manufacturing environment. Different part‐types are to be produced in a flexible manufacturing cell organized into a two‐stage production line. The jobs are processed in batches on the first machine, and the completion time of a job is defined as the completion time of the batch containing it. When processing of all jobs in a batch is completed on the first machine, the whole batch of jobs is transferred intact to the second machine. A constant setup time is incurred whenever a batch is formed on any machine. The tradeoff between the setup times and batch processing times gives rise to the batch composition decision. The problem is to find the optimal batch composition and the optimal schedule of the batches so that the makespan is minimized. The problem is shown to be strongly NP‐hard. We identify some special cases by introducing their corresponding solution methods. Heuristic algorithms are also proposed to derive approximate solutions. We conduct computational experiments to study the effectiveness of the proposed heuristics. © 2000 John Wiley & Sons, Inc. Naval Research Logistics 47: 128–144, 2000     

Worst‐case performance of approximation algorithms for tool management problems

Since the introduction of flexible manufacturing systems, researchers have investigated various planning and scheduling problems faced by the users of such systems. Several of these problems are not encountered in more classical production settings, and so‐called tool management problems appear to be among the more fundamental ones of these problems. Most tool management problems are hard to solve, so that numerous approximate solution techniques have been proposed to tackle them. In this paper, we investigate the quality of such algorithms by means of worst‐case analysis. We consider several polynomial‐time approximation algorithms described in the literature, and we show that all these algorithms exhibit rather poor worst‐case behavior. We also study the complexity of solving tool management problems approximately. In this respect, we investigate the interrelationships among tool management problems, as well as their relationships with other well‐known combinatorial problems such as the maximum clique problem or the set covering problem, and we prove several negative results on the approximability of various tool management problems. © 1999 John Wiley & Sons, Inc. Naval Research Logistics 46: 445–462, 1999     

Optimal control of noncollaborative servers in two‐stage tandem queueing systems

We consider two‐stage tandem queueing systems with dedicated servers in each station and a flexible server that is trained to serve both stations. We assume no arrivals, exponential service times, and linear holding costs for jobs present in the system. We study the optimal dynamic assignment of servers to jobs assuming a noncollaborative work discipline with idling and preemptions allowed. For larger holding costs in the first station, we show that (i) nonidling policies are optimal and (ii) if the flexible server is not faster than the dedicated servers, the optimal server allocation strategy has a threshold‐type structure. For all other cases, we provide numerical results that support the optimality of threshold‐type policies. Our numerical experiments also indicate that when the flexible server is faster than the dedicated server of the second station, the optimal policy may have counterintuitive properties, which is not the case when a collaborative service discipline is assumed. © 2014 Wiley Periodicals, Inc. Naval Research Logistics 61: 435–446, 2014     

Case‐based reasoning and improved adaptive search for project scheduling

Most scheduling problems are notoriously intractable, so the majority of algorithms for them are heuristic in nature. Priority rule‐based methods still constitute the most important class of these heuristics. Of these, in turn, parametrized biased random sampling methods have attracted particular interest, due to the fact that they outperform all other priority rule‐based methods known. Yet, even the “best” such algorithms are unable to relate to the full range of instances of a problem: Usually there will exist instances on which other algorithms do better. We maintain that asking for the one best algorithm for a problem may be asking too much. The recently proposed concept of control schemes, which refers to algorithmic schemes allowing to steer parametrized algorithms, opens up ways to refine existing algorithms in this regard and improve their effectiveness considerably. We extend this approach by integrating heuristics and case‐based reasoning (CBR), an approach that has been successfully used in artificial intelligence applications. Using the resource‐constrained project scheduling problem as a vehicle, we describe how to devise such a CBR system, systematically analyzing the effect of several criteria on algorithmic performance. Extensive computational results validate the efficacy of our approach and reveal a performance similar or close to state‐of‐the‐art heuristics. In addition, the analysis undertaken provides new insight into the behaviour of a wide class of scheduling heuristics. © 2000 John Wiley & Sons, Inc. Naval Research Logistics 47: 201–222, 2000     

Response surface analysis of two‐stage stochastic linear programming with recourse

We apply the techniques of response surface methodology (RSM) to approximate the objective function of a two‐stage stochastic linear program with recourse. In particular, the objective function is estimated, in the region of optimality, by a quadratic function of the first‐stage decision variables. The resulting response surface can provide valuable modeling insight, such as directions of minimum and maximum sensitivity to changes in the first‐stage variables. Latin hypercube (LH) sampling is applied to reduce the variance of the recourse function point estimates that are used to construct the response surface. Empirical results show the value of the LH method by comparing it with strategies based on independent random numbers, common random numbers, and the Schruben‐Margolin assignment rule. In addition, variance reduction with LH sampling can be guaranteed for an important class of two‐stage problems which includes the classical capacity expansion model. © 1999 John Wiley & Sons, Inc. Naval Research Logistics 46: 753–776, 1999     

Subspace dynamic‐simplex linear interpolation search for mixed‐integer black‐box optimization problems

Design and management of complex systems with both integer and continuous decision variables can be guided using mixed‐integer optimization models and analysis. We propose a new mixed‐integer black‐box optimization (MIBO) method, subspace dynamic‐simplex linear interpolation search (SD‐SLIS), for decision making problems in which system performance can only be evaluated with a computer black‐box model. Through a sequence of gradient‐type local searches in subspaces of solution space, SD‐SLIS is particularly efficient for such MIBO problems with scaling issues. We discuss the convergence conditions and properties of SD‐SLIS algorithms for a class of MIBO problems. Under mild conditions, SD‐SLIS is proved to converge to a stationary solution asymptotically. We apply SD‐SLIS to six example problems including two MIBO problems associated with petroleum field development projects. The algorithm performance of SD‐SLIS is compared with that of a state‐of‐the‐art direct‐search method, NOMAD, and that of a full space simplex interpolation search, Full‐SLIS. The numerical results suggest that SD‐SLIS solves the example problems efficiently and outperforms the compared methods for most of the example cases. © 2017 Wiley Periodicals, Inc. Naval Research Logistics 64: 305–322, 2017     

A three‐stage procurement optimization problem under uncertainty

This article examines a problem faced by a firm procuring a material input or good from a set of suppliers. The cost to procure the material from any given supplier is concave in the amount ordered from the supplier, up to a supplier‐specific capacity limit. This NP‐hard problem is further complicated by the observation that capacities are often uncertain in practice, due for instance to production shortages at the suppliers, or competition from other firms. We accommodate this uncertainty in a worst‐case (robust) fashion by modeling an adversarial entity (which we call the “follower”) with a limited procurement budget. The follower reduces supplier capacity to maximize the minimum cost required for our firm to procure its required goods. To guard against uncertainty, the firm can “protect” any supplier at a cost (e.g., by signing a contract with the supplier that guarantees supply availability, or investing in machine upgrades that guarantee the supplier's ability to produce goods at a desired level), ensuring that the anticipated capacity of that supplier will indeed be available. The problem we consider is thus a three‐stage game in which the firm first chooses which suppliers' capacities to protect, the follower acts next to reduce capacity from unprotected suppliers, and the firm then satisfies its demand using the remaining capacity. We formulate a three‐stage mixed‐integer program that is well‐suited to decomposition techniques and develop an effective cutting‐plane algorithm for its solution. The corresponding algorithmic approach solves a sequence of scaled and relaxed problem instances, which enables solving problems having much larger data values when compared to standard techniques. © 2013 Wiley Periodicals, Inc. Naval Research Logistics, 2013     

Optimal shift scheduling: A branch‐and‐price approach

We present a branch‐and‐price technique for optimal staff scheduling with multiple rest breaks, meal break, and break windows. We devise and implement specialized branching rules suitable for solving the set covering type formulation implicitly, using column generation. Our methodology is more widely applicable and computationally superior to the alternative methods in the literature. We tested our methodology on 365 test problems involving between 1728 and 86400 shift variations, and 20 demand patterns. In a direct comparison with an alternative method, our approach yields significant improvements both in cpu time and in the number of problem instances solved to optimality. The improvements were particularly marked for problems involving larger numbers of feasible shifts. © 2000 John Wiley & Sons, Inc. Naval Research Logistics 47: 185–200, 2000     

Scheduling and due‐date quotation in a make‐to‐order supply chain

We consider a manufacturer, served by a single supplier, who has to quote due dates to arriving customers in a make‐to‐order production environment. The manufacturer is penalized for long lead times and for missing due dates. To meet due dates, the manufacturer has to obtain components from a supplier. We model this manufacturer and supplier as a two‐machine flow shop, consider several variations of this problem, and design effective due‐date quotation and scheduling algorithms for centralized and decentralized versions of the model. We perform extensive computational testing to assess the effectiveness of our algorithms and to compare the centralized and decentralized models to quantify the value of centralized control in a make‐to‐order supply chain. Since complete information exchange and centralized control is not always practical or cost‐effective, we explore the value of partial information exchange for this system. © 2008 Wiley Periodicals, Inc. Naval Research Logistics, 2008     

Analysis of decentralized multi‐product pull systems with lost sales

We study a pull‐type, flexible, multi‐product, and multi‐stage production/inventory system with decentralized two‐card kanban control policies. Each stage involves a processor and two buffers with finite target levels. Production stages, arranged in series, can process several product types one at a time. Transportation of semi‐finished parts from one stage to another is performed in fixed lot sizes. The exact analysis is mathematically intractable even for smaller systems. We present a robust approximation algorithm to model two‐card kanban systems with batch transfers under arbitrary complexity. The algorithm uses phase‐type modeling to find effective processing times and busy period analysis to identify delays among product types in resource contention. Our algorithm reduces the effort required for estimating performance measures by a considerable margin and resolves the state–space explosion problem of analytical approaches. Using this analytical tool, we present new findings for a better understanding of some tactical and operational issues. We show that flow of material in small procurement sizes smoothes flow of information within the system, but also necessitates more frequent shipments between stages, raising the risk of late delivery. Balancing the risk of information delays vis‐à‐vis shipment delays is critical for the success of two‐card kanban systems. Although product variety causes time wasted in setup operations, it also facilitates relatively short production cycles enabling processors to switch from one product type to another more rapidly. The latter point is crucial especially in high‐demand environments. Increasing production line size prevents quick response to customer demand, but it may improve system performance if the vendor lead‐time is long or subject to high variation. Finally, variability in transportation and processing times causes the most damage if it arises at stages closer to the customer. © 2007 Wiley Periodicals, Inc. Naval Research Logistics, 2007     

Two‐stage component test plans for testing the reliability of a series system

A system reliability is often evaluated by individual tests of components that constitute the system. These component test plans have advantages over complete system based tests in terms of time and cost. In this paper, we consider the series system with n components, where the lifetime of the i‐th component follows exponential distribution with parameter λ_i. Assuming test costs for the components are different, we develop an efficient algorithm to design a two‐stage component test plan that satisfies the usual probability requirements on the system reliability and in addition minimizes the maximum expected cost. For the case of prior information in the form of upper bounds on λ_i's, we use the genetic algorithm to solve the associated optimization problems which are otherwise difficult to solve using mathematical programming techniques. The two‐stage component test plans are cost effective compared to single‐stage plans developed by Rajgopal and Mazumdar. We demonstrate through several numerical examples that our approach has the potential to reduce the overall testing costs significantly. © 2002 John Wiley & Sons, Inc. Naval Research Logistics, 49: 95–116, 2002; DOI 10.1002/nav.1051     

Cyclic scheduling in robotic flowshops with bounded work‐in‐process levels

This study addresses cyclic scheduling in robotic flowshops with bounded work‐in‐process (WIP) levels. The objective is to minimize the cycle time or, equivalently, to maximize the throughput, under the condition that the WIP level is bounded from above by a given integer number. We present several strongly polynomial algorithms for the 2‐cyclic robotic flowshop scheduling problems for various WIP levels. © 2010 Wiley Periodicals, Inc. Naval Research Logistics 58: 1–16, 2011     

Operations sequencing for a multi‐stage production inventory system

This article studies operations sequencing for a multi‐stage production inventory system with lead times under predictable (deterministic) yield losses and random demand. We consider various cases with either full or partial release of work‐in‐process inventories, for either pre‐operation or post‐operation cost structures, and under either the total discounted or average cost criteria. We derive necessary and sufficient criteria for the optimal sequence of operations in all cases. While the criteria differ in their specific forms, they all lead to the same principal: those operations with (1) lower yields, (2) lower processing costs, (3) longer lead times, and (4) lower inventory holding costs should be placed higher upstream in the system.Copyright © 2014 Wiley Periodicals, Inc. Naval Research Logistics 61: 144–154, 2014     

A multi‐stage stochastic programming approach for network capacity expansion with multiple sources of capacity

In networks, there are often more than one sources of capacity. The capacities can be permanently or temporarily owned by the decision maker. Depending on the nature of sources, we identify the permanent capacity, spot market capacity, and contract capacity. We use a scenario tree to model the uncertainty, and build a multi‐stage stochastic integer program that can incorporate multiple sources and multiple types of capacities in a general network. We propose two solution methodologies for the problem. Firstly, we design an asymptotically convergent approximation algorithm. Secondly, we design a cutting plane algorithm based on Benders decomposition to find tight bounds for the problem. The numerical experiments show superb performance of the proposed algorithms compared with commercial software. © 2016 Wiley Periodicals, Inc. Naval Research Logistics 63: 600–614, 2017     

Two‐machine flow shop scheduling with common due window to minimize weighted number of early and tardy jobs

This article studies two due window scheduling problems to minimize the weighted number of early and tardy jobs in a two‐machine flow shop, where the window size is externally determined. These new scheduling models have many practical applications in real life. However, results on these problems have rarely appeared in the literature because of a lack of structural and optimality properties for solving them. In this article, we derive several dominance properties and theorems, including elimination rules and sequencing rules based on Johnsos order, lower bounds on the penalty, and upper bounds on the window location, which help to significantly trim the search space for the problems. We further show that the problems are NP‐hard in the ordinary sense only. We finally develop efficient pseudopolynomial dynamic programming algorithms for solving the problems. © 2009 Wiley Periodicals, Inc. Naval Research Logistics, 2009     

Approximation algorithms for general one‐warehouse multi‐retailer systems

Logistical planning problems are complicated in practice because planners have to deal with the challenges of demand planning and supply replenishment, while taking into account the issues of (i) inventory perishability and storage charges, (ii) management of backlog and/or lost sales, and (iii) cost saving opportunities due to economies of scale in order replenishment and transportation. It is therefore not surprising that many logistical planning problems are computationally difficult, and finding a good solution to these problems necessitates the development of many ad hoc algorithmic procedures to address various features of the planning problems. In this article, we identify simple conditions and structural properties associated with these logistical planning problems in which the warehouse is managed as a cross‐docking facility. Despite the nonlinear cost structures in the problems, we show that a solution that is within ε‐optimality can be obtained by solving a related piece‐wise linear concave cost multi‐commodity network flow problem. An immediate consequence of this result is that certain classes of logistical planning problems can be approximated by a factor of (1 + ε) in polynomial time. This significantly improves upon the results found in literature for these classes of problems. We also show that the piece‐wise linear concave cost network flow problem can be approximated to within a logarithmic factor via a large scale linear programming relaxation. We use polymatroidal constraints to capture the piece‐wise concavity feature of the cost functions. This gives rise to a unified and generic LP‐based approach for a large class of complicated logistical planning problems. © 2009 Wiley Periodicals, Inc. Naval Research Logistics, 2009     

Single‐warehouse multi‐retailer inventory systems with full truckload shipments

We consider a multi‐stage inventory system composed of a single warehouse that receives a single product from a single supplier and replenishes the inventory of n retailers through direct shipments. Fixed costs are incurred for each truck dispatched and all trucks have the same capacity limit. Costs are stationary, or more generally monotone as in Lippman (Management Sci 16, 1969, 118–138). Demands for the n retailers over a planning horizon of T periods are given. The objective is to find the shipment quantities over the planning horizon to satisfy all demands at minimum system‐wide inventory and transportation costs without backlogging. Using the structural properties of optimal solutions, we develop (1) an O(T²) algorithm for the single‐stage dynamic lot sizing problem; (2) an O(T³) algorithm for the case of a single‐warehouse single‐retailer system; and (3) a nested shortest‐path algorithm for the single‐warehouse multi‐retailer problem that runs in polynomial time for a given number of retailers. To overcome the computational burden when the number of retailers is large, we propose aggregated and disaggregated Lagrangian decomposition methods that make use of the structural properties and the efficient single‐stage algorithm. Computational experiments show the effectiveness of these algorithms and the gains associated with coordinated versus decentralized systems. Finally, we show that the decentralized solution is asymptotically optimal. © 2009 Wiley Periodicals, Inc. Naval Research Logistics 2009     

Discrete equal‐capacity p‐median problem

This paper examines the discrete equal‐capacity p‐median problem that seeks to locate p new facilities (medians) on a network, each having a given uniform capacity, in order to minimize the sum of distribution costs while satisfying the demand on the network. Such problems arise, for example, in local access and transport area telecommunication network design problems where any number of a set of p facility units can be constructed at the specified candidate sites (hence, the net capacity is an integer multiple of a given unit capacity). We develop various valid inequalities, a separation routine for generating cutting planes that are specific members of such inequalities, as well as an enhanced reformulation that constructs a partial convex hull representation that subsumes an entire class of valid inequalities via its linear programming relaxation. We also propose suitable heuristic schemes for this problem, based on sequentially rounding the continuous relaxation solutions obtained for the various equivalent formulations of the problem. Extensive computational results are provided to demonstrate the effectiveness of the proposed valid inequalities, enhanced formulations, and heuristic schemes. The results indicate that the proposed schemes for tightening the underlying relaxations play a significant role in enhancing the performance of both exact and heuristic solution methods for this class of problems. © 2000 John & Sons, Inc. Naval Research Logistics 47: 166–183, 2000.     

Exploiting self‐canceling demand point aggregation error for some planar rectilinear median location problems

When solving location problems in practice it is quite common to aggregate demand points into centroids. Solving a location problem with aggregated demand data is computationally easier, but the aggregation process introduces error. We develop theory and algorithms for certain types of centroid aggregations for rectilinear 1‐median problems. The objective is to construct an aggregation that minimizes the maximum aggregation error. We focus on row‐column aggregations, and make use of aggregation results for 1‐median problems on the line to do aggregation for 1‐median problems in the plane. The aggregations developed for the 1‐median problem are then used to construct approximate n‐median problems. We test the theory computationally on n‐median problems (n ≥ 1) using both randomly generated, as well as real, data. Every error measure we consider can be well approximated by some power function in the number of aggregate demand points. Each such function exhibits decreasing returns to scale. © 2003 Wiley Periodicals, Inc. Naval Research Logistics 50: 614–637, 2003.