需准备时间的FFS调度的一种拉格朗日松弛算法

针对需调度顺序相关准备时间的柔性流水车间生产调度问题，建立以成本最小化为目标的整数规划模型，用基于拉格朗日松弛的方法来求解。在常用的次梯度算法处理拉格朗日对偶问题时，迭代过程易出现振荡，严重影响了收敛效率。因此，利用了隶属度函数给出迭代过程中所有次梯度的合适权重，将它们线性加权得到新的迭代方向。最后通过算例表明，此算法有效的减少了迭代次数，提高了算法的优化性能。

Lagrangian Relaxation Algorithm for Flexible Flow Shops Scheduling With Sequence-Dependent Setup Time

The problem of flexible flow shop scheduling with sequence-dependent setup time is formulated as an integer programming model with synchronization constraints between part production and machine usage scheduling variables. A solution methodology based on Lagrangian relaxation is presented. In this method the scheduling problem, whose synchronization constraints are relaxed, is decomposed into two classes of subprob -lems. Then, the interative solution algorithm adopts a minimum cost network flow algorithm to solving all the subproblems respectively and applies an improved subgradient method to optimize Lagrangian multipliers. Compa -ring with subgradient method, numerical results of 21 cases, each having 20 test problems indicated that the improved subgradient method provided a less iteration and a faster convergence.