轧钢切断阶段动态HFS调度模型和LR算法研究

以钢管生产为背景,在分析钢管切割工艺的基础上,提炼出第一阶段具有批处理特征的动态HFS调度问题,建立了数学规划模型,目标是最小化所有工件的加权完成时间.针对该模型,构造了改进的拉格朗日松弛算法(lagrangian relaxation,LR)的求解过程,设计了求解批级子问题的动态规划算法和构造可行解的启发式算法.

带有限等待的动态HFS调度的拉格朗日松弛算法

作为基于最优化的近似算法,分析了拉格朗日松弛算法的分解策略,设计了算法的实现优化过程。针对从钢铁生产提炼出的带有限等待时间要求的动态HFS调度,采用基于工件解耦的分解策略,应用拉格朗日松弛算法进行求解,以最小化总加权完成时间和工件等待惩罚之和。该算法将工件耦合约束松弛到目标函数中,将形成的松弛问题分解成多个更易求解的工件级子问题,进而利用动态规划求解这些子问题,通过拉格朗日乘子的更新迭代过程获得原问题的近优解。对不同问题规模的测试结果表明,该算法能在较短的计算时间内得到较好的近优解,说明了拉格朗日松弛算法求解等待时间受限的HFS调度的可行性和有效性。