Research On Algorithms Of Generating Composite Dispatching Rule In Dynamic Assembly Job Shop Scheduling Problem

With the changes in the domestic and international economic environment,the manufacturing industry is facing unprecedented opportunities and challenges.In order to adapt to the new international situation and increasingly fierce market competition,the manufacturing industry has to undergo transformation and technological innovation.To improve their competitiveness,manufacturing companies are paying more and more attention to how to more effectively develop a satisfactory scheduling strategy for limited production resources and complex production activities in the production workshop.The problem of shop scheduling has become one of the hot areas of research in manufacturing companies.In the past few decades,the workshop scheduling problem has been extensively studied.Adding multi-level of assembly processes(just like tree structure)in classic Job Shop Scheduling Problem(JSP)becomes Assembly Job Shop Problem(AJSP),and AJSP AJSP is often encountered in real life.Dispatching rule is one of the effective methods for solving scheduling problems.This paper studies how to design excellent composite dispatching rules to solve dynamic AJSP.The main work is as follows:(1)A dynamic AJSP simulation model was Established.The multi-level "tree" structure jobs which included many assembly or sub-assembly operations and a lot of compoments was studied,and an assembly job shop based on discrete event simulation was constructed.Based on the queuing theory,the relationship between the interval of arrival time about jobs and the machine utilization rate was derived according to the formula.The traditional TWKCP workpiece due date setting criterion was introduced into the simulation model,a complete dynamic AJSP simulation model was constructed,relevant dispatching rules were input,and the corresponding evaluation index value was obtained by running the simulation model.(2)Three meta-heuristic algorithms were studied to generate composite scheduling rules.According to the characteristics of genetic programming(GP)algorithm and Gene Expression Programming(GEP)algorithm chromosomes,the idea of solving scheduling rules based on GP,GEP algorithm and their improved algorithm is proposed.Simulation experiments show that compared with the basic GP and GEP algorithms,the proposed adaptive GP and GEP algorithms can effectively avoid the premature phenomenon of the basic algorithm,enabling it to search for more excellent solutions and obtain the better compound dispatching rules.In addition to the above two algorithms,a method based on BP neural network to fit the shop scheduling system is proposed,and the method of simulating the input parameters of BP neural network by Simulated Annealing(SA)algorithm is applied.The network structure of BP neural network is determined experimentally.For the wellfitted BP network,the SA algorithm is used to solve the optimal input parameters,so that the BP network output is minimized,and finally a scheduling rule is obtained.(3)Using the Control Variable Method to compare the performance of the composite dispatching rules generating by the heuristic algorithm and simple dispatching rules.Following the principle of the Control Variable Method,the simulation experiment is carried out on the composite dispatching rules and simple dispatching rules by changing the random number seed,machine utilization rate and product type.Experiments show that the performance of the composite dispatching rules is much better than the simple dispatching rules,which indicates that the composite dispatching rules obtained by the heuristic algorithm have strong robustness and generalization ability.But when the evaluation index becomes the average delay time,the percentage of delayed products,and the average flowtime,the composite dispatching rule is inferior to the performance of the simple dispatching rule.This shows that the heuristic algorithm solves the composite dispatching rules with great pertinence.For a specific fitness function,excellent dispatching rules can be obtained.