本发明提出了一种利用优先级策略混合遗传算法的炼钢连铸生产调度方法，包括如下步骤：建立生产调度计划目标函数，建立约束条件集，利用优先级策略混合遗传算法对目标函数进行迭代运算，求取决策变量，具体为：进行模型初始化；计算可行解：设计了由连铸机开浇时间信息和炉次加工设备信息构成的分段式组合实数编码，依据分布规律随机产生作业时间，由倒推计算和冲突消除方法得到无时间冲突的调度计划；种群遗传优化：用任务可执行设备的加工权重赋值来量化描述现实中加工设备间的匹配关系，并以设备选择优先级策略的形式引入到遗传操作，进行种群进化。该方法能够解决生产中的设备选择和作业时间的不确定性问题，得到优化的可执行生产调度计划。
1.一种利用优先级策略混合遗传算法的炼钢连铸生产调度方法，其特征在于，包括如下步骤：S1，炼钢连铸调度控制器分别与炼钢厂的MES数据库及MES客户端系统连接并获取炼钢厂的MES数据库及MES客户端系统中的炼钢连铸计划数据；
其中，α1为连铸机偏离预定开浇时间所产生的惩罚费用系数，α2为炉次在生产中等待时间所产生的惩罚费用系数；α1和α2皆为算法可调参数；
f1表示各连铸机偏离预定开浇时间量的总和，f2表示各浇次内的所有炉次在生产过程中等待时间的总和，具体表示为：其中，L为连铸机的数量；Tq为第q台连铸机预定的开浇时间；tq为第q台连铸机实际的开浇时间，即炉次i在工序M设备q上加工的开浇时间为N为炉次总数，i为加工炉次，M为工序总数，Ωj为炉次i在工序j上可用设备的集合，是为炉次i在工序j-1设备kj-1和工序j设备kj之间的运输时间；工序j-1为工序j的紧前工序，设备kj-1为设备kj的紧前设备；
Kj为工序j上所有设备集合， 为炉次i在工序j设备kj上作业前的等待时间；
为炉次i在工序j设备kj上加工的开始时间； 为炉次i在紧前工序j-1设备kj-1上的开始时间； 为炉次i在紧前工序j-1设备kj-1上的结束时间； 为炉次i在紧前工序j-1设备kj-1上的加工时间；
S3，建立约束条件集，所述约束条件集包括如下约束条件之一或任意组合：各浇次内炉次的连浇约束条件，炉次在工序前有限等待时间约束条件，机器能力析取约束条件，炉次在每道工序上最多被加工一次的约束条件，同一炉次要等到前一工序加工完才可进行下一工序加工的约束条件，设备最早可用约束条件，可选设备约束条件，生产中时间不确定性约束条件；
S4，利用优先级策略混合遗传算法对目标函数进行迭代运算，求取决策变量，具体的算法包括如下步骤：S41，进行模型初始化：输入模型参数信息并且初始化遗传算法迭代计数器t＝0，产生种群规模为Q的初始种群P(t)；
S42，计算可行解：确定的染色体编码，依据时间分布规律随机产生作业时间，根据逆流程的倒推计算和设备上的冲突消除方法得到无时间冲突的生产调度计划；
S43，进行种群遗传优化：依据设备的任务加工权重，通过结合现实环境中设备选择优先级策略的遗传变异、交叉操作，进行种群进化，产生优化解并输出；
S5，控制器根据输出的最优解得到优化的炼钢-连铸生产调度计划，并对生产运行系统实施有效控制。
2.如权利要求1所述的利用优先级策略混合遗传算法的炼钢连铸生产调度方法，其特征在于：所述步骤S3中约束条件集中，具体的约束条件为：
其中，i+1为同一设备上加工炉次i的紧后炉次； 为末尾工序M设备kM上相邻炉次间因辅助作业产生的间隙时间，包括钢包回转台通过转动将待浇侧钢水包转动到浇铸侧所需的时间；
其中， 为炉次i在工序j设备kj上作业前的最大允许等待时间；
3)机器能力析取约束条件,即机器同时只能加工一件任务：其中， 为工序j设备kj上相邻炉次间因辅助作业产生的间隙时间；
其中， 为炉次i被分配到工序j的设备kj加工的决策变量；
5)同一炉次要等到前一工序加工完才可进行下一工序加工的约束条件：其中，j-1为同一炉次的工艺路径中工序j的紧前工序； 为炉次i在工序j-
6)设备最早可用约束条件，即各设备上第一炉次的开始作业时间晚于该设备的最早可用时：其中， 为工序j设备kj上第一炉次的开始作业时间， 为初始时刻工序j设备kj的最早可用时间，所述初始时刻指的是计划编制时刻各设备的最早可用时间；
7)可选设备约束条件，即炉次只能选择紧后工序上任务加工权重值非零的设备进行加工：ω[(j-1,kj-1),(j,kj)]≥0，
其中，ω[(j-1,kj-1),(j,kj)]为炉次从工序j-1设备kj-1转至紧后工序j设备kj上的任务加工权重；
8)生产中时间不确定性约束条件，即设备加工时间和设备间运输时间在一定范围内波动；
其中， 和 分别为工序j-1设备kj-1和工序j设备kj之间的最小和最大运输时间， 和 分别为炉次i在工序j设备kj上最小加工时间和最大加工时间。
3.如权利要求1所述的利用优先级策略混合遗传算法的炼钢连铸生产调度方法，其特征在于：所述步骤S42中采用的分段式组合染色体编码方法：C＝{(T1,T2,...,TL),(a1b1f1g1,a2b2f2g2,...,aNbNfNgN)},其中，(T1,T2,...,TL)为开浇时间编码，(a1b1f1g1,a2b2f2g2,...,aNbNfNgN)为各炉次加工路径编码，T1是1#连铸机开浇时间，TL为L#连铸机的开浇时间，aNbNfNgN为N#炉次的加工路径为：a#转炉—b#LF—f#RH—g#连铸机,其中，LF为钢包精炼炉；RH为真空循环脱气精炼炉。
4.如权利要求1所述的利用优先级策略混合遗传算法的炼钢连铸生产调度方法，其特征在于：所述步骤S42中逆流程的倒推算法为：设定计算初始值为无等待生产过程，即
计算所用作业时间和运输时间均采用依实际分布规律产生的随机值，具体步骤为：S421，令j＝M，并由批量计划信息和染色体中连铸机开浇时间信息，计算出所有任务在最后一道工序，即连铸工序上的开始和结束作业时间；
S422，根据染色体中各炉次生产路径信息，通过随机产生的作业时间和运输时间，倒推出工序j上各炉次任务在紧前工序j-1上的开始和结束作业时间；
S423，检查工序j-1上各工位是否存在作业时间冲突，若有，应用冲突消除算法解决；
S424，判断工序j-1是否是生产流程第一道工序，即转炉工序，若(j-1)＞1，则令j＝j-
S425，由工位可用约束： 和有限等待时间约束： 标记该生产调度计划是否合理。
5.如权利要求1所述的利用优先级策略混合遗传算法的炼钢连铸生产调度方法，其特征在于：所述步骤S42中设备上的冲突消除方法为：冲突消除算法是统计相邻炉次间冲突时间大小，采取调整运输时间、作业时间以及增加等待时间来消除，具体的调整策略如下：若冲突时间超过调整运输时间、作业时间以及增加等待时间的总的最大能力，则冲突时间全部计入等待时间，并标记该生产调度计划不合格，若冲突时间小于调整运输时间和作业时间的总的最大能力，则冲突时间通过调整运输时间和作业时间来消除，若冲突时间在以上两种情况之间，则通过调整运输时间、作业时间以及增加等待时间来消除。
6.如权利要求1所述的利用优先级策略混合遗传算法的炼钢连铸生产调度方法，其特征在于：所述交叉操作中，开浇时间编码的结合优先级策略的算术交叉方法为：CT1′＝r×CT1+(1-r)×CT2
其中，r为[0,1]之间的随机数,CT1，CT2为父代染色体的开浇时间编码，CT1′，CT2′为子代染色体的开浇时间编码。
7.如权利要求1所述的利用优先级策略混合遗传算法的炼钢连铸生产调度方法，其特征在于：所述交叉操作中，炉次加工路径的编码的结合优先级策略的均匀交叉方法为：两个父代对应的每一位基因都以一定交叉概率进行交换，即炉次i的两个父代染色体子串中对应于工序j的基因位值 和 的交叉概率P(j)值为：其中， 为工序j设备 对应于工序j+1设备 的加工权重值，为工序j设备 对应于工序j+1设备 的加工权重值。
8.如权利要求1所述的利用优先级策略混合遗传算法的炼钢连铸生产调度方法，其特征在于：所述变异操作中，开浇时间的编码变异操作方法为：其中，β是连铸机开浇时间的扰动量，为变异前连铸机开浇时间，为变异后连铸机开浇时间。
9.如权利要求1所述的利用优先级策略混合遗传算法的炼钢连铸生产调度方法，其特征在于：所述变异操作中，各炉次加工路径的编码变异操作方法为：对于炉次i的染色体子串执行变异操作时，其对应于工序j的基因位值 变异成该工序上其它设备 的变异概率p(j)为：其中， 为工序j-1设备kj-1对应于工序j设备 的加工权重值，为工序j设备 对应于工序j+1设备kj+1的加工权重值。
10.如权利要求1、2、7、9之一所述的利用优先级策略混合遗传算法的炼钢连铸生产调度方法，其特征在于：所述任务加工权重的赋值方法为：若因生产布局或设备故障等导致工序j设备kj为工序j-1设备kj-1的不可达设备，则ω[(j-1,kj-1),(j,kj)]＝0，若工序j上仅有设备kj为工序j-1设备kj-1的可达设备，则ω[(j-1,kj-1),(j,kj)]＝1，
若工序j上存在多个工序j-1设备kj-1的可达设备 则其中：
ω[(j-1,kj-1),(j,kj)]为炉次从工序j-1设备kj-1转至紧后工序j设备kj上的任务加工权重值。
利用优先级策略混合遗传算法的炼钢连铸生产调度方法
技术领域
[0001] 本发明涉及冶金控制技术领域，具体涉及一种利用优先级策略混合遗传算法的炼钢连铸生产调度方法。
背景技术
[0002] 炼钢连铸生产调度是钢铁企业生产管理的重要组成部分。在现实生产中，由于生产环境和生产条件存在多种不确定性，会导致生产调度计划难以执行或执行的效果受限。因此，研究可执行生产调度计划的合理高效制定方法，对提升生产系统的整体运行效率，降低物耗、能耗和成本等具有重要意义。
[0003] 近年来，炼钢连铸生产调度问题作为研究热点，主要围绕建模与模型求解方法进行。建模方法主要有数学规划建模、图形化建模和仿真建模等，其中，数学规划建模是最常用的模型描述方法。问题的优化求解方法主要有最优化方法和近似优化方法。最优化方法包括数学规划、分枝定界和拉格朗日法等数学方法，这类方法对于小规模的生产调度问题能够有效求解。还有混合整数线性规划模型，用于描述炼钢生产中的工艺约束并求解炼钢连铸生产调度问题，模型对除连铸工序外的作业时间作了标准化处理。近似优化方法主要包括多种智能计算方法(遗传算法、蚁群算法、蜂群算法等)、启发式方法、人工智能方法以及多种方法的混合方法等。近似优化求解方法具有较高的求解效率，更加面向实际应用，但求解结果的合理性还需进一步检验。
[0004] 目前，不确定条件下的生产调度问题开始受到关注。现有的方法主要采用了随机变量、模糊理论和粗糙集理论等对不确定问题进行处理。现有技术中还有利用广义粗糙集理论描述不确定变量的建模方法，并用差分进化算法求解；以及采用模糊数表示不确定加工时间信息，建立了炼钢连铸生产调度问题的模糊规划模型并进行求解。这类方法主要集中于生产调度中时间不确定性问题，对设备选择的不确定性问题，一般是以假设设备分派不受限制或者采用启发式分派规则的简化处理方法，这样可能会导致生产调度计划难以执行等问题。
发明内容
[0005] 为了克服上述现有技术中存在的缺陷，本发明的目的是提供一种利用优先级策略混合遗传算法的炼钢连铸生产调度方法，该方法能够解决生产中的设备选择和作业时间的不确定性问题，得到优化的可执行生产调度计划。
[0006] 为了实现本发明的上述目的，本发明提供了一种利用优先级策略混合遗传算法的炼钢连铸生产调度方法，包括如下步骤：
[0007] S1，炼钢连铸调度控制器分别与炼钢厂的MES数据库及MES客户端系统连接并获取炼钢厂的MES数据库及MES客户端系统中的炼钢连铸计划数据；
[0008] S2，建立生产调度计划目标函数，所述目标函数为：
[0009] minZ＝α1×f1+α2×f2
[0010] 其中，α1为连铸机偏离预定开浇时间所产生的惩罚费用系数，α2为炉次在生产中等待时间所产生的惩罚费用系数；α1和α2皆为算法可调参数。
[0011] f1表示各连铸机偏离预定开浇时间量的总和，f2表示各浇次内的所有炉次在生产过程中等待时间的总和，具体表示为：
[0012]
[0013]
[0014] 其中，L为连铸机的数量；Tq为第q台连铸机预定的开浇时间；tq为第q台连铸机实际的开浇时间，即
[0015] N为炉次总数，i为加工炉次，M为工序总数，Ωj为炉次i在工序j上可用设备的集合， 是为炉次i在工序j-1设备kj-1和工序j设备kj之间的运输时间；工序j-1为工序j的紧前工序，设备kj-1为设备kj的紧前设备；
[0016] Kj为工序j上所有设备集合， 为炉次i在工序j设备kj上作业前的等待时间；
[0017] 为炉次i在工序j设备kj上加工的开始时间； 为炉次i在紧前工序j-1设备kj-1上的开始时间； 为炉次i在紧前工序j-1设备kj-1上的结束时间； 为
炉次i在紧前工序j-1设备kj-1上的加工时间；
[0018] S3，建立约束条件集，所述约束条件集包括如下约束条件之一或任意组合：各浇次内炉次的连浇约束条件，炉次在工序前有限等待时间约束条件，机器能力析取约束条件，炉次在每道工序上最多被加工一次的约束条件，同一炉次要等到前一工序加工完才可进行下一工序加工的约束条件，设备最早可用约束条件，可选设备约束条件，生产中时间不确定性约束条件；
[0019] S4，利用优先级策略混合遗传算法对目标函数进行迭代运算，求取决策变量，具体的算法包括如下步骤：
[0020] S41，进行模型初始化：输入模型参数信息并且初始化遗传算法迭代计数器t＝0，产生种群规模为Q的初始种群P(t)；
[0021] S42，计算可行解：确定的染色体编码，依据时间分布规律(根据钢种及作业类型统计)随机产生作业时间，根据逆流程的倒推计算和设备上的冲突消除方法得到无时间冲突的生产调度计划；
[0022] S43，进行种群遗传优化：依据设备的任务加工权重，通过结合现实环境中设备选择优先级策略的遗传变异、交叉操作，进行种群进化，产生优化解并输出；
[0023] S5，控制器根据得到的最优解进行炼钢-连铸生产的作业计划编制，并对生产运行系统实施有效控制。
[0024] 本发明的利用优先级策略混合遗传算法的炼钢连铸生产调度方法对于设备选择的不确定性问题，提出了赋予设备任务加工权重值的量化描述方法，并以设备选择优先级策略的形式结合遗传算法形成了模型的优化求解算法，能够解决不确定条件下的炼钢连铸调度问题。
[0025] 本发明的附加方面和优点将在下面的描述中部分给出，部分将从下面的描述中变得明显，或通过本发明的实践了解到。
附图说明
[0026] 本发明的上述和/或附加的方面和优点从结合下面附图对实施例的描述中将变得明显和容易理解，其中：
[0027] 图1是现有技术中炼钢-连铸生产过程示意图；
[0028] 图2是本发明利用优先级策略混合遗传算法的炼钢连铸生产调度方法的算法流程；
[0029] 图3是本发明一种优选实施方式中的炼钢厂生产流程简图；
[0030] 图4是利用本发明的混合遗传算法编制的生产调度计划甘特图；
[0031] 图5是各炉次从转炉出钢至连铸机开始浇铸的流程作业时间的仿真计算值与生产实绩比较图。
具体实施方式
[0032] 下面详细描述本发明的实施例，所述实施例的示例在附图中示出，其中自始至终相同或类似的标号表示相同或类似的元件或具有相同或类似功能的元件。下面通过参考附图描述的实施例是示例性的，仅用于解释本发明，而不能理解为对本发明的限制。
[0033] 图1是现有炼钢-连铸过程主要包含的3个生产环节：炼钢、精炼和连铸。炼钢与连铸环节各自包含一个并行机组，而精炼环节一般包含多个并行机组，以实现不同精炼工艺要求。一般性的炼钢-连铸生产过程如图1所示：从高炉运来的高温铁水经铁水预处理工序后兑入转炉冶炼成钢水，钢水倒入转炉下台车上的钢包内，通过天车和台车的运输作业，把钢水包运送至精炼环节，根据生产工艺要求依次在不同的精炼设备上精炼钢水，精炼完成后，再通过天车和台车，把钢水包运送至连铸并实施浇铸，形成铸坯。
[0034] 在钢厂生产调度中，炉次是指某个转炉在一个冶炼周期内生产的钢水，由于一个炉次的钢水被装入一个钢包中，所以从炼钢到连铸前被调度的对象均为炉次，炉次是钢厂生产调度中最小的生产单元。浇次是指在同一连铸机上连续浇铸的炉次集合，是钢厂生产调度中最大的生产单元。炼钢-连铸调度方案制定流程是：首先将用户合同按照技术标准转化为生产合同；然后根据炼钢生产能力和工艺要求等编制炉次计划和浇次计划，并结合热轧轧制能力和工艺要求等编制热轧单元计划，形成炼钢与热轧生产相协调的生产批量计划。在生产批量计划中，已经确定了浇次的浇铸连铸机以及浇次内炉次的加工顺序和生产工艺。
[0035] 炼钢连铸生产调度是在生产批量计划的基础上,以计划期内若干浇次中的炉次为最小计划单位,在满足生产工艺约束的前提下,追求综合评价函数的效果最佳的情况下，安排N个炉次到M道工序中的若干设备K上进行生产。即是要确定炉次i从转炉到连铸的生产过程中，选择适当的工序设备 以执行炼钢－精炼－连铸等加工任务，并且确定炉次在设备上加工的开始时间 加工时间 和结束时间
[0036]
[0037] 且有i∈(1,N),j∈(1,M),k∈(1,Kj),Kj为工序j上所有设备的集合。
[0038] 本发明为了解决不确定条件下的炼钢连铸调度问题，提出了利用优先级策略混合遗传算法的炼钢连铸生产调度方法，具体包括如下步骤：
[0039] 第一步：炼钢连铸调度控制器分别与炼钢厂的MES(Manufacturing Execution Systems，制造执行系统)数据库及MES客户端系统连接并获取炼钢厂的MES数据库及MES客户端系统中的炼钢连铸计划数据。根据以上数据解决不确定条件下的炼钢连铸调度问题。
[0040] 第二步：建立求解模型，本发明模型的基本假设：①已知批量计划；②已知连铸机的预定开浇时间(取连铸机在最早可开浇时刻后的预定开浇时间的经验值，具体经验证采用相应炼钢厂的经验数据)；③炉次沿生产流程加工时，物流时间由三部分构成：在工序前的等待时间、在工序上的作业时间和运送至下一个工序的运输时间；④已知炉次在各工序上作业时间及工序间运输时间的分布规律(由根据以前生产实际统计的现实生产作业时间统计得到)；⑤已知计划编制时刻的各设备最早可用时间。
[0041] 考虑到现实生产中的准时生产原则，以及过长等待时间会对钢水冶金性能产生影响，设定以最小化连铸机偏离预定开浇时间和炉次在工序前等待时间共同引起的惩罚费用为生产调度的优化目标。
[0042] 炼钢连铸生产调度计划模型目标函数为：
[0043] minZ＝α1×f1+α2×f2 (1)
[0044] 需要确定的决策变量为：
[0045] 其中，α1为连铸机偏离预定开浇时间所产生的惩罚费用系数，α2为炉次在生产中等待时间所产生的惩罚费用系数。
[0046] f1表示各连铸机偏离预定开浇时间量的总和，f2表示各浇次内的所有炉次在生产过程中等待时间的总和，具体表示为：
[0047]
[0048]
[0049] 其中，L为连铸机的数量；Tq为第q台连铸机预定的开浇时间；tq为第q台连铸机实际的开浇时间，即
[0050] N为炉次总数，i为加工炉次，M为工序总数，Ωj为炉次i在工序j上可用设备的集合， 是为炉次i在工序j-1设备kj-1和工序j设备kj之间的运输时间；工序j-1为工序j的紧前工序，设备kj-1为设备kj的紧前设备；
[0051] Kj为工序j上所有设备集合， 为炉次i在工序j设备kj上作业前的等待时间；
[0052] 为炉次i在工序j设备kj上加工的开始时间； 为炉次i在紧前工序j-1设备kj-1上的开始时间； 为炉次i在紧前工序j-1设备kj-1上的结束时间； 为
炉次i在紧前工序j-1设备kj-1上的加工时间；
[0053] 第三步：建立约束条件集，主要包括连铸机连浇、钢水生产工艺等常规生产的约束条件。并且，为描述生产过程中存在的设备选择和作业时间的不确定性问题，考虑用设备任务加工权重值非零来表示可选设备的约束，以及用根据现实作业时间统计分布中取随机数的方式来表示作业时间的随机约束。
[0054] 约束条件集包括如下约束条件之一或任意组合：各浇次内炉次的连浇约束条件，炉次在工序前有限等待时间约束条件，机器能力析取约束条件，炉次在每道工序上最多被加工一次的约束条件，同一炉次要等到前一工序加工完才可进行下一工序加工的约束条件，设备最早可用约束条件，可选设备约束条件，生产中时间不确定性约束条件。
[0055] 具体的约束条件为：
[0056] 1)各浇次内炉次的连浇约束条件：
[0057]
[0058] 其中，i+1为同一设备上加工炉次i的紧后炉次； 为末尾工序M设备kM上相邻炉次间因辅助作业产生的间隙时间，包括钢包回转台通过转动将待浇侧钢水包转动到浇铸侧所需的时间；
[0059] 2)炉次在工序前等待时间有限约束条件：
[0060]
[0061] 其中， 为炉次i在工序j设备kj上作业前的最大允许等待时间；
[0062] 3)机器能力析取约束条件,即机器同时只能加工一件任务：
[0063]
[0064] 其中， 为工序j设备kj上相邻炉次间因辅助作业产生的间隙时间；
[0065] 4)炉次在每道工序上最多被加工一次的约束条件：
[0066]
[0067] 5)同一炉次要等到前一工序加工完才可进行下一工序加工的约束条件：
[0068]
[0069] 其中，j-1为同一炉次的工艺路径中工序j的紧前工序； 为炉次i在工序j-1设备kj-1和工序j设备kj之间的运输时间；
[0070] 6)设备最早可用约束条件，即各设备上第一炉次的开始作业时间晚于该设备的最早可用时：
[0071]
[0072] 其中， 为工序j设备kj上第一炉次的开始作业时间， 为初始时刻工序j设备kj的最早可用时间，所述初始时刻指的是计划编制时刻各设备的最早可用时间；
[0073] 7)可选设备约束条件，即炉次只能选择紧后工序上任务加工权重值非零的设备进行加工：
[0074] ω[(j-1,kj-1),(j,kj)]≥0，
[0075] 其中，ω[(j-1,kj-1),(j,kj)]为炉次从工序j-1设备kj-1转至紧后工序j设备kj上的任务加工权重；
[0076] 8)生产中时间不确定性约束条件，即设备加工时间和设备间运输时间在一定范围内波动；
[0077]
[0078] 其中， 和 分别为工序j-1设备kj-1和工序j设备kj之间的最小和最大运输时间， 和 分别为炉次i在工序j设备kj上最小加工时
间和最大加工时间。
[0079] 第四步：利用优先级策略混合遗传算法对目标函数进行迭代运算，求取决策变量，算法流程包括模型初始化、可行解产生和种群优化三个阶段。其中可行解产生和种群优化阶段构成了模型的分步决策优化求解过程。如图2所示，在模型初始化阶段，输入钢厂制造流程网络的结构信息、批量计划信息以及算法所涉及各种参数信息(包括从生产数据库统计的作业时间分布、遗传算法参数等)，并且初始化遗传算法迭代器。在可行解产生阶段，根据确定的染色体编码，依据时间分布规律随机产生作业时间，根据逆流程的倒推计算和设备上的冲突消除编写相应算法得到无时间冲突的生产调度计划。考虑到生产过程中存在的作业时间的不确定性，允许上述过程循环进行，通过作业时间的多次随机产生，形成用于优化解搜索的由确定染色体编码所表达的解空间。在种群优化阶段，通过对解空间的搜索，以及结合现实环境中设备选择优先级策略的遗传操作，进行种群进化，直至产生优化解并输出。
[0080] 在本发明中，当产生下一代种群后，重新返回进行可行解计算(为一个循环)，本发明可以设置循环迭代次数，也可以设置退出的阈值，当循环迭代次数达到设定值或者前后两次的最优解之间的误差小于退出阈值，则结束迭代。
[0081] 在现实生产过程中，由于生产流程布局差异和设备状态的变化，各工序的设备之间的匹配关系是动态变化的。为此设计了用任务加工权重ω[(j-1,kj-1),(j,kj)]来量化描述这类可加工设备之间动态匹配关系的方法。ω[(j-1,kj-1),(j,kj)]代表了炉次从工序j-1设备kj-1转至紧后工序j设备kj的任务加工权重，其值的大小体现了设备间的可达状态以及设备选择的优先级高低。具体量化方法准则表示如下：
[0082] 准则1、若因生产布局或设备故障等导致工序j设备kj为工序j-1设备kj-1的不可达设备，则：ω[(j-1,kj-1),(j,kj)]＝0。
[0083] 准则2、若工序j上仅有设备kj为工序j-1设备kj-1的可达设备，
[0084] 则：ω[(j-1,kj-1),(j,kj)]＝1。
[0085] 准则3、若工序j上存在多个工序j-1设备kj-1的可达设备
[0086]
[0087] 则：
[0088]
[0089] 由此可知，ω[(j-1,kj-1),(j,kj)]最大值为1，此时工序j-1设备kj-1和工序j设备kj为设备匹配状态。
[0090] 基于以上量化描述方法，通过任务加工权重ω[(j-1,kj-1),(j,kj)]可以形成设备选择的优先级策略，即：任务加工权重ω[(j-1,kj-1),(j,kj)]值越大，代表了选择该设备进行任务加工的优先级越高，进而再将任务加工权重以优先级策略形式引入到遗传算法的交叉、变异操作中去，增加了遗传算法向着可行有序方向进化的概率，有利于产生优化解。
[0091] 本发明具体的算法如图2所示，包括如下步骤：
[0092] S41，进行模型初始化：输入模型已知参数信息并且初始化遗传算法迭代计数器t＝0，产生种群规模为Q的初始种群P(t)，具体是根据染色体编码随机产生的，种群是由染色体构成，而染色体是由两段数字编码构成。那么通过随机数产生形成数字编码，就能产生染色体。当产生Q个染色体时就构成了初始种群。
[0093] S42，计算可行解：确定的染色体编码，依据时间分布规律(根据钢种及作业类型统计)随机产生作业时间，根据逆流程的倒推计算和设备上的冲突消除方法得到无时间冲突的生产调度计划。
[0094] 针对生产过程中执行计划的设备选择不确定，本发明构造了包含连铸机开浇时间信息和各炉次加工路径信息的分段组合实数编码方式，其中编码第一部分包含了L台连铸机的开浇时间，第二部分包含了M个炉次任务的加工路径，即在各个工序上设备选择的信息。采用的染色体编码为：
[0095] C＝{(T1,T2,...,TL),(a1b1f1g1,a2b2f2g2,...,aNbNfNgN)},
[0096] 其中，(T1,T2,...,TL)为开浇时间编码，(a1b1f1g1,a2b2f2g2,...,aNbNfNgN)为各炉次加工路径编码，T1是1#连铸机开浇时间，TL为L#连铸机的开浇时间，aNbNfNgN为N#炉次的加工路径为：a#转炉—b#LF(钢包精炼炉)—f#RH(真空循环脱气精炼炉)—g#连铸机。
[0097] 例如，染色体C＝{(T1，T2…TL)，(1201,3211…3122)}，
[0098] 其中，T1代表1#连铸机开浇时间为第T1min；TL代表L#连铸机的开浇时间为第TLmin；1201代表1#炉次的生产路径为:1#转炉—2#LF—1#连铸机；3122代表N#炉次的加工路径为：3#转炉—1#LF—2#RH—2#连铸机。
[0099] 基于以上的编码方式，在算法求解过程中对其解码，便可得到各炉次沿生产流程的设备选择信息。通过按作业时间的统计分布随机产生加工时间和运输时间，再采用倒推和冲突消除算法，便可得到对应染色体的无时间冲突的调度计划。
[0100] 倒推算法为：
[0101] 设定计算初始值为无等待生产过程，即
[0102] 计算所用作业时间和运输时间均采用依实际分布规律产生的随机值，具体步骤为：
[0103] S1，令j＝M，并由批量计划信息和染色体中连铸机开浇时间信息，计算出所有任务在最后一道工序，即连铸工序上的开始和结束作业时间，各炉次的开始作业时间：结束作业时间是用开始作业时间加上加工时间，即：
[0104] S2，根据染色体中各炉次生产路径信息，通过随机产生的作业时间和运输时间，倒推出工序j上各炉次任务在紧前工序j-1上的开始和结束作业时间，具体为：
[0105] 炉次i在紧前工序j-1上的结束作业时间：
[0106] 炉次i在紧前工序j-1上的开始作业时间：
[0107] S3，检查工序(j-1)上各工位是否存在作业时间冲突，若有，应用冲突消除算法解决，
[0108] S4，判断工序(j-1)是否是生产流程第一道工序(转炉)，若(j-1)＞1，则令j＝j-1，转回步骤S2；否则执行步骤S5；
[0109] S5，由工位可用约束： 和有限等待时间约束： 标记该生产调度计划是否合理。
[0110] 在本实施方式中，倒推算法也可以采用现有的已经公开的倒推算法。
[0111] 设备上的任务冲突消除方法为：
[0112] 冲突消除算法是统计相邻炉次间冲突时间大小：采取调整运输时间、作业时间以及增加等待时间来消除。其中，作业时间受钢种及作业类型影响，可调范围较小；而运输时间与加工路径有关，可调范围较大。具体的调整策略如下：
[0113] 策略1，若冲突时间超过调整运输时间、作业时间以及增加等待时间的总的最大能力，则冲突时间全部计入等待时间，并标记该作业计划不合格，
[0114] 即：如果
[0115]
[0116]
[0117]
[0118]
[0119] 策略2，若冲突时间小于调整运输时间和作业时间的总的最大能力，则冲突时间通过调整运输时间和作业时间来消除，
[0120] 即：如果
[0121]
[0122]
[0123]
[0124]
[0125] 策略3，若冲突时间在以上两种情况之间，则通过调整运输时间、作业时间以及增加等待时间来消除，
[0126] 即：
[0127]
[0128]
[0129]
[0130] S43，进行种群遗传优化：依据设备的任务加工权重，通过结合现实环境中设备选择优先级策略的遗传变异、交叉操作，进行种群进化，产生优化解并输出。
[0131] 在遗传算法中，选择操作通过适应度选择优质个体而抛弃劣质个体。本发明采用最优个体保存策略以保证遗传过程中所得到的最优个体不会被交叉和变异操作破坏，这是遗传算法收敛性的重要保证条件。
[0132] 鉴于构成解的染色体是由连铸机开浇时间和计划执行设备的两段编码构成，并且两段编码数据结构有所不同，故染色体采用分段遗传操作方式进行：连铸机开浇时间部分的编码采用算术交叉和扰动变异的方法；而计划执行设备部分的编码，是通过将设备选择优先级策略引入到遗传操作中，依据各设备上任务加工权重值确定均匀交叉操作中的交叉概率和基本位变异操作中的变异概率。遗传操作算法流程描述如下：
[0133] Step1：将上代种群P(t)中除最优个体外的剩余染色体存入集合Ωp(t)中，并且令染色体交叉计数器ic＝1；
[0134] Step2：交叉操作。从集合Ωc中随机抽取两个父代染色体C1和C2，并以概率Pc进行交叉，得到两个子代染色体C′1和C′2。
[0135] Step3：从集合Ωp(t)中删除染色体C1和C2，并将染色体C′1和C′2存入集合Ωp(t+1)′中。若集合Ωp(t)不为空，令ic＝ic+2,返回Step2；否则执行Step4。
[0136] Step4：令染色体变异计数器im＝1
[0137] Step5：变异操作。从集合Ωp(t+1)′中抽取父代染色体C1′，并且以概率Pm进行变异，得到子代染色体C″1；
[0138] Step6：从集合Ωp(t+1)′中删除染色体C1′，并将染色体C″1存入集合Ωp(t+1)中。若集合Ωp(t+1)′不为空，令im＝im+1，返回Step5；否则结束，集合Ωp(t+1)中的染色体与上代种群中的最优个体共同组成新一代种群P(t+1)。
[0139] 关键遗传操作部分的实现方法为：
[0140] (1)交叉操作：
[0141] 1)模型中将连铸机偏离预定开浇时间总量作为优化目标之一，故开浇时间的编码采用算术交叉操作以控制其变化范围，避免多次交叉后造成大幅偏离预定开浇时间的现象，从而提高了作业计划的合理性和可执行性。
[0142] 交叉操作中，开浇时间的编码交叉操作方法为：
[0143] CT1′＝r×CT1+(1-r)×CT2
[0144] CT2′＝r×CT2+(1-r)×CT1
[0145] 其中，r为[0,1]之间的随机数,CT1，CT2为父代染色体的开浇时间编码，CT1′，CT2′为子代染色体的开浇时间编码。
[0146] 2)各炉次加工路径的编码采用均匀交叉法，即两个父代对应的每一位基因都以一定交叉概率进行交换。即，炉次i的两个父代染色体子串中对应于工序j的基因位值 和的交叉概率P(j)值为：
[0147]
[0148] P(j)值的大小取决于交叉后子代染色体中工序j设备 对应于工序j+1设备的加工权重值 和工序j设备 对应于工序j+1设备 的加工权重值对P(j)值的非零效核可以保证交叉后的子代染色体的合法性。同时，
P(j)值越大，则该部分编码以更大的概率向设备匹配状态更佳的加工路径演化，有利于产生优化解。
[0149] (2)变异操作：
[0150] 1)各连铸机开浇时间编码变异：增加或减少一个随机扰动
[0151] 即：
[0152] β为[a,b]之间的随机量,[a,b]为人工设定的较小扰动区间，具体可根据生产实际要求设定，以避免多次变异后连铸机开浇时间大幅偏离预定开浇时间，为变异前连铸机开浇时间，为变异后连铸机开浇时间。
[0153] 2)炉次生产路径编码采取基本位变异，即随机指定某些基因位(除对应于连铸工序的基因位)进行变异。对于炉次i的染色体子串执行变异操作时，其对应于工序j的基因位值 变异成该工序上其它设备 的变异概率p(j)为：
[0154]
[0155] j+1为同一炉次的工艺路径中工序j的紧后工序。
[0156] p(j)值大小取决于变异后子代染色体中工序j-1设备kj-1对应于工序j设备 的加工权重值 和工序j设备 对应于工序j+1设备kj+1的加工权重值对p(j)值的非零判断可以效核变异后的新染色体是否合法。同时，p
(j)值越大，则该部分编码以较大概率向设备匹配状态更佳的加工路径演化，有利于解的更优化。
[0157] 本发明中，加工权重值函数以及其他变量中(例如 采用的自变量虽然有的形式不同，但是具体的计算方法一致。具体都按照本发明的准则确定。
[0158] 第五步：控制器根据得到的最优解进行炼钢-连铸生产的作业计划编制，并对生产运行系统实施有效控制。
[0159] 在本发明的一种优选实施方式中，混合遗传算法中不计算目标函数的最小值，而是计算适应度函数的最大值，适应度函数采用如下形式：
[0160]
[0161] Z为模型目标函数值，Cmax为一足够大正数，例如Cmax大于z。
[0162] 在本发明的一个优选实施方式中，以某炼钢厂的生产调度计划编制实例进行了算法的检验和应用测试。该炼钢厂有转炉炼钢-LF精炼-RH精炼-连铸四个主要生产工序，其生产流程简图如图3所示。统计生产实绩数据得到了各钢种在各工序上加工时间和设备间运输时间的分布规律。依据现实生产中某段时间的浇次计划进行仿真实验，如表1所示。遗传算法参数设置为:种群大小200，进化代数100，交叉概率Pc为0.8，变异概率Pm为0.01。经过多次实验，混合遗传算法均能在50s内得到优化的生产调度计划，如图4所示。
[0163] 表1浇次计划
[0164]
[0165] 图5为计划内各炉次(1≤i≤40)从转炉出钢至连铸机开始浇铸的流程作业时间的仿真计算值与生产实绩的比较，包括结合本发明设备选择优先级策略的混合遗传算法(HybridGeneticAlgorithm，HGA)仿真计算值，与未结合本发明设备选择优先级策略的基本遗传算法(SimpleGeneticAlgorithm，SGA)仿真计算值，以及生产实绩值的比较。表2给出了仿真计算与生产实绩的流程作业时间的统计平均值，由比较可知HGA和SGA的计算值均优于生产实绩，且HGA优化效果更为明显。这是因为现实生产中并未对生产计划进行优化，造成了现实生产中炉次往往有更长的运输距离及较长的等待时间。同时，图5还显示出作业时间的仿真计算值HGA方法较SGA方法要更趋于平稳，原因是由于在未经优化的SGA遗传操作中，设备选择的随机性更大，造成了个别炉次加工任务的生产路径更为复杂且不尽合理，从而增加了全流程作业时间。
[0166] 表2仿真计算与生产实绩的流程作业时间的统计平均值
[0167]
[0168] 在现实生产中，选择不同的加工路径会对运输环节产生不同的影响，如设备匹配较差的加工路径通常具有更长的运输距离或者更复杂的运输中转环节，物流更容易在途中因等待而导致较大的温降。因此可以用工序间设备匹配率来衡量物流在运输环节能否顺畅运行。
[0169] 相邻工序间设备匹配率的计算公式为：
[0170]
[0171] 其中设备匹配指炉次选择紧后工序上任务加工权重值ω[(j-1,kj-1),(j,kj)]最大的设备生产，即ω[(j-1,kj-1),(j,kj)]＝1。
[0172] 本发明对引入优先级策略的混合遗传算法(HGA)和未引入优先级策略的基本遗传算法(SGA)，在相同的输入条件下分别进行了10次仿真实验，其中对转炉-LF间设备匹配率ηBOF-LF、LF-CC间设备匹配率ηLF-CC和终解适应度函数值yE的比较结果如表3所示。
[0173] 表3仿真实验结果对比
[0174]
[0175] 对比实验结果，最终解的适应度函数平均值相当，因而两种遗传算法在减少钢水等待时间和保证准时生产上的优化性能相当。但是，由于未引入设备选择优先级策略的简单遗传算法在遗传过程中，生产设备的选择具有更大的随机性，因而各项性能指标值的变化幅度较大，并且在工序间设备匹配率上相比较低。而引入设备选择优先级策略的混合遗传操作，在进化过程中，染色体以较大概率向着设备匹配关系更好的生产路径演变，最终解的设备匹配率比简单遗传算法平均高出15％，解的合理性更优。
[0176] 本发明从有利于炼钢连铸生产调度计划可有效执行的角度，针对现实生产中存在的设备选择和作业时间的不确定性问题，提出了基于设备选择优先级策略的炼钢连铸调度计划制定的建模方法，以及相应的混合遗传求解算法。模型采用了作业时间分布函数的随机变量取值方法来描述生产作业时间的不确定性；并提出了用任务可执行设备的加工权重赋值来对现实生产中加工设备间匹配关系进行量化描述以解决设备选择的不确定性问题；同时将设备选择优先级策略引入遗传算法的遗传操作中形成混合遗传算法进行模型的优化求解。通过生成可行解、再进行解的优化的分步决策方式搜索解空间，能够便捷得到优化的可执行的炼钢连铸调度计划。针对某炼钢厂炼钢连铸调度计划的编制实例的仿真计算，结果表明了所提出的优先级策略混合遗传算法具有优化炉次加工路径、缩短流程作业时间、提高设备匹配率的效果，验证了模型和算法的有效性。进一步的研究将立足于把该算法扩展到现实生产扰动下的炼钢连铸动态调度问题领域，以更好适应复杂生产的需求。
[0177] 在本说明书的描述中，参考术语“一个实施例”、“一些实施例”、“示例”、“具体示例”、或“一些示例”等的描述意指结合该实施例或示例描述的具体特征、结构、材料或者特点包含于本发明的至少一个实施例或示例中。在本说明书中，对上述术语的示意性表述不一定指的是相同的实施例或示例。而且，描述的具体特征、结构、材料或者特点可以在任何的一个或多个实施例或示例中以合适的方式结合。
[0178] 尽管已经示出和描述了本发明的实施例，本领域的普通技术人员可以理解：在不脱离本发明的原理和宗旨的情况下可以对这些实施例进行多种变化、修改、替换和变型，本发明的范围由权利要求及其等同物限定。
