Research On Shuffled Frog Leaping Algorithm And Its Application To Permutation Flow-shop Scheduling Problem

Flow-shop production model has been widely used in modern manufacturing enterprise, so scheduling is a common problem in manufacturing flow-shop and is a hot issue in workshop scheduling research. The solution of this problem has both academic and practical value. In a practical environment, proper and effective flow-shop scheduling can help the enterprise improve production level, save time and meet the customer diversification demand. In theory an effective solution to the combined optimization problems also has a strong significance on other optimization problems.In this research, an advanced Shuffled Frog Leaping Algorithm (SFLA) is proposed, which aims at solving Permutation Flow-shop Scheduling Problem (PFSP) to minimize make span. To make the research more universal and representative, a Multi-objective SFLA has been designed to solve the Multi-objective PFSP (MPFSP).Firstly, a systematic representation of the optimization principle, operation process of SFLA, and its application in different optimization areas is presented. Since SFLA suffers from weak local search ability, it is improved through a new individual update strategy combined with particle swarm optimization (PSO). To verify the validity of the improved algorithm, functional optimization problems are solved. The results show that the convergence velocity of improved algorithm is better than the original SFLA and PSO.Secondly, the advanced SFLA is used to solve PFSP aiming at minimization of make span. The algorithm is modified by using the rule of random key representation in designing arithmetic coding, to solve the discrete and combinatorial optimization problems. At the same time, diverse initial solutions are created by improved NEH heuristic algorithm to improve the quality of the initial solution. Reversibility principle of PFSP is used to calculate make span in less time. The advanced SFLA is compared with other algorithms, and it proved to be a successful way for solving this problem.Afterwards, MPFSP is modeled with optimization objective of minimizing total flow time, make span and tardiness time, and it is solved by the designed Multi-objective SFLA. In the algorithm, high-quality initial solution is created by four heuristic algorithms; elitist solution set is set up to store Pareto solution and update it with adaptive niche method. Compared to the other algorithms, the advanced SFLA provided a better solution to this problem.