Research A Hybrid Particle Swarm Optimization Algorithm For Permutation Flowshop Scheduling Problem

Scheduling in manufacturing industry plays the role of planning in production process. Proper and effective flowshop scheduling can help the enterprise to save time, decrease storage, guarantee due date and improve the production efficiency. With fierce competition in global markets and the increasing customer demand for personalized and diversified, scheduling attracts more and more attention. Permutation flowshop scheduling problem (PFSP) is one common and important scheduling problem. A hybrid particle swarm optimization (PSO) was proposed in this paper to solve single objective PFSP. Meantime, based on solving PFSP, deep research about handling multi-objective PFSP (MPFSP) was developed.Firstly, the aim and significance of this research work are given. Then, A comprehensive review of both former and the state-of-the-art approaches on PFSP and MPFSP was introduced. Meantime, future research trends and challenges in this field were analyzed.Secondly, a hybrid PSO, named NE-HPSO, was proposed to solve PFSP with minimization of makespan. NEH algorithm was taken to produce high quality initial solutions. An improved solution representation rule, smallest position value (SPV), is used to present solutions. Variable neighborhood search (VNS) algorithm is combined with PSO to enhance the local search ability. Two effective neighborhood structures concerned with characteristics of PFSP have been adopted to enhance the performance of VNS. Computational experiments have been conducted on benchmarks (Taillard's instances) and comparison results with other existing algorithms show the efficiency of the proposed algorithm.Thirdly, research on MPFSP was based on the research of PFSP. Considering the characters of three objectives solved, four constructed methods, NEH,SPT,EDD and CDS was used to improve the quality of inintial solutions. Meantime, a method based on distance was used to keep the diversity of solutions. To improve the performance of PSO, Pareto solutions were stored in a special elite set. What's more, a vibrate procedure was adopted to enhance the search exploitation of searching optimal solutions for MPFSP. Then comparison of performance between Strength Pareto Evolutionary Algorithm2 (SPEA2) and this proposed was given based on Taillard's tests.Finally, a software prototype system for solving PFSP and MPFSP was developed with MFC in Visual C++ language based on the previous chapters. Conclusions of the paper as well as the future perspectives of PSO for PFSP were discussed.