Research On Multi-Objective Flowshop Scheduling With Batching Based On Evolutionary Algorithm

Flowshop Scheduling with Batching (FSB) problem is widely encountered in manufacturing industries with high complexity. Motivation for batching jobs is a gain in efficiency. The study on the FSB problem has not only the theoretical value but also the practical meaning. Evolutionary algorithm have incomparable advantages over traditional methods in solving multi-objective problems. Focused on multi-objective FSB problem, the topics researched in this thesis, and the innovations of our investigations are listed as follows:The FSB problem model with multiple objectives is established under the splitting the job groups. A multi-objective hybrid genetic algorithm (MOHGA) is designed for minimize the makespan and maximum tardiness.. Two new neighborhood structures based on the problem-concerned knowledge are defined, and a two-stage search strategy is used in the local search procedure to improve efficiency of optimization. The fitness assignment based on the double rank of the individual and its density value is conducted to preserve diversity of the solutions to ensure the convergence of the solutions. The effectiveness of the scheduling models and the high efficiency of the proposed methods are demonstrated by computational results and practical problem. By using the theory of finite Markov chain, the convergence properties of this algorithm are analyzed.The batch delivery FSB problem model with multiple objectives including earliness and tardiness is constructed. Firstly, the property of the problem to minimize total earliness/tardiness is analyzed. Secondly, the optimal scheduling method under given order sequencing is presented to minimize total earliness/tardiness, and algorithm incorporating the genetic algorithm is developed to search the best sequence, and influences of group technology assumption bring on optimization results is analyzed by the experiment. To solve influences of large-dimensional objective bring on optimization problems, a control weight evolutionary algorithm (CWEA) is presented which can dynamically adjust the evolutionary direct in evolutionary process to ensure the convergence and the diversity of the solutions.Aiming at the FSB problem with limited machine availability, according to the characteristics of the problem, a non-permutation schedule is used to reduce the idle time on machine. In this thesis, two cases of problem are considered. In the first case, availability time windows are fixed, while in the second one the availability time windows must be based on running time. A schedule generator that builds feasible solutions given a priority rule between jobs is developed, an improved control weight evolutionary algorithm (ICWEA) is applied to optimize the input sequence of the schedule generator. Simulation results and practical problem show that the ICWEA is a viable and effective approach in solving the problem.The multi-objective optimization of FSB problem with batching machines is considered. For a hybrid two-stage FSB problem with a batch processor in stage 1 and a single processor in stage 2, a batch scheduling heuristic is used to transform the permutations of jobs into batches, the ICWEA is applied to determine scheduling sequence preference. For a FSB problem with two batch-processing machines, a multi-objective hybrid particle swarm optimization (MOHPSO) is designed to solve problem with non-identical job sizes and batch processing times, and a neighborhood structure based on the batch-swap is used in the local search procedure. Simulation results show that the MOHPSO prior to other multi-objective particle swarm optimization algorithms for the two batch-processing machines with better performance.