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

作者：苏志雄; 魏汉英

来源：南昌工程学院学报, 2019, 38(04): 98-103.

• 项目调度
• 离散型时间—费用权衡问题
• 广义优先关系
• 下界
• Lagrange松弛

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

• 单位
  南昌工程学院