本发明公开了一种基于图模型的不确定炼钢‑连铸柔性优化调度方法及系统，该方法包括如下步骤：柔性调度模型构建，根据炼钢‑连铸生产过程的特征，运用图模型描述调度解的柔性决策形式，并设置时间缓冲以保护不确定条件下调度解的性能指标和可行性；基于分布估计算法的优化求解，使用基于工序关联的概率分布模型描述决策变量之间的关联关系以产生高质量的新种群，并采用随机仿真方法对柔性调度解的期望性能进行评价。在仿真过程中，运用最优计算量分配方法对有限计算资源进行动态分配以提高种群的评价效率。本发明实现了不确定环境下炼钢‑连铸调度过程等待时间和断浇比例期望值的优化。
1.一种基于图模型的不确定炼钢-连铸柔性优化调度方法，其特征在于，包括如下步骤：S1，构造原始调度问题，设置如下输入变量并根据钢厂MES下达的生产计划赋值，具体如下：决策变量为：
操作过程Oi,j的开工时间si,j∈{0,1,…,T1}，其中T1为最大时长，操作过程Oi,j的加工机器xi,j∈Mi，
设置调度模型的约束条件，具体包括：加工先后性约束；工艺路径约束；连续性约束；准备时间约束；到达时间约束；
其中，f为平均工序等时间成本，γi为各工序等待时间的成本系数；
S2,构造柔性调度模型，设置一个有向图网络ψ描述调度解的任务优选顺序和机器指派关系，则可定义Ji,k(i＜g)为机器Mi,k上的炉次排列，定义Lk为连铸机Mg,k上的浇次排列，设置缓冲时间θ，包括炉次缓冲时间和/或浇次缓冲时间；
其中， 为对柔性调度解 抽样仿真的第q次结果，Π为柔性调度解空间，N为仿真总次数，且N＝Nf+Ne，Nf为不发生断浇的仿真次数，Ne为发生断浇的仿真次数,β1和β2分别表示等待时间成本系数和断浇成本系数；
S4，仿真评价，采用最优计算量分配方法分配仿真次数，采用随机仿真方法估计每个个体解的目标均值和方差；
S6，构造步骤S5选择出的优势个体的概率分布模型；
S7，对概率分布模型进行随机采样，生成NP/2个新的个体，与当前优势种群中NP/2个个体构成新的种群；
S8，如果步骤S4至步骤S7执行后达到停止条件则执行步骤S9，否则，执行步骤S4；
2.根据权利要求1所述的基于图模型的不确定炼钢-连铸柔性优化调度方法，所述约束条件包括：(1)加工先后性约束：同一台机器上两个不同操作的先后加工顺序是唯一的，(2)工艺路径约束：各炉次必须按照工艺路径的先后顺序加工，即炉次j在当前工序i加工完成后，经天车运送至下道工序后方可开工，(si,j+pi,j,k+tri,i+1≤si+1,j)∧(xi,j＝k),i∈{1,…,g-1},k∈Mi,j∈J，(3)连续性约束：在连铸工序，同一浇次内的相邻炉次安排在同一连铸机加工，且操作之间不允许中断，连铸工序浇次b内第r个炉次的开工时间,
连铸工序浇次b内第r-1个炉次在连铸机Mg,k上的加工时间,连铸工序浇次b内第r个炉次的加工机器,
(4)准备时间约束：在浇次b2开始加工之前，需考虑前一浇次b1完成后连铸机更换中间包的准备时间，连铸工序浇次b2内第一个炉次的开工时间，
连铸工序浇次b1内最后一个炉次在连铸机Mg,k上的加工时间,连铸工序浇次b1内最后一个炉次的加工机器,
(5)到达时间约束：炼钢工序操作需在铁水到达后才能开始，s1,j≥atj,j∈J。
3.根据权利要求1所述的基于图模型的不确定炼钢-连铸柔性优化调度方法，步骤S2中缓冲时间的设置方法为：S31，关键链识别：由于任一浇次b在连铸工序均需无中断连续加工，则定义其关键链为其浇次首炉次所有操作序列及连铸工序所有操作，即:其中，Ωb,1为浇次b首炉次的机器
S32，浇次缓冲时间：保证浇次b连续加工，需要在浇次末端插入项目缓冲时间，即根据不确定风险程度延迟开浇时间，其中， η是一个常数,代表扰动水平；
S33，炉次缓冲时间：为保证连浇操作不受其他非关键炉次的影响，还需在到达连铸工序前插入非关键缓冲，其中，G\g表示工序集合G除工序g外的工序子集；
S34，将炉次缓冲时间插入全部炉次连铸开始之前，将浇次缓冲时间插入全部浇次开浇之前。
4.根据权利要求1所述的基于图模型的不确定炼钢-连铸柔性优化调度方法，其特征在于，柔性调度解的编码方法为：运用基于机器编码的多段式向量π表示炼钢-连铸柔性调度的有向图结构,即第b段向量的第一位代表浇次b的目标连铸机，之后每一位分别代表浇次b各炉次在精炼和炼钢工序的加工机器。
5.根据权利要求1所述的基于图模型的不确定炼钢-连铸柔性优化调度方法，其特征在于，种群初始化方法为：令所有机器的反向释放时间为MRi,k＝∞，
S51，连铸调度，i＝g，按照待调度浇次集合的顺序及最早可用规则，确定各浇次的目标铸机和开浇时间，依据开浇时间和连续加工原则，计算各炉次在连铸工序的开始时间sg,j；
S52，反向调度，1≤i＜g，根据各炉次在下游工序i+1的开始时间，确定其在精炼工序i的最晚完成时间：LFTi,j＝si+1,j-tri,i+1，将所有炉次按照LFTi,j降序排列，然后依次按照柔性调度解的编码方案选择加工机器Mi,k，反向确定操作过程Oi,j的开始时间：si,j＝min(LFTj,MRi,k)-pi,j,k，更新Mi,j的反向释放时间MRi,k＝si,j；
S53，计算到达时间冲突量TCj＝max(atj-s1,j,0)，若TCj＞0，则将炉次j所属浇次及其后续浇次的开浇时间右移TCj个时间单位，然后转S52；否则，退出，输出初始个体π1；
S54,基于π1使用随机交换的方法构造其他NP-1个个体，形成初始种群。
6.根据权利要求1所述的基于图模型的不确定炼钢-连铸柔性优化调度方法，其特征在于，假设需要抽样的个体解总数为NP，其中新生成的解数量为NP0，可供分配的仿真总次数为T，第d个候选解的仿真次数为Δd(τ)，最优计算量分配方法具体流程可描述如下：S61：令τ＝0，对每个新生成的解执行ε0次仿真，则：S62：如果T(τ)≥T则退出，其中，T(τ)为第τ次仿真的次数；否则，执行S63；
S63：令新增仿真次数为ε，T(τ+1)＝T(τ)+ε，T(τ+1)为第τ+1次仿真的次数，计算Δ1(τ),…,Δd(τ),…,ΔNP(τ)，执行如下步骤：若当前最优解的序号为d*，选择第d′个解，令 其中， 为第d′个解的目标函数的均值， 为当前最优解d*的目标函数的均值，δd′为第d′个解的目标函数的均值与当前最优解d*的目标函数的均值之差；
根据下式计算临时分配量Δd′(τ+1)，d′≠d*，其中，σd为第d个解的目标函数的统计方差，σd′为第d′个解的目标函数的统计方差，为最优解d*的目标函数的统计方差，δd为第d个解的目标函数的均值与当前最优解d*的目标函数的均值之差，根据下式计算Δd(τ+1)，d≠d′≠d*，计算
S64：置εd＝max{0,Δd(τ+1)-Δd(τ)}，对调度解执行εd次动态仿真评价过程，令Δd(τ+
1)＝Δd(τ)+εd，d＝1,2,…,NP；同时，Δd(τ+1)＝max{Δd(τ+1),Δd(τ)}，τ＝τ+1，返回S62。
7.根据权利要求1所述的基于图模型的不确定炼钢-连铸柔性优化调度方法，其特征在于，优势个体的选择方法为：随机选择两个个体的目标函数的均值 和 进行比较，认为两个个体的目标函数均值之差 服从正态分布，根据t检验方法，可做出如下假设：H0:F1≤F2,H1:F1＞F2
其中， 和 分别为 和 的统计方差，若统计量Z没有落入Z拒绝域H0，则认为 的目标函数F1占优；反之，则认为 的目标函数F2占优，其中，为第一个个体的柔性调度解，为第二个个体的柔性调度解。
8.根据权利要求1所述的基于图模型的不确定炼钢-连铸柔性优化调度方法，其特征在于，根据柔性调度解中各炉次前后工序的关联关系，定义如下单工序关联变量 和双工序关联变量其中，k′为双工序关联变量中炉次j的第二个工序的索引；
其中， 表示在第it次迭代中炉次j在机器Mi,k上加工的概率；
其中ρ为学习速率，采用反向倒退的方式进行随机采样，即：对于炉次j，首先按照概率矩阵公式(a)随机选择一个连铸工序的加工机器，然后按照概率矩阵公式(b)随机选择炼钢和精炼工序加工机器。
9.一种利用权利要求1-8之一所述基于图模型的不确定炼钢-连铸柔性优化调度方法的系统，其特征在于，包括智能调度器，所述智能调度器连接并从钢厂MES数据库中获得输入变量的取值，构造相应的原始调度问题，并利用权利要求1-8之一所述柔性调度方法获得最优柔性调度解并控制炼钢-连铸生产系统的运行。
一种基于图模型的不确定炼钢-连铸柔性优化调度方法及
系统
技术领域
[0001] 本发明属于自动控制、信息技术和先进控制领域，涉及炼钢-连铸调度过程，具体涉及一种基于图模型的不确定炼钢-连铸柔性优化调度方法及系统。
背景技术
[0002] 炼钢-连铸(Steelmaking-Continuous Casting,SCC)过程是钢铁制造全流程中的关键环节：高温液态铁水经过炼钢、精炼和连铸三类工序加工转换成固态钢坯，然后送往下游热轧工序轧制成材，如图1所示。在此过程中，炼钢炉一次产出的钢水称之为炉次(最小加工单元)；同一连铸中间包寿命周期内连续加工的炉次集合称之为浇次。炼钢-连铸调度的主要任务在于依据企业生产管理部门下达的计划指令(包括浇次数量/顺序、浇次内炉次数量/顺序以及相关钢种和铸坯规格等信息)，在满足资源和工艺规程的前提下，确定待排产炉次在各工序的加工机器(机器指派)、加工顺序(任务排序)以及操作开始时间和完工时间(时间表规划)，实现一类或多类生产性能指标的最优化。炼钢-连铸调度问题的高效求解是钢铁企业生产运行控制的核心内容。
[0003] 一般来说，车间调度员在接收生产计划指令后可立即运行优化调度算法获得初始调度解(静态调度)，形成作业指令下发至各生产岗位。事实上，由于实际生产过程具有不可控和不可知性，炼钢-连铸调度问题中存在一些不确定因素，如铁水随机到达、加工时间波动和机器故障等。这使得初始调度解常出现性能恶化甚至不可行现象，进而要求调度员在较短时间内(10-30秒左右)对初始调度解进行动态修复或再优化(动态调度)。另一方面，为了保证其他生产组织工作(如机器维护、工器具和原料准备等)不受影响，调度员需要时刻保证初始调度解的稳定性，不应频繁地进行动态调度。基于上述原因，炼钢-连铸调度模型不仅需要为动态调度的高效运行提供便利，还应提前考虑生产过程中可能存在的不确定因素以降低动态调度的频次。
[0004] 炼钢-连铸调度问题一般采用静态调度与动态调度相结合的策略：即首先根据确定性参数确定初始调度解；然后再根据生产过程中典型扰动事件对初始调度解进行修复或再优化。从决策形式上来看，这些调度解明确规定了每个炉次在各个工序的加工机器和开始/完成时间，可以唯一对应实际生产过程中的作业指令，是一种“刚性”模型。然而，这种基于确定性参数的刚性决策方式在不确定环境下易出现性能恶化和不可行等问题，对环境的适应性较差，不利于生产稳定运行。
发明内容
[0005] 本发明旨在至少解决现有技术中存在的技术问题，特别创新地提出了一种基于图模型的不确定炼钢-连铸柔性优化调度方法及系统。
[0006] 本发明提出了一种基于有向图网络的柔性调度模型，即调度员在静态调度阶段只需确定各炉次的加工机器及其连铸开始的缓冲时间，然后再依据实际加工时间动态确定各操作的开始/完成时间。基于这种柔性调度模型，构建一种基于最优计算量分配的分布式估计算法。
[0007] 为了实现本发明的上述目的，根据本发明的第一个方面，本发明提供了一种基于图模型的不确定炼钢-连铸柔性优化调度方法，其包括如下步骤：
[0008] S1，构造原始调度问题，设置如下输入变量并根据钢厂MES下达的生产计划赋值，具体如下：
[0009]
[0010] 决策变量为：
[0011] 操作过程Oi,j的开工时间si,j∈{0,1,…,T1}，其中T1为最大时长，
[0012] 操作过程Oi,j的加工机器xi,j∈Mi，
[0013] 设置调度模型的约束条件，具体包括：加工先后性约束；工艺路径约束；连续性约束；准备时间约束；到达时间约束；、
[0014] 设置目标函数：
[0015]
[0016] 其中，f为平均工序等时间成本，γi为各工序等待时间的成本系数；
[0017] S2,构造柔性调度模型，设置一个有向图网络ψ描述调度解的任务优选顺序和机器指派关系，则可定义Ji,k(i＜g)为机器Mi,k上的炉次排列，定义Lk为连铸机Mg,k上的浇次排列，
[0018] 设置缓冲时间θ，包括炉次缓冲时间和/或浇次缓冲时间；
[0019] 设置随机环境下柔性调度模型 的目标函数，
[0020]
[0021] 其中， 为对柔性调度解 抽样仿真的第q次结果，Π为柔性调度解空间，N为仿真总次数，且N＝Nf+Ne，Nf为不发生断浇的仿真次数，Ne为发生断浇的仿真次数,β1和β2分别表示等待时间成本系数和断浇成本系数；
[0022] S3，初始化，构造柔性调度解的初始种群；
[0023] S4，仿真评价，采用OCBA方法分配仿真次数，采用随机仿真方法估计每个个体解的目标均值和方差；
[0024] S5，选择NP/2个优势个体；
[0025] S6，构造步骤S5选择出的优势个体的概率分布模型；
[0026] S7，对概率分布模型进行随机采样，生成NP/2个新的个体，与当前优势种群中NP/2个个体构成新的种群；
[0027] S8，如果步骤S4至步骤S7执行后达到停止条件则执行步骤S9，否则，执行步骤S4；
[0028] S9，输出最优柔性调度解。
[0029] 本发明运用图模型描述调度解的柔性决策，然后设置时间缓冲以保护不确定条件下调度解的性能指标和可行性；基于分布估计算法的优化求解，使用基于工序关联的概率分布模型描述决策变量之间的关联关系以产生高质量的新种群，并采用随机仿真方法对柔性调度解的期望性能进行评价。在仿真过程中，运用最优计算量分配(OCBA)方法对有限计算资源进行动态分配以提高种群的评价效率。本发明实现了不确定环境下炼钢-连铸调度过程等待时间和断浇比例期望值的优化。
[0030] 在本发明的一种优选实施方式中，所述原始调度问题的约束条件为：所述约束条件包括：
[0031] (1)加工先后性约束：同一台机器上两个不同操作的先后加工顺序是唯一的，[0032]
[0033] i∈{1,…,g-1}，k∈Mi，j1,j2∈J，j1≠j2，
[0034] (2)工艺路径约束：各炉次必须按照工艺路径的先后顺序加工，即炉次j在当前工序i加工完成后，经天车运送至下道工序后方可开工，
[0035] (si,j+pi,j,k+tri,i+1≤si+1,j)∧(xi,j＝k),i∈{1,…,g-1},k∈Mi,j∈J，[0036] (3)连续性约束：在连铸工序，同一浇次内的相邻炉次安排在同一连铸机加工，且操作之间不允许中断，
[0037]
[0038] 连铸工序浇次b内第r个炉次的开工时间,
[0039] 连铸工序浇次b内第r-1个炉次的开工时间,
[0040] 连铸工序浇次b内第r-1个炉次在连铸机Mg,k上的加工时间,
[0041] 连铸工序浇次b内第r个炉次的加工机器,
[0042] 连铸工序浇次b内第r-1个炉次的加工机器,
[0043] (4)准备时间约束：在浇次b2开始加工之前，需考虑前一浇次b1完成后连铸机更换中间包的准备时间，
[0044]
[0045] 连铸工序浇次b2内第一个炉次的开工时间，
[0046] 连铸工序浇次b1内最后一个炉次的开工时间,
[0047] 连铸工序浇次b1内最后一个炉次在连铸机Mg,k上的加工时间,
[0048] 连铸工序浇次b1内最后一个炉次的加工机器,
[0049] 连铸工序浇次b2内第一个炉次的加工机器,
[0050] 浇次b2开始加工的准备时间；
[0051] (5)到达时间约束：炼钢工序的操作需在铁水到达后才能开始，
[0052] s1,j≥atj,j∈J。
[0053] 通过以上约束条件，保证调度模型准确高效地运行。
[0054] 在本发明的另一个优选实施方式中，步骤S2中缓冲时间的设置方法为：
[0055] S31，关键链识别：由于任一浇次b在连铸工序均需无中断连续加工，则定义其关键链为浇次首炉次所有操作序列及连铸工序所有操作，即:
[0056] 其中，Ωb,1为浇次b首炉次的机器排序；
[0057] S32，浇次缓冲时间：保证浇次b连续加工，需要在浇次末端插入项目缓冲时间，即根据不确定风险程度延迟开浇时间，
[0058]
[0059] 其中， η是一个常数,代表扰动水平；
[0060] S33，炉次缓冲时间：为保证连浇操作不受其他非关键炉次的影响，还需在到达连铸工序前插入非关键缓冲，
[0061] 其中，其中，G\g表示工序集合G除工序g外的工序子集；
[0062] S34，将炉次缓冲时间插入全部炉次连铸开始之前，将浇次缓冲时间插入全部浇次开浇之前。
[0063] 通过设置缓冲时间，保护关键任务，降低断浇比例。
[0064] 在本发明的另一个优选实施方式中，柔性调度解的编码方法为：
[0065] 运用基于机器编码的多段式向量π表示炼钢-连铸柔性调度的有向图结构,即第b段向量的第一位代表浇次b的目标连铸机，之后每一位分别代表浇次b各炉次在精炼和炼钢工序的加工机器。
[0066] 保证初始种群的多样性。
[0067] 在本发明的另一个优选实施方式中，种群初始化方法为：
[0068] 令所有机器的反向释放时间为Mi,k＝∞，
[0069] S51，连铸调度，i＝g，按照待调度浇次集合的顺序及最早可用规则，确定各浇次的目标铸机和开浇时间，依据开浇时间和连续加工原则，计算各炉次在连铸工序的开始时间sg,j；
[0070] S52，反向调度，1≤i＜g，根据各炉次在下游工序i+1的开始时间，确定其在精炼工序i的最晚完成时间：
[0071] 将所有炉次按照LFTi,j降序排列，然后依次按照柔性调度解的编码方案选择加工机器Mi,k，反向确定操作过程Oi,j的开始时间：si,j＝min(LFTj,MRi,k)-pi,j,k，更新Mi,j的反向释放时间MRi,k＝si,j；
[0072] S53，计算到达时间冲突量TCj＝max(atj-s1,j,0)。若TCj＞0，则将炉次j所属浇次及其后续浇次的开浇时间右移TCj个时间单位，然后转S52；否则，退出，输出初始个体π1。
[0073] S54,基于π1使用随机交换的方法构造其他NP-1个个体，形成初始种群。
[0074] 在本发明的另一个优选实施方式中，假设需要抽样的个体解总数为NP，其中新生成的解数量为NP0，可供分配的仿真总次数为T，第d个候选解的仿真次数为Δd(τ)，OCBA具体流程可描述如下：
[0075] S61：令τ＝0，对每个新生成的解执行ε0次抽样，则：
[0076]
[0077] S62：如果T(τ)≥T则退出；否则，执行S63。
[0078] S63：令新增仿真次数为ε，T(τ+1)＝T(τ)+ε，计算Δ1(τ),…,Δd(τ),…,ΔNP(τ)，执行如下步骤：
[0079] 若当前最优解为序号为d*，选择第d′个解，令
[0080] 根据下式计算临时分配量Δd′(τ+1)，d′≠d*，
[0081]
[0082] 根据下式计算Δd(τ+1)，d≠d′≠d*，
[0083]
[0084] 计算Δd*(τ+1)，
[0085]
[0086] S64：置εd＝max{0,Δd(τ+1)-Δd(τ)}，对调度解执行εd次动态仿真评价过程，令Δd(τ+1)＝Δd(τ)+εd，d＝1,2,…,NP；同时，Δd(τ+1)＝max{Δd(τ+1),Δd(τ)}，τ＝τ+1，返回S62。
[0087] 增量迭代式抽样仿真方法，能够尽可能将计算资源分配给高质量的个体解。
[0088] 在本发明的另一个优选实施方式中，优势个体的选择方法为：
[0089] 随机选择两个个体的目标函数的均值 和 进行比较，认为两个个体的目标函数均值之差 服从正态分布。根据t检验方法，可做出如下假设：
[0090] H0:F1≤F2,H1:F1＞F2
[0091] 然后，构造统计量：
[0092]
[0093] 其中， 和 分别为F1和F2的统计方差，若统计量Z没有落入Z拒绝域H0，则认为的目标函数F1占优；反之，则认为 的目标函数F2占优。
[0094] 基于假设检验的统计分析方法可降低优势个体的误选概率。
[0095] 在本发明的另一个优选实施方式中，根据柔性调度解中各炉次前后工序的关联关系，定义如下变量：
[0096]
[0097]
[0098] 令 则可得到如下概率矩阵：
[0099]
[0100] 其中， 表示在第it次迭代中炉次j在机器Mi,k上加工的概率；
[0101] 在概率分布模型中加入如下增量学习机制：
[0102]
[0103] 其中ρ为学习速率，采用反向倒退的方式进行随机采样，即：对于炉次j，首先按照概率矩阵公式(a)随机选择一个连铸工序的加工机器，然后按照概率矩阵公式(b)随机选择炼钢和精炼工序加工机器
[0104] 能够反映变量之间相互依赖关系，以较大的概率产生高质量的子代种群。
[0105] 为了实现本发明的上述目的，根据本发明的第二个方面，本发明提供了一种利用本发明基于图模型的不确定炼钢-连铸柔性优化调度方法的系统，其包括智能调度器，所述智能调度器连接并从钢厂MES数据库中获得输入变量的取值，构造相应的原始调度问题，并利用本发明所述柔性调度方法获得最优柔性调度解并控制炼钢-连铸生产系统的运行。本发明实现了不确定环境下炼钢-连铸调度过程等待时间和断浇比例期望值的优化。
[0106] 本发明的附加方面和优点将在下面的描述中部分给出，部分将从下面的描述中变得明显，或通过本发明的实践了解到。
附图说明
[0107] 本发明的上述和/或附加的方面和优点从结合下面附图对实施例的描述中将变得明显和容易理解，其中：
[0108] 图1是现有技术中炼钢-连铸过程的流程图；
[0109] 图2是本发明一个优选实施方式中柔性调度解的有向图网络描述；
[0110] 图3是基于缓冲设置的炼钢-连铸调度方案；
[0111] 图4是本发明一个优选实施方式中OCBA-EDA算法流程图；
[0112] 图5是一个炼钢-连铸柔性调度解的向量编码形式；
[0113] 图6是本发明一个优选实施方式中离散事件仿真流程；
[0114] 图7是本发明提出的多目标柔性调度优化算法实现方式的结构图。
具体实施方式
[0115] 下面详细描述本发明的实施例，所述实施例的示例在附图中示出，其中自始至终相同或类似的标号表示相同或类似的元件或具有相同或类似功能的元件。下面通过参考附图描述的实施例是示例性的，仅用于解释本发明，而不能理解为对本发明的限制。
[0116] 在本发明的描述中，除非另有规定和限定，需要说明的是，术语“安装”、“相连”、“连接”应做广义理解，例如，可以是机械连接或电连接，也可以是两个元件内部的连通，可以是直接相连，也可以通过中间媒介间接相连，对于本领域的普通技术人员而言，可以根据具体情况理解上述术语的具体含义。
[0117] 本发明所公开的一种面向不确定炼钢-连铸生产调度的基于有向图网络的柔性调度方法，即调度员在静态调度阶段只需确定各炉次的加工机器及其连铸开始的缓冲时间，然后再依据实际加工时间动态确定各操作的开始/完成时间。基于这种柔性调度模型，构建一种基于最优计算量分配(Optimal Computing Budget Allocation，OCBA)的分布式估计算法(Estimation of Distribution Algorithm，EDA)。最后，可将具体的参数定义如下：
[0118] 表1炼钢-连铸调度问题参数说明
[0119]
[0120] 本发明所研究的炼钢-连铸调度问题包含的参数见表1。为获得一个可行的调度解，需要确定如下决策变量：
[0121] 操作过程Oi,j的开工时间：si,j∈{0,1,…,T1}，T1为最大时长。
[0122] 操作过程Oi,j的加工机器：xi,j∈Mi。
[0123] 所必须满足的资源和工艺约束包括：
[0124] 加工先后性约束：同一台机器上两个不同操作的先后加工顺序是唯一的。
[0125]
[0126] 工艺路径约束：各炉次必须按照工艺路径的先后顺序加工，即炉次j在当前工序i加工完成后，经天车运送至下道工序后方可开工。
[0127] (si,j+pi,j,k+tri,i+1≤si+1,j)∧(xi,j＝k),i∈{1,…,g-1},k∈Mi,j∈J (2)[0128] 连续性约束：在连铸工序，同一浇次内的相邻炉次安排在同一机器加工，且操作之间不允许中断。
[0129]
[0130] 准备时间约束：在浇次b开始加工之前，需考虑连铸机更换中间包的准备时间。
[0131]
[0132] 到达时间约束：炼钢工序的操作需在铁水到达后才能开始。
[0133] s1,j≥atj,j∈J， (5)
[0134] 在确定性环境下，考虑生产过程中的温降成本损失和生产效率提升，以平均工序等时间成本的最小化作为优化目标：
[0135]
[0136] 其中γi为各工序等待时间的成本系数。
[0137] 对于调度问题P而言，本发明假设加工时间pi,j,k服从如下正态随机分布：
[0138]
[0139] 其中ηi为工序i的噪声水平， 为操作过程Oi,j在机器Mi,k的标准加工时间。在实际生产环境下，炼钢-连铸调度解在执行过程中出现的性能恶化和不可行问题常表现为等待时间延长和浇次断浇现象。
[0140] 为平衡调度解的性能与可行性之间的关系，不确定炼钢-连铸调度问题的目标函数可以表示如下：
[0141] (SP)E(F)＝E(β1×f+β2×e) (8)
[0142] 其中 为期望值函数，e为断浇比例，F为加权目标函数，β1和β2为目标成本系数。
[0143] 在炼钢-连铸调度问题中，炉次排序和机器指派子问题(简称分派子问题)的解可以用一个有向图网络ψ描述。例如，图2所示的有向图网络。根据ψ的网络连接关系，定义Ji,k为机器Mi,k(i＜g)上的炉次排列，Lk为连铸机Mg,k上的浇次排列。则原调度问题可简化为如下线性规划问题(LP)。
[0144]
[0145]
[0146] si,j+pi,j,k+tri,i+1≤si+1,j；j∈Ji,k；i＝1,…g-1；k∈Mi (11)[0147]
[0148]
[0149] s1,j≥atj,j∈J (14)
[0150] 从项目调度的视角看，分派子问题可视为一个多项目调度问题对应的有向图网络(如图2所示)，其中每个浇次对应的子问题可视为一个子项目。为平衡等待时间和断浇比例之间的矛盾，本发明确定缓冲大小的具体步骤如下：
[0151] 关键链识别：由于任一浇次b在连铸工序均需无中断连续加工，则可定义其关键链为浇次首炉次所有操作序列及连铸工序所有操作，即
[0152] 浇次缓冲：保证浇次b连续加工，需要在浇次末端插入项目缓冲时间(Project Buffer，PB)，即根据不确定风险程度延迟开浇时间。
[0153]
[0154] 其中，
[0155] 炉次缓冲：为保证连浇操作不受其他非关键炉次的影响，还需在到达连铸工序前插入非关键缓冲(Feeding Buffer，FB)
[0156]
[0157] 插入缓冲构造新的调度解，如图3所示。与项目管理的调度方法不同是，炼钢-连铸调度的PB插入在连铸开浇前，而不是项目末端。
[0158] 本发明所设计的OCBA-EDA的算法流程如图4所示。
[0159] 首先，进行编码和初始化，根据炼钢-连铸调度问题的特点，本发明运用基于机器的编码方法表示炼钢-连铸柔性调度的有向图结构ψ。以图5所示向量为例，浇次1内炉次集合{1,2,3}在连铸工序的加工机器为M3,1，精炼和炼钢的加工机器序列分别为{M2,2,M2,1,M2,2}和{M1,2,M1,1,M1,2}；浇次2内所有炉次{4,5,6}在连铸工序的加工机器为M3,2，精炼和炼钢的加工机器序列分别为{M2,1,M2,2,M2,1}和{M1,2,M1,2,M1,1}。
[0160] 为尽量获取优势个体在解空间内的概率分布模型，应使初始化种群具有一定的多样性。具体过程为：首先，根据基于标准加工时间的反向列表调度方法(BLS)构造初始调度解ψ0；然后对ψ0进行随机交换产生NP-1个解。其中BLS算法流程具体步骤如下：
[0161] 初始化：令所有机器的反向释放时间为MRi,k＝∞。
[0162] Step 1：连铸调度，i＝g
[0163] (1.1)按照待调度浇次集合的顺序及最早可用规则，确定各浇次的目标铸机和开浇时间。
[0164] (1.2)依据开浇时间和连续加工原则，计算各炉次在连铸工序的开始时间sg,j。
[0165] Step 2：反向调度，1≤i＜g
[0166] (2.1)根据各炉次在下游工序i+1的开始时间，确定其在精炼工序i的最晚完成时间：
[0167]
[0168] (2.2)将所有炉次按照LFTi,j降序排列，然后依次按照调度解的编码方案选择加工机器Mi,k，反向确定Oi,j的开始时间：
[0169] si,j＝min(LFTj,MR2,k)-pi,j,k,MRi,k＝si,j (19)
[0170] Step 3：
[0171] (3.1)计算到达时间冲突量TCj，TCj＝max(atj-s1,j,0)。若TCj＞0，则将炉次j所属浇次及其后续浇次的开浇时间右移TCj个时间单位，然后转Step 2；否则，退出。
[0172] 然后，进行离散事件仿真，为估计柔性调度方案 在不确定条件下的期望性能，可执行N(d)次离散事件仿真估计目标均值和方差，具体流程如图6所示。针对第q个抽样实例，随机生成一组加工时间pi,j,k(q)，然后执行初始事件列表，动态推进仿真进程，直至仿真结束输出等待时间或断浇事故。
[0173] 再后，基于OCBA的仿真抽样，由于计算机在一定时间范围内所能提供的计算资源有限，群体中候选解评价的总评价次数也受到制约。OCBA方法可以将有限的计算资源尽量分配给性能最优概率最大的调度解。假设需要抽样的个体解总数为NP，其中新生成的解数量为NP0，可供分配的仿真总次数为T，第d个候选解的仿真次数为Δd(τ)。OCBA具体流程可描述如下：
[0174] Step 1：令τ＝0，对每个新生成的解执行ε0次抽样，则：
[0175]
[0176] Step 2：如果T(τ)≥T则退出；否则，执行Step 3，其中，T(τ)为第τ次仿真的次数。
[0177] Step 3：令新增仿真次数为ε，T(τ+1)＝T(τ)+Δ，，T(τ+1)为第τ+1次仿真的次数，[0178] 执行如下步骤：
[0179] (3.1)若当前最优解为序号为d*，选择第d′个解，令 其中， 为第d′个解的目标函数的均值， 为当前最优解d*的目标函数的均值，δd′为第d′个解的目标函数*
的均值与当前最优解d的目标函数的均值之差；
[0180] (3.2)根据下式计算临时分配量Δd′(τ+1)，d′≠d*，
[0181]
[0182] 其中，σd为第d个解的目标函数的统计方差，σd′为第d′个解的目标函数的统计方差， 为最优解d*的目标函数的统计方差，δd为第d个解的目标函数的均值与当前最优解d*的目标函数的均值之差。(3.3)根据下式计算Δd(τ+1)，d≠d′≠d*，
[0183]
[0184] (3.3)计算Δd*(τ+1)，
[0185]
[0186] Step 4：置εd＝max{0,Δd(τ+1)-Δd(τ)}，对调度解执行εd次动态仿真评价过程。令Δd(τ+1)＝Δd(τ)+εd，d＝1,2,…,NP；同时，Δd(τ+1)＝max{Δd(τ+1),Δd(τ)}，τ＝τ+1，返回Step 2。
[0187] 从上述算法中可看出，OCBA抽样资源的分配方法是在权衡调度解目标函数的均值和方差的基础上进行迭代的。当均值差距(δd)较小时，方差较大的解将获得更多的仿真次数；当方差(σd)较大时，均值较优的解将获得更多的仿真次数。
[0188] 接着，进行优势个体的选择。本发明采用锦标赛选择方法随机选择两个个体的目标函数的均值 和 进行比较。经过一定次数随机仿真评价之后，根据大数定理可认为两个个体的目标函数均值之差 服从正态分布(t检验)。
[0189] 优势个体的选择方法为：
[0190] 随机选择两个个体的目标函数的均值 和 进行比较，认为两个个体的目标函数均值之差 服从正态分布。根据t检验方法，可做出如下假设：
[0191] H0:F1≤F2,H1:F1＞F2
[0192] 然后，构造统计量：
[0193]
[0194] 其中， 和 分别为F1和F2的统计方差，若统计量Z没有落入Z拒绝域H0，则认为的目标函数F1占优；反之，则认为 的目标函数F2占优，其中， 为第一个个体的柔性调度解， 为第二个个体的柔性调度解。
[0195] 最后，进行概率分布模型构造与采样。
[0196] 在EDA算法的迭代过程中，因为种群中的变量分布和新种群的产生均是通过概率分布模型获得的，所以概率分布模型的合理性对算法性能的提升至关重要。根据 中各炉次前后工序的关联关系，定义如下变量：
[0197]
[0198]
[0199] 其中，k′为双工序关联变量中炉次j的第二个工序的索引；
[0200] 令 和 则可得到如下概率矩阵：
[0201]
[0202] 其中， 表示在第it次迭代中炉次j在机器Mi,k上加工的概率。
[0203] EDA算法通过初始种群的优势个体获得初始概率分布模型，继而构造新的种群。并在每次迭代过程中根据新种群中决策变量的分布情况更新概率分布模型。随着概率分布模型逐渐逼近局部最优解的空间结构，精确的概率模式会使种群丧失多样性，在种群大小和迭代数量有限的条件下算法容易出现早熟收敛现象。因此，为了平衡EDA算法的全局和局部搜索性能，在概率分布模型中加入如下增量学习机制：
[0204]
[0205] 其中ρ为学习速率。为生成新的个体调度解，本发明采用反向倒退的方式进行随机采样，即：对于炉次j，首先按照公式(24.a)随机选择一个连铸工序的加工机器，然后按照公式(24.b)随机选择炼钢和精炼工序加工机器。
[0206] 在本说明书的描述中，参考术语“一个实施例”、“一些实施例”、“示例”、“具体示例”、或“一些示例”等的描述意指结合该实施例或示例描述的具体特征、结构、材料或者特点包含于本发明的至少一个实施例或示例中。在本说明书中，对上述术语的示意性表述不一定指的是相同的实施例或示例。而且，描述的具体特征、结构、材料或者特点可以在任何的一个或多个实施例或示例中以合适的方式结合。
[0207] 尽管已经示出和描述了本发明的实施例，本领域的普通技术人员可以理解：在不脱离本发明的原理和宗旨的情况下可以对这些实施例进行多种变化、修改、替换和变型，本发明的范围由权利要求及其等同物限定。
