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

《等效化简带有广义优先关系的时间-费用权衡问题》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、第２４卷第５期运筹与管理Ｖｏｌ．２４，Ｎｏ．５２０１５年１０月ＯＰＥＲＡＴＩＯＮＳＲＥＳＥＡＲＣＨＡＮＤＭＡＮＡＧＥＭＥＮＴＳＣＩＥＮＣＥＯｃｔ．２０１５等效化简带有广义优先关系的时间-费用权衡问题１，２１１苏志雄，　乞建勋，　阚芝南（１．华北电力大学经济与管理学院，北京１０２２０６；２．南昌工程学院工商管理学院，江西南昌３３００９９）摘要：对于经典的时间－费用权衡问题，工序之间只存在单一时间约束，可用ＣＰＭ网络表示。但是对于工序之间存在多种时间约束的时间-费用权衡问题，包括最大和最小时间约束（称为广义优先关系，简称ＧＰＲｓ），则只能

2、用ＧＰＲｓ网络表示，比ＣＰＭ网络复杂许多。首先，论述了带有ＧＰＲｓ的时间-费用权衡问题与经典问题的巨大差别：在ＧＰＲｓ中，（１）缩短某些关键工序的工期能使总工期缩短，但缩短另一些关键工序的工期反而能使总工期延长；（２）缩短或延长工序的工期可能会破坏项目自身的可行性；等。其次，研究了ＧＰＲｓ网络的特性，推导出该网络的路长定理。第三，根据该定理，设计出等效化简带有ＧＰＲｓ的大型时间-费用权衡问题的简单方法，从而大幅减小求解该问题的难度和计算量。最后，通过算例演示了该方法。关键词：项目调度；时间-费用权衡问题；等效化简；路长定理；广义优先关

3、系中图分类号：ＴＢ１１４．１　　　文章标识码：Ａ文章编号：１００７-３２２１（２０１５）０５-０１７５-０９SimplificationofTime-costTradeoffProblemwithGeneralizedPrecedenceRelations１，２１１ＳＵＺｈｉ-ｘｉｏｎｇ，ＱＩＪｉａｎ-ｘｕｎ，ＫＡＮＺｈｉ-ｎａｎ（１．SchoolofEconomicandManagement，NorthChinElectricPowerUniversity，Beijing１０２２０６，China；２．BusinessAdminist

4、rationCollege，NanchangInstituteofTechnology，Nanchang３３００９９，China）Abstract：Ｆｏｒｃｌａｓｓｉｃｔｉｍｅ-ｃｏｓｔｔｒａｄｅｏｆｆｐｒｏｂｌｅｍ，ｏｎｌｙｓｉｎｇｌｅｔｉｍｅｃｏｎｓｔｒａｉｎｔｅｘｉｓｔｓｂｅｔｗｅｅｎａｃｔｉｖｉｔｉｅｓ，ａｎｄｉｔｃｏｕｌｄｂｅｒｅｐｒｅｓｅｎｔｅｄｂｙＣＰＭｎｅｔｗｏｒｋ．Ｂｕｔｆｏｒｔｉｍｅ-ｃｏｓｔｔｒａｄｅｏｆｆｐｒｏｂｌｅｍｗｈｅｎｍｕｌｔｉｐｌｅｔｉｍｅｃｏｎｓｔｒａｉｎｔｓｅｘｉｓｔｂｅｔｗｅｅｎａｃｔｉｖｉｔｉ

