Research On Flexible Job Shop Scheduling In Multi-Agent Environment

Job shop scheduling is a typical NP-hard problem and has always been a research hotspot.Genetic algorithm has the advantages of less computing time and high robustness,so it is one of the earliest and most commonly used intelligent optimization methods in the field of job shop scheduling research.In order to apply the genetic algorithm to the actual job shop,improve the processing ability of the genetic algorithm for complex job scheduling problems,and solve the problems such as crossover mutation probability and other algorithm parameters that need to be selected according to different algorithm evolution periods.Aiming at the scheduling requirements of multi-objective flexible job shop,this thesis establishes a flexible job shop scheduling system based on multi-agent,and analyzes the non-dominated sorting genetic algorithm(NSGA-Ⅱ)with elite strategy from the aspects of crossover,mutation operator and elite individual selection strategy is improved,and an adaptive NSGA-Ⅱ algorithm(ANSGA-Ⅱ)is established.Based on the self-learning and interactivity of agents,aiming at the functional requirements of the workshop scheduling system,a multi-agent flexible job shop scheduling system model is designed in this thesis.Three types of agents including management agent,scheduling agent and equipment agent are selected to realize the functions of each level of the flexible job shop scheduling system.Meanwhile,a multi-agent negotiation mechanism and scheduling strategy based on the contract network protocol are established.In order to facilitate the application of the NSGA-Ⅱ algorithm to the workshop scheduling system and solve the multi-objective FJSP scheduling problem,combined with the constraints of flexible job shops,a multi-objective FJSP mathematical model with maximum completion time,total delay time and total machine load as performance indicators is established in this thesis.In order to improve the adaptive ability of the algorithm,an adaptive crossover and mutation operator that dynamically adjusts the crossover and mutation probability parameters in different evolutionary periods of the algorithm is introduced,and an adaptive scale factor that dynamically filters the number of elite individuals entering the next generation parent population in each level of the population.The number of adaptive scale factors,the traditional NSGA-Ⅱ algorithm’s crossover mutation operator and the selection process of elite individuals are improved,and the ANSGA-Ⅱ algorithm is established.The simulation results of two groups of different scales and the performance comparison test results show that the ANSGA-Ⅱ algorithm is significantly better than the traditional NSGA-Ⅱ algorithm in the optimization effect of scheduling performance indicators,pareto solution set diversity and pareto solution set coverage,which improves the search performance,convergence and diversity of the algorithm.Based on the above theoretical research,combined with the actual needs of a machinery manufacturing branch,a small flexible job shop scheduling software prototype system is initially developed in this thesis.The system can provide workshop managers with a simple and effective decision support tool for production scheduling.