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.     

Dynamic evacuation routes for personnel on a naval ship

We propose a dynamic escape route system for emergency evacuation of a naval ship. The system employs signals that adapt to the causative contingency and the crew's physical distribution about the ship. A mixed‐integer nonlinear programming model, with underlying network structure, optimizes the evacuation process. The network's nodes represent compartments, closures (e.g., doors and hatches) and intersections, while arcs represent various types of passageways. The objective function integrates two potentially conflicting factors: average evacuation time and the watertight and airtight integrity of the ship after evacuation. A heuristic solves the model approximately using a sequence of mixed‐integer linear approximating problems. Using data for a Spanish frigate, with standard static routes specified by the ship's designers, computational tests show that the dynamic system can reduce average evacuation times, nearly 23%, and can improve a combined measure of ship integrity by up to 50%. In addition, plausible design changes to the frigate yield further, substantial improvements. Published 2008 Wiley Periodicals, Inc. Naval Research Logistics 2008     

Column generation for stochastic green telecommunication network planning with switchable base stations

We present the green telecommunication network planning problem with switchable base stations, where the location and configuration of the base stations are optimized, while taking into account uncertainty and variability of demand. The problem is formulated as a two‐stage stochastic program under demand uncertainty with integers in both stages. Since solving the presented problem is computationally challenging, we develop the corresponding Dantzig‐Wolfe reformulation and propose a solution approach based on column generation. Comprehensive computational results are provided for instances of varying characteristics. The results show that the joint location and dynamic switching of base stations leads to significant savings in terms of energy cost. Up to 30% reduction in power consumption cost is achieved while still serving all users. In certain cases, allowing dynamic configurations leads to more installed base stations and higher user coverage, while having lower total energy consumption. The Dantzig‐Wolfe reformulation provides solutions with a tight LP‐gap eliminating the need for a full branch‐and‐price scheme. Furthermore, the proposed column generation solution approach is computationally efficient and outperforms CPLEX on the majority of the tested instances. © 2016 Wiley Periodicals, Inc. Naval Research Logistics 63: 351–366, 2016     

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     

A forward network simplex algorithm for solving multiperiod network flow problems

An optimization model which is frequently used to assist decision makers in the areas of resource scheduling, planning, and distribution is the minimum cost multiperiod network flow problem. This model describes network structure decision-making problems over time. Such problems arise in the areas of production/distribution systems, economic planning, communication systems, material handling systems, traffic systems, railway systems, building evacuation systems, energy systems, as well as in many others. Although existing network solution techniques are efficient, there are still limitations to the size of problems that can be solved. To date, only a few researchers have taken the multiperiod structure into consideration in devising efficient solution methods. Standard network codes are usually used because of their availability and perceived efficiency. In this paper we discuss the development, implementation, and computational testing of a new technique, the forward network simplex method, for solving linear, minimum cost, multiperiod network flow problems. The forward network simplex method is a forward algorithm which exploits the natural decomposition of multiperiod network problems by limiting its pivoting activity. A forward algorithm is an approach to solving dynamic problems by solving successively longer finite subproblems, terminating when a stopping rule can be invoked or a decision horizon found. Such procedures are available for a large number of special structure models. Here we describe the specialization of the forward simplex method of Aronson, Morton, and Thompson to solving multiperiod network network flow problems. Computational results indicate that both the solution time and pivot count are linear in the number of periods. For standard network optimization codes, which do not exploit the multiperiod structure, the pivot count is linear in the number of periods; however, the solution time is quadratic.     

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     

Single‐commodity stochastic network design under demand and topological uncertainties with insufficient data

Stochastic network design is fundamental to transportation and logistic problems in practice, yet faces new modeling and computational challenges resulted from heterogeneous sources of uncertainties and their unknown distributions given limited data. In this article, we design arcs in a network to optimize the cost of single‐commodity flows under random demand and arc disruptions. We minimize the network design cost plus cost associated with network performance under uncertainty evaluated by two schemes. The first scheme restricts demand and arc capacities in budgeted uncertainty sets and minimizes the worst‐case cost of supply generation and network flows for any possible realizations. The second scheme generates a finite set of samples from statistical information (e.g., moments) of data and minimizes the expected cost of supplies and flows, for which we bound the worst‐case cost using budgeted uncertainty sets. We develop cutting‐plane algorithms for solving the mixed‐integer nonlinear programming reformulations of the problem under the two schemes. We compare the computational efficacy of different approaches and analyze the results by testing diverse instances of random and real‐world networks. © 2017 Wiley Periodicals, Inc. Naval Research Logistics 64: 154–173, 2017     

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     

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     

