并行机实时调度的LR&CG算法优化

本文主要探讨了并行机实时调度问题，这是一种在计算机科学领域中的关键挑战，尤其是在制造业和云计算环境中，需要高效地分配任务以满足严格的截止日期。目标是通过最小化总加权完成时间来优化资源利用率和生产效率。 作者构建了一个混合整数规划模型，该模型将非线性决策变量和离散决策变量结合在一起，以便准确地反映现实世界中的并行机环境。这种模型的复杂性促使研究者寻找更高效的求解策略。 为此，他们提出了一个创新的LR&CG混合算法，即拉格朗日松弛（Lagrangian Relaxation）和列生成（Column Generation）的融合方法。这个算法采用双重迭代结构：内环部分采用次梯度法作为下界求解器，这种方法在处理连续决策变量时表现出优异的性能，同时利用列生成技术来逐步增加问题的可行域，这有助于处理大规模的决策变量。 在外环，LR&CG算法通过求解限制主问题来更新拉格朗日乘子，并利用影子价格的概念来动态调整这些乘子，从而更好地平衡约束和目标函数之间的关系。这种方法有助于提升算法的收敛速度和质量，尤其是在解决具有大量约束的复杂问题时。 实验结果显示，相比于传统的LR算法，LR&CG算法在相同的计算时间内能提供更优的上界和下界估计，这表明它在收敛性和解决方案质量上具有显著优势。这对于实际应用来说非常重要，因为它意味着可以更有效地找到全局最优解，而不会因为计算时间过长而错过最佳决策。 总结起来，这篇文章的核心贡献在于提出了一种有效的并行机实时调度问题求解策略，通过LR&CG算法的双重迭代和结合拉格朗日松弛与列生成技术，提高了调度问题的求解效率和解决方案的质量，对于提高工业生产环境中的调度决策水平具有实际价值。