Symbolic Scheduling of Robotic Cellular Manufacturing Systems With Timed Petri Nets
Symbolic Scheduling of Robotic Cellular Manufacturing Systems With Timed Petri Nets
复制标题
具有定时 Petri 网的机器人细胞制造系统的符号调度
DOI：
10.1109/tcst.2021.3123963
复制
发表时间：
2022-01-04
影响因子：
4.8
通讯作者：
Zhou, MengChu
中科院分区：
文献类型：
--
作者：
Huang, Bo;Zhou, MengChu
为了减少基于Petri网（PN）可达图的机器人单元制造（RCM）系统调度中的计算负担，现有方法主要集中在以调度最优性为代价的图搜索算法的松弛。与此不同的是，本文提出了一种方法，通过使用符号表示和操作来加速搜索过程。所提出的方法使用二元决策图（BDDs）功能表示和发展离散和位置定时PN的RCM系统，然后调度它们与符号A* 搜索找到一个最小的最佳解决方案，最大完工时间。它使用紧凑的BDD结构来表示状态集，而不是单个状态，然后执行有效的布尔操作来进化网络并搜索系统调度。提出了一种启发式函数及其布尔实现的符号A* 搜索。所提出的启发式函数的可接受性证明，这保证了所获得的调度的最优性。因此，在不牺牲调度最优性的情况下减少了计算时间。最后，通过实验验证了该方法的有效性.
To reduce the computational burden in the scheduling of robotic cellular manufacturing (RCM) systems based on Petri nets' (PNs) reachability graphs, existing methods mainly focus on the relaxation of a graph search algorithm at the cost of schedule optimality. Different from that, this article presents a method that accelerates the search process by using symbolic representations and manipulations. The proposed method uses binary decision diagrams (BDDs) to functionally represent and evolve discrete and place-timed PNs of RCM systems and then schedule them with a symbolic A* search to find an optimal solution with minimal makespan. It uses compact BDD structures to represent sets of states, instead of individual states, and then performs efficient Boolean manipulations to evolve the net and search for a system schedule. A heuristic function and its Boolean implementations for the symbolic A* search are developed. The admissibility of the proposed heuristic function is proven, which guarantees the optimality of the obtained schedule. The computational time is thus reduced without sacrificing the schedule optimality. Finally, experiments are carried out to show the effectiveness and efficiency of the presented method.