GERT网络的矩阵式表达及求解模型
|
摘要
图示评审技术(graphic evaluation and review technique,GERT)解析法一般利用信号流图的拓扑特征(梅森公式)和矩母函数进行求解,但当GERT网络节点较多且结构复杂(回路众多)时,拓扑结构特征的分析十分困难,易出现错判或遗漏情况。针对此问题,将GERT网络用矩阵形式进行表征,分析了以梅森公式为基础的解析法与矩阵变换的关系,设计了两类基于矩阵的GERT求解算法。首先给出GERT网络与信号流图增益矩阵、流图增益矩阵一一对应关系,分析增益矩阵行列式变换与信号流图求解公式的对应关系,设计GERT网络的增益矩阵行列式变换求解算法。另外,研究GERT网络(信号流图)化简操作(消除自环、消除节点)在信号流图增益矩阵上的变换形式,提出了GERT网络解析的矩阵变换方法。最后用两个例子说明矩阵表征及求解模型的简便性和正确性,为GERT解析的计算机操作奠定基础。
The typical analytical algorithm for graphic evaluation and review technique(GERT)is based on the topological properties of the signal flow graph(Mason formula)and the moment generating function,whereas it is tremendously difficult to analyze the topological characteristics of the GERT network when the network consists of a large number of nodes and complex structure(including many loops).The complexity of GERT network may lead to misjudge and false negative of the loops.For this problem,the matrix representation of the GERT network is explored,the corresponding relationship between the Mason formula-based algorithm and the matrix transform is analyzed,and two kinds of algorithms based on matrix for GERT network are designed.The first method is to give the gain matrix of the signal flow graph and gain matrix of the flow graph for a given GERT network firstly,and then to study the relationship between the determinant of the gain matrix and the Mason formula,and to design the resolving algorithm finally.The other method is to utilize the transform operators on the matrix to represent the simplification operators of the signal flow graph including eliminating self-loop and some unconcerned nodes.As a consequence,the algorithm based on matrix transform is introduced.Finally,two illustrative examples are presented to demonstrate the convenience and accuracy of the proposed methods,which may provide a tool for the computer calculation of the GERT network.
The typical analytical algorithm for graphic evaluation and review technique(GERT)is based on the topological properties of the signal flow graph(Mason formula)and the moment generating function,whereas it is tremendously difficult to analyze the topological characteristics of the GERT network when the network consists of a large number of nodes and complex structure(including many loops).The complexity of GERT network may lead to misjudge and false negative of the loops.For this problem,the matrix representation of the GERT network is explored,the corresponding relationship between the Mason formula-based algorithm and the matrix transform is analyzed,and two kinds of algorithms based on matrix for GERT network are designed.The first method is to give the gain matrix of the signal flow graph and gain matrix of the flow graph for a given GERT network firstly,and then to study the relationship between the determinant of the gain matrix and the Mason formula,and to design the resolving algorithm finally.The other method is to utilize the transform operators on the matrix to represent the simplification operators of the signal flow graph including eliminating self-loop and some unconcerned nodes.As a consequence,the algorithm based on matrix transform is introduced.Finally,two illustrative examples are presented to demonstrate the convenience and accuracy of the proposed methods,which may provide a tool for the computer calculation of the GERT network.
引文
[1]PRITSKER A A B.GERT:graphical evaluation and review technique,RM-4973-NASA[R].Santa Monica:RAND Corporation,1966.
[2]LIN K P,WEN W,CHOU C C,et al.Applying fuzzy GERT with approximate fuzzy arithmetic based on the weakest t-norm operations to evaluate repairable reliability[J].Applied Mathematical Modeling,2011,35(11):5314-5325.
[3]MOHAN P,AGARWA M,SEN K.Combined m-consecutive-kout-of-n F&consecutive kc-out-of-n:F systems[J].IEEE Trans.on Reliability,2009,58(2):328-337.
[4]MOORE L J,TAYLOR III B W.Multi-team,multi-project research and development planning with GERT[J].Management Science,1977,24(4):401-410.
[5]刘红旗,方志耕,陶良彦.复杂装备研制项目进度规划GERT网络“反问题”模型[J].系统工程与电子技术,2015,37(12):2758-2763.LIU H Q,FANG Z G,TAO L Y.Complex equipment development project planning GERT network“inversion problem”model[J].Systems Engineering and Electronics,2015,37(12):2758-2763.
[6]陶良彦,刘思峰,方志耕,等.基于多层次GERT的复杂产品研制进度规划“超冲突均衡”博弈模型[J].控制与决策,2014,29(11):2002-2010.TAO L Y,LIU S F,FANG Z G,et al.“Super-conflict equalization”game model for complex product development scheduling based on multi-level GERT[J].Control and Decision,2014,29(11):2002-2010.
[7]LI C,LIU S.Random network models and sensitivity algorithms for the analysis of ordering time and inventory state in multistage supply chains[J].Computers&Industrial Engineering,2014,70(4):168-175.
[8]李翀,刘思峰,方志耕,等.多级供应链系统成本分析随机网络模型及算法研究[J].中国管理科学,2013,21(4):105-111.LI C,LIU S F,FANG Z G,et al.The study of multi-stage supply chain cost distribution based on GERT model[J].Chinese Journal of Management Science,2013,21(4):105-111.
[9]刘远,方志耕,刘思峰,等.基于供应商图示评审网络的复杂产品关键质量源诊断与探测问题研究[J].管理工程学报,2011,25(2):212-219.LIU Y,FANG Z G,LIU S F,et al.Diagnosis and detection of critical quality resource of complex product based on supplier GERT model[J].Journal of Industrial Engineering and Engineering Management,2011,25(2):212-219.
[10]NELSON R G,AZARON A,AREF S.The use of a GERT based method to model concurrent product development processes[J].European Journal of Operational Research,2016,250(2):566-578.
[11]郭本海,方志耕,俞斌,等.基于能效视角的主导产业选择多参量GERT网络模型[J].系统工程理论与实践,2011,31(5):944-953.GUO B H,FANG Z G,YU B,et al.Multi-parameter GERT network model of leading industry choice based on energy efficiency perspective[J].Systems Engineering-Theory&Practice,2011,31(5):944-953.
[12]方志耕,杨保华,陆志鹏.基于Bayes推理的灾害演化GERT网络模型研究[J].中国管理科学,2009,17(2):102-107.FANG Z G,YANG B H,LU Z P.The GERT network model study of disaster evolution based on Bayes inference[J].Chinese Journal of Management Science,2009,17(2):102-107.
[13]李成川,李聪波,曹华军,等.基于GERT图的废旧零部件不确定性再制造工艺路线模型[J].计算机集成制造系统,2012,18(2):298-305.LI C C,LI C B,CAO H J,et al.Uncertain remanufacturing process routings model for used components based on GERT network[J].Computer Integrated Manufacturing Systems,2012,18(2):298-305.
[14]WU D D,KEFAN X,GANG C,et al.A risk analysis model in concurrent engineering product development[J].Risk Analysis,2010,30(9):1440-1453.
[15]冯允成.随机网络及其应用[M].北京:北京航空学院出版社,1987.FENG Y C.Stochastic network and its application[M].Beijing:Beijing University of Aeronautics and Astronautics Press,1987.
[16]赵国枝,刘志决.流图矩阵分析[J].太原机械学院学报,1989,10(1):96-103.ZHAO G Z,LIU Z J.A matrix analysis method of flow graph[J].Journal of Taiyuan Institute of Machinery,1989,10(1):96-103.
[17]曾建平,雷宏.系统传递函数的矩阵求解法[J].太原机械学院学报,1991,12(2):65-73.ZENG J P,LEI H.The matrix method for solving the system transfer function[J].Journal of Taiyuan Institute of Machinery,1991,12(2):65-73.
[18]罗涛,何振亚.信号与系统分析的流图矩阵法[J].通信学报,1993,14(6):73-79.LUO T,HE Z Y.Analysis of signals and systems by flow graph matrix method[J].Journal of Chinese Institute of Communications,1993,14(6):73-79.
[2]LIN K P,WEN W,CHOU C C,et al.Applying fuzzy GERT with approximate fuzzy arithmetic based on the weakest t-norm operations to evaluate repairable reliability[J].Applied Mathematical Modeling,2011,35(11):5314-5325.
[3]MOHAN P,AGARWA M,SEN K.Combined m-consecutive-kout-of-n F&consecutive kc-out-of-n:F systems[J].IEEE Trans.on Reliability,2009,58(2):328-337.
[4]MOORE L J,TAYLOR III B W.Multi-team,multi-project research and development planning with GERT[J].Management Science,1977,24(4):401-410.
[5]刘红旗,方志耕,陶良彦.复杂装备研制项目进度规划GERT网络“反问题”模型[J].系统工程与电子技术,2015,37(12):2758-2763.LIU H Q,FANG Z G,TAO L Y.Complex equipment development project planning GERT network“inversion problem”model[J].Systems Engineering and Electronics,2015,37(12):2758-2763.
[6]陶良彦,刘思峰,方志耕,等.基于多层次GERT的复杂产品研制进度规划“超冲突均衡”博弈模型[J].控制与决策,2014,29(11):2002-2010.TAO L Y,LIU S F,FANG Z G,et al.“Super-conflict equalization”game model for complex product development scheduling based on multi-level GERT[J].Control and Decision,2014,29(11):2002-2010.
[7]LI C,LIU S.Random network models and sensitivity algorithms for the analysis of ordering time and inventory state in multistage supply chains[J].Computers&Industrial Engineering,2014,70(4):168-175.
[8]李翀,刘思峰,方志耕,等.多级供应链系统成本分析随机网络模型及算法研究[J].中国管理科学,2013,21(4):105-111.LI C,LIU S F,FANG Z G,et al.The study of multi-stage supply chain cost distribution based on GERT model[J].Chinese Journal of Management Science,2013,21(4):105-111.
[9]刘远,方志耕,刘思峰,等.基于供应商图示评审网络的复杂产品关键质量源诊断与探测问题研究[J].管理工程学报,2011,25(2):212-219.LIU Y,FANG Z G,LIU S F,et al.Diagnosis and detection of critical quality resource of complex product based on supplier GERT model[J].Journal of Industrial Engineering and Engineering Management,2011,25(2):212-219.
[10]NELSON R G,AZARON A,AREF S.The use of a GERT based method to model concurrent product development processes[J].European Journal of Operational Research,2016,250(2):566-578.
[11]郭本海,方志耕,俞斌,等.基于能效视角的主导产业选择多参量GERT网络模型[J].系统工程理论与实践,2011,31(5):944-953.GUO B H,FANG Z G,YU B,et al.Multi-parameter GERT network model of leading industry choice based on energy efficiency perspective[J].Systems Engineering-Theory&Practice,2011,31(5):944-953.
[12]方志耕,杨保华,陆志鹏.基于Bayes推理的灾害演化GERT网络模型研究[J].中国管理科学,2009,17(2):102-107.FANG Z G,YANG B H,LU Z P.The GERT network model study of disaster evolution based on Bayes inference[J].Chinese Journal of Management Science,2009,17(2):102-107.
[13]李成川,李聪波,曹华军,等.基于GERT图的废旧零部件不确定性再制造工艺路线模型[J].计算机集成制造系统,2012,18(2):298-305.LI C C,LI C B,CAO H J,et al.Uncertain remanufacturing process routings model for used components based on GERT network[J].Computer Integrated Manufacturing Systems,2012,18(2):298-305.
[14]WU D D,KEFAN X,GANG C,et al.A risk analysis model in concurrent engineering product development[J].Risk Analysis,2010,30(9):1440-1453.
[15]冯允成.随机网络及其应用[M].北京:北京航空学院出版社,1987.FENG Y C.Stochastic network and its application[M].Beijing:Beijing University of Aeronautics and Astronautics Press,1987.
[16]赵国枝,刘志决.流图矩阵分析[J].太原机械学院学报,1989,10(1):96-103.ZHAO G Z,LIU Z J.A matrix analysis method of flow graph[J].Journal of Taiyuan Institute of Machinery,1989,10(1):96-103.
[17]曾建平,雷宏.系统传递函数的矩阵求解法[J].太原机械学院学报,1991,12(2):65-73.ZENG J P,LEI H.The matrix method for solving the system transfer function[J].Journal of Taiyuan Institute of Machinery,1991,12(2):65-73.
[18]罗涛,何振亚.信号与系统分析的流图矩阵法[J].通信学报,1993,14(6):73-79.LUO T,HE Z Y.Analysis of signals and systems by flow graph matrix method[J].Journal of Chinese Institute of Communications,1993,14(6):73-79.