基于异步次梯度法的LR算法及其在多阶段HFSP的应用

轩 华， 李 冰

(郑州大学 管理工程学院，河南 郑州 450001)



基于异步次梯度法的LR算法及其在多阶段HFSP的应用

轩 华， 李 冰

(郑州大学 管理工程学院，河南 郑州 450001)

为降低求解复杂度和缩短计算时间，针对多阶段混合流水车间总加权完成时间问题，提出了一种结合异步次梯度法的改进拉格朗日松弛算法。建立综合考虑有限等待时间和工件释放时间的整数规划数学模型，将异步次梯度法嵌入到拉格朗日松弛算法中，从而通过近似求解拉格朗日松弛问题得到一个合理的异步次梯度方向，沿此方向进行搜索，逐渐降低到最优点的距离。通过仿真实验，验证了所提算法的有效性。对比所提算法与传统的基于次梯度法的拉格朗日松弛算法，结果表明，就综合解的质量和计算效率而言，所提算法能在较短的计算时间内获得更好的近优解，尤其是对大规模问题。

系统工程；异步次梯度法；拉格朗日松弛算法；多阶段混合流水车间问题；总加权完成时间

0 引言

混合流水车间问题(HFSP)所处的制造环境一般可描述为：一组工件L={1, 2, …,M}按照相同的加工顺序依次经过G个加工阶段进行加工，每个阶段g由mg台同构并行机组成，且至少有一个加工阶段的mg> 1；每个工件在每个阶段至多在一台同构机上加工；每台机器任何时间至多只能加工一个工件而每个工件在任何时间也只能在一台机器上加工。因此，HFSP要解决的问题是：将工件分配到机器上且确定在每个加工阶段的机器上工件的调度，同时还要最优化某个给定的目标函数[1，2]。