关键词: AOV网络, 层次, LAOV网络, 拓扑排序, 网格工作流

Abstract:

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.

Key words: AOV network;level;LAOV network;topological sorting;grid workflow