求解广义优先关系下的项目最小费用问题

摘要

在项目调度中,求解与费用相关的问题时,需要先求得项目的最小费用,然后以此为起点进行优化,例如时间-费用权衡问题.当工序之间只存在单一优先关系时,各工序只需选用费用最小的工期就能得到项目最小费用.但是当工序之间存在广义优先关系(GPRs)时,各工序若都选用费用最小的工期通常无法满足既定的优先关系,导致项目不可行.针对GPRs下的项目最小费用问题,首先,通过分析GPRs的特点,建立了其数学模型;其次,对该模型进行对偶变换,将其等效转化为特殊的最小费用最大流模型.该模型能够运用现有算法求解,并跟据初始—对偶关系求得GPRs下的项目最小费用.