GPRs条件下时间-费用权衡问题的初始最优解

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

等效化简连续型时间-费用权衡问题

大型工程项目中的连续型时间-费用权衡问题是复杂的项目调度问题,特别是非线性问题,需要先用适当的分段线性函数近似逼近原先的非线性时间-费用函数。等效化简是有效减少其计算量,进而使其便于求解的理想方法。针对该问题,本文采用等效化简的方法,把大型问题转化为等价的小型问题,即在不影响解的最优性的前提下,减少问题所涉及的工序数量,并减小工序的工期范围,使原来不可计算的问题变得可以计算,使复杂的问题变得简单。另外,减小工序的工期范围,便于用更精细的分段线性函数来近似逼近原非线性函数,从而提高解的准确性。在该原理的基础上,本文以CPM网络为工具,利用机动时间与网络中路长的关系,寻找求解原问题过程中的冗余工序,以及非冗余工序的冗余工期,并将其去掉,进而实现问题的等效简化。

基于Lagrange松弛求解带有广义优先关系的离散型时间—费用权衡问题解的下界

时间-费用权衡问题(TCTP)是项目调度领域最重要的、用途最广的问题之一。然而,对于各工序具有多个模式,且工序间存在广义优先关系(GPRs)的情况,相应的TCTP目前却没有受到很多重视,该问题称为带有GPRs的离散型TCTP(DTCTP)。DTCTP是NP-hard问题,且工序调度在GPRs下会存在很多奇异现象,有悖于常规理论和方法。因此,启发式方法有必要被用于求解该类型的大规模问题。而为了评估启发式方法的效果,需要得到原问题的解的尽量紧的下界。该文基于Lagrange松弛、分解和对偶,计算出带有GPRs的DTCTP的一个较紧的下界。