Solving Hybrid Flow-shop Scheduling Problem By Two-phase Force Particle Swarm Optimization Algorithm

Aiming at reasonablly allocating the workpiece and the parallel machines in each process based on limited production resource conditions, hybrid flow-shop scheduling problem(Hybrid Flow-shop Scheduling Problem, HFSP) is an extension of the traditional flow-shop scheduling problem. And the difference between the traditional flow-shop scheduling problem and the HFSP is that HFSP has multi-process and there is at least one process in parallel machines, so it has a strong engineering application background. In addition, in a lot practical productions, the buffer space or storage device between each machine is limited, which has a great impact on effective production. Therefore, it has an important theoretical significance and engineering application to study the HFSP.It has confirmed that the HFSP has a strict NP-hard nature, so it is very difficult to get an accurate solution and the conventional method is much harder for solving the HFSP. As a kind of efficient swarm intelligence optimization algorithm, particle swarm optimization algorithm has been successfully used in solving complex optimization problems, which shows its strong adaptability and a good global search capability that are helpful to solve the HFSP. Therefore, in this article, particle swarm optimization algorithm is studied and improved aiming at solving the HFSP, and algorithm is designed for solving the HFSP, which can improve the algorithm’s performance. Main work includes the following three aspects:Firstly, the particle swarm optimization algorithm is summarized and analyzed. Aiming at the shortcomings of the existing particle swarm optimization algorithms, two kinds of force rules are constructed again referencing the attraction and repulsion ideas in arti?cial physics. For the aboves, a novel two-phase force particle swarm optimization algorithm based on staged search strategy is proposed and a new intelligent switching method is designed for switching between the different stages. Through the tests on the proposed algorithm and compared with other particle swarm optimization algorithms, the results show that the proposed algorithm has a better optimization performance.Secondly, according to the characteristics of the HFSP, as well as when the particle population is initialized, less good individuals are produced, illegal solutions are easy to get and decoding the particles is complex and so on, a new encoding and decoding method based on matrix is adopted. Compared with results in the literature and other improved particle swarm optimization algorithms, it is confirmed that the proposed algorithm can effectively solve the HFSP.Finally, an idea that hybrid flow-shop scheduling problem with blocking(Hybrid Flow-shop Scheduling Problem with Blocking, HFSP-B) is applied to one train scheduling problem is put forward, through discussing the HFSP-B. To consider the effect of blocking for the HFSP, another mathematic model is drawn on and applied to the train scheduling problem. For the characteristics of the mathematic model and particle swarm optimization algorithm, the decoding method of the particles is designed again and the particle adjustment is added to eliminate the imbalance in the machines or orbitals distribution. Through the experiments and comparative analyses, it has been demonstrated that the above method in this paper is effective and feasible to sovle the train scheduling problem on double-track line.In conclusion, the research of the HFSP as a main line in this article, scheduling algorithm, scheduling with blocking and train scheduling are studied in order to provide a new way for solving scheduling problems, and make the scheduling theory can be more practical. Meanwhile, these can achieve the optimal allocation of resources in production to reach energy saving and emission reduction, and provide a theoretical basis for the decision-makers.