有向图理论在工序排序决策中的应用
Application ofDigraph Theory to Process Scheduling
-
摘要: 为了建立有效的工序排序决策模型,运用有向图理论,用有向图的节点描述加工特征,用有向边描述加 工特征之间的基准关系,从而有向图上经过所有节点且没有环路的有向路径即为可行的工艺路线.为了便于计 算机处理,将有向图用矩阵表示,通过有向图矩阵的乘法运算搜索最长的有向路径.如果最长的有向路径没有包 括所有节点,可以根据基准关系,将最长有向路径外的节点插入,得到最终的工序排序结果.Abstract: To set up an effective decision model of process scheduling, the digraph theory was applied. Based on the theory, processing features are expressedwith the vertices of a directed graph, and datum relationships among the processing features are describedwith directed edges. As a resul,t a directed path without a loop and through every vertex in the directed graph is a feasible process schedule. For computer processing of the directed digraph, it is expressed by amatrix, and then the longest directed paths can be obtained through matrices multiplication. If some vertices do not be included in a longestdirected path, these verticeswillbe inserted into the longestdirected path in the lightof the datum relationships so as to obtain satisfied process schedules.
-
Key words:
- process scheduling /
- digraph /
- CAPP (computer aided process planning) /
- matrix
点击查看大图
计量
- 文章访问数: 1418
- HTML全文浏览量: 68
- PDF下载量: 187
- 被引次数: 0