The stochastic U‐line balancing problem

A U‐line arranges tasks around a U‐shaped production line and organizes them into stations that can cross from one side of the line to the other. In addition to improving visibility and communication between operators on the line, which facilitates problem‐solving and quality improvement, U‐lines can reduce the total number of operators required on the line and make rebalancing the line easier compared to the traditional, straight production line. This paper studies the (type 1) U‐line balancing problem when task completion times are stochastic. Stochastic completion times occur when differences between operators cause completion times to vary somewhat and when machine processing times vary. A recursive algorithm is presented for finding the optimal solution when completion times have any distribution function. An equivalent shortest path network is also presented. An improvement for the special case of normally distributed task completion times is given. A computational study to determine the characteristics of instances that can be solved by the algorithms shows that they are able to solve instances of practical size (like the 114 Japanese and U.S. U‐lines studied in a literature review paper). © 2002 Wiley Periodicals, Inc. Naval Research Logistics, 2003     

Multi‐item capacitated lot‐sizing problems with setup times and pricing decisions

We study a multi‐item capacitated lot‐sizing problem with setup times and pricing (CLSTP) over a finite and discrete planning horizon. In this class of problems, the demand for each independent item in each time period is affected by pricing decisions. The corresponding demands are then satisfied through production in a single capacitated facility or from inventory, and the goal is to set prices and determine a production plan that maximizes total profit. In contrast with many traditional lot‐sizing problems with fixed demands, we cannot, without loss of generality, restrict ourselves to instances without initial inventories, which greatly complicates the analysis of the CLSTP. We develop two alternative Dantzig–Wolfe decomposition formulations of the problem, and propose to solve their relaxations using column generation and the overall problem using branch‐and‐price. The associated pricing problem is studied under both dynamic and static pricing strategies. Through a computational study, we analyze both the efficacy of our algorithms and the benefits of allowing item prices to vary over time. © 2009 Wiley Periodicals, Inc. Naval Research Logistics, 2010     

Flow shop scheduling with earliness,tardiness, and intermediate inventory holding costs

We consider the problem of scheduling customer orders in a flow shop with the objective of minimizing the sum of tardiness, earliness (finished goods inventory holding), and intermediate (work‐in‐process) inventory holding costs. We formulate this problem as an integer program, and based on approximate solutions to two different, but closely related, Dantzig‐Wolfe reformulations, we develop heuristics to minimize the total cost. We exploit the duality between Dantzig‐Wolfe reformulation and Lagrangian relaxation to enhance our heuristics. This combined approach enables us to develop two different lower bounds on the optimal integer solution, together with intuitive approaches for obtaining near‐optimal feasible integer solutions. To the best of our knowledge, this is the first paper that applies column generation to a scheduling problem with different types of strongly ????‐hard pricing problems which are solved heuristically. The computational study demonstrates that our algorithms have a significant speed advantage over alternate methods, yield good lower bounds, and generate near‐optimal feasible integer solutions for problem instances with many machines and a realistically large number of jobs. © 2004 Wiley Periodicals, Inc. Naval Research Logistics, 2004.     

Optimization of schedule stability and efficiency under processing time variability and random machine breakdowns in a job shop environment

The ability to cope with uncertainty in dynamic scheduling environments is becoming an increasingly important issue. In such environments, any disruption in the production schedule will translate into a disturbance of the plans for several external activities as well. Hence, from a practical point of view, deviations between the planned and realized schedules are to be avoided as much as possible. The term stability refers to this concern. We propose a proactive approach to generate efficient and stable schedules for a job shop subject to processing time variability and random machine breakdowns. In our approach, efficiency is measured by the makespan, and the stability measure is the sum of the variances of the realized completion times. Because the calculation of the original measure is mathematically intractable, we develop a surrogate stability measure. The version of the problem with the surrogate stability measure is proven to be NP‐hard, even without machine breakdowns; a branch‐and‐bound algorithm is developed for this problem variant. A tabu search algorithm is proposed to handle larger instances of the problem with machine breakdowns. The results of extensive computational experiments indicate that the proposed algorithms are quite promising in performance. © 2011 Wiley Periodicals, Inc. Naval Research Logistics, 2011     

