带批和离散机柔性流水车间问题的混合异步次梯度优化的拉格朗日松弛算法  

Lagrangian relaxation mixed with interleaved subgradient optimization for flexible flowshop problem with batch and discrete processors

作　　者：轩华[1] 王薛苑[1] 李冰[1] XUAN Hua;WANG Xueyuan;LI Bing(School of Management Engineering,Zhengzhou University,Zhengzhou 450001,China)

机构地区：[1]郑州大学管理工程学院,河南郑州450001

出　　处：《计算机集成制造系统》2020年第4期1001-1010,共10页Computer Integrated Manufacturing Systems

基　　金：教育部人文社会科学研究基金资助项目(15YJC630148);国家自然科学基金资助项目(U1804151,U1604150);河南省高等学校重点科研资助项目(17A520058);河南省科技攻关计划项目(202102310310)。

摘　　要：为有效解决串行批调度问题,提出了一个混合异步次梯度优化的拉格朗日松弛算法,来求解带批和离散机的柔性流水车间问题(FFSP),目标是最小化总加权完成时间。该问题来源于钢铁业的炼钢-连铸-热轧一体化生产过程,为了加快算法的求解速度,扩大求解规模,在拉格朗日松弛优化算法中引入异步次梯度优化,每次迭代仅最优求解一个批级子问题,而其他子问题的解仍维持为前一次迭代的值,以此获取一个合理的乘子更新方向,大大缩短了每次迭代所消耗的运行时间。通过与基于批解耦和次梯度法的拉格朗日松弛算法的实验对比,说明了无论是实际生产数据还是随机产生的大规模数据,所提出的改进拉格朗日松弛算法都能获得具有竞争性的结果,对于较大规模问题,它在解的质量和收敛速度方面的优势更加明显。To effectively solve serial batch scheduling, an improved Lagrangian Relaxation algorithm mixed with Interleaved Subgradient Optimization(LR&ISO)was presented for the Flexible Flow Shop Problem(FFSP)with batch and discrete processors. The objective was to minimize total weighted completion time. This problem arises from the integrated production process of steelmaking-continuous casting-hot rolling in iron and steel industry. In order to speed up resolution process and expand resolution scale, the ISO was introduced into LR where a batch-level subproblem was optimized at each iteration and the other solutions were kept the same as the ones at the previous iteration to obtain a reasonable multiplier updating direction. It leaded to a much shorter computational time of each iteration. Numerical experiments was carried out to compare the proposed algorithm with LR based on batch decoupling and subgradient optimization. The results on practical production data and randomly generated larger-sized instances showed that the proposed algorithm can obtain the competitive performance, and its superiority on solution quality and convergence speed was more obvious with the increasing of problem size.

关 键 词：异步次梯度优化 拉格朗日松弛算法 柔性流水车间问题 批处理机和离散机 总加权完成时间 

分 类 号：TB49[一般工业技术]