一种基于遗传算法的炼钢-连铸重调度方法及系统

专利类型：发明专利 

语 言：中文 

申 请 号：CN201310684203.2 

申 请 日：20131213 

发 明 人：郑忠龙建宇高小强呼万哲龚永民 

申 请 人：重庆大学 

申请人地址：400044 重庆市沙坪坝区沙正街174号 

公 开 日：20151230 

公 开 号：CN103631243B 

代 理 人：郭云 

代理机构：重庆市前沿专利事务所(普通合伙) 50211 

摘　　要：本发明提出了一种基于遗传算法的炼钢-连铸重调度方法及系统，包括如下步骤：重调度系统获取炼钢-连铸系统的生产批量计划、当前调度方案和实时调度数据，进行扰动识别与分析，小扰动时调整当前调度方案，大扰动时进行重调度，对已完成作业炉次集合中各炉次，采用调度实绩信息作为该集合内各炉次的重调度子方案；对正在作业炉次集合中各炉次，基于已完成作业炉次集合的实际调度信息和重调度目标，根据流程顺推和遗传算法的混合算法求解；对未作业的炉次集合中各炉次，基于已完成作业炉次集合的重调度子方案和正在作业炉次集合的重调度子方案，根据流程逆推和遗传算法的混合算法求解。本发明能够处理炼钢-连铸生产过程中随机扰动下的重调度问题。 

