带多处理器任务的动态混合流水车间调度问题  

Dynamic hybrid flowshop scheduling problem with multiprocessor tasks

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

机构地区：[1]郑州大学管理工程系,河南郑州450001 [2]东北大学物流优化与控制研究所,辽宁沈阳110004

出　　处：《计算机集成制造系统》2007年第11期2254-2260,2288,共8页Computer Integrated Manufacturing Systems

摘　　要：研究了具有多处理器任务的混合流水车间调度问题,且考虑相邻两阶段之间的运输时间、机器故障和工件动态到达的实际生产特征。由于该问题不但求解非常复杂,对它的不同部分的简化还会使其变成其他不同的典型调度问题,探讨该类问题的近似解法具有挑战性和广义性。据此分别采用结合次梯度算法的拉格朗日松弛算法、结合次梯度和bundle算法的交替算法(交替S&B算法)的拉格朗日松驰算法进行求解。对多达100个工件的问题进行测试,结果表明,所设计的算法能够在合理的CPU时间内产生较好的时间表。Hybrid flowshop scheduling with multiprocessor tasks considering transportation time,machine breakdown and job dynamic arrival was studied.Since this problem was caused by several classical scheduling problems,and was complex and difficult to solve,it was challenged to develop effective approximation algorithms to solve the problem.Two Lagrangian relaxation algorithms were proposed to determine near optimal solutions respectively combined with sub-gradient optimization and interleaved sub-gradient and bundle algorithm.Computational results on the problem with up to 100 jobs indicated that the proposed algorithms could generate good schedules within a reasonable CPU time.

关 键 词：混合流水车间多处理器任务 运输时间 机器故障 工件动态到达 拉格朗日松弛 

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