Research On Cultural Algorithm In Flexible Job-shop Scheduling Problem

Under the opportunities and challenges brought by the "industry 4.0" and "Made in China 2025",workshop scheduling once again become the focus of manufacturing again.The production mode of " Multi-species,Small quantities,Customization "impels the enterprise to adjust its scheduling correspondingly,which requires a more flexible and agile manufacturing workshop in response to the changing demand in the market.In fact,the production system is only partially flexible,and enterprise need to take multiple scheduling objectives into account in the process of production.Thus,it's an imperative problem should be solved that to be flexible and multi-objective in workshop scheduling process.Therefore,this paper presents a cultural algorithm that integrates the genetic algorithm and variable neighborhood search to solve the multi-objective flexible job shop scheduling problem,which can balance global exploration and local exploitation effectively.Firstly,in this algorithm,the selection process is guided by the situation knowledge of belief space.The chromosomes are selected by the combination of tournament selection and optimal individual retention.The next is to select chromosomes offspring randomly and to compare with the excellent chromosomes in situation knowledge by hamming distance.Then the chromosomes with the lowest similarity were replaced by excellent chromosomes.This process can increase the probability of genes with excellent traits in the offspring,and then improve the convergence speed and convergence quality of the algorithm.Secondly,in this algorithm,the mutation probability is dynamically adjusted by the terrain knowledge in the belief space,which records the distribution of excellent individuals.When the number of non-dominated solutions of a unit in the terrain knowledge reaches the threshold,the mutation probability of the mutation operation is dynamically adjusted by the influence function.This process can maintain population diversity,expand the search range of the mutation process,and prevent the algorithm trapping into local optimal prematurely.In addition,in order to improve the convergence speed and quality of the algorithm,three neighborhood structures based on the optimized objective function and the critical path theory are proposed in this paper.On one hand,the initial population of the variable neighborhood search is derived from the superior individuals of the population space,which makes up for the defect that the final solution quality depends on the initial population quality.On the other hand,the local search ability is further enhanced by the systematic change of the three neighborhood structures.Finally,in order to verify the feasibility and effectiveness of the algorithm,a number of experimental examples were tested on 13 standard examples and 320 experimental results were obtained.The results show that the three neighborhood structures proposed in this paper can improve the quality of the algorithm.Compared with the experimental results proposed by other scholars,the higher quality Pareto solution is obtained in most case which proves that the cultural algorithm can effectively solve the multi-objective flexible job shop scheduling problem.