Research On Path Planning For Job-shop Obstacle Diagram Model And Scheduling Optimization

In order to accelerate the development of intelligent manufacturing,taking workshops and factories as manufacturing carriers and accelerating the development of system integration technology is one of the key tasks,which is pointed out in the "14th Five Year Plan for the Development of Intelligent Manufacturing".At the same time,"planning and scheduling" and "dynamic production planning and scheduling in complex environments" are taken as key core technologies.Intelligent manufacturing cannot do without intelligent decision-making,and workshop scheduling technology is an indispensable part of workshop intelligent system decision-making,directly related to the issuance of production instructions.There are various types of workshop scheduling techniques,among which Job-shop scheduling problem(JSP)is known as the most basic and famous scheduling problem,and it is also an NP Hard problem.Therefore,the research of JSP has high theoretical significance and practical value,which is in line with the current national situation of vigorously developing intelligent manufacturing.The first chapter of this article introduces the research background and significance of the topic,summarizes the current research status of JSP problems,and analyzes the shortcomings of existing problems: 1)the multi-job obstacle diagram model has a time-consuming problem in finding the shortest path;2)The problem of fusing search scales at the job and operation levels.Therefore,based on the above two points,the research content of this article is proposed.In the second chapter,JSP problem,mathematical model,disjunctive graph model and obstacle diagram model are introduced.Neighborhood search algorithm,tabu search algorithm and fireworks algorithm are following,which lays the foundation for the subsequent chapters.Firstly,the multi-job obstacle diagram model is introduced and the time-consuming problem of finding the shortest path is explained in chapter 3.Then,a review was conducted on the existing two-job obstacle diagram path planning algorithms,and the advantages and disadvantages were analyzed.Secondly,a new path planning algorithm is proposed for multi-job obstacle diagram.The research on this algorithm includes: 1)simplifying obstacle diagram using layered methods;2)Design node extension methods;3)Design a fast distance evaluation formula;4)Integrate A * algorithm.Finally,the effectiveness of the proposed algorithm was verified through 242 benchmark instance tests.In the fourth chapter,two hybrid algorithms are designed for the fusion of the search scale at the job-level and the operation-level: 1)A hybrid algorithm based on the obstacle diagram model and tabu search is proposed.This algorithm realizes the job-level scale search by using the path planning algorithm and designing the neighborhood solution generation method in the obstacle diagram model.In the tabu search algorithm,the neighborhood structure is used to realize the mobile operations search.By mixing two algorithms,collaborative search at the joblevel and operation-level scales is achieved.Through testing with 53 benchmark examples,the experimental results reached or exceeded the level of the comparative algorithm.2)In view of the limitations of individual search,obstacle graph model and Tabu search algorithm,a hybrid algorithm with more comprehensive search performance is proposed.The hybrid of the three algorithms uses the group iteration search method,which makes the global search and local search more balanced.Through 60 benchmark questions,including the more difficult ABZ and YN benchmark questions,the experimental results verify the effectiveness of the algorithm.Chapter 5,based on the theoretical research results mentioned above,introduces the developed prototype system for job shop scheduling with a case study.Chapter 6 summarizes and prospects the entire work.