搭接网络中的路长悖论及其特性研究

中国管理科学 ›› 2014, Vol. 22 ›› Issue (5): 121-130.

搭接网络中的路长悖论及其特性研究

阚芝南¹, 孔峰², 乞建勋¹

1. 华北电力大学经济与管理学院, 北京 102206;
2. 华北电力大学经济与管理学院, 河北保定 071003

收稿日期:2012-07-05 修回日期:2013-05-06 出版日期:2014-05-20 发布日期:2014-05-14
作者简介:阚芝南（1987-），女（汉族），江苏扬州人，华北电力大学经济与管理学院博士生，研究方向：管理科学与工程.
基金资助:
国家自然科学基金资助项目（711171079）

Tresearch on Path Lengths Paradox and Its Characteristics Under Spliced Network

KAN Zhi-nan¹, KONG Feng², QI Jian-xun¹

1. Economics and Management School of North China Electric Power University, Beijing 102206, China;
2. Economics and Management School of North China Electric Power University(Baoding), Baoding 071003, China

Received:2012-07-05 Revised:2013-05-06 Online:2014-05-20 Published:2014-05-14

摘要/Abstract

摘要： 本文发现在搭接网络中存在“工序间加入不同表现形式的同一时间约束，可能会产生不同的最大路长”这个悖论。通过研究此悖论形成原因从而提出搭接网络的一种新表示方法。该方法不但与经典的CPM网络在表示形式上完全统一，而且在求解时间参数及关键路线的方法上也保持一致。该新表示法使得CPM网络中许多基础理论可以推广到搭接网络中来，例如工序的总时差T_ij等于关键路长μ^∇与过该工序（ij）的最大路长μ_ij^∇之差（μ^∇-μ_ij^∇）;任意一条路线μ上自由时差的和都等于关键路长μ与该条路的路长之差（μ^∇-μ_ij^∇）等。利用这些定理与规律，本文解决了搭接网络中如何正确求解时间参数问题，提出在搭接网络中评估关键路长与次关键路长之差的简便方法以及求解搭接网络次关键路线的一系列精确算法，并通过算例表明这些方法在搭接网络应用中的具有有效性与简便性。

关键词: 搭接网络, 最大路长, 机动时间, CPM网络

Abstract: A paradox in spliced network is found in this paper, that is when adding a time constraint but in two different types between activities may produce different longest path. A whole new presentation of spliced network is given by studying the paradox. The new spliced network presentation is quite simple but also unified with the classic CPM network in forms. This unification not only helps to solve the problems of how to calculate the time parameters, activity floats and how to find the critical path in spliced network, but also makes extension of the theory found in CPM network to spliced network becomes possible. For example, the activity total float T_ij equals to the critical path length μ^∇ minus the longest path length μ_ij^∇ through activity(ij), that is (μ^∇-μ_ij^∇); the sum of activity free float of any path μ equals to the critical path lengthμ^∇ minus the length of this path μ, that is (μ^∇-μ_ij^∇). By using these extended theory, three convenient methods are designed to detect the difference of critical and sub-critical path lengths and to find out the sub-critical path. These methods are illustrated both effective and convenient in spliced network applications.

Key words: spliced network, longest path, activity floats, CPM network

中图分类号:

C931

阚芝南, 孔峰, 乞建勋. 搭接网络中的路长悖论及其特性研究[J]. 中国管理科学, 2014, 22(5): 121-130.

KAN Zhi-nan, KONG Feng, QI Jian-xun. Tresearch on Path Lengths Paradox and Its Characteristics Under Spliced Network[J]. Chinese Journal of Management Science, 2014, 22(5): 121-130.

参考文献

[1] Crandall K C. 1973. Project planning with precedence lead/lag factors[J]. Project Management Quarterly,1973,4:18-27.

[2] Bartusch M, Mohring R H, Radermacher F J. Scheduling project networks with resource constraints and time windows[J]. Annals of Operations Research,1988,16(1):201-240.

[3] Elmaghraby S E, Kamburowski J. The analysis of activity networks under generalized precedence relations(GPRs) [J]. Management Science, 1992, 38(9): 1245-1263.

