基于不同支付规则的MPPSP及其模拟退火与禁忌搜索算法  

MPPSP and its simulated annealing and tabu search heuristics based on different payment rules

作　　者：何正文[1] 刘人境[1] 徐渝[1] 

机构地区：[1]西安交通大学管理学院,西安710049

出　　处：《系统工程理论与实践》2010年第8期1439-1447,共9页Systems Engineering-Theory & Practice

基　　金：国家自然科学基金(70971105);国家社会科学基金(07XJL002);陕西省自然科学基金(2009JM9001);陕西省软科学研究计划项目(2008KR11)

摘　　要：研究了基于不同支付规则的多模式项目支付进度问题.首先对所研究问题进行界定;在此基础上构建不同支付规则下的多模式项目支付进度优化模型,证明问题的强NP-hard属性;随后设计模拟退火及禁忌搜索两种启发式求解算法;在随机生成的标准算例集合上对算法进行比较测试,分析关键参数对目标函数的影响.结果表明:该文所开发的模拟退火启发式算法的求解质量要优于禁忌搜索启发式算法,而且这种优势随算例规模的增大而增加;此外,承包商收益随着支付次数与支付比例的增加而增加,随着折现率的提高而减小;基于时间、进展和费用支付规则下的满意解的目标函数值不超过基本支付规则下的对应值.This paper involves the multi-mode project payment scheduling problem based on different payment rules.Firstly the studied problem is identified and the optimization models under different payment rules are constructed.For the strong NP-hardness of the problem,two heuristic algorithms, namely simulated annealing and tabu search,are developed.The two algorithms are tested and evaluated on the basis of a computational experiment performed on a data set constructed by ProGen.The results show that the proposed simulated annealing heuristic algorithm outperforms the tabu search heuristic algorithm especially when the instances become larger.The objective value ascends with the increase of the payment number or the compensation proportion whereas descends as the interest rate per period goes up.Moreover,the desirable objective values under the time-based,progress-based,and expense-based rules cannot exceed those under the corresponding basic rule anyway.

关 键 词：多模式项目支付进度安排 支付规则 优化模型 模拟退火 禁忌搜索 

分 类 号：C935[经济管理—管理学] F224.33