多邻域局部搜索算法求解资源受限项目调度

针对资源受限项目调度问题,提出了一种基于多邻域的局部搜索算法。在算法中,设计了两种不同结构的搜索邻域,分别为交换邻域和插入邻域。算法中先使用交换邻域进行较大范围的局部搜索,然后再用插入邻域进行小范围内的精细搜索。两种邻域的交替使用有利于产生尽可能多的多样性解。为了使搜索能够跳出当前邻域,避免陷入局部最优,设计了一种基于均匀交叉操作的邻域移动方法来逐步移动邻域范围。此外,通过双向对齐技术提高每次求得的解的质量,而对具有相同工期的调度方案,则设计了一种新的时间压缩指标用来选择其中的最有潜力者。对标准测试库PSPLIB的2 040个测试案例进行了仿真测试,并与其他启发式算法进行比较,验证了算法的有效性。

批量流水线调度问题的混合离散蛙跳算法

研究了以提前/拖后惩罚指标为目标的批量流水线调度问题,给出了该问题的数学模型以及小批量的调整策略。根据蛙跳算法的原理,采用基于工序的编码方式并利用两点交叉操作设计了新的位置生成公式,提出了解决该问题的离散蛙跳算法。为进一步增强算法的开发能力和效率,结合扰动策略、模拟退火概率接受准则和插入邻域搜索对该算法进行改进。对随机生成的实例进行了广泛的试验,结果表明了所提算法的高效性。