Research On Particle Swarm Optimization Algorithm Based On Flow Shop Scheduling Problem

With the development of economic globalization, the expansion scale of the production, and the increase of the product complexity. Which leads to the market competition more fierce. All of this are bring the serious challenge to the traditional manufacturing enterprise. Production Scheduling Problem is the core of the manufacturing enterprise, which is a major means of enterprise resource configuration and a key of the enterprise production and management technology. It has always been the hot spot of the production management research problem,Therefore, it is significance both in theory and engineering applications to develop effective and efficient novel solution techniques to solve such problems.Flow Shop Scheduling Problem(FSP) is a typical of widely studied scheduling problems,it was an abstract model which based on the special practical production problem, It focused on the processing order of the job in the machine that has been one of the considerable researches, in order to find the best solution which based on some optimization functions for the scheduling problem. Permutation Flow Shop Scheduling Problem(PFSP)is a kind of a simplified model, which abstracts from the field of real production scheduling. It was built on the foundation of the FSP that added new constraints, and demands the processing sequences of all jobs are the same on each machine. which has engineering background and been proved to be an NP-hard problem.Particle swarm optimization(PSO) algorithm is a novel computational evolution algorithms, it was an global optimization method which was inspired by the biological social behavior, the characteristic of this algorithm is simpler, less parameters, easy implementation, good robustness, etc. Therefore, it has been widely used in many optimization research as an global optimization search algorithm, and also has been used with great success to many scheduling problems. But the PSO algorithm exists this phenomenon that emerge premature convergence, and easily to fall into local extreme. Therefore, PSO algorithm that applied to production scheduling problem research work still need to further exploration.In order to solve the PFSP, according to minimize the maximum completion time(Makespan). We take the PSO algorithm as the basic solution, combined with other intelligent optimization algorithms and optimization strategy, then we put forward two kinds of hybrid particle swarm optimization algorithm: The first hybrid PSO algorithm which based on the self-adaptively method that take the famous heuristic NEH algorithm which used to initialize the extreme values of the global particle. After that,we take some optimized strategy which based on random self-adaptively strategy for setting this parameters. The second hybrid PSO algorithm which based on the local search strategy that add a Dynamic Disturbance Term(DDT) in the velocity updating formulation of the particle, in order to avoid this volatility phenomenon that appeared in the later. A local search based on crossing-over operation for the changed local particle. The destruction and construction operation of Iterated Greedy(IG) method which be used to mutate the global particle, in order to find the better neighborhood, the SA strategy employs certain probability to accepted the new particles which being mutated.Combined with the new optimized strategy and method, then we put forward an immune PSO algorithm, the Immune PSO(IPSO)takes the Immune Algorithm(IA), and the immune selection and vaccination operation are used to strengthen the global search ability of the algorithm, the particle swarm as the antibody swarm which through the immune selection to choice the particles of the next generation, the global particle as the memory cells which was storage the memory bank. The Simulated Annealing(SA) algorithm is adopted in the vaccination operation to restrain the degenerate phenomenon. The three kinds of hybrid PSO algorithms are simulated in the Matlab simulation experiment, and the experimental results verify the effectiveness of those hybrid algorithms.The No-Idle Flow Shop Problem(NIFSP) is the classical special case in FSP. It not allow to exist the waiting time once the machine begin to work. This kind of constraints reduced the operation cost of the machine from a certain extent, it also improve the efficiency of the production for the company. This scheduling problem is more closely to the actual production process, so it has more applicable than others. In order to solve the NIFSP, we put forward a chaotic PSO algorithm, the initial solution of the global particle extreme is generated by the famous heuristic NEH algorithm. And we add a DDT in the velocity updating formulation of the particle, it used to prevent optimizing course from trapping the local minimum. During the running time, a chaotic control strategy is incorporated into PSO algorithm which be used in the global optimal particle searching, it provide uncertain randomly strategy to search the better particle around the area in the global particle, for enhance the global search ability of the algorithm. At last, simulated results demonstrate that the hybrid PSO method is feasible and effective for the problem.