刘倩等：基于“炉-机对应”的炼钢一连铸生产调度问题遗传优化模型 649. 2.3适应度计算 (3)算法A3:启发式算法，以目标炉次工序间 遗传算法的适应度计算是染色体性状的评价 总等待时间最小为优化目标，在连续浇铸的前提 指标.基于排序选择能够根据适应度的大小进行 下，倒推出各炉次在各工序的开始和结束作业时 选择操作，能够保留优良个体能直接进入后代种 间，以设备时间冲突最小规则为炉次指派设备，生 群，因此，本文选择基于排序选择的适应度计算， 成粗调度，再用线性规划模型消除设备冲突 其适应度分配的计算公式为： 图4为改进遗传算法求解步骤，输入钢厂浇次 F=2-SP+2(SP-1)(Pos-1)/Nind-1)(9) 计划信息及算法参数，根据“炉-机对应”策略进行 其中，F表示适应度，Nind为种群中个体数目， 设备指派，然后倒推计算出炉次在精炼和冶炼设 Pos为个体在种群中的排序位置，SP为选择压力， 备工序的开工时间；若产生炉次作业时间冲突，遵 一般取[1.0,2.01，这里取2.0 循先到先加工原则，返回炉次上一工序，重新对炉 2.4遗传操作 次加工顺序进行调整，消除时间冲突；此时，若满 通过编码组成初始群体后，遗传操作的任务 足进化代数直接输出最优解，若不满足，通过适应 就是对个体按照它们对适应度大小进行选择、交 度计算选择最优个体进入下一代，再进行交叉、局 叉和变异，从而实现优胜劣汰的进化过程.遗传操 部搜索和变异操作，形成新一代种群，重复上述操 作的关键步骤如下： 作直至产生最优解 (1)选择操作：选择操作是在适应度函数的评 3实验结果讨论分析 估上进行的，通过基于排序适应度选择方法进行 操作，将上一代优良的个体保留下来，淘汰性能较 以国内某炼钢厂的生产调度方案编制为例， 差的个体 用上文提出的三种算法对本文建立炼钢-连铸生 (2)交叉操作：随机选择种群内某两个个体， 产调度模型进行求解，从时间结果和炉-机匹配程 交换两个个体上同一炉次i在工序j的加工设备 度两方面进行分析和评价，选出优化性能最佳的 (不包含连铸工序) 算法及生产调度方案 (3)局部搜索：将(2)中当前最优解作为局部 3.1实验背景及数据 搜索的初始解，通过邻域动作交换相邻工序上的 国内某钢厂现有4座转炉(BOF)、4座LF精 设备指派（不包括连铸工序），从当前解的临近解 炼炉(LF)、4台连铸机(CCM),由于4台连铸机的 空间中选择一个最优解作为当前解，迭代100次， 生产能力大于4座转炉（精炼炉），因此，兼顾工序 直到达到最优解 产能匹配和产能最大化的前提下，主要采用4座 (4)变异操作：随机选择种群内某个个体工序 转炉供应3台连铸机的生产模式.其生产模式主 了上的任意两台设备，并从两台设备上分别随机选 要有：4BOF-3CCM模式大约占比80%，4BOF-4CCM 择所加工的炉次、进行交换 模式大约占比10%，3BOF-3CCM模式占10%. 2.5基于“炉-机对应”策略的改进遗传算法 本文第2节的算法采用C#语言进行编程，运 为获得更为合理、可行性高的调度方案，考虑 行于Microsoft Visual Studio软件.基于前人的研究 到等待时间和“炉一机对应”程度的相互制约，本文 成果20，四，经过多次实验，确定改进遗传算法参数 在遗传算法初始种群生成过程中引入“炉一机对 设置如下：进化代数为100，种群规模为500.自适 应”策略，构建改进遗传算法模型.此外，为考察改 应函数参数pc=0.8、pm=0.001 进遗传算法的高效性，采用启发式算法作为对照 3.2实验结果与分析 实验，详细说明如下 下面运用本文建立三种算法进行生产调度方 (1)算法A1:不包含“炉-机对应”策略的遗传 案的求解，从运行过程的等待时间和炉-机匹配程 算法； 度两方面对调度方案进行分析讨论 (2)算法A2:在A1算法基础上，种群生成过 3.2.1等待时间分析 程中引入“炉一机对应”调控策略，若个体满足 由上文的研究可知，本文提出三种算法来比 22节中的策略(1)或(3)，则该个体对应工序上的 较调度方案的有效性，除炉次各工序间等待时间 炉次不进行交叉、变异操作；若个体不满足策略 之和最小的目标函数T。之外，还选取部分能够反 (1)或(3)，则该个体对应工序上的炉次进行交叉、 映实际生产顺行情况的数据作为算法有效性的评 变异操作 价指标，即工序间最长等待时间T、工序间等待时2.3    适应度计算 遗传算法的适应度计算是染色体性状的评价 指标. 基于排序选择能够根据适应度的大小进行 选择操作，能够保留优良个体能直接进入后代种 群，因此，本文选择基于排序选择的适应度计算， 其适应度分配的计算公式[14] 为： F = 2−SP+2(SP−1) (Pos−1) / (Nind−1) （9） 其中 ， F 表示适应度 ， Nind 为种群中个体数目 ， Pos 为个体在种群中的排序位置，SP 为选择压力， 一般取 [1.0，2.0]，这里取 2.0. 2.4    遗传操作 通过编码组成初始群体后，遗传操作的任务 就是对个体按照它们对适应度大小进行选择、交 叉和变异，从而实现优胜劣汰的进化过程. 遗传操 作的关键步骤如下： （1）选择操作：选择操作是在适应度函数的评 估上进行的，通过基于排序适应度选择方法进行 操作，将上一代优良的个体保留下来，淘汰性能较 差的个体. （2）交叉操作：随机选择种群内某两个个体， 交换两个个体上同一炉次 i 在工序 j 的加工设备 （不包含连铸工序）. （3）局部搜索：将（2）中当前最优解作为局部 搜索的初始解，通过邻域动作交换相邻工序上的 设备指派（不包括连铸工序），从当前解的临近解 空间中选择一个最优解作为当前解，迭代 100 次， 直到达到最优解. （4）变异操作：随机选择种群内某个个体工序 j 上的任意两台设备，并从两台设备上分别随机选 择所加工的炉次 i'、i"进行交换. 2.5    基于“炉−机对应”策略的改进遗传算法 为获得更为合理、可行性高的调度方案，考虑 到等待时间和“炉−机对应”程度的相互制约，本文 在遗传算法初始种群生成过程中引入“炉−机对 应”策略，构建改进遗传算法模型. 此外，为考察改 进遗传算法的高效性，采用启发式算法作为对照 实验，详细说明如下. （1）算法 A1：不包含“炉−机对应”策略的遗传 算法； （2）算法 A2：在 A1 算法基础上，种群生成过 程中引入 “ 炉 −机对应 ” 调控策略 ，若个体满 足 2.2 节中的策略（1）或（3），则该个体对应工序上的 炉次不进行交叉、变异操作；若个体不满足策略 （1）或（3），则该个体对应工序上的炉次进行交叉、 变异操作. （3）算法 A3：启发式算法，以目标炉次工序间 总等待时间最小为优化目标，在连续浇铸的前提 下，倒推出各炉次在各工序的开始和结束作业时 间，以设备时间冲突最小规则为炉次指派设备，生 成粗调度，再用线性规划模型消除设备冲突. 图 4 为改进遗传算法求解步骤，输入钢厂浇次 计划信息及算法参数，根据“炉−机对应”策略进行 设备指派，然后倒推计算出炉次在精炼和冶炼设 备/工序的开工时间；若产生炉次作业时间冲突，遵 循先到先加工原则，返回炉次上一工序，重新对炉 次加工顺序进行调整，消除时间冲突；此时，若满 足进化代数直接输出最优解，若不满足，通过适应 度计算选择最优个体进入下一代，再进行交叉、局 部搜索和变异操作，形成新一代种群，重复上述操 作直至产生最优解. 3    实验结果讨论分析 以国内某炼钢厂的生产调度方案编制为例， 用上文提出的三种算法对本文建立炼钢‒连铸生 产调度模型进行求解，从时间结果和炉−机匹配程 度两方面进行分析和评价，选出优化性能最佳的 算法及生产调度方案. 3.1    实验背景及数据 国内某钢厂现有 4 座转炉（BOF）、4 座 LF 精 炼炉（LF）、4 台连铸机（CCM），由于 4 台连铸机的 生产能力大于 4 座转炉（精炼炉），因此，兼顾工序 产能匹配和产能最大化的前提下，主要采用 4 座 转炉供应 3 台连铸机的生产模式. 其生产模式主 要有：4BOF−3CCM 模式大约占比 80%，4BOF−4CCM 模式大约占比 10%，3BOF−3CCM 模式占 10%. 本文第 2 节的算法采用 C#语言进行编程，运 行于 Microsoft Visual Studio 软件. 基于前人的研究 成果[20, 22] ，经过多次实验，确定改进遗传算法参数 设置如下：进化代数为 100，种群规模为 500，自适 应函数参数 pc= 0.8、pm= 0.001. 3.2    实验结果与分析 下面运用本文建立三种算法进行生产调度方 案的求解，从运行过程的等待时间和炉−机匹配程 度两方面对调度方案进行分析讨论. 3.2.1    等待时间分析 由上文的研究可知，本文提出三种算法来比 较调度方案的有效性. 除炉次各工序间等待时间 之和最小的目标函数 T0 之外，还选取部分能够反 映实际生产顺行情况的数据作为算法有效性的评 价指标，即工序间最长等待时间 T1、工序间等待时 刘    倩等： 基于“炉−机对应”的炼钢−连铸生产调度问题遗传优化模型 · 649 ·