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

A Lagrangian Relaxation Algorithm for Dynamic HFS Scheduling with Limited-wait Constraints

作　　者：轩华[1] 

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

出　　处：《工业工程与管理》2013年第3期24-29,共6页Industrial Engineering and Management

基　　金：国家自然科学基金资助项目(71001090;71001091)

摘　　要：作为基于最优化的近似算法,分析了拉格朗日松弛算法的分解策略,设计了算法的实现优化过程。针对从钢铁生产提炼出的带有限等待时间要求的动态HFS调度,采用基于工件解耦的分解策略,应用拉格朗日松弛算法进行求解,以最小化总加权完成时间和工件等待惩罚之和。该算法将工件耦合约束松弛到目标函数中,将形成的松弛问题分解成多个更易求解的工件级子问题,进而利用动态规划求解这些子问题,通过拉格朗日乘子的更新迭代过程获得原问题的近优解。对不同问题规模的测试结果表明,该算法能在较短的计算时间内得到较好的近优解,说明了拉格朗日松弛算法求解等待时间受限的HFS调度的可行性和有效性。As an optimization-based approximation algorithm, decomposition strategy of Lagrangian relaxation is analyzed and its optimization process is designed. Dynamic hybrid flowshop scheduling considering limited job waiting time between adiacent processing stages is abstracted from practical steel production and the above Lagrangian relaxation is applied to solve the minimization of the sum of total weighted completion time and waiting penalty for the above problem based on job decoupling strategy. In the algorithm, after relaxing job-coupling constraints to objective function, the formed relaxed problem can be decomposed into several job level subproblems to solve earlier. Dynamic programming is then applied to solve these subproblems. The near-optimal schedule is obtained during the iteration process of Lagrangian multipliers. Numerical results show that for small to large-sized problems this algorithm can obtain better solution quality within a shorter computational time. Therefore Lagrangian relaxation is feasible and effective for the HFS scheduling with limited-wait.

关 键 词：动态HFS调度 有限等待约束 运输时间 工件分解 拉格朗日松弛 

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