Font Size: a A A

General Particle Swarm Optimization Algorithm And Its Application To The Job Shop Scheduling Problems

Posted on:2007-12-30Degree:MasterType:Thesis
Country:ChinaCandidate:C Y PengFull Text:PDF
GTID:2178360242961055Subject:Management Science and Engineering
Abstract/Summary:PDF Full Text Request
Particle Swarm Optimization (PSO) algorithm is based on swarm intelligence theory. The algorithm can provide efficient solutions for optimization problems through intelligence generated from complex activities such as cooperation and competition among individuals in the biologic colony. Firstly, the basic PSO is introduced and its developments are reviewed. The basic applications of PSO are summarized. Secondly, the optimization mechanism of the traditional PSO is analyzed and a general particle swarm optimization model is proposed.Thirdly, according to the general particle swarm optimization model, a General Particle Swarm Optimization (GPSO) algorithm is designed to solve the Job-shop Scheduling Problem (JSP). In the algorithm, crossover and mutation operations in Genetic Algorithm (GA) are respectively utilized by particles to exchange information and search randomly. Besides, Tabu Search (TS) is used for particles'local search. To control the local search and convergence to the global optimum solution, time-varying crossover probability and time-varying maximum step size of TS are introduced. The experimental results show that JSP can be solved by the GPSO algorithm effectively. The feasibility of the proposed optimization model is also demonstrated.Fourthly, another GPSO algorithm is presented to solve the Flexible Job-shop Scheduling Problem (FJSP). FJSP is extended by the classical JSP and it is more difficult to be solved. In this algorithm, particles'coding method and Tabu Search strategy are designed separately according to the characteristics of the FJSP. GPSO is tested on two groups of benchmark problems and the experimental results show that FJSP can be solved by the algorithm effectively. The effectiveness of the general particle swarm optimization model is also validated.Fifthly, two scheduling tools GPSO2JSP and GPSO2FJSP are developed separately. GPSO2JSP is to solve the JSP with GPSO. GPSO2FJSP is to solve the FJSP with GPSO.Finally, conclusion is drawn and the future research focus is pointed out.
Keywords/Search Tags:Particle Swarm Optimization, General Particle Swarm Optimization, Job-shop Scheduling, Flexible Job-shop Scheduling, Genetic Algorithm, Tabu Search
PDF Full Text Request
Related items