实时无等待HFS调度的一种拉格朗日松弛算法  

Lagrangian Relaxation Algorithm for Real-time Hybrid Flowshop Scheduling with No-wait in Process

作　　者：轩华[1] 唐立新[2] 

机构地区：[1]东北大学教育部暨辽宁省流程工业综合自动化重点实验室,沈阳110004 [2]东北大学物流优化与控制研究所,沈阳110004

出　　处：《控制与决策》2006年第4期376-380,共5页Control and Decision

基　　金：国家杰出青年科学基金项目(70425003);国家自然科学基金项目(70171030;60274049);高等学校优秀青年教师教学科研奖励计划基金项目(教育司[2002]383)

摘　　要：研究了实时无等待HFS调度问题,并建立一个整数规划模型,提出运用拉格朗日松弛算法来求解.在此算法中,常采用次梯度方法更新拉格朗日乘子,但它随着迭代数的增加收敛速度会减慢,因此设计了一个改进的bund le方法,将以前的次梯度累积到bund le中,以获得一个更好的乘子更新方向.仿真实验表明,与次梯度方法相比,所设计的bund le法不仅在较少的迭代数内得到了更快的收敛速度而且改进了优化性能,对于大规模问题效果更为显著.The no-wait hybrid flowshop scheduling problem in a real-time environment is formulated as an integer programming model which has been proven NP-hard. A solution methodology based on Lagrangian relaxation is presented. In this method, the subgradient algorithm is commonly used to update Lagrange multipliers. However, the zigzagging behavior of subgradient optimization motivates the development of an improved bundle approach that accumulates the past subgradients in a bundle to achieve a better direction. Testing results show that the designed bundle approach provides a faster convergence and a better performance within less iteration, especially for largescale problems, comparing with subgradient method.

关 键 词：实时混合流水车间调度 无等待 整数规划 拉格朗日松弛 改进的bundle法 

分 类 号：TP278[自动化与计算机技术—检测技术与自动化装置]