Research Of The Dynamic Job Scheduling Problem Of Automatic Guided Vehicles Based On The Hypergraph

Nowadays, with the rapid development of Automatic Logistics System, Flexible Manufacturing System(FMS) and automatic three-dimensional storage, Automated Guided Vehicle system(AGVs) has been increasingly widely used. As an important means of flexible production, it plays an important role in the production system. Taking the place of the traditional transportation such as manual labor, trailer and conveyor belt,and with no limitations as traditional workshop logistics had, AGVs has cut down on the cost of manual labor, provided a convenient way for the automatic management and at the same time raised the flexibility of the system and improved enterprises’ benefits.The application of AGV should take account of its whole system. In terms of the system,AGV path planning and the impingement of multiple AGV seems quite crucial. Path planning is a basic sector of AGV navigation. Based on the science and technology planning project in Liaoning Province--Provincial Key Lab Construction of Integrated Automation on Equipment Manufacturing and the market’s practical needs of AGV, the paper will study AGV path planning algorithm in the FMS. The study of path planning of AGV system will be carried on with its theoretical and practical points. The study is mainly about:(1) The AGV runtime environment is abstracted into a weighted digraph.And the theoretical reserves on graph theory.It on acyclic weighted digraph establishes path planning model.The path planning model is based on Hypergraph using genetic algorithm,and it carries out simulation analysis.(2) The study on Single AGV path planning in the FMS will be carried on the basis of graph theory. Directed graph algorithm will be selected for AGV path planning by the analysis of the Dijkstra arithmetic, A* arithmetic and the features of path planning method of minimal algebra. Minimal algebra will be used to solve the single AGV path planning problem. It is more suitable for its practical application because the practicalrunning condition is taken into account.(3) After the study of the conflict and deadlock problem of multiple AGV system,dynamic path planning algorithm based on the time widow is put forward. It can effectively avoid conflict and collision problems between cars and can provide time optimal path. By the update of time window and time calculating, several cars running at the same time can be realized without conflict with each other. Simulation experiment shows that the algorithm has a good effect, because in most cases it can solve AGV path planning problems and the algorithm is feasible and correct.