Heuristic optimal method of flexible manufacturing based on Petri nets and artificial potential field
The optimal scheduling of manufacturing systems is a NP-hard combinatorial optimization problem,and the tight coupling between the automated guided vehicle(AGV)path planing and task allocation intensifies its complexity.To address this issue,a heuristic optimization method based on Petri nets and artificial potential fields is proposed.First,the processes of a manufacturing system and the AGV system are described as a task Petri net and a path one respectively,which are then combined.Second,the potential energy parameters of the net nodes are designed using the topology of Petri nets,thereby assigning an artificial potential field to the Petri net.Third,two heuristic functions are designed using artificial potential fields,including a maximum-potential-difference heuristic function and a total-potential-difference one,and the corresponding A*algorithm is constructed.Experimental results show that the maximum-potential-difference heuristic function is admissible.Finally,two sets of numerical experiments are performed to show that the maximum-potential-difference A*algorithm can obtain the optimal solution,and the average computing efficiency is 57％higher than that of the Dijkstra algorithm,but it cannot meet the requirements of large task quantity scheduling,while the total-potential-difference heuristic A*algorithm is at least one order of magnitude more efficient on average than the former algorithm that can solve the joint problem of AGV task allocation and path planning in a limited time.
Petri netartificial potential fieldA*algorithmoptimal schedulingflexible manufacturing system
NETL
NSTL
万方数据