A nested benders decomposition approach for telecommunication network planning

Despite its ability to result in more effective network plans, the telecommunication network planning problem with signal‐to‐interference ratio constraints gained less attention than the power‐based one because of its complexity. In this article, we provide an exact solution method for this class of problems that combines combinatorial Benders decomposition, classical Benders decomposition, and valid cuts in a nested way. Combinatorial Benders decomposition is first applied, leading to a binary master problem and a mixed integer subproblem. The subproblem is then decomposed using classical Benders decomposition. The algorithm is enhanced using valid cuts that are generated at the classical Benders subproblem and are added to the combinatorial Benders master problem. The valid cuts proved efficient in reducing the number of times the combinatorial Benders master problem is solved and in reducing the overall computational time. More than 120 instances of the W‐CDMA network planning problem ranging from 20 demand points and 10 base stations to 140 demand points and 30 base stations are solved to optimality. © 2010 Wiley Periodicals, Inc. Naval Research Logistics, 2010     

Chance‐constrained multi‐terminal network design problems

We consider a reliable network design problem under uncertain edge failures. Our goal is to select a minimum‐cost subset of edges in the network to connect multiple terminals together with high probability. This problem can be seen as a stochastic variant of the Steiner tree problem. We propose two scenario‐based Steiner cut formulations, study the strength of the proposed valid inequalities, and develop a branch‐and‐cut solution method. We also propose an LP‐based separation for the scenario‐based directed Steiner cut inequalities using Benders feasibility cuts, leveraging the success of the directed Steiner cuts for the deterministic Steiner tree problem. In our computational study, we test our branch‐and‐cut method on instances adapted from graphs in SteinLib Testdata Library with up to 100 nodes, 200 edges, and 17 terminals. The performance of our branch‐and‐cut method demonstrates the strength of the scenario‐based formulations and the benefit from adding the additional valid inequalities that we propose. © 2015 Wiley Periodicals, Inc. Naval Research Logistics 62: 321–334, 2015     

Expansion planning for waste‐to‐energy systems using waste forecast prediction sets

We consider an expansion planning problem for Waste‐to‐Energy (WtE) systems facing uncertainty in future waste supplies. The WtE expansion plans are regarded as strategic, long term decisions, while the waste distribution and treatment are medium to short term operational decisions which can adapt to the actual waste collected. We propose a prediction set uncertainty model which integrates a set of waste generation forecasts and is constructed based on user‐specified levels of forecasting errors. Next, we use the prediction sets for WtE expansion scenario analysis. More specifically, for a given WtE expansion plan, the guaranteed net present value (NPV) is evaluated by computing an extreme value forecast trajectory of future waste generation from the prediction set that minimizes the maximum NPV of the WtE project. This problem is essentially a multiple stage min‐max dynamic optimization problem. By exploiting the structure of the WtE problem, we show this is equivalent to a simpler min‐max optimization problem, which can be further transformed into a single mixed‐integer linear program. Furthermore, we extend the model to optimize the guaranteed NPV by searching over the set of all feasible expansion scenarios, and show that this can be solved by an exact cutting plane approach. We also propose a heuristic based on a constant proportion distribution rule for the WtE expansion optimization model, which reduces the problem into a moderate size mixed‐integer program. Finally, our computational studies demonstrate that our proposed expansion model solutions are very stable and competitive in performance compared to scenario tree approaches. © 2016 Wiley Periodicals, Inc. Naval Research Logistics 63: 47–70, 2016     

Balancing a one‐way corridor capacity and safety‐oriented reliability: A stochastic optimization approach for metro train timetabling