主 权 项：一种基于遗传算法的炼钢?连铸重调度方法，其特征在于，包括如下步骤：S1，重调度系统获取炼钢?连铸系统的生产批量计划和当前调度方案，以及炼钢?连铸系统的实时调度数据，并进行扰动识别与分析，根据扰动对当前调度方案的可持续执行性的影响程度判断是大扰动还是小扰动，所述小扰动是指在扰动发生时任务性质和数量不变的前提下，针对某一炉次，不会影响其预定加工设备及在铸机上开始浇铸时间的扰动，所述大扰动是指任务性质或数量改变，或者针对某一炉次，会影响其预定加工设备或在铸机上开始浇铸时间的扰动，当扰动是小扰动时，执行步骤S2，当扰动是大扰动时，执行步骤S3；S2，对当前调度方案进行修复处理，结束,所述修复处理是针对发生小扰动的炉次L_ij，利用其尚未加工的除铸机外的设备作业时间与设备间的运输时间的柔性，对原调度方案进行局部调整，具体步骤为：S2?1"：确定炉次L_ij在重调度发生时刻所处的操作数wo_ij、以及其实际作业时间与初始调度方案中作业时间的时间偏差大小PT；S2?1"?1：初始化炉次操作数o_ij＝1；S2?1"?2：若o_ij＜O(i,j)，则执行步骤S2?1"?3，否则，该扰动不是小扰动，修复结束；S2?1"?3：若${\beta }_{{\mathrm{ijo}}_{ij}}=2,$则${k^{\prime }}_{{\mathrm{ijo}}_{ij}}^g={k^{\prime \prime }}_{{\mathrm{ijo}}_{ij}}^g,$$P^{\prime }{S}_{{\mathrm{ijo}}_{ij}}^g\left({k^{\prime }}_{{\mathrm{ijo}}_{ij}}^g\right)=P^{\prime \prime }{S}_{{\mathrm{ijo}}_{ij}}^g\left({k^{\prime \prime }}_{{\mathrm{ijo}}_{ij}}^g\right),$$P^{\prime }{E}_{{\mathrm{ijo}}_{ij}}^g\left({k^{\prime }}_{{\mathrm{ijo}}_{ij}}^g\right)=P^{\prime \prime }{E}_{{\mathrm{ijo}}_{ij}}^g\left({k^{\prime \prime }}_{{\mathrm{ijo}}_{ij}}^g\right),$执行步骤S2?1"?6；S2?1"?4：若${\beta }_{{\mathrm{ijo}}_{ij}}=1,$则${k^{\prime }}_{{\mathrm{ijo}}_{ij}}^g={k^{\prime \prime }}_{{\mathrm{ijo}}_{ij}}^g,$$P^{\prime }{S}_{{\mathrm{ijo}}_{ij}}^g\left({k^{\prime }}_{{\mathrm{ijo}}_{ij}}^g\right)=P^{\prime \prime }{S}_{{\mathrm{ijo}}_{ij}}^g\left({k^{\prime \prime }}_{{\mathrm{ijo}}_{ij}}^g\right),$令wo_ij＝o_ij，$PT=P^{\prime }{S}_{{\mathrm{ijo}}_{ij}}^g\left({k^{\prime }}_{{\mathrm{ijo}}_{ij}}^g\right)-{\mathrm{PS}}_{{\mathrm{ijo}}_{ij}}^g\left(k_{{\mathrm{ijo}}_{ij}}^g\right),$执行步骤S2?2"；S2?1"?5：若${\beta }_{{\mathrm{ijo}}_{ij}}=0,$则令wo_ij＝o_ij?1，$PT=P^{\prime }{E}_{{\mathrm{ijo}}_{ij}-1}^g\left({k^{\prime }}_{{\mathrm{ijo}}_{ij}-1}^g\right)-{\mathrm{PE}}_{{\mathrm{ijo}}_{ij}-1}^g\left(k_{{\mathrm{ijo}}_{ij}-1}^g\right),$执行步骤S2?3"；S2?1"?6：令o_ij＝o_ij+1，返回执行步骤S2?1"?2；S2?2"：时间偏差为炉次开始时间的偏差处理，处理步骤如下：S2?2"?1：若PT＞0，执行步骤S2?2"?2，否则执行步骤S2?2"?3；S2?2"?2：时间偏差为正的偏差处理，处理步骤如下：S2?2"?2?1：初始化炉次操作数o_ij＝wo_ij；S2?2"?2?2：若o_ij＜O(i,j)，则执行步骤S2?2"?2?3，否则，该扰动不是小扰动，修复结束；S2?2"?2?3：若$PT\le \left({\mathrm{PE}}_{{\mathrm{ijo}}_{ij}}^g\right(k_{{\mathrm{ijo}}_{ij}}^g)-{\mathrm{PS}}_{{\mathrm{ijo}}_{ij}}^g(k_{{\mathrm{ijo}}_{ij}}^g\left)\right)-{\mathrm{WT}}_g^{min},$则$P^{\prime }{E}_{{\mathrm{ijo}}_{ij}}^g\left({k^{\prime }}_{{\mathrm{ijo}}_{ij}}^g\right)={\mathrm{PE}}_{{\mathrm{ijo}}_{ij}}^g\left(k_{{\mathrm{ijo}}_{ij}}^g\right),$L_ij的后续操作的时间与原调度方案一致，修复结束；否则，$P^{\prime }{E}_{{\mathrm{ijo}}_{ij}}^g\left({k^{\prime }}_{{\mathrm{ijo}}_{ij}}^g\right)=P^{\prime }{S}_{{\mathrm{ijo}}_{ij}}^g\left({k^{\prime }}_{{\mathrm{ijo}}_{ij}}^g\right)+{\mathrm{WT}}_g^{\min },$$PT=P^{\prime }{E}_{{\mathrm{ijo}}_{ij}}^g\left({k^{\prime }}_{{\mathrm{ijo}}_{ij}}^g\right)-{\mathrm{PE}}_{{\mathrm{ijo}}_{ij}}^g\left(k_{{\mathrm{ijo}}_{ij}}^g\right);$S2?2"?2?4：若则L_ij的后续操作的时间与原调度方案一致，修复结束；S2?2"?2?5：若o_ij＝O(i,j)?1，该扰动不是小扰动，修复结束；否则，$P^{\prime }{S}_{{\mathrm{ijo}}_{ij}+1}^{g^{\prime }}\left({k^{\prime }}_{{\mathrm{ijo}}_{ij}+1}^{g^{\prime }}\right)=P^{\prime }{E}_{{\mathrm{ijo}}_{ij}}^g\left({k^{\prime }}_{{\mathrm{ijo}}_{ij}}^g\right)+{\mathrm{TT}}_{k^{\prime g}{k}^{g^{\prime }}}^{\min },$$PT=P^{\prime }{S}_{{\mathrm{ijo}}_{ij}+1}^{g^{\prime }}\left({k^{\prime }}_{{\mathrm{ijo}}_{ij}+1}^{g^{\prime }}\right)-{\mathrm{PS}}_{{\mathrm{ijo}}_{ij}+1}^{g^{\prime }}\left(k_{{\mathrm{ijo}}_{ij}+1}^{g^{\prime }}\right);$S2?2"?2?6：令o_ij＝o_ij+1，执行步骤S2?2"?2?2；S2?2"?3：时间偏差为负的偏差处理，处理步骤如下：S2?2"?3?1：PT＝?PT，初始化炉次操作数o_ij＝wo_ij；S2?2"?3?2：若o_ij＜O(i,j)，则执行步骤S2?2"?3?3，否则，该扰动不是小扰动，修复结束；S2?2"?3?3：若$PT\le {\mathrm{WT}}_g^{max}-\left({\mathrm{PE}}_{{\mathrm{ijo}}_{ij}}^g\right(k_{{\mathrm{ijo}}_{ij}}^g)-{\mathrm{PS}}_{{\mathrm{ijo}}_{ij}}^g(k_{{\mathrm{ijo}}_{ij}}^g\left)\right),$则$P^{\prime }{E}_{{\mathrm{ijo}}_{ij}}^g\left({k^{\prime }}_{{\mathrm{ijo}}_{ij}}^g\right)={\mathrm{PE}}_{{\mathrm{ijo}}_{ij}}^g\left(k_{{\mathrm{ijo}}_{ij}}^g\right),$L_ij的后续操作的时间与原调度方案一致，修复结束；否则，$PT=-\left(P^{\prime }{E}_{{\mathrm{ijo}}_{ij}}^g\right({k^{\prime }}_{{\mathrm{ijo}}_{ij}}^g)-{\mathrm{PE}}_{{\mathrm{ijo}}_{ij}}^g(k_{{\mathrm{ijo}}_{ij}}^g\left)\right);$S2?2"?3?4：若则L_ij的后续操作的时间与原调度方案一致，修复结束；S2?2"?3?5：若o_ij＝O(i,j)?1，该扰动不是小扰动，修复结束；否则，$P^{\prime }{S}_{{\mathrm{ijo}}_{ij}+1}^{g^{\prime }}\left({k^{\prime }}_{{\mathrm{ijo}}_{ij}+1}^{g^{\prime }}\right)=P^{\prime }{E}_{{\mathrm{ijo}}_{ij}}^g\left({k^{\prime }}_{{\mathrm{ijo}}_{ij}}^g\right)+{\mathrm{TT}}_{k^{\prime g}{k}^{g^{\prime }}}^{\max },$$PT=-\left(P^{\prime }{S}_{{\mathrm{ijo}}_{ij}+1}^{g^{\prime }}\right({k^{\prime }}_{{\mathrm{ijo}}_{ij}+1}^{g^{\prime }})-{\mathrm{PS}}_{{\mathrm{ijo}}_{ij}+1}^{g^{\prime }}(k_{{\mathrm{ijo}}_{ij}+1}^{g^{\prime }}\left)\right);$S2?2"?3?6：令o_ij＝o_ij+1，执行S2?2"?3?2；S2?3"：时间偏差为炉次结束时间的偏差处理，处理步骤如下：S2?3"?1：若PT＞0，执行S2?3"?2，否则执行S2?3"?3；S2?3"?2：时间偏差为正的偏差处理，处理步骤如下：S2?3"?2?1：初始化炉次操作数o_ij＝wo_ij；S2?3"?2?2：若o_ij＜O(i,j)，则执行步骤S2?3"?2?3，否则，该扰动不是小扰动，修复结束；S2?3"?2?3：若则L_ij的后续操作的时间与原调度方案一致，修复结束；S2?3"?2?4：若o_ij＝O(i,j)?1，该扰动不是小扰动，修复结束；否则，$P^{\prime }{S}_{{\mathrm{ijo}}_{ij}+1}^{g^{\prime }}\left({k^{\prime }}_{{\mathrm{ijo}}_{ij}+1}^{g^{\prime }}\right)=P^{\prime }{E}_{{\mathrm{ijo}}_{ij}}^g\left({k^{\prime }}_{{\mathrm{ijo}}_{ij}}^g\right)+{\mathrm{TT}}_{k^{\prime g}{k}^{\prime g^{\prime }}}^{\min },$$PT=P^{\prime }{S}_{{\mathrm{ijo}}_{ij}+1}^{g^{\prime }}\left({k^{\prime }}_{{\mathrm{ijo}}_{ij}+1}^{g^{\prime }}\right)-{\mathrm{PS}}_{{\mathrm{ijo}}_{ij}+1}^{g^{\prime }}\left(k_{{\mathrm{ijo}}_{ij}+1}^{g^{\prime }}\right);$S2?3"?2?5：若$PT\le \left({\mathrm{PE}}_{{\mathrm{ijo}}_{ij}+1}^{g^{\prime }}\right(k_{{\mathrm{ijo}}_{ij}+1}^{g^{\prime }})-{\mathrm{PS}}_{{\mathrm{ijo}}_{ij}+1}^{g^{\prime }}(k_{{\mathrm{ijo}}_{ij}+1}^{g^{\prime }}\left)\right)-{\mathrm{WT}}_{g^{\prime }}^{\min },$则$P^{\prime }{E}_{{\mathrm{ijo}}_{ij}+1}^{g^{\prime }}\left({k^{\prime }}_{{\mathrm{ijo}}_{ij}+1}^{g^{\prime }}\right)=$${\mathrm{PE}}_{{\mathrm{ijo}}_{ij}+1}^{g^{\prime }}\left(k_{{\mathrm{ijo}}_{ij}+1}^{g^{\prime }}\right),$L_ij的后续操作的时间与原调度方案一致，修复结束；否则，$P^{\prime }{E}_{{\mathrm{ijo}}_{ij}+1}^{g^{\prime }}\left({k^{\prime }}_{{\mathrm{ijo}}_{ij}+1}^{g^{\prime }}\right)=P^{\prime }{S}_{{\mathrm{ijo}}_{ij}+1}^{g^{\prime }}\left({k^{\prime }}_{{\mathrm{ijo}}_{ij}+1}^{g^{\prime }}\right)+{\mathrm{WT}}_{g^{\prime }}^{\min },$$PT=P^{\prime }{E}_{{\mathrm{ijo}}_{ij}+1}^{g^{\prime }}\left({k^{\prime }}_{{\mathrm{ijo}}_{ij}+1}^{g^{\prime }}\right)-{\mathrm{PE}}_{{\mathrm{ijo}}_{ij}+1}^{g^{\prime }}\left(k_{{\mathrm{ijo}}_{ij}+1}^{g^{\prime }}\right);$S2?3"?2?6：令o_ij＝o_ij+1，执行S2?3"?2?2；S2?3"?3：时间偏差为负的偏差处理，处理步骤如下：S2?3"?3?1：PT＝?PT，初始化炉次操作数o_ij＝wo_ij；S2?3"?3?2：若o_ij＜O(i,j)，则执行步骤S2?3"?3?3，否则，该扰动不是小扰动，修复结束；S2?3"?3?3：若则L_ij的后续操作的时间与原调度方案一致，修复结束；S2?3"?3?4：若o_ij＝O(i,j)?1，该扰动不是小扰动，修复结束；否则，$P^{\prime }{S}_{{\mathrm{ijo}}_{ij}+1}^{g^{\prime }}\left({k^{\prime }}_{{\mathrm{ijo}}_{ij}+1}^{g^{\prime }}\right)=P^{\prime }{E}_{{\mathrm{ijo}}_{ij}}^g\left({k^{\prime }}_{{\mathrm{ijo}}_{ij}}^g\right)+{\mathrm{TT}}_{k^{\prime g}{k}^{\prime g^{\prime }}}^{\max },$$PT=-\left(P^{\prime }{S}_{{\mathrm{ijo}}_{ij}+1}^{g^{\prime }}\right({k^{\prime }}_{{\mathrm{ijo}}_{ij}+1}^{g^{\prime }})-{\mathrm{PS}}_{{\mathrm{ijo}}_{ij}+1}^{g^{\prime }}(k_{{\mathrm{ijo}}_{ij}+1}^{g^{\prime }}\left)\right);$S2?3"?3?5：若$PT\le {\mathrm{WT}}_{g^{\prime }}^{max}-\left({\mathrm{PE}}_{{\mathrm{ijo}}_{ij}+1}^{g^{\prime }}\right(k_{{\mathrm{ijo}}_{ij}+1}^{g^{\prime }})-{\mathrm{PS}}_{{\mathrm{ijo}}_{ij}+1}^{g^{\prime }}(k_{{\mathrm{ijo}}_{ij}+1}^{g^{\prime }}\left)\right),$则$P^{\prime }{E}_{{\mathrm{ijo}}_{ij}+1}^{g^{\prime }}\left({k^{\prime }}_{{\mathrm{ijo}}_{ij}+1}^{g^{\prime }}\right)=$${\mathrm{PE}}_{{\mathrm{ijo}}_{ij}+1}^{g^{\prime }}\left(k_{{\mathrm{ijo}}_{ij}+1}^{g^{\prime }}\right),$L_ij的后续操作的时间与原调度方案一致，修复结束；否则，$P^{\prime }{E}_{{\mathrm{ijo}}_{ij}+1}^{g^{\prime }}\left({k^{\prime }}_{{\mathrm{ijo}}_{ij}+1}^{g^{\prime }}\right)=P^{\prime }{S}_{{\mathrm{ijo}}_{ij}+1}^{g^{\prime }}\left({k^{\prime }}_{{\mathrm{ijo}}_{ij}+1}^{g^{\prime }}\right)+{\mathrm{WT}}_{g^{\prime }}^{\max },$$PT=-\left(P^{\prime }{E}_{{\mathrm{ijo}}_{ij}+1}^{g^{\prime }}\right({k^{\prime }}_{{\mathrm{ijo}}_{ij}+1}^{g^{\prime }})-{\mathrm{PE}}_{{\mathrm{ijo}}_{ij}+1}^{g^{\prime }}(k_{{\mathrm{ijo}}_{ij}+1}^{g^{\prime }}\left)\right)·,$S2?3"?3?6：令o_ij＝o_ij+1，执行步骤S2?3"?3?2；其中,O(i,j)为炉次L_ij从转炉到连铸工序的操作总数，即炉次所经过的加工设备总数,为重调度时炉次L_ij的第o_ij个操作的运行状态，表示“未加工”，表示“正在进行”，表示“已完成”,WT_g为第g类工序设备的加工时间,为第g类工序设备上的第k台设备到第g"类设备上的第k"台设备的运输时间,表示原调度炉次L_ij的第o_ij个操作在第g类工序设备上的第k台设备上冶炼,表示重调度中炉次L_ij的第o_ij个操作在第g类工序设备上的第k个加工设备上冶炼，表示实际中炉次L_ij的第o_ij个操作在第g类工序设备上的第k个加工设备上冶炼，表示炉次L_ij的第o_ij个操作在第g类工序设备的第k个机器上的原调度开始时间,表示炉次L_ij的第o_ij个操作在第g类工序设备的第k个加工设备上的重计划开始时间，表示炉次L_ij的第o_ij个操作在第g类工序设备的第k个加工设备上的实际开始时间，表示炉次L_ij的第o_ij个操作在第g类工序设备的第k个机器上的原调度结束时间表示炉次L_ij的第o_ij个操作在第g类工序设备的第k个加工设备上的重计划结束时间，表示炉次L_ij的第o_ij个操作在第g类工序设备的第k个设备上的实际结束时间，g表示工序设备类，所述g、k、i、j均为正整数；S3，进行重调度，给各炉次安排加工设备，并计算所述炉次在所述加工设备上的开始加工时间和结束加工时间，首先将炉次集合Ω进行分类，分为已完成作业的炉次集合Ω_P、未作业的炉次集合Ω_W和正在作业炉次集合Ω_H；对于已完成作业的炉次集合Ω_P中各炉次，采用实际调度信息作为该集合内各炉次的重调度子方案，即令

关 键 词： 

法律状态：公开 

IPC专利分类号：G05B19/418(2006.01)I