基于Petri网和人工势场的柔性制造启发式优化方法

制造系统优化调度是NP难组合优化问题,而自动导引车(AGV)路径规划与任务分配紧密耦合,又极大加剧了问题的复杂性.基于此,提出一种基于Petri网和人工势场的启发式优化方法.首先,将制造系统的工艺工序描述为一个任务Petri网,将AGV系统描述为一个路径Petri网,将两个网合成在一起;然后,利用Petri网的拓扑结构,为网络结点设计势能参数,从而为Petri网赋予一个人工势场;接着,利用人工势场设计制造系统加工时间的启发式函数,并构建Petri网人工势场启发式A*算法,其中包括最大势差启发式函数和总体势差启发式函数,并验证最大势差启发式函数是可采纳的;最后,进行两组数值实验,实验结果表明,最大势差A*算法能够得到最优解,且平均计算效率比Dijkstra算法提高57%,但是无法满足大任务量的调度需求,而总体势差A*算法比最大势差A*算法平均计算效率提高至少1个数量级,能够在有限时间内求解AGV任务分配和路径规划的联合问题.

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.