【摘要】 求解时间-费用权衡问题时,特别是在确定项目的最优时间-费用曲线时,首先必须找出初始最优解,即费用最低的总工期,然后在该解的基础上,用最低的压缩费用将总工期逐步缩短。在工序之间只有严格优先关系下,各工序的费用最低的工期就是初始最优解。但是当工序之间存在一般优先关系(简称GPRs)时,各工序都选用费用最低的工期往往无法满足既定的优先关系,使得项目不可行,因此必须考虑其它费用较高的工期,并且在时间约束范围内使得总费用最低。所以求解GPRs条件下时间-费用权衡问题的初始最优解是一个项目调度问题。针对该问题,首先,通过分析GPRs及其表示方法的特点,建立了该问题的数学模型;其次,通过对该模型进行对偶变换,将其等效转化为产销平衡的运输模型。运用已有的相关算法能够简便有效地求得该模型的最优解,并跟据初始-对偶关系可求得原问题的最优解。更多还原

【Abstract】 The time-cost tradeoff problem is of great importance in project scheduling because one of its main purposes is to determine an optimal project duration-cost function.In standard CPM,the identification of the optimal project duration-cost curve starts from the point corresponding to the upper bound,which is easily determined by simply assuming that all activities are realized at their least-cost durations.In addition,the optimal project cost curve for successively shorter durations are constructed until the project duration cannot be diminished any further. However,such an approach may fail in GPR networks because their least-cost durations may be inconsistent with the prescribed precedence relations.Therefore,identifying a starting point on the optimal project duration-cost function becomes crucial in identifying this curve.This is also a project scheduling problem because the precedence relations are determined by objective conditions which can’t be changed,but guaranteed by adjusting activity’s duration.Based on the property of GPRs representation and the primal-dual algorithm,this paper presents a transportation model with balanced supply and demand in order to solve the problem.The model could be solved by using existing simple algorithm.Optimal solutions could be obtained according to primal-dual relation.The paper mainly contains four parts. The first section introduces and analyzes GPR,its representation and property.GPRs include all the relationships between beginning and ending activities of a project.The second section introduces the problem of finding a starting point on the optimal project duration-cost function under GPRs.This part describes and analyzes difficulties when solving the problem under GPRs network.The third and fourth sections discuss how to obtain the starting point under GPRs by mathematical programming.The third section proposes an optimal solution model.The model is a special linear programming model,and each constraint in model only has two variables with coefficients +1 and-1.The fourth section presents the algorithm to solve the model proposed in the third section In summary,obtaining an initial optimal solution to time-cost tradeoff problems under GPRs is a project scheduling problem. We cansimplify the problem by using property of GPRs network and dual theory.A transportation model with balanced supply and demand has initial-dual relation to the problem.The proposed model provides a starting point for solving time-cost tradeoff problems under GPRs,and helps efficiently identity effective solutions to these problems.更多还原