(19)国家知识产权局 (12)发明 专利申请 (10)申请公布号 (43)申请公布日 (21)申请 号 202210798498.5 (22)申请日 2022.07.06 (71)申请人 中国人民解 放军陆军 军医大学第一 附属医院 地址 400038 重庆市沙坪坝区高滩岩正 街 30号 (72)发明人 左锋　袁驰　蒙国学　程坤　贾锋　 (74)专利代理 机构 重庆青飞知识产权代理有限 公司 50283 专利代理师 彭启龙 (51)Int.Cl. G06F 9/48(2006.01) G06F 16/25(2019.01) (54)发明名称 一种基于模拟退火算法的数据仓库ETL调度 优化方法 (57)摘要 本发明涉及一种基于模拟退火算法的数据 仓库ETL调度优化方法， 包 括以下步骤： 初始化初 始温度、 初始任务调度状态、 每一个温度的迭代 次数、 温度下降的速率、 最低温度； 生成初始任务 工作队列， 计算初始任务调度的任务执行时间； 产生新的任务工作队列和任务执行时间； 根据 Metropolis准则， 判断 是否成立； 接受当前任务工作队列和， 判断是否达到最大迭 代次数， 若是则将温度以一定的温度下降速率下 降得到新的温度； 当前任务工作队列， 任务调度 的任务执行时间即为模拟退火算法所找到的最 优解。 本发明将模拟退火算法引入到数据仓库 ETL任务调度中， 将 模拟退火算法最优解与ET L最 优任务进行对应， 提高了 ETL访问效率。 权利要求书2页 说明书4页 附图1页 CN 115129451 A 2022.09.30 CN 115129451 A 1.一种基于模拟退火算法的数据仓库ETL调度优化方法， 其特征在于： 该方法包括以下 步骤： S1： 初始化初始温度C、 初始任务调度状态S、 每一个温度的迭代次数D、 温度下降的速率 R、 最低温度C0； S2： 生成初始任务工作队列Queue0， 计算初始任务调度的任务执 行时间f(0)； S3： 判断C>C0， 满足条件的话执 行步骤S4； 否则执 行步骤S9； S4： 根据产生新解的规则： 对于初始化各个工作流的时间情况下， 随机交换最大工作流 与最小工作流的其中一个任务； 对于未知工作流时间的情况下， 随机交换两个流的一个任 务； 根据该规则会产生一个新的任务工作队列和任务执行时间， 产生新的任务工作队列 Queuei和任务执 行时间f(i)， 迭代计算D0++， 即迭代次数自加1， 继续执 行步骤S5； S5： 判断fi<f(0)， 若满足条件则执 行步骤S7， 否则执 行步骤S6； S6： 根据Metropolis准则， 判断 是否成立， 其中P为区间(0,1)之间的随机 数， T表示迭代过程中的控制参数， 若上式成立， 则继续执 行步骤S7， 否则继续执 行步骤S8； S7： 接受当前任务工作队列Queuei和f(i)， 即Queue0＝Queuei， f(0)＝f(i)， 继续执行步 骤S8； S8： 判断是否达到最大迭代次数， 即D0>D， 若是则将温度C以一定的温度下降速率R下降 得到新的温度， 继续执 行步骤S3， 否则继续执 行步骤S4； S9： 当前任务工作队列Queue0， 任务调度的任 务执行时间 f(0)即为模拟退火算 法所找到 的最优解。 2.根据权利要求1所述的一种基于模拟退火算法的数据仓库ETL调度优化方法， 其特征 在于： 在步骤S1中， 初始化过程中对于某个ETL过程包含的m个任务， 任务i执行所需要的时 间就是ti(1≤i≤m)； 所有任务通过处理后分为了n组队列， 其中第j组任务所 需要的总执行 时间为Tj(1≤j≤n)： 其中的 3.根据权利要求2所述的一种基于模拟退火算法的数据仓库ETL调度优化方法， 其特征 在于： 在步骤S 6中， 根据Metr opolis准则， 判断 是否成立， 其中P为区间(0,1)之 间的随机数， 若上式成立， 则继续执 行步骤S7， 否则继续执 行步骤S8； 所述Metropolis准则基本思想在退火迭代过程中， 通过一定概率接收劣解， 从而可能 跳出局部最优， 并且随着温度降低， 会降低接受劣解的概率， 直到温度逐渐趋于一定值时， 那么接受劣化 解的概率也会接近于0， 从而完成退火的过程； Metropolis接受准则数 学表达式为： 其中P是当前新解的接受概率； ΔE是当前新解与先前解对应目标函数的差； T表示迭代权　利　要　求　书 1/2 页 2 CN 115129451 A 2过程中的控制参数。权　利　要　求　书 2/2 页 3 CN 115129451 A 3