自由时差定理与k阶次关键路线的求法  被引量:13

Free float theorem and algorithm of seeking the k-th order critical path

在线阅读下载全文

作  者:李星梅[1] 乞建勋[1] 苏志雄[1] 

机构地区:[1]华北电力大学工商管理学院,北京102206

出  处:《管理科学学报》2009年第2期98-104,共7页Journal of Management Sciences in China

基  金:国家自然科学基金资助项目(70671040);教育部博士点基金资助项目(20050079008)

摘  要:针对项目进度计划管理中如何寻找CPM网络图中任意阶次关键路线等问题,在分析了自由时差概念和特性的基础上提出了k级标准工序、k级特征值和k级标准路线等新概念,推导出自由时差定理和特征值定理,进而利用这些概念和定理给出k阶次关键路线的求法——最小特征值法,分析了算法的正确性,并且得出该算法的计算复杂度为O(n2).证明了该算法可以通过局部寻优实现全局寻优.最后结合应用举例论述了该方法的应用范围及特点.To Solve problems such as how to seek any k-th order path in CPM network in project scheduling, some new conceptions: The k-th order normal activity, the k-th order eigenvalue and the k-th order normal path, are given. The free float theorem and eigenvalue theorem are deduced by analyzing these conceptions and the characteristics of free float. Then, an algorithm of seeking the k-th order critical path--the smallest eigenvalue algorithm whose complexity is O (n^2) , is proposed according to these conceptions and theorems, and correctness of the algorithm is analyzed. It is proved that the algorithm could achieve whole optimum by partial optimization. Finally, some properties and scope of this method are given by an example.

关 键 词:CPM网络计划 k阶次关键路线 最小特征值法 自由时差 

分 类 号:TB114.1[理学—运筹学与控制论]

 

参考文献:

正在载入数据...

 

二级参考文献:

正在载入数据...

 

耦合文献:

正在载入数据...

 

引证文献:

正在载入数据...

 

二级引证文献:

正在载入数据...

 

同被引文献:

正在载入数据...

 

相关期刊文献:

正在载入数据...

相关的主题
相关的作者对象
相关的机构对象