用最少的虚工序构建等效多阶段工序网络  

Creating an equivalent multi-phases activity network by adding the least dummy activities

作　　者：苏志雄[1] 乞建勋[1] 阚芝南[1] 

机构地区：[1]华北电力大学经济与管理学院,北京102206

出　　处：《运筹学学报》2013年第3期45-56,共12页Operations Research Transactions

基　　金：国家自然科学基金项目(No.71171079)

摘　　要：运用网络计划可以直观地表示项目管理中的诸多疑难问题,便于分析和求解.但是它也存在明显的缺点,如,(1)工序网络的有向无回路性表明很多时候适合运用动态规划法,但它在通常情况下的无阶段性使得该方法无法直接应用;(2)任意构建的工序网络容易表现得错综复杂,不利于研究;(3)用最少的虚工序表示双代号网络是NP-难问题,因此对一个工序系统可能构建出多个差别迥异的工序网络,有碍于进度计划管理研究,等等.如果能将工序网络构建成等效的多阶段网络,各工序分别表示在相应的阶段中,无疑有助于上述问题的解决.构建等效多阶段工序网络需要添加虚工序.通过添加最少的虚工序将工序网络构建成等效多阶段网络,从而有助于建立更合理的工序网络表示法.Network planning can be used to show many difficult problems intuitively in project management, which helps to analyze and solve them. But it also has obvious defects, for example, （1） direction character with no loop of an activity network illuminates that dynamic programming is capable to it, but non-phases of an activity network in generally makes the algorithm cannot be used directly; （2） an activity network which created arbitrarily may be intricate easily in presentation, which leads difficulty to study; （3） the problem of representing activity-on-arc representation network with the least dummy activities is NP-hard, therefore many different activity networks may be created for an activity system, which blocks study on scheduling and planning manage- ment, etc. It will help to resolve above problems if transforming an activity network into an equivalent multi-phases network that each activity lies in a corresponding phase. Creating an equivalent multi-phases activity network need to add dummy activities. In this article, we design a method to create the equivalent multi-phases network by adding the least dummy activities to an activity network, which helps to found a more appropriate representation of activity network.

关 键 词：多阶段工序网络 改进的Ford-Fulkerson算法 网络计划 

分 类 号：O221[理学—运筹学与控制论]