等效化简带有广义优先关系的时间-费用权衡问题

doi:10.12005/orms.2015.0174

运筹与管理 ›› 2015, Vol. 24 ›› Issue (5): 175-183.DOI: 10.12005/orms.2015.0174

等效化简带有广义优先关系的时间-费用权衡问题

苏志雄^1,2,乞建勋¹,阚芝南¹

1.华北电力大学经济与管理学院,北京102206;
2.南昌工程学院工商管理学院,江西南昌330099

收稿日期:2012-09-29 出版日期:2015-10-12
作者简介:苏志雄(1983-),男,山西朔州人,博士生,研究方向:运筹学,项目进度与计划管理;乞建勋(1946-),男,河北邢台人,教授,博士生导师,研究方向:运筹学,项目进度与计划管理;阚芝南(1987-),女,江苏扬州人,博士生,研究方向:运筹学,项目进度与计划管理。
基金资助:
国家自然科学基金资助项目(71171079)

Simplification of Time-cost Tradeoff Problem with Generalized Precedence Relations

SU Zhi-xiong^1,2, QI Jian-xun¹, KAN Zhi-nan¹

1.School of Economic and Management,North Chin Electric Power University, Beijing 102206, China;
2.Business Administration College, Nanchang Institute of Technology, Nanchang 330099, China

Received:2012-09-29 Online:2015-10-12

摘要/Abstract

摘要： 对于经典的时间-费用权衡问题,工序之间只存在单一时间约束,可用CPM网络表示。但是对于工序之间存在多种时间约束的时间-费用权衡问题,包括最大和最小时间约束(称为广义优先关系,简称GPRs),则只能用GPRs网络表示,比CPM网络复杂许多。首先,论述了带有GPRs的时间-费用权衡问题与经典问题的巨大差别:在GPRs中,(1)缩短某些关键工序的工期能使总工期缩短,但缩短另一些关键工序的工期反而能使总工期延长;(2)缩短或延长工序的工期可能会破坏项目自身的可行性;等。其次,研究了GPRs网络的特性,推导出该网络的路长定理。第三,根据该定理,设计出等效化简带有GPRs的大型时间-费用权衡问题的简单方法,从而大幅减小求解该问题的难度和计算量。最后,通过算例演示了该方法。

关键词: 项目调度, 时间-费用权衡问题, 等效化简, 路长定理, 广义优先关系

Abstract: For classic time-cost tradeoff problem, only single time constraint exists between activities, and it could be represented by CPM network. But for time-cost tradeoff problem when multiple time constraints exist between activities, which mainly contain maximal and minimal time constraints and are named as generalized precedence relations(GPRs), it only could be represented by GPRs network which is more complicated than CPM network. Firstly, huge differences between the time-cost tradeoff problem with GPRs and the classic problem are analyzed: under GPRs, (1)compressing durations of some critical activities could compress total duration, but compressing durations of some other ones could prolong the total duration; (2)compressing or prolonging duration of activity may damage feasibility of project etc. Secondly, property of GPRs network is studied, and path length theorem of the network is deduced. Thirdly, according to the theorem, simple algorithm to simplify large scale time-cost tradeoff problem with GPRs is designed for decreasing difficulty and computation greatly of solving the problem. And finally, the algorithm is illustrated by example.

Key words: project scheduling, time-cost tradeoff problem, equivalent simplification, path length theorem, generalized precedence relations(GPRs)

中图分类号:

TB114.1

苏志雄,乞建勋,阚芝南. 等效化简带有广义优先关系的时间-费用权衡问题[J]. 运筹与管理, 2015, 24(5): 175-183.

SU Zhi-xiong, QI Jian-xun, KAN Zhi-nan. Simplification of Time-cost Tradeoff Problem with Generalized Precedence Relations[J]. Operations Research and Management Science, 2015, 24(5): 175-183.

参考文献

