Font Size: a A A

Study On Intelligent Optimization Algorithm For Solving Flexible Job Shop Scheduling Problem

Posted on:2017-08-14Degree:MasterType:Thesis
Country:ChinaCandidate:T ZhangFull Text:PDF
GTID:2348330488482278Subject:Computer Science and Technology
Abstract/Summary:PDF Full Text Request
Job-shop scheduling problem is a typical combinatorial optimization problem, and the purpose is to meet some performance indicators through the rational arrangement of various productive resources. It is the core factor for manufacturing enterprises to survive and improve market competitiveness. Flexible job-shop scheduling problem is different from the traditional job-shop scheduling problem, and it increases the flexibility of the machine, so that it is more close to the reality of the enterprise production mode. So, research on it has more practical application value. In this paper, a latest swarm intelligence optimization algorithm which is bat algorithm as optimization algorithm. It is used to optimize the single objective and multi-objective for flexible job-shop scheduling. The main works are as follows: first of all, a systematic exposition is given for flexible job-shop scheduling which included the concept, classification, characteristics and performance. Then, the bat algorithm is analyzed in details which included the bat echolocation behavior, the acoustic principle, hypothesis, variable update rules, algorithm flow and binary bat algorithm. And then, studies on the application of the bat algorithm and its improved algorithm in flexible job-shop scheduling. At last, the main results and prospects are given. Details of the work are summarized as follows:(1) Using the basic bat algorithm to solve the single objective flexible flow shop scheduling problem(FFSP). In order to make the bat algorithm to solve the discrete combination optimization problem, a discrete bat algorithm is proposed according to the research on the idea of basic bat algorithm. First of all, the mathematical model is constructed. Then, a strategy of double layer coding based on the priority of working procedure and work piece is given based on the in-depth study of the characteristics of the bat algorithm and FFSP. And then, the workpiece and process correlation matrix, the workpiece process matrix, temporary resource pool matrix and resource state matrix are defined, in order to express the information of the workpieces, processes, machines, processing time and processing status. The algorithm redefines the operation of position and velocity to realize the move ment of bat individual in the search space. At last, the simulation results of three sets of actual production scheduling data are carried out. The experimental results show that the proposed algorithm has higher accuracy and is an effective optimization a lgorithm, which provides a new way and method for FFSP.(2) Aiming at the shortcomings of low accuracy and local exploration ability of the bat algorithm for solving flexible job-shop scheduling problem(FJSP), an improved bat algorithm is proposed based on the depth study on the bat algorithm for FJSP. First of all, four operations which are insertion, inversion, crossover and mutation are defined in order to enhance the search ability of the population neighborhood and jump out of the local optimal solution. Then, readjust the value of inertia weight in order to overcome the shortcomings of the fixed parameters from the basic bat algorithm. The inertia weight strategy is used to make the population reasonably control the global search ability and local exp loration ability. At last, the effectiveness and superiority of the improved algorithm are verified by the actual production workshop scheduling data.(3) A hybrid discrete bat algorithm is proposed to solve the multi-objective flexible job shop scheduling problem. First of all, the multi-objective FJSP model is established by considering the target of the maximum completion time, processing cost and processing quality. Then, a strategy of process sort and machine selection encoding are given according to the processing time, processing cost, processing quality and machine information. The encoding method not only gives the sequence of the various parts of the process, but also gives the processing machines of each process selected. And then, a priority assignment rule is proposed based on the analysis of the initial selection of the machine and the scheduling of each process in order to improve the quality of the bat algorithm initial population. At the same time, the position variation strategy is adopted in order to search the optimal position in the shortest possible time. Finally, simulations and results indicate that the hybrid bat algorithm has better feasibility, effectiveness and superiority.(4) In order to solve the problem of multiple workpieces on the machine in parallel processing, a clock algorithm is first proposed to calculate the target value of FJSP.
Keywords/Search Tags:Flexible Flow-shop Scheduling, F lexible Job-shop Scheduling, Bat Algorithm, Optimization Algorithm, Clock Algorithm, Mulit-objective Optimization
PDF Full Text Request
Related items