Font Size: a A A

Research On Swarm Intelligent Optimization Algorithm For Flexible Job Shop Scheduling

Posted on:2012-11-28Degree:DoctorType:Dissertation
Country:ChinaCandidate:L LiFull Text:PDF
GTID:1118330374971412Subject:Mechanical design and theory
Abstract/Summary:PDF Full Text Request
With global market competition intensified, in order to enhance the competitiveness, enterprises need to design reasonable scheduling schemes to satisfy demands of customer for diversification and personalization, improve customer satisfaction, shorten production cycle and deliver just-in-time. Job-shop scheduling system becomes more flexible with the enhancing of route flexibility, and it also makes flexible job-shop scheduling as one of the most difficult problems in combinatorial optimization problems. For the need of production, flexible job-shop scheduling problems usually make optimization decision according several objectives. So, it is of important theoretical value and practical significance to carry out deep research on effective methods for solving multi-objective flexible job-shop scheduling problem.In this dissertation, the improvement and fusion of swarm intelligent optimization algorithms are studied and these algorithms are applied to solve flexible job-shop scheduling problems. The main researches are as follows.The classical ant colony algorithm is improved and applied to solve single-objective flexible job-shop scheduling problem. In the improved ant colony optimization algorithm, the number of subsets is defined according to the number of jobs and the local search method in the period of path construction is designed. To avoid early stagnation state, rule of trail intensity update is adopt. The problem of parameters'setting is discussed. According to the scale of problem, reasonable parameters setting is given to balance capacity of global search and fast convergence. Satisfactory results are obtained through algorithm experiments.According to research on mathematical model and optimization method of multi-objective FJSP, further improvement for ant colony optimization algorithm is made based on the redesign of local heuristic information. The optimization objective of the improved algorithm is to obtain the balanced minimum of make span, total machine load and bottle-neck machine load. The algorithm is applied to solve multi-objective FJSP and validated by experiments.The traditional PSO algorithm is improved and applied to solve single objective FJSP and multi-objective FJSP. In he improved PSO algorithm, global research capacity of algorithm is enhanced by theory of population evolution and the strategy of self-adaptive parameters based on chaos. Local research capacity of algorithm is enhanced by importing local search based on chaos. The improved algorithm can reduce the possibility of falling into the local extremum for traditional PSO. Therefore the solution quality, search efficiency and convergence rate are all enhanced. Finally, capacity of the algorithm is validated by standard instances of8X8partial FJSP with27operations and10X10total FJSP with30operations.In order to overcome the shortcomings exist in simple optimization algorithm, a hybrid of ACO and PSO is designed to provide more powerful search capability. According to character of multi-objective FJSP, two stage ant particle optimization algorithm (TSAPO) is put forward on the basic of the previous improved ant colony optimization algorithm and the improved particle swarm optimization algorithm. In TSAPO, the multi-objective optimization is realized by decomposition method through two stages. In the ant colony optimization algorithm, through the processing machines'extract graph model, the minimum of workload for total machine and bottle-neck machine can be realized in the first stage on the basic of improved ant colony algorithm and the redesign of ants transfer probability. In the second stage, the minimum of make span is realized on the basic of improved particle swarm optimization algorithm and the design of decoding of particle swarm. Simulation experiments show TSAPO algorithm has a good solution performance in solving multi-objective FJSP.
Keywords/Search Tags:Flexible Job-shop Scheduling Problem, Multi-objective Optimization, AntColony Optimization Algorithm, Particle Swarm Optimization Algorithm, Two Stages AntParticle Optimization Algorithm
PDF Full Text Request
Related items