求解RCPSP问题的迭代局部搜索算法研究
2016-03-24赵轩
现代计算机 2016年8期
赵轩
(北京交通大学计算机与信息技术学院,北京 100044)
求解RCPSP问题的迭代局部搜索算法研究
赵轩
(北京交通大学计算机与信息技术学院,北京 100044)
迭代局部搜索(Iterated Local Search)算法是一个简单、高效的元启发式算法。提出一种新的求解资源受限项目调度问题(RCPSP)的迭代局部搜索算法。通过对当前解进行迭代交换实现局部搜索过程,再通过扰动多个任务的方式进行有效的扰动,防止陷入局部最优。迭代过程中通过优先对关键链的任务进行局部搜索进一步缩小解空间,通过双对齐技术提高解的质量。最终通过标准问题库求出各项参数并且验证算法的性能。
迭代局部搜索;资源受限项目调度问题;扰动多个任务;关键链;双对齐
0 引言
资源约束项目调度问题(Resource-Constrained project Scheduling Problem,RCPSP)主要任务是为调度项目的活动安排时间和资源,合理使用资源实现既定目标的最优化[1]。RCPSP问题广泛地存在于各种领域,如交通设施的建设、通信带宽资源的分配等[2]。
RCPSP问题属于NP-难问题,其求解方法可以分为精确算法和启发式算法[3]。精确算法能求得最优的调度结果,但无法在可接受的时间内求解大规模的调度问题。因此大多数文献都致力于启发式方法包括启发式算法(heuristic)和元启发式算法(meta-heuristic)的研究。启发式算法基于一定的启发规则快速得到问题的解,但不能保证解的质量。与元启发式算法相比,启发式算法的求解结果普遍较差,目前不再是研究热点,而各类元启发式算法是RCPSP算法领域的重点研究对象[4]。……
登录APP查看全文
