Spelling suggestions: "subject:"anested benders decomposition"" "subject:"anested benders ecomposition""
1 |
Modeling, Analysis, and Algorithmic Development of Some Scheduling and Logistics Problems Arising in Biomass Supply Chain, Hybrid Flow Shops, and Assembly Job ShopsSingh, Sanchit 15 July 2019 (has links)
In this work, we address a variety of problems with applications to `ethanol production from biomass', `agile manufacturing' and `mass customization' domains. Our motivation stems from the potential use of biomass as an alternative to non-renewable fuels, the prevalence of `flexible manufacturing systems', and the popularity of `mass customization' in today's highly competitive markets. Production scheduling and design and optimization of logistics network mark the underlying topics of our work. In particular, we address three problems, Biomass Logistics Problem, Hybrid Flow Shop Scheduling Problem, and Stochastic Demand Assembly Job Scheduling Problem.
The Biomass Logistics Problem is a strategic cost analysis for setup and operation of a biomass supply chain network that is aimed at the production of ethanol from switchgrass. We discuss the structural components and operations for such a network. We incorporate real-life GIS data of a geographical region in a model that captures this problem. Consequently, we develop and demonstrate the effectiveness of a `Nested Benders' based algorithm for an efficient solution to this problem.
The Hybrid Flow Shop Scheduling Problem concerns with production scheduling of a lot over a two-stage hybrid flow shop configuration of machines, and is often encountered in `flexible manufacturing systems'. We incorporate the use of `lot-streaming' in order to minimize the makespan value. Although a general case of this problem is NP-hard, we develop a pseudo-polynomial time algorithm for a special case of this problem when the sublot sizes are treated to be continuous. The case of discrete sublot sizes is also discussed for which we develop a branch-and-bound-based method and experimentally demonstrate its effectiveness in obtaining a near-optimal solution.
The Stochastic Demand Assembly Job Scheduling Problem deals with the scheduling of a set of products in a production setting where manufacturers seek to fulfill multiple objectives such as `economy of scale' together with achieving the flexibility to produce a variety of products for their customers while minimizing delivery lead times. We design a novel methodology that is geared towards these objectives and propose a Lagrangian relaxation-based algorithm for efficient computation. / Doctor of Philosophy / In this work, we organize our research efforts in three broad areas - Biomass Supply Chain, Hybrid Flow Shop, and Assembly Job Shop, which are separate in terms of their application but connected by scheduling and logistics as the underlying functions. For each of them, we formulate the problem statement and identify the challenges and opportunities from the viewpoint of mathematical decision making. We use some of the well known results from the theory of optimization and linear algebra to design effective algorithms in solving these specific problems within a reasonable time limit. Even though the emphasis is on conducting an algorithmic analysis of the proposed solution methods and in solving the problems analytically, we strive to capture all the relevant and practical features of the problems during formulation of each of the problem statement, thereby maintaining their applicability. The Biomass Supply Chain pertains to the production of fuel grade ethanol from naturally occurring biomass in the form of switchgrass. Such a system requires establishment of a supply chain and logistics network that connects the production fields at its source, the intermediate points for temporary storage of the biomass, and bio-energy plant and refinery at its end for conversion of the cellulosic content in the biomass to crude oil and ethanol, respectively. We define the components and operations necessary for functioning of such a supply chain. The Biomass Logistics Problem that we address is a strategic cost analysis for setup and operation of such a biomass supply chain network. We focus our attention to a region in South Central Virginia and use the detailed geographic map data to obtain land use pattern in the region. We conduct survey of existing literature to obtain various transportation related cost factors and costs associated with the use of equipment. Our ultimate aim here is to understand the feasibility of running a biomass supply chain in the region of interest from an economic standpoint. As such, we represent the Biomass Logistics Problem with a cost-based optimization model and solve it in a series of smaller problems. A Hybrid Flow Shop (HFS) is a configuration of machines that is often encountered in the flexible manufacturing systems, wherein a particular station of machines can execute processing of jobs/tasks simultaneously. In our work, we approach a specific type of HFS, with a single machine at the first stage and multiple identical machines at the second stage. A batch or lot of jobs/items is considered for scheduling over such an HFS. Depending upon the area of application, such a batch is either allowed to be split into continuous sections or restricted to be split in discrete sizes only. The objective is to minimize the completion time of the last job on its assigned machine at the second stage. We call this problem, Hybrid Flow Shop Scheduling Problem, which is known to be a hard problem in literature. We aim to derive the results which will reduce the complexity of this problem, and develop both exact as well as heuristic methods in order to obtain near-optimal solution to this problem. An Assembly Job Shop is a variant of the classical Job Shop which considers scheduling a set of assembly operations over a set of assembly machines. Each operation can only be started once all the other operations in its precedence relationship are completed. Assembly Job Shop are at the core of some of the highly competitive manufacturing facilities that are principled on the philosophy of Mass Customization. Assuming an inherent nature of demand uncertainty, this philosophy aims to achieve ‘economy of scale’ together with flexibility to produce a variety of products for the customers while minimizing the delivery lead times simultaneously. We incorporate some of these challenges in a concise framework of production scheduling and call this problem as Stochastic Demand Assembly Job Scheduling Problem. We design a novel methodology that is geared towards achieving the set objectives and propose an effective algorithm for efficient computation.
|
2 |
Modeling and Analysis of a Feedstock Logistics ProblemJudd, Jason D. 02 May 2012 (has links)
Recently, there has been a surge in the research and application of "Green energy" in the United States. This has been driven by the following three objectives: (1) to reduce the nation's reliance on foreign oil, (2) to mitigate emission of greenhouse gas, and (3) to create an economic stimulus within the United States. Switchgrass is the biomass of choice for the Southeastern United States. In this dissertation, we address a feedstock logistics problem associated with the delivery of switchgrass for conversion into biofuel. In order to satisfy the continual demand of biomass at a bioenergy plant, production fields within a 48-km radius of its location are assumed to be attracted into production. The bioenergy plant is expected to receive as many as 50-400 loads of biomass per day. As a result, an industrialized transportation system must be introduced as early as possible in order to remove bottlenecks and reduce the total system cost. Additionally, we assume locating multiple bioenergy plants within a given region for the production of biofuel. We develop mixed integer programming formulations for the feedstock logistics problem that we address and for some related problems, and we solve them either through the use of decomposition-based methods or directly through the use of CPLEX 12.1.0.
The feedstock logistics problem that we address spans the entire system-from the growing of switchgrass to the transporting of bio-crude oil, a high energy density intermediate product, to a refinery for conversion into a final product. To facilitate understanding, we present the reader with a case study that includes a preliminary cost analysis of a real-life-based instance in order to provide the reader appropriate insights of the logistics system before applying optimization techniques for its solution. First, we consider the benefits of active versus passive ownership of the production fields. This is followed by a discussion on the selection of baler type, and then, a discussion of contracts between various business entities. The advantages of storing biomass at a satellite storage location (SSL) and interactions between the operations performed at the production field with those performed at the storage locations are then established. We also provide a detailed description of the operations performed at a SSL. Three potential equipment options are presented for transporting biomass from the SSLs to a utilization point, defined in this study as a Bio-crude Plant (BcP). The details of the entire logistics chain are presented in order to highlight the need for making decisions in view of the entire chain rather than basing them on its segments.
We model the feedstock logistics problem as a combination of a 2-level facility location-allocation problem and a multiple traveling salesmen problem (mATSP). The 2-level facility location-allocation problem pertains to the allocation of production fields to SSLs and SSLs to one of the multiple bioenergy plants. The mATSP arises because of the need for scheduling unloading operations at the SSLs. To this end, we provide a detailed study of 13 formulations of the mATSP and their reformulations as ATSPs. First, we assume that the SSLs are always full, regardless of when they are scheduled to be unloaded. We, then, relax this assumption by providing precedence constraints on the availability of the SSLs. This precedence is defined in two different ways and, is then, effectively modeled utilizing all the formulations for the mATSP and ATSP.
Given the location of a BcP for the conversion of biomass to bio-crude oil, we develop a feedstock logistics system that relies on the use of SSLs for temporary storage and loading of round bales. Three equipment systems are considered for handling biomass at the SSLs, and they are either placed permanently or are mobile, and thereby, travel from one SSL to another. We use a mathematical programming-based approach to determine SSLs and equipment routes in order to minimize the total cost incurred. The mathematical program is applied to a real-life production region in South-central Virginia (Gretna, VA), and it clearly reveals the benefits of using SSLs as a part of the logistics system. Finally, we provide a sensitivity analysis on the input parameters that we used. This analysis highlights the key cost factors in the model, and it emphasizes areas where biggest gains can be achieved for further cost reduction.
For a more general scenario, where multiple BcPs have to be located, we use a nested Benders' decomposition-based method. First, we prove the validity of using this method. We, then, employ this method for the solution of a potential real-life instance. Moreover, we successfully solve problems that are more than an order of magnitude larger than those solved directly by CPLEX 12.1.0.
Finally, we develop a Benders' decomposition-based method for the solution of a problem that gives rise to a binary sub-problem. The difficulty arises because of the sub-problem being an integer program for which the dual solution is not readily available. Our approach consists of first solving the integer sub-problem, and then, generating the convex hull at the optimal integer point. We illustrate this approach for an instance for which such a convex hull is readily available, but otherwise, it is too expensive to generate for the entire problem. This special instance is the solution of the mATSP (using Benders' decomposition) for which each of the sub-problems is an ATSP. The convex hull for the ATSP is given by the Dantzig, Fulkerson, and Johnson constraints. These constraints at a given integer solution point are only polynomial in number. With the inclusion of these constraints, a linear programming solution and its corresponding dual solution can now be obtained at the optimal integer points. We have proven the validity of using this method. However, the success of our algorithm is limited because of a large number of integer problems that must be solved at every iteration. While the algorithm is theoretically promising, the advantages of the decomposition do not seem to outweigh the additional cost resulting from solving a larger number of decomposed problems. / Ph. D.
|
Page generated in 0.1751 seconds