Research On Comprehensive Scheduling Method Of Product Processing And Assembly Based On GA

Production scheduling is a key factor affecting the production efficiency of enterprises.Reasonable and orderly scheduling can effectively shorten the production cycle,improve the utilization of equipment,and reduce the inventory of in-process products and capital occupation,thereby enhancing the competitiveness of enterprises.There are many kinds of production scheduling and various solving methods.Among them,the traditional job shop scheduling problem(JSP)is the most basic and famous machine scheduling problem.At the same time,it is also a typical NP-hard problem.It has been widely studied by scholars at home and abroad for decades,and has promoted the development of a large number of algorithms,such as genetic algorithm(GA),tabu search algorithm,simulated annealing algorithm,shifting bottleneck procedure(SB),neighborhood search and related hybrid algorithm.The traditional JSP is only for the processing stage of the product,regardless of its assembly stage,and is suitable for mass production of the same product.The product processing and assembly comprehensive scheduling problem(product comprehensive scheduling problem)studied in this paper will be considered together with the processing and assembly process.It is suitable for multi-variety and small-batch production processes,and can quickly respond to the increasing demand for personalized products in society.Its research has strong practical significance.At the same time,the product comprehensive scheduling problem as an extension of the JSP is also a typical NP-hard problem.Research on JSP problems has accumulated a large number of efficient methods.However,the research method of product comprehensive scheduling problem is still not mature.The reason is that the product comprehensive scheduling problem has more complicated assembly constraint relationship than the JSP,which leads to the failure of various existing coding technologies and local search guarantee technologies.Therefore,it is urgent to study the efficient solution method of product comprehensive scheduling problem.Firstly,this paper reviewed the research status of product comprehensive scheduling problem,summarized and analyzed the shortcomings of existing research methods,and then put forward the research content of this paper.By analyzing the optimization objectives commonly used in traditional JSP,and combining the product operation tree,the mathematical model of product comprehensive scheduling problem was given.The basic flow and characteristics of the algorithm of basic GA and SB were expounded respectively,which layed a foundation for the improvement of subsequent GA and SB.Aiming at the shortcomings of the virtual component level division coding method proposed in the literature,a coding method based on the operation constraint chain was designed to make up for its shortcomings,and the active decoding with the constraints of job processing assembly order was given.For the infeasible solutions generated by the crossover and mutation operations,a repair method based on adjacency matrix was designed.Then a GA based on operation constrained chain coding was proposed.The experimental results verified the effectiveness of the proposed algorithm.In order to make up for the shortcomings of the single algorithm and further improve the performance of the algorithm,a hybrid solution method based on the improved extended shifting bottleneck procedure(i-ESB)and GA was proposed.Hybrid genetic algorithm(HGA)uses GA based on operation constraint chain coding to achieve global search,and implements local search based on i-ESB.In the improved research of extended shifting bottleneck procedure(ESB),the extended disjunction graph model(EDG)corresponding to the product comprehensive scheduling problem was given.The calculation method of the head and tail length of the operations based on the EDG and the searching method of the key operations were studied.The Schrage algorithm with disturbance was used to solve the single machine scheduling sub-problem and the selection criteria of the bottleneck machine was added.A greedy bottleneck machine re-optimization process was designed.The effectiveness of the i-ESB and HGA were verified by testing and analyzing the related examples given in the relevant literature.Finally,on the basis of the above theoretical research results,we developed a prototype system of product integrated scheduling software with a practical case.The application background,system development environment and main functional modules of the prototype system were introduced.The system operation process was briefly introduced by testing an actual case,and the effectiveness of the prototype system was verified.