5、ｅｓ，ｗｈｉｃｈｍａｉｎｌｙｃｏｎｔａｉｎｍａｘｉｍａｌａｎｄｍｉｎｉｍａｌｔｉｍｅｃｏｎｓｔｒａｉｎｔｓａｎｄａｒｅｎａｍｅｄａｓｇｅｎｅｒａｌｉｚｅｄｐｒｅｃｅｄｅｎｃｅｒｅｌａｔｉｏｎｓ（ＧＰＲｓ），ｉｔｏｎｌｙｃｏｕｌｄｂｅｒｅｐｒｅｓｅｎｔｅｄｂｙＧＰＲｓｎｅｔｗｏｒｋｗｈｉｃｈｉｓｍｏｒｅｃｏｍｐｌｉｃａｔｅｄｔｈａｎＣＰＭｎｅｔｗｏｒｋ．Ｆｉｒｓｔｌｙ，ｈｕｇｅｄｉｆｆｅｒｅｎｃｅｓｂｅｔｗｅｅｎｔｈｅｔｉｍｅ-ｃｏｓｔｔｒａｄｅｏｆｆｐｒｏｂｌｅｍｗｉｔｈＧＰＲｓａｎｄｔｈｅｃｌａｓｓｉｃｐｒｏｂ-ｌｅｍａｒｅａｎａｌ

6、ｙｚｅｄ：ｕｎｄｅｒＧＰＲｓ，（１）ｃｏｍｐｒｅｓｓｉｎｇｄｕｒａｔｉｏｎｓｏｆｓｏｍｅｃｒｉｔｉｃａｌａｃｔｉｖｉｔｉｅｓｃｏｕｌｄｃｏｍｐｒｅｓｓｔｏｔａｌｄｕｒａ-ｔｉｏｎ，ｂｕｔｃｏｍｐｒｅｓｓｉｎｇｄｕｒａｔｉｏｎｓｏｆｓｏｍｅｏｔｈｅｒｏｎｅｓｃｏｕｌｄｐｒｏｌｏｎｇｔｈｅｔｏｔａｌｄｕｒａｔｉｏｎ；（２）ｃｏｍｐｒｅｓｓｉｎｇｏｒｐｒｏｌｏｎ-ｇｉｎｇｄｕｒａｔｉｏｎｏｆａｃｔｉｖｉｔｙｍａｙｄａｍａｇｅｆｅａｓｉｂｉｌｉｔｙｏｆｐｒｏｊｅｃｔｅｔｃ．Ｓｅｃｏｎｄｌｙ，ｐｒｏｐｅｒｔｙｏｆＧＰＲｓｎｅｔｗｏｒｋｉｓｓｔｕ

7、ｄｉｅｄ，ａｎｄｐａｔｈｌｅｎｇｔｈｔｈｅｏｒｅｍｏｆｔｈｅｎｅｔｗｏｒｋｉｓｄｅｄｕｃｅｄ．Ｔｈｉｒｄｌｙ，ａｃｃｏｒｄｉｎｇｔｏｔｈｅｔｈｅｏｒｅｍ，ｓｉｍｐｌｅａｌｇｏｒｉｔｈｍｔｏｓｉｍ-ｐｌｉｆｙｌａｒｇｅｓｃａｌｅｔｉｍｅ-ｃｏｓｔｔｒａｄｅｏｆｆｐｒｏｂｌｅｍｗｉｔｈＧＰＲｓｉｓｄｅｓｉｇｎｅｄｆｏｒｄｅｃｒｅａｓｉｎｇｄｉｆｆｉｃｕｌｔｙａｎｄｃｏｍｐｕｔａｔｉｏｎｇｒｅａｔ-ｌｙｏｆｓｏｌｖｉｎｇｔｈｅｐｒｏｂｌｅｍ．Ａｎｄｆｉｎａｌｌｙ，ｔｈｅａｌｇｏｒｉｔｈｍｉｓｉｌｌｕｓｔｒａｔｅｄｂｙｅｘａｍｐｌｅ．Keyw

8、ords：ｐｒｏｊｅｃｔｓｃｈｅｄｕｌｉｎｇ；ｔｉｍｅ-ｃｏｓｔｔｒａｄｅｏｆｆｐｒｏｂｌｅｍ；ｅｑｕｉｖａｌｅｎｔｓｉｍｐｌｉｆｉｃａｔｉｏｎ；ｐａｔｈｌｅｎｇｔｈｔｈｅｏｒｅｍ；ｇｅｎｅｒａｌｉｚｅｄｐｒｅｃｅｄｅｎ