Search for: All records

Abstract In this paper, we consider an application of lot-streaming for processing a lot of multiple items in a hybrid flow shop (HFS) for the objective of minimizing makespan. The HFS that we consider consists of two stages with a single machine available for processing in Stage 1 andmidentical parallel machines in Stage 2. We call this problem a 1 + mTSHFS-LSP (two-stage hybrid flow shop, lot streaming problem), and show it to be NP-hard in general, except for the case when the sublot sizes are treated to be continuous. The novelty of our work is in obtaining closed-form expressions for optimal continuous sublot sizes that can be solved in polynomial time, for a given number of sublots. A fast linear search algorithm is also developed for determining the optimal number of sublots for the case of continuous sublot sizes. For the case when the sublot sizes are discrete, we propose a branch-and-bound-based heuristic to determine both the number of sublots and sublot sizes and demonstrate its efficacy by comparing its performance against that of a direct solution of a mixed-integer formulation of the problem by CPLEX^®. 

Abstract In this paper, we address a biomass feedstock logistics problem to supply biomass from production fields to satellite storage locations (SSLs) and from there to bioenergy plants (BePs) and then to a biorefinery. It entails a new problem feature of routing load-out equipment sets among the SSLs to perform loading/unloading of biomass and/or its pre-processing operations. The ownership of the loading equipment is a very capital-intensive link of the ethanol production supply chain, which when loaded onto trucks and routed along the logistics chain significantly brings down the ethanol production costs. This will make ethanol a cost-competitive alternative to fossil fuels, lead to sustainable use of fossil fuels and add to the overall relevance of the bioenergy sector. In this regard, the objective of our problem is to minimize the total cost incurred due to the ownership of equipment sets, fixed setups, and land rental cost, as well as the cost of transporting biomass from the fields to the BePs and biocrude oil from the BePs to the refinery. A mixed-integer mathematical model of the problem is presented, and a nested Benders decomposition-based solution approach is developed which involves decomposing this large problem into three stages. Stage 1 deals with the selection of fields, BePs, and SSLs, and assignment of fields to the SSLs. The remaining model consists of multiple Capacitated Vehicle Routing Problems (CVRPs) that are separable over individual BePs. For each BeP, the CVRP is further decomposed into Stage 2 and Stage 3 sub-problems where the Stage 2 problem is an allocation problem that assigns SSLs to tours associated to each BeP, and the Stage 3 problem is a variant of Traveling Salesman Problem (TSP) that determines the sequence in which equipment is routed over the predesignated set of SSLs for each tour. These sub-problems are integer programs rather than linear programs. First novelty of our proposed approach is to effectively handle the integrality of variables arising due to the consideration of the routing of load-out equipment. Second is solution methodology and in the use of proposed multi-cut version of optimality cuts that capture the solution value at an integer solution for the sub-problems. These cuts aid in faster convergence and are shown to be stronger than those proposed in the literature. The applicability of the proposed methodology is demonstrated by applying it to a real-life problem that utilizes available GIS data for the catchment area of regions around Gretna and Bedford in Virginia. We then solved a set of varying problem size instances using the state-of-the-art CPLEX® Branch-and-Bound and Benders Strategy methods. The CPLEX® algorithms struggled to solve instances even 10 times smaller than the real-life problem size instances; with MIP optimality gaps ranging from 5.85% to 82.79% in the allowed time limit of 10,000 s. On the other hand, our proposed nested Benders decomposition algorithm was able to achieve faster convergence and provided optimal solutions for all the considered problem instances with an average CPU run-time of around 3,700 s. This validates the efficacy and superiority of our solution approach. Lastly, we summarize our work and point out some interesting potential future research opportunities.