基于Petri网和监督学习的机器人柔性流水车间调度方法

Scheduling method of robot flexible flow shops based on Petri nets and supervised learning

中文关键词  库所赋时Petri网  全连接神经网络  启发式函数  机器人柔性流水车间

英文关键词  place-timed Petri nets  fully connected neural network  heuristic function  robot flexible flow shops

中文摘要

      机器人柔性流水车间的调度属于组合优化问题, 涉及在指数增长的事件序列集合中寻找最优路径. 为了借 助机器学习和启发式搜索的优势, 提高调度优化的求解质量和效率, 本文提出了一种基于库所赋时Petri网和监督学 习的启发式优化方法. 首先, 利用库所赋时Petri网的运行规律, 设计了启发式数据集的生成算法; 其次, 设计库所赋 时Petri网的全连接神经网络学习模型, 从数据集中学习Petri网行为的启发式; 再次, 以全连接神经网络模型作为启 发式函数, 设计了库所赋时Petri网A *和集束搜索算法; 最后, 以某机器人柔性流水车间为例, 进行了系列数值实验. 本文方法获得了该流水车间库所赋时Petri网的高精度启发式, 其平均相对误差低于0.05%, 基于该启发式的A *和集 束搜索算法均能快速求解给定任务的最优或近似最优的调度策略.

英文摘要

      The scheduling of robot flexible flow shops is a combinatorial optimization problem, which involves searching for an optimal path in the exponentially growing set of event sequences. In order to improve the quality and efficiency of scheduling optimization by taking advantage of the machine learning and heuristic search, a heuristic optimization method is proposed based on the place-timed Petri nets and supervised learning. Firstly, the algorithm is presented to generate a heuristic data set by the executing rules of place-timed Petri nets. Secondly, the fully connected neural network is designed to learn the heuristic function to predict Petri net behavior from data sets. Thirdly, the neural network is used as the heuristic function, and the A * and beam search algorithms are presented for a place-timed Petri net. Finally, taking a robot flexible flow shop as an example, numerical experiments are carried out. The experimental results show that a high-precision heuristic is obtained by the proposed method for the flow shop’s place-timed Petri net model, whose average relative error is less than 0.05%. Both A * and beam search algorithms designed by us can be used to quickly solve the optimal or nearly optimal scheduling strategies for the flow shop.