有向图理论在工序排序决策中的应用  

Application of Digraph Theory to Process Scheduling

作　　者：马术文 陈永[1] 杜全兴[1] 张建安[2] 

机构地区：[1]西南交通大学机械工程学院,四川成都610031 [2]中国人民解放军信息工程大学电子技术学院昆明分院,云南昆明650091

出　　处：《西南交通大学学报》2005年第5期633-636,共4页Journal of Southwest Jiaotong University

基　　金：四川省应用基础研究基金资助项目(2989929)

摘　　要：为了建立有效的工序排序决策模型,运用有向图理论,用有向图的节点描述加工特征,用有向边描述加工特征之间的基准关系,从而有向图上经过所有节点且没有环路的有向路径即为可行的工艺路线.为了便于计算机处理,将有向图用矩阵表示,通过有向图矩阵的乘法运算搜索最长的有向路径.如果最长的有向路径没有包括所有节点,可以根据基准关系,将最长有向路径外的节点插入,得到最终的工序排序结果.To set up an effective decision model of process scheduling, the digraph theory was applied. Based on the theory, processing features are expressed with the vertices of a directed graph, and datum relationships among the processing features are described with directed edges. As a result, 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 a matrix, and then the longest directed paths can be obtained through matrices multiplication. If some vertices do not be included in a longest directed path, these vertices will be inserted into the longest directed path in the light of the datum relationships so as to obtain satisfied process schedules.

关 键 词：工序排序 有向图 计算机辅助工艺设计 矩阵 

分 类 号：TH162.1[机械工程—机械制造及自动化]