基于有向赋权图的RGV动态调度策略研究

Dynamic Schedule Strategy of RGV Based on the Weighted Directed Graph

摘要: 本文针对RGV调度问题，建立了基于有向赋权图的RGV动态调度模型。我们将问题中所提及的距离时间化，以时间作为权值，将实际问题转化为一个有向赋权图的数学模型，并设置虚拟节点以解决时间为零时的情况。对于一道工序问题，我们基于贪心算法进行动态调度，每一步都通过Floyd算法搜索距离RGV当前位置权值总和最小的虚拟节点，用于确定RGV的下一步移动节点。针对两道工序问题，我们基于粒子群算法(PSO)改进了传统的模拟退火算法(SA)，并结合一道工序的调度算法，以产量最大作为目标，搜索得到CNC的最佳分配。从而得出在规定的工作时间内，RGV最佳的调度策略。

Abstract: To solve the RGV scheduling problem, a RGV dynamic scheduling model based on graph theory is established. We transform distance into time in the problem so that the practical problem can be transformed into a mathematical model represented by a weighted directed graph, and virtual nodes are set up to solve the situation that the time is zero. In the one process, we schedule dy-namically based on Greedy Algorithm. In each step, Floyd algorithm is used to search the virtual node with the smallest total distance from current of RGV position weight to determine the next moving node of RGV. In the two processes, we improve the traditional Simulated Annealing Algo-rithm (SA) based on Particle Swarm Optimization (PSO), and combine the scheduling algorithm in the one process. Aiming at maximizing the output, the optimal allocation of CNCs is provided, and then the optimal scheduling strategy of RGV is obtained within the specified working time.