运输能力有限混合流水车间调度的改进拉格朗日松弛算法  

Improved LR algorithm for hybrid flowshop scheduling with transportation consideration

作　　者：轩华[1] 

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

出　　处：《计算机集成制造系统》2013年第7期1633-1639,共7页Computer Integrated Manufacturing Systems

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

摘　　要：为改善在制品库存和能耗问题,研究了从钢铁实际生产环境提炼出的运输能力有限的动态混合流水车间调度问题。将运输机视为虚拟机器,可将原问题转换成与其等价的不考虑运输能力但在偶数阶段机器有不可用时间段的动态混合流水车间调度问题,其中机器不可用时间段取决于其运送的工件。对转换后的问题建立数学模型,提出基于阶段分解的拉格朗日松弛算法进行求解,该算法将优先级约束松弛到目标函数中,将拉格朗日松弛问题分解为多个阶段级子问题,进而设计了动态规划求解这些带任意权重和机器不可用时间段的并行同构机调度子问题。对不同问题规模的测试结果表明,所提算法能够在较短的运行时间内获得满意的近优解。To improve the inventory and energy consumption of work in process,the dynamic hybrid flowshop scheduling with transportation consideration in practical manufacturing circumstances of steel enterprises was studied.Transporters were viewed as virtual machines to transform the original problem into dynamic Hybrid FlowShop（HFS）scheduling problem of one without transportation but with job-dependent unavailable time windows of machines at even stages,in which the unavailable time of machines depended on delivery workpieces.The mathematical model for transformed problem was constructed,and Lagrangian Relaxation（LR）algorithm based on stage-decomposition was solved.In this algorithm,the precedence constraints were relaxed into objective function,and LR problem was decomposed in multiple stage-level sub-problems.Thus a dynamic programming algorithm was designed to solve these parallel identical machine scheduling sub-problems with any job weight and unavailable time windows of machines.Numerical results on problems with different scale showed that the designed LR algorithm could obtain acceptable near-optimal solutions within a shorter computational time.

关 键 词：动态混合流水车间调度 有限运输能力 阶段分解 拉格朗日松弛 动态规划 机器不可用时间段 

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