零等待混合流水车间问题优化研究  

Research on Optimization of Zero-wait Hybrid Flowshop Problem

作　　者：轩华[1] 孙振轩[1] 李冰[1] 

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

出　　处：《工业工程与管理》2014年第5期13-17,30,共6页Industrial Engineering and Management

基　　金：国家自然科学基金资助项目(71001090;71001091);中国博士后科学基金面上资助项目(2013M531683);2013年河南省教育厅科学技术研究重点项目(13A410645);河南省科技攻关计划资助项目(142102310335;142102310313)

摘　　要：研究了带零等待的混合流水车间调度问题,考虑工件动态到达的实际生产特征,以最小化总加权完成时间为目标,建立整数规划模型,然后设计一种基于代理次梯度法的改进拉格朗日松弛算法。基于工件分解策略将拉格朗日松弛问题分解为多个工件级子问题,不同于每次迭代要求最优求解所有子问题的次梯度法,所设计的代理次梯度法通过每次迭代最优求解几个子问题得到松弛问题的近似解,进而获得搜索拉格朗日乘子的代理次梯度方向,最后设计启发式构造可行时间表。通过仿真实验,证明了所设计的算法在解的质量和收敛性方面均优于传统的使用次梯度法的拉格朗日松弛算法。Zero-wait hybrid flowshop scheduling problem is studied considering practical production characteristic of job dynamic arrival.The problem is formulated as an integer programming model to minimize the objective of total weighted completion time.A Lagrangian relaxation algorithm based on surrogate subgradient method is then designed to solve the problem.Based on job decomposition strategy,Lagrangian relaxed problem is decomposed into multiple job-level subproblems.Instead of subgradient method which requires optimal resolution of all subproblems at each iteration,the designed surrogate subgradient method requires approximate resolution of the relaxed problem by minimizing several subproblems,so that a surrogate subgradient direction is obtained to search Lagrangian multipliers.A heuristic method is then designed to construct feasible schedules.Computation experiments show that the developed Lagrangian relaxation is superior to the one using subgradient method in aspect of solution quality and convergence.

关 键 词：零等待混合流水车间 工件动态到达 代理次梯度法 拉格朗日松弛 

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