LAOV网络及其拓扑排序算法

针对网格工作流调度、生产和施工计划的制订等领域的特殊需求,引入了一类顶点带层次的AOV网络-LAOV网络。本文对AOV网络、层次、LAOV网络进行了严格的定义,并对顶点层次取值的几种情形作了详细的讨论。然后针对其中一种合理情形的LAOV网络提出了拓扑排序算法,讨论了栈或队列的选择、有向回路的判定等问题,并分析了算法的复杂度。最后对LAOV网络及拓扑排序算法进行实验分析。因为算法输出的解不唯一,在实验分析时设计了评判程序对算法输出进行验证。实验分析结果表明算法是正确的,时空效率也比较好。

The LAOV Network and Its Topological Sorting Algorithm

For special needs in grid workflow scheduling, production and construction planning, and so on. a kind of AOV network with all vertices possessing a level (denoted by LAOV) is introduced. The definitions of AOV, level and LAOV are given. Several cases of the level of vertices are discussed in detail. Then the topological sorting algorithm for a reasonable one of the LAOV networks is presented. Some problems are discussed, such as the choice of stack or queue, the determination of directed circuits, etc. And the complexity of the algorithm is analyzed. Finally, an experimental analysis of LAOV and its topological sorting algorithm is carried out. Because the output of the algorithm is not unique, a special judge program is written to verify the correctness of the output. The experimental results show that the algorithm is correct, and its time and space efficiency is well.