[1]Prabuddha D, James D, Jay B G, et al. Complexity of the discrete time-cost tradeoff problem for project networks[J]. Operations Research, 1997, 45(2): 302-306.
[2]Falk J E, Horowitz, J L. Critical path problem with concave cost-time curve[J]. Management Science, 1972, 19(4): 446-455.
[3]Kapur K C. An algorithm for the project cost/duration analysis problem with quadratic and convex cost functions [J]. IIE Transactions, 1973, 5(4): 314-322.
[4]Moder J J, Phillips C R, Davis E W. Project management with CPM, PERT and precedence diagramming(3rd edn)[M] . New York: Van Nostrand Reinhold Company, 1983. 64-81.
[5]张静文,徐渝,柴国荣.项目进度中的离散时间-费用决策问题研究[J].系统工程学报,2007,22(2):122-127.
[6]张静文,徐渝,何正文,柴国荣.项目调度中的时间-费用权衡问题研究综述[J].管理工程学报,2007,22(1):92-97.
[7]Elmaghraby S E, Kamburowski J. The analysis of activity networks under generalized precedence relations(GPR)[R]. Parts Ⅰand Ⅱ. OR Reports, 1989. 231-232.
[8]Elmaghraby S E, Kamburowski J. The analysis of activity networks under generalized precedence relations(GPRs)[J]. Management Science, 1992, 38(9): 1245-1263.
[9]Neumann K, Zhan J. Heuristics for the minimum project-duration problem with minimal and maximal time lags under fixed resource constraints[J]. Intell. Manuf. 1995, 6: 145-154.
[10]Sakellaropoulos S, Chassiakos A P. Project time-cost analysis under generalised precedence relations[J]. Advances in Engineering Software, 2004, 35(10): 715-724.
[11]Chassiakos A P, Sakellaropoulos S. Time-cost optimization of construction projects with generalized activity constraints[J]. Journal of Construction Engineering and Management, 2005, 131(10): 1115-1124.
[12]吴唤群,唐莉,孙相军,等.搭接施工网络工期优化研究[J].系统工程,2001,19(4):43-46.
[13]杨冰.网络计划计算模型的统一[J].系统工程理论与实践,2002,3:51-55.
[14]Akkan C, Drexl A, Kimms A. Network decomposition-based benchmark results for the discrete time-cost tradeoff problem[J]. European Journal of Operational Research, 2005, 165(2): 339-358.
[15]乞建勋,李星梅,王强.等效子网络构建的理论与方法[J].管理科学学报,2010,13(1):40-44.
[16]李星梅,乞建勋,苏志雄.自由时差定理与k阶次关键路线的求法[J].管理科学学报,2009,12(2):98-104.
[17]乞建勋,张立辉,李星梅.网络计划管理中的机动时间特性及其应用[M].北京:科学出版社,2009.82-112.

等效化简带有广义优先关系的时间-费用权衡问题

Simplification of Time-cost Tradeoff Problem with Generalized Precedence Relations

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

[1]	马咏, 何正文, 江波, 王能民. 一种求解柔性资源约束前摄性项目调度问题的启发式算法[J]. 运筹与管理, 2021, 30(8): 14-20.
[2]	刘万琳, 张静文, 刘婉君. 带有资源柔性约束的max-NPV分布式多项目调度问题[J]. 运筹与管理, 2021, 30(8): 37-43.
[3]	张静文, 刘婉君, 李琦. 基于关键链改进搜索的遗传算法求解分布式多项目调度[J]. 运筹与管理, 2021, 30(3): 123-129.
[4]	宁敏静, 郑小强, 何正文. 基于随机活动工期的现金流动态均衡前摄性与反应性项目调度优化[J]. 运筹与管理, 2021, 30(2): 117-123.
[5]	刘国山, 王敏, 张转霞. 基于时间窗延迟的资源约束项目调度双层优化研究[J]. 运筹与管理, 2021, 30(12): 6-12.
[6]	胡雪君, 王建江, 谭跃进, 徐培德, 崔南方. 带有资源转移时间的RCPSP资源流模型及算法[J]. 运筹与管理, 2021, 30(12): 42-50.
[7]	陈俊杰, 同淑荣, 王曜, 聂亚菲, 张静文. 人力资源约束下的项目群调度问题建模与求解[J]. 运筹与管理, 2020, 29(3): 107-116.
[8]	宁敏静, 何正文, 刘人境. 基于随机活动工期的多模式现金流均衡项目调度优化[J]. 运筹与管理, 2019, 28(9): 91-98.
[9]	刘寅斌,胡子怡,李洪波,余咪咪. 可抢占条件下的项目调度研究综述[J]. 运筹与管理, 2019, 28(4): 191-195.
[10]	李雪, 何正文, 王能民. 不确定环境下基于时间、费用及鲁棒性权衡的多目标项目调度优化[J]. 运筹与管理, 2019, 28(1): 6-16.
[11]	付芳, 张涛. 考虑返修的建设项目时间-成本-质量问题[J]. 运筹与管理, 2018, 27(7): 193-199.
[12]	刘洋, 陈志, 白思俊. 广义优先关系约束下Max-npv项目调度问题及其遗传算法[J]. 运筹与管理, 2016, 25(6): 91-98.
[13]	郑维博, 何正文, 刘人境. 基于融资能力约束的多模式Max-npv项目调度优化: 双重视角[J]. 运筹与管理, 2016, 25(1): 25-34.
[14]	李佳媛, 何正文. 基于资源随机中断的反应性多模式项目调度优化[J]. 运筹与管理, 2015, 24(6): 44-50.
[15]	王伟鑫,葛显龙,王旭,倪霖. 供应链环境下跨组织的PCPSP问题研究[J]. 运筹与管理, 2015, 24(5): 24-33.