具有时间窗约束的柔性流水车间设备利用率排产优化问题研究

董晓婷

（四川建筑职业技术学院设备工程系，四川 德阳 618000）

0 引言

柔性流水车间排产优化问题 (flexible flow-shop scheduling problem, FFSP)既需要解决工件的上线序，还需处理每道工序并行工位的分配， 属NP-Hard 问题。实际制造企业生产过程是滚动连续的生产过程， 计划部门按照固定时间节奏在生产线投放生产任务， 在多工序、 生产周期长的生产车间中各个工序的正在加工在制品是多次投产的生产任务， 如果每次投产生产任务在各个工序不限制在一定时间范围内生产， 会增加排产冲突的可能性， 所以可以通过设置每个工序的时间窗进行控制， 使得排产在各工序时间窗内进行排产， 增加排产时间窗约束会增加排产的问题复杂性，但是也可以更好提升排产结果在实际应用的效果。 紧致遗传算法(compact genetic algorithm, CGA)属于一种变量无关的分布估计算法[1]，于1998 年被美国UIUC 大学Harik 教授首次提出[2]。 该算法计算量小，优化速度非常快， 但同时具有随着进化代数进化活力不足，容易落入局部极值的缺陷。 本文采用一种改进CGA 算法，增强该算法进化活力，克服落入局部极值，以达到更好解决FFSEUP-TWC 的目标。

1 数学模型

1.1 问题描述

具有时间窗约束[3]的柔性流水车间设备利用率排产优化问题可以描述为： 个工件按上线顺序经过每道工序进行加工， 工件在每个工序给定的时间窗内进行生产加工， 即限定每个工序的并行工位的有效工作时间范围内加工， 工件可选择并行工位中任意一个工位加工， 工件在各工序的加工时间已知， 通过全局优化算法来优化上线序和并行工位分配情况， 进而提高的生产线上设备利用率。

1.2 约束条件

（1）柔性流水车间排产的一般性约束：

式（1）表示工序Operj上的开工时间与完工时间的约束。 工件Ji的生产时间用Ti,j，表示，开工时间用Si,j表示，完工时间用Ci,j表示。

（2）柔性流水车间排产的时间窗约束

式（3）表示工序Operj的时间窗开始时间Twbj与工件Ji的开工时间Si,j的约束关系，要求在工序Operj，所有工件的开工时间Si,j都要大于等于时间窗开始时间Twbj。

式（4）表示工序Operj的时间窗结束时间Twej与工件Ji的完工时间Ci,j， 的约束关系， 要求在工序Operj所有工件的完工时间Ci,j，都要小于等于时间窗结束时间Twej。

1.3 建立设备利用率优化目标

式5 中fUR表示的FFS 中所有工位总设备利用率，为工位实际工作时间与工位提供工作时间的比值，工件在各工序中在所分配工位上的加工时间之和为实际工作时间， 工位提供工作时间是时间窗开始时间Twbj和最后一个工件的完工时间max{Ci,j}之差，这个时间设置成该工序的时间窗的时间范围Ts1。

2 算法分析

2.1 建立并初始化概率模型

建立n×n 的矩阵P1作为CGA 算法的上线序概率模型来优化排产的上线序, 概率模型中1 至n 行对应工件J1至Ji，1 至n 列对应个体的1 至n 位表示工件Ji在上线加工队列中位置s 上出现的概率； 建立n×Ms的矩阵P2作为CGA 算法的工位分配概率模型来优化多工序并行工位分配, 概率模型中1 至n 行对应工件J1至Ji，1 至Ms列对应个体的工序Oper1至工序Operm选择工位的概率表 示 工 件Ji在工序Operj的并行工位WSj,k上出现的概率。 矩阵P1和矩阵P2合成为一个n×(n+Ms)的矩阵P 作为CGA 算法的概率模型。

2.2 新个体的编码和解码

3 仿真分析

3.1 构建仿真数据

为了研究FFSEUP-TWC 问题， 构造具备4 道工序的FFS 验证模型的数据， 每道工序的并行工位数分别为{3,2,3,2}。生产任务是加工8 个工件(n=8)，每个工件在各工序并行工位加工时间取[20,40]内的随机数。

3.2 研究方案和参数设置

构造2 组调度方案： 方案1 是采用CGA 算法的柔性流水车间设备利用率排产优化方案； 方案2 是采用SACGA 算法的柔性流水车间设备利用率fUR排产优化方案； 以总设备利用率作为2 组方案的全局调度优化目标和适应度函数，也做优化结果的评价指标。

设置CGA 算法种群规模NP=4， 最大训练代数Gmax=500，学习系数K=6，基于信息熵的自适应学习速率调整关联的参数 （式9）， 学习速率的调整倍率β1=1.2，β2=0.8，学习速率的信息熵调整阀值α1=0.4，α2=0.6。

表1 每个工序时间窗时间范围表（单位：min）

3.3 仿真结果分析

20 次仿真运算结果的平均值如表3。

表3 2 组方案仿真结果数值分析表

表2 数值分析结果可知： 2 组方案都可以得到较好的调度结果，但方案2 的总设备利用率fUR和总设备利用率变化幅度f'UR的值最大，总设备利用率变化幅度的均值比方案1 的CGA 算法的的提高23.04%，但是由于加入了自适应策略， 增加了计算的复杂性，增加了16.27%运行时间成本。

4 结论

在解决FFSEUP-TWC 问题时， 以fUR作为优化目标。 在全局优化优化过程中， 分别采用CGA 算法、SACGA 算法进行排产优化效果对比分析，SACGA 算法在FFS 的全局优化过程中能够获取更高设备利用率。证明采用SACGA 的全局优化方法可以得到更好的排产优化调度结果。