搭接网络的新表示方法与奇异现象研究

苏志雄, 乞建勋, 阚芝南

系统工程理论与实践 ›› 2015, Vol. 35 ›› Issue (1) : 130-141.

PDF(826 KB)
PDF(826 KB)
系统工程理论与实践 ›› 2015, Vol. 35 ›› Issue (1) : 130-141. DOI: 10.12011/1000-6788(2015)1-130
论文

搭接网络的新表示方法与奇异现象研究

    苏志雄1,2, 乞建勋1, 阚芝南1
作者信息 +

New representations and strange phenomenon of spliced networks

    SU Zhi-xiong1,2, QI Jian-xun1, KAN Zhi-nan1
Author information +
文章历史 +

摘要

针对搭接网络,设计了新的表示方法,将工序之间的所有搭接关系(时距)都等效地用经典的关键路线法(critical path method,CPM)双代号网络表示,并且能直接运用CPM法计算搭接网络的各类时间参数,使搭接网络具有和CPM双代号网络一样的直观性和便利性,更使建工行业规定的计算程序大为简化.另外,利用搭接网络的新表示方法,发现了搭接网络中的奇异现象,例如,某些关键工序的工期缩短,总工期反而延长,而某些非关键工序的工期无论如何变动,其机动时间总保持不变,等等,为项目调度等问题的解决提出新的挑战,开拓了搭接网络在研究和应用上的新领域.

Abstract

Focused on spliced networks, new representations were designed, which equivalently represent all spliced relations (time lags) between activities by using classic critical path method (CPM) networks with activity-on-arc representations, and time parameters were computed by using algorithms of the CPM networks. The new representations make the spliced networks be intuitive and convenient like the CPM networks with activity-on-arc representations, and furthermore greatly simplify calculation procedures which provided by construction industry. In additional, by applying the new representations, strange phenomenon were discovered in the spliced networks, for example, the project duration will be prolonged instead of being shortened if shortening durations of some critical activities; and floats of some non-critical activities will be unchanged instead of changing no matter whether prolonging or shortening their durations; and so on. The strange phenomenon cause new challenges to solve project scheduling problems etc., and open up new field of the spliced networks in theory and application.

关键词

搭接网络 / 奇异现象 / 关键路线法(CPM)网络 / 时距 / 机动时间

Key words

spliced networks / strange phenomenon / critical path method (CPM) networks / time lags / floats

引用本文

导出引用
苏志雄 , 乞建勋 , 阚芝南. 搭接网络的新表示方法与奇异现象研究. 系统工程理论与实践, 2015, 35(1): 130-141 https://doi.org/10.12011/1000-6788(2015)1-130
SU Zhi-xiong , QI Jian-xun , KAN Zhi-nan. New representations and strange phenomenon of spliced networks. Systems Engineering - Theory & Practice, 2015, 35(1): 130-141 https://doi.org/10.12011/1000-6788(2015)1-130
中图分类号: O221   

参考文献

[1] Roy B. Graphes et ordonnancement[J]. Revue Francaise de Recherche Operationelle, 1962, 25: 323-326.
[2] Elmaghraby S E. An algebra for the analysis of generalized activity networks[J]. Management Science, 1964, 10: 494-514.
[3] Kelley J E, Walker M R. Critical-path planning and scheduling[C]//Proceedings of Eastern Joint IRE-ACM Computer Conference, 1959: 160-173.
[4] 王众托, 张军. 网络计划技术[M]. 辽宁: 辽宁人民出版社, 1984.Wang Zhongtuo, Zhang Jun. Network planning technology[M]. Liaoning: Liaoning People's Press, 1984.
[5] Demeulemeester E L, Herroelen W S. Project scheduling: A research handbook[M]. Boston/Dordrecht/London: Kluwer Academic Publishers, 2002.
[6] 乞建勋, 张立辉, 李星梅. 网络计划管理中的机动时间特性理论及其应用[M]. 北京: 科学出版社, 2009.Qi Jianxun, Zhang Lihui, Li Xingmei. Theory and application of float's property in network planning management[M]. Beijing: Science Press, 2009.
[7] Elmaghraby S E, Kamburowski J. The analysis of activity networks under generalized precedence relations (GPRs)[J]. Management Science, 1992, 38(9): 1245-1263.
[8] 曹吉明, 徐伟. 网络计划技术与施工组织设计[M]. 上海: 同济大学出版社, 2000.Cao Jiming, Xu Wei. Network planning technology and construction organization design[M]. Shanghai: Tongji University Press, 2000.
[9] Zhan J. Heuristics for scheduling resource-constrained projects in MPM networks[J]. European Journal of Operational Research, 1994, 76(1): 192-205.
[10] Wikum E D, Donna C L, Nemhauser G L. One-machine generalized precedence constrained scheduling problems[J]. Operations Research Letters, 1994, 16: 87-99.
[11] 杨冰. 网络计划计算模型的统一[J]. 系统工程理论与实践, 2002, 22(3): 51-55.Yang Bing. Unifying calculating models for the network planning[J]. Systems Engineering——Theory & Practice, 2002, 22(3): 51-55.
[12] 杨冰. 搭接网络计划模型分析[J]. 北方交通大学学报, 2001, 26(5): 84-89.Yang Bing. Analyzing the models for spliced network planning[J]. Journal of Northern Jiaotong University, 2001, 26(5): 84-89.
[13] 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(4): 263-271.
[14] Haji Y S, Hassan G S. Computing latest starting times of activities in interval-valued networks with minimal time lags[J]. European Journal of Operational Research, 2010, 200(3): 874-880.
[15] 张照煌, 梁会森. 搭接网络计划工作总时差计算方法[J]. 应用基础与工程科学学报, 2009, 17: 151-157.Zhang Zhaohuang, Liang Huisen. The study on the calculation method for the works total float time for network planning[J]. Journal of Basic Science and Engineering, 2009, 17: 151-157.
[16] 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(1): 73-85.
[17] Lombardi M, Milano M. A min-flow algorithm for minimal critical set detection in resource constrained project scheduling[J]. Artficial Intelligence, 2012, 182-183: 58-67.
[18] Alfieri A, Tolio T, Urgo M. A project scheduling approach to production planning with feeding precedence relations[J]. International Journal of Production Research, 2011, 49(4): 995-1020.
[19] JGJ/T 121-99. 工程网络计划技术规程[S]. 北京: 中国建筑工业出版社, 1999.JGJ/T 121-99. Engineering network planning technology regulation[S]. Beijing: China Construction Industry Press, 1999.

基金

国家自然科学基金(71171079);江西省水安全与可持续发展研究基地

PDF(826 KB)

Accesses

Citation

Detail

段落导航
相关文章

/