An Iterated Dynasearch Algorithm for the Single-Machine Total Weighted Tardiness

资 源 简 介

An Iterated Dynasearch Algorithm for the Single-Machine Total Weighted Tardiness

详 情 说 明

该论文提出了一种新颖的迭代Dynasearch算法，专门用于解决单机调度问题中的总加权延迟优化。这类问题在制造系统和项目管理中具有广泛的实际应用背景。

算法核心结合了Dynasearch的局部搜索能力和迭代改进策略。Dynasearch本身是一种高效的邻域搜索技术，通过评估和组合多个独立的移动操作来寻找更优解。在传统应用中，它通常局限于特定邻域结构，而本算法通过迭代框架打破了这种限制。

实现过程中，算法首先构建初始解，然后循环执行两个关键阶段：破坏阶段使用随机移除策略打乱当前解的部分结构，重建阶段则应用Dynasearch进行精细化改进。这种破坏-重建的迭代机制有助于算法跳出局部最优，在解空间中进行更全面的探索。

针对加权延迟目标函数的特点，算法还融入了问题特定的启发式规则，在评估解的优劣时综合考虑任务的权重和紧迫程度。实验结果表明，该方法在求解质量和计算效率方面都表现出色，尤其适用于中等规模到大规模的问题实例。

该研究的创新点主要体现在将Dynasearch技术置于迭代改进框架中，既保留了Dynasearch的高效局部搜索能力，又通过迭代机制增强了全局探索性能。这种混合策略为类似的组合优化问题提供了新的解决思路。