[4] De Reyck B, Herroelen W. A branch-and-bound algorithm for the resource-constrained project scheduling problem with generalized precedence relations[J]. European Journal of Operational Research,1998,111(1):152-174.

[5] De Reyck B, Herroelen W. An optimal procedure for the resource-constrained project scheduling problem with discounted cash-flows and generalized precedence relations.[J] Computers and Operations Research,1998, 25(1):1-17.

[6] De Reyck B, Demeulemeester E, Herroelen W. Algorithms for scheduling projects with generalised precedence relations[M]// WOeglarz J. Project Scheduling-Recent Models, Algorithms and Applications. Boston, MA:Kluwer Academic Publishers, 77-105.

[7] Brucker P, Drexl A, MNohring R, et al. Resource-constrained project scheduling: Notation, classification, models, and methods[J]. European Journal of Operational Research,1999,112(1):3-41.

[8] De Reyck B. Willy Herroelen. The multi-mode resource-constrained project scheduling problem with generalized precedence relations[J]. European Journal of Operational Research,1999, 119(2):538-556.

[9] Schwindt C. A branch-and-bound algorithm for the resource-constrained project duration problem subject to temporal constraints. Technical report, 1998.

[10] Fest A R H, MNohring F, Uetz S M. Resource constrained project scheduling with time windows: A branching scheme based on dynamic release dates. Technical report, 1999.

[11] Dorndorf U, Pesch E, Phan-Huy T. A time-oriented branch-and-bound algorithm for resource-constrained project scheduling with generalised precedence constraints[J]. Management Science, 2000,46(10):1365-1384.

[12] Sakellaropoulos S, Chassiakos A P. Project time-cost analysis under generalized precedence relations[J]. Advances in Engineering Software, 2004,35: 715-724.

[13] Chassiakos A P, Sakellaropoulos S P. Time-cost optimization of construction projects with generalized activity constraints[J].Journal of Construction Engineering and Management,2005,131(10):1115-1124.

[14] Najafi A A, Niaki S T A, Shahsavar M. A parameter-tuned genetic algorithm for the resource investment problem with discounted cash flows and generalized precedence relations[J]. Computers & Operations Research,2009,36(11):2994-3001.

[15] Bianco L, Caramia M. A new formulation of the resource-unconstrained project scheduling problem with generalized precedence relations to minimize the completion time[J]. Networks, 2010,56:263-271.

[16] Bianco L, Caramia M, A new lower bound for the resource-constrained project scheduling problem with generalized precedence relations[J]. Computers & Operations Research,2011,38(1):14-20.

[17] Bianco L,Caramia M. An exact algorithm to minimize the makespan in project scheduling with scarce resources and generalized precedence relations[J]. European Journal of Operational Research,2012, 219:73-85.

[18] 杨冰. 搭接网络计划计算模型的改进[J].中国公路学报,2002,15(1):116-122.

[19] 杨冰. 搭接网络计划模型分析[J].北方交通大学学报,2002,26(5):84-87.

[20] 廖钰. 搭接网络中关键链的识别方法. 武汉:华中科技大学, 2007.

[21] 夏中煌. 实用双代号搭接网络[J].施工技术,1993,22(3):29-30.

[22] 赵铁生. 双代号搭接施工网络计划研究[J]. 基建优化,1985,6(4):55-58.

[23] 佟鹤晶,乞建勋. 搭接网络向双代号网络的转化[J].技术经济,2009,28(10):125-128.

[24] 闫瑾,张奉举,闫睿. 单代号搭接网络模糊工期的计算方法[J].河南城建高等专科学校学报,2000,9(3):23-24.

[25] 杨冰. 网络计划计算模型的统一[J]. 系统工程理论与实践, 2002, 03: 51-55.

[26] 魏道升, 张智洪. 搭接网络计划在公路和桥梁施工项目管理中的应用[J]. 2001, 1(3): 48-50.

[27] 李金云. 搭接网络计划时间参数计算方法的改进[J]. 建筑科学, 2009,21(02): 88-91.

[28] 黄彬,孟国勇. 工程搭接网络计划浅议[J].大众科技,2009,14(2):75-77.

[29] 张照煌, 梁会森. 搭接网络计划工作总时差计算方法[J]. 应用基础与工程科学学报, 2009, 17:151-157.