STUDENTS' THESIS
PhD Thesis
Danial Rooyani (2023). Efficient Two-Stage Genetic Algorithms for Comprehensive Multi-Objective Flexible Job Shop Scheduling Problems
In a flexible job-shop scheduling problem (FJSP), an operation can be assigned to one of a set of eligible machines. Therefore, the problem is to simultaneously determine both the assignment of operations to machines and their sequences. Accordingly, the solution encoding of many regular genetic algorithms (RGAs) developed in literature has two parts: one part encodes the assignment decision and the other the sequencing decision. The genetic search determines both the assignment and the sequencing of the operations simultaneously through a random process guided by the principles of natural selection and evolution. In this paper, we develop a two-stage genetic algorithm (2SGA) with the first stage being different from a typical RGA for FJSP found in the literature. The first stage of 2SGA has a solution encoding that only dictates the sequence in which the operations are considered for assignment. Whenever an operation is considered for assignment, the machine that can complete this operation the soonest is selected while taking into account the operations that are already assigned to this machine. The order in which the operations are assigned to machines determines their sequence. The second stage, starting from the solutions of the first stage, follows the common approach of genetic algorithm for FJSP to enable the algorithm to search the entire solution space by including solutions that might have been excluded because of the greedy nature of the first stage. We tested the proposed algorithm by solving many benchmark problems and several other large-size problems of a comprehensive FJSP model with sequence-dependent setup, machine release date, and lag-time. The performance of the proposed two-stage algorithm greatly exceeds that of the common approach of genetic algorithm for FJSP. We also show that further performance improvement of the proposed algorithm can be achieved using high-performance parallel computation. However, the more interesting result we found was that the sequential version of the proposed algorithm (using a single CPU) outperformed a parallel implementation of the regular genetic algorithm that uses many CPUs. We also noted that the superiority of the proposed algorithm over RGA is much greater when solving large-size problems, rendering the proposed algorithm as a viable choice for solving practical problems that are typically encountered in industries.
The developed two-stage genetic algorithm was further extended to (1) a multi-objective lot streaming flexible job shop scheduling and (2) another multi-objective flexible job shop scheduling where assembly requirements and outsourcing of operations were considered. In both extensions, extensive numerical examples were presented to provide managerial insights and demonstrate the computational efficiency of the proposed algorithm..
Seyedfarhad Shafigh (2015). mathematical Models and Solution Procedures in the Design and Scheduling of Manufacturing Systems with Distributed Layouts
Numerous studies have been conducted to design facility layouts since the early 1950s. The majority of these studies have primarily focused on product layout, functional layout, cellular layout or their variants. Recent trend in manufacturing systems literature establishes the consensus that these conventional configurations do not meet the needs of today's multi-product enterprises working in dynamic environment. A promising approach to address changes in the production environment is to build facility layouts that can easily adapt to volatilities. Distributed layouts are among such facilities enabling industries to address volatilities and uncertainties.
This thesis addresses two distinct problems in facility design and scheduling for manufacturing firms operating in volatile environment and producing the multiple batches of products. In regards to the facility layout problem, a new comprehensive mathematical model that integrates layout configuration and production planning in the design of dynamic distributed layouts is formulated. The model incorporates a number of important manufacturing attributes such as demand fluctuation, system reconfiguration, lot splitting, work load balancing, alternative routings, machine capability and tooling requirements. In addition, the model allows the optimization of several cost elements in an integrated manner. These include material handling, machine relocation, setup, inventory carrying, in-house production and subcontracting costs. With respect to the scheduling problem, a mathematical formulation for scheduling of manufacturing systems with distributed layouts is developed. The objective of scheduling model is the minimization of the weighted sum of makespan and total traveling distance by the products. Thus on one hand, the problem is to find a schedule of operations on machines (the sequence and starting times of the various operations) which minimizes the overall finishing time or makespan. On the other hand, the problem is to find assignment of jobs to the machines such that total distance traveled by parts is minimized.
Optimal solutions for the proposed mathematical models can only be found for small size problems due to NP-complexity. To solve both models for larger-size problems, two hybrids metaheuristics (linear programming embedded a metaheuristic) for solving the facility design model and a genetic algorithm for the scheduling model have been developed. All proposed algorithms are thoroughly examined with an emphasis on solution convergence, solution quality and algorithm robustness. For both cases, we provide numerical results to support various managerial insights. In particular in facility design problem, we draw a managerial insight as to how high product variety and high volatility in the production environment can be accommodated without harm to operational efficiency or cost. Similarly in the scheduling study, we show that linking scheduling and material handling performance can contribute to the development of accurate models to obtain a schedule that can also greatly enhance system performance.
Master Thesis
Amin amouzadeh (2023). A genetic algorithm for a setup operator constrained flexible flow shop lot streaming with detached and sequence dependent setups
DownloadPDF (comming soon after embargo period ended)
This thesis explores the use of genetic algorithms to optimize the flexible flow shop scheduling process in the presence of dual resource constraints. The objective is to minimize the makespan, which is a critical factor in improving production efficiency. Lot streaming is used to reduce the processing time of the jobs and the genetic algorithm is applied to identify the optimal sequence of jobs. The proposed approach is tested on a set of benchmark problems and compared with other solution representations in GA. The results show that the proposed approach can effectively reduce the makespan and improve the overall performance of the scheduling process in flexible flow shop systems with dual resource constraints.
Ammar Sulaimani (2022). Multi-Objective Genetic Algorithm for an Integrated Inspection Allocation and Flow Shop Scheduling with Sequence Dependent Setup Time
DownloadPDF (comming soon after embargo period ended)
One of the most critical elements in manufacturing is production scheduling. Hence, any improvement in the scheduling system has significantly impacts time, quality, productivity, flexibility, and total cost. Improving these factors can easily increase the customer satisfaction. Multi-objective flow-shop scheduling with sequence-dependent set up time is considered as an NP-hard problem (nondeterministic polynomial time). Integrating inspection allocation with flow-shop scheduling problem results in a complex scheduling problem. For this degree of complexity, genetic algorithm is an excellent choice. Adding many inspection points in the production line can help to avoid reject items. However, the operation cost and productivity will be impacted negatively. The main objectives in this thesis are minimizing the inspection cost, minimizing the cost of processing defective items, and minimizing penalty cost by using genetic algorithm. Moreover, establishing a balance between cost and quality is extremely important in modern manufacturing management to avoid waste according to lean
manufacturing methodology.
Syeda Manjia Tahsien (2020). A Neural Network Guided Genetic Algorithm for Flexible Flow Shop Scheduling Problem with Sequence Dependent Setup Time
This thesis presents a discriminating technique and clustering ordered permutation using Adaptive Resonance Theory (ART) and potential applications in the ART-guided Genetic Algorithm (GA). In this regard, we have introduced two novel techniques for converting ordered permutations to binary vectors to cluster them using ART. The proposed binary conversion methods are evaluated under varying parameters, and problem sizes with the performance analysis of ART-1 and Improved-ART-1. The numerical results indicate the superiority of one of the proposed binary conversion techniques over the other and Improved-ART-1 over ART-1. Finally, we develop Improved-ART-1 Neural Network guided GA to solve a flexible flow show scheduling problem (FFSP) with sequence dependant setup time. Numerical examples show that ANN-guided GA outperforms the pure GA in solving several large size FFSP problems.
Dolapo obimuyiwa (2020). Solving Flexible Job Shop Scheduling Problem in the Presence of Limited Number of Skilled Cross-trained Setup Operators
Many researchers developed algorithms for a dual-resource constrained flexible job shop (DRC-FJSP) where both machines and workers need to be simultaneously scheduled. In those models and algorithms in the literature, the authors assumed that workers are machine operators responsible for performing production process steps from the beginning to the end of the operation. However, because of increased automation and the adoption of numerically controlled machines, workers became machine tenders and should not be bottleneck and constraining resources. On the other hand, skilled setup operators remain being constraining limited resources in industries. Unlike machine tenders, setup operator can leave the machine once a setup is done and take on another setup operation on another machine. In this thesis, we develop a genetic algorithm for a new DRC-FJSP where setup operators and machine tools are constraining resources. Numerical examples of varying problem sizes are presented to show the performance of the algorithm.
Dhruv Patel (2019). A Genetic Algorithm with Monte-Carlo Simulation for an Optimal Inspection Allocation in a Batch Assembly Line with Tolerance Stack-up
In this thesis, the total inspection policy cost of a batch assembly line in the multi-stage production system (MSPS) is optimized by using the Genetic Algorithm with Monte Carlo simulation. Total inspection policy cost (consist of inspection, rework and penalty costs) can be optimized by allocating different inspection strategies without compromising the quality of the final product. Inspection (Full, Sample, No inspection) is allocated at each station in such a way as to reduce the total inspection policy cost. As far as concerning tolerance stack-up which mainly depends on optimizing the limits (lower and upper inspection limits), the Genetic Algorithm is trying to optimize the limits as closely as possible to reduce the penalty cost. In multi quality characteristics problem if the part fails in any of the impacted quality characteristics, it goes for rework and reworks cost is added depends on part fails in which quality characteristics.
Debela Tesfay tadele (2019). Environmental Life Cycle Assessment of Biomaterials and Bio-Composites for Automotive Components: A Comparison between Talc and Biochar Reinforced Polypropylene Composites
The concern about the environmental impact such as global warming has driven the automotive part manufacturer in a paradigm shift from conventional fossil sources to renewable sources. In this study, the life cycle of miscanthus biochar (MB), as well as biochar and talc reinforced composites, have been evaluated, and the results are compared. The conventional material was chosen to be a talc reinforced polypropylene (talc-PP) at a 70% PP to 30% talc, and alternative bio-composite has MB reinforced PP (MB-PP) at a 70% PP to 30% MB by weight. The global warming potential (GWP) of the life cycle of MB is found to be 114.63 kg CO2 eq/ton. Miscanthus cultivation is the main contributor in the life cycle of MB (93.3 kg CO2 eq/ton) followed by pyrolysis (16.2 kg CO2 eq/ton) and transportation (4.8 kg CO2 eq/ton). This study also shows that MB reinforced composite had the least environmental impacts across all categories approximately by 25% compared to talc reinforced polypropylene composite. The main question addressed in this thesis is whether there are general environmental advantages of the use of MB-PP over talc-PP composites.
MOhammad Moein Jalalian (2018). Application of Metaheuristics in Scheduling Continuous/Semi-continuous Process Industries and a Case Study
In today's competitive industry, scheduling plays a significant role in improving the efficiency of manufacturing systems. Hence, many scholars and practitioners have been researching to enhance the quality of scheduling methods. In this research, the focus is on solving a real-world scheduling problem in the food industry which was previously dealt with a very time-consuming manual method without high-quality solutions. The problem is to find the best schedule for producing multiple products on multiple machines in a semi-continuous manufacturing system. Having a continuous section in the system makes scheduling too complicated than the manual method could deal with properly. So, similar to many scheduling problems, in this thesis, metaheuristics (GA and MPSA) are applied to the problem in order to address the defects of the manual method. Selected methods show promising results and performance against the manual method used before. Statistical analysis shows better performance of the genetic algorithm while the other method is more robust to the selected parameters.
Hayson C. H. Ko (2017). Permutation based Genetic Algorithm with Event-Scheduling/Time-Advance Algorithm as Decoder for a Flexible Job-shop Scheduling Problem
Today, numerous research support the growing scheduling problems that exist globally in competitive businesses. Scheduling needs to become efficient in order to remain relevant against competitors. Simulations need to provide results in short periods of time so that adjustments can be made and unnecessary costs can be avoided. Scheduling problems have become larger in size and greater in complexity given the rising product variations and increase in variety for manufacturing equipment. Hence, there is a practical need for genetic algorithms solving scheduling problems to be fast and versatile. This thesis introduces an event-scheduling/time-advance algorithm for the decoder to reduce the load on the genetic algorithm with a smaller global search space. Consequently, convergence can be reached sooner and larger problems can be tackled easily. The structure of this heuristic algorithm allows metrics to be easily implemented in order to give the user performance measures on the scheduling problem.
Fatemeh Mohebalizadehgashti (2016). Balancing, Sequencing and Determining the Number and Length of Workstations in a Mixed Model Assembly Line
In this thesis, a mathematical model and a linear programming embedded genetic algorithm is developed to solve an assembly line balancing problem. The mathematical model addresses a multi-model-product manual assembly line situation where the stations are interconnected by a continuously moving convey. The objective function is to simultaneously minimize the length and number of workstation, and the cost of assigning common tasks of several models of a product to more than one station. The mathematical model can also be adjusted to handle assembly lines served by intermittent synchronous conveyor which are common in automated assembly lines. An off-the-shelf optimization packages can be used to solve the model to optimality for medium size problems (up to 3 models and 40 tasks). For larger problems, we developed a linear programming embedded multi-phased genetic algorithm. The computational performance of the hybrid genetic algorithm is very encouraging based on the results obtained by solving arbitrarily generated large size problems.
Abenet Hodiya (2015). A Mathematical Model and a Simulated Annealing Algorithm for an Integrated Facility Layout and Cell Formation
In this thesis, we develop a mathematical model that integrates distributed layout and cell formation configurations in manufacturing systems. The proposed model incorporates a number of operational attributes such as sequence of operations, lot splitting, alternative process plans, and detailed relationships between pairs of locations along with material handling and product flow costs to determine Intra and Inter-cell layout configurations. Good solutions quality for the proposed mathematical model can only be found for small size problems because of NP-complexity. To solve the model for large size problems, an efficient simulated annealing algorithm is developed. A number of numerical examples of different sizes are presented to demonstrate the nature of the proposed model. In addition, some empirical studies to demonstrate the computational behaviors of the proposed solution procedure are presented.
Saber Bayat Mohaved (2014). Linear Programming Assisted Genetic Algorithm for Solving a Comprehensive Job shop Lot Streaming Problem
The hybridization of metaheuristics with other techniques for optimization has been one of the most interesting trends in recent years. The focus of research on metaheuristics has also notably shifted from an algorithm-oriented point of view to a problem-oriented one. Many researchers focus on solving a problem at hand as best as possible rather than promoting a certain metaheuristic. This has led researchers to try combining different algorithmic components in order to design algorithms that are more powerful than the ones resulting from the implementation of a pure metaheuristic. In this thesis, a linear programming assisted genetic algorithm is developed for solving a flexible job-shop scheduling problem with lot streaming. The genetic algorithm searches over both discrete and continuous variables in the problem/ solution space. Linear programming model is used to further refine promising solutions in the initial population and during the genetic search process by determining the optimal values of the continuous variables corresponding to the values of the integer variables of these promising solutions. Numerical examples showed that the hybridization of the genetic algorithm with the linear programming greatly improves its convergence behavior.