In urban rail transit systems of large cities, the headway and following distance of successive trains have been compressed as much as possible to enhance the corridor capacity to satisfy extremely high passenger demand during peak hours. To prevent train collisions and ensure the safety of trains, a safe following distance of trains must be maintained. However, this requirement is subject to a series of complex factors, such as the uncertain train braking performance, train communication delay, and driver reaction time. In this paper, we propose a unified mathematical framework to analyze the safety‐oriented reliability of metro train timetables with different corridor capacities, that is, the train traffic density, and determine the most reliable train timetable for metro lines in an uncertain environment. By employing a space‐time network representation in the formulations, the reliability‐based train timetabling problem is formulated as a nonlinear stochastic programming model, in which we use 0‐1 variables to denote the time‐dependent velocity and position of all involved trains. Several reformulation techniques are developed to obtain an equivalent mixed integer programming model with quadratic constraints (MIQCP) that can be solved to optimality by some commercial solvers. To improve the computational efficiency of the MIQCP model, we develop a dual decomposition solution framework that decomposes the primal problem into several sets of subproblems by dualizing the coupling constraints across different samples. An exact dynamic programming combined with search space reduction strategies is also developed to solve the exact optimal solutions of these subproblems. Two sets of numerical experiments, which involve a relatively small‐scale case and a real‐world instance based on the operation data of the Beijing subway Changping Line are implemented to verify the effectiveness of the proposed approaches.     

The network redesign problem for access telecommunications networks

The network redesign problem attempts to design an optimal network that serves both existing and new demands. In addition to using spare capacity on existing network facilities and deploying new facilities, the model allows for rearrangement of existing demand units. As rearrangements mean reassigning existing demand units, at a cost, to different facilities, they may lead to disconnecting of uneconomical existing facilities, resulting in significant savings. The model is applied to an access network, where the demands from many sources need to be routed to a single destination, using either low‐capacity or high‐capacity facilities. Demand from any location can be routed to the destination either directly or through one other demand location. Low‐capacity facilities can be used between any pair of locations, whereas high‐capacity facilities are used only between demand locations and the destination. We present a new modeling approach to such problems. The model is described as a network flow problem, where each demand location is represented by multiple nodes associated with demands, low‐capacity and high‐capacity facilities, and rearrangements. Each link has a capacity and a cost per unit flow parameters. Some of the links also have a fixed‐charge cost. The resulting network flow model is formulated as a mixed integer program, and solved by a heuristic and a commercially available software. © 1999 John Wiley & Sons, Inc. Naval Research Logistics 46: 487–506, 1999     

Benders decomposition with alternative multiple cuts for a multi‐product closed‐loop supply chain network design model

In this article, we consider a multi‐product closed‐loop supply chain network design problem where we locate collection centers and remanufacturing facilities while coordinating the forward and reverse flows in the network so as to minimize the processing, transportation, and fixed location costs. The problem of interest is motivated by the practice of an original equipment manufacturer in the automotive industry that provides service parts for vehicle maintenance and repair. We provide an effective problem formulation that is amenable to efficient Benders reformulation and an exact solution approach. More specifically, we develop an efficient dual solution approach to generate strong Benders cuts, and, in addition to the classical single Benders cut approach, we propose three different approaches for adding multiple Benders cuts. These cuts are obtained via dual problem disaggregation based either on the forward and reverse flows, or the products, or both. We present computational results which illustrate the superior performance of the proposed solution methodology with multiple Benders cuts in comparison to the branch‐and‐cut approach as well as the traditional Benders decomposition approach with a single cut. In particular, we observe that the use of multiple Benders cuts generates stronger lower bounds and promotes faster convergence to optimality. We also observe that if the model parameters are such that the different costs are not balanced, but, rather, are biased towards one of the major cost categories (processing, transportation or fixed location costs), the time required to obtain the optimal solution decreases considerably when using the proposed solution methodology as well as the branch‐and‐cut approach. © 2007 Wiley Periodicals, Inc. Naval Research Logistics, 2007     

Optimal empty vehicle redistribution for hub‐and‐spoke transportation systems

This article considers the empty vehicle redistribution problem in a hub‐and‐spoke transportation system, with random demands and stochastic transportation times. An event‐driven model is formulated, which yields the implicit optimal control policy. Based on the analytical results for two‐depot systems, a dynamic decomposition procedure is presented which produces a near‐optimal policy with linear computational complexity in terms of the number of spokes. The resulting policy has the same asymptotic behavior as that of the optimal policy. It is found that the threshold‐type control policy is not usually optimal in such systems. The results are illustrated through small‐scale numerical examples. Through simulation the robustness of the dynamic decomposition policy is tested using a variety of scenarios: more spokes, more vehicles, different combinations of distribution types for the empty vehicle travel times and loaded vehicle arrivals. This shows that the dynamic decomposition policy is significantly better than a heuristics policy in all scenarios and appears to be robust to the assumptions of the distribution types. © 2008 Wiley Periodicals, Inc. Naval Research Logistics, 2008