Multi-Objective Shop Scheduling Algorithm Based On Particle Swarm Optimization

Recently, multi-objective scheduling is becoming a hot research topic of shop scheduling. Particle Swarm Optimization (PSO) algorithm is a simple and effective method, which simulates the activities of biologic colony. PSO algorithm's speciality of multi-point parallel search makes it be applicable to multi-objective optimization problem's solving. This work concentrates on three multi-objective shop schedulings based on PSO algorithm.Firstly, the three kinds of solving methods about multi-objective shop scheduling are introduced. The PSO algorithm is also introduced and its development are reviewed. The basic application of PSO algorithm and the research actuality of multi-objective PSO algorithm are summarized.Secondly, multi-objective Flow-shop Scheduling Problem (FSP) based on PSO is researched and PSO algorithm which competently solve multi-objective FSP is constructed. In the algorithm, PMX crossover operator is used to realize particle's renewal, vicinage framework (key path) based on scheduling problem is used to realize particle's local search, and inserting mutation operator is used to realize particle's random search. The algorithm's efficiency and superiority are indicated through experimental results.Thirdly, basing on multi-objective FSP has been solved, more complicated multi-objective Job-shop Scheduling Problem (JSP) based on PSO is researched and PSO algorithm that can solve multi-objective JSP is constructed. In the algorithm, crossover operator based on workpiece is used to realize particle's renewal, Tabu Search (TS) is used to realize particle's local search, and changing position mutation operator is used to realize particle's random search. This algorithm's feasibility and superiority are also validated through the experimental results based on normal testing problem.Fourthly, according to the experience of solving multi-objective JSP successfully, more complicated multi-objective Flexible Job-shop Scheduling Problem (FJSP) based on PSO is researched. Basing on the characteristic of multi-objective FJSP, Coding precept based on both working procedure sequence and machine assigning is designed. Crossover operator and mutation operator based on both working procedure sequence and machine assigning is also used as particle's renewal strategy and random search strategy. And TS is also used as particle's local search. So, the PSO algorithm which competently solves multi-objective FJSP is constructed. And its efficiency and advantage are also proved through experimental results.Finally, conclusion is drawn and the future research focus about multi-objective PSO and multi-objective shop scheduling is pointed out.