(19)国家知识产权局 (12)发明 专利申请 (10)申请公布号 (43)申请公布日 (21)申请 号 202210982965.X (22)申请日 2022.08.16 (71)申请人 河南大学 地址 475001 河南省开封市顺河区明伦街 85号 (72)发明人 侯彦娥　何雯雯　党兰学　乔保军　 左宪禹　葛强　周黎鸣　 (74)专利代理 机构 郑州大通专利商标代理有限 公司 41111 专利代理师 刘莹莹 (51)Int.Cl. G06F 9/48(2006.01) G06F 9/50(2006.01) G06N 3/00(2006.01) (54)发明名称 一种基于粒子群算法的遥感产品生产任务 调度方法 (57)摘要 本发明提供一种基于粒子群算法的遥感产 品生产任务调度方法。 该方法包括： 步骤1： 给定 任务集合信息和生产节点集合信息； 步骤2： 构建 任务的预执行时间ETC矩阵和资源分配CAL矩阵； 步骤3： 采用间接编码方式对粒子进行编码， 建立 规模为N的粒子群， 并设定最大迭代次数； 步骤4： 选择典型线性递减策略作为惯 性权重算法； 步骤 5： 根据预执行时间ETC矩阵和资源分配CAL矩阵 计算每个粒子的适应度值； 步骤6： 更新粒子的速 度和位置； 步骤7： 更新全局最优解； 步骤8： 判断 是否收敛或达到设定的最大迭代次数， 若是， 则 输出此时的全局最优解， 并根据全局最优解将任 务分配至相应的生产节点中进行生产； 若否， 则 返回步骤5继续下一次搜索过程。 权利要求书2页 说明书8页 附图3页 CN 115357357 A 2022.11.18 CN 115357357 A 1.一种基于粒子群算法的遥感产品生产任务调度方法， 其特 征在于， 包括： 步骤1： 给定任务集合信 息和生产节点集合信 息， 所述任务集合是指由需要被分配的遥 感产品生产任务组成的集合， 所述生产节点集合信息是指由用于执行遥感产品生产任务的 生产节点组成的集 合； 步骤2： 根据任务集合与生产节点集合构建任务的预执行时间ETC矩阵和资源分配CAL 矩阵； 其中， ETCij表示ETC矩阵中第i行第j列的元素， 用于表示任务i在生产节点j上的任务 预执行时间； CALij表示CAL矩阵中第i 行第j列的元素， 用于表示将任务i分配至 生产节点j上 执行时所需要消耗的资源； 步骤3： 采用间接编码方式对粒子进行编码， 建立规模为N的粒子群， 根据 粒子位置构建 任务分配DIS矩阵， 并设定最大迭代次数； 其中， 一个粒子代表 一种任务分配结果， 编码的长 度为任务的数量； 任务量越大， 粒子群的规模和设定的最 大迭代次数越大； 其中， DISij＝1表 示任务i分配到生产节点j上， DISij＝0表示生产节点j上 未分配任务； 步骤4： 选择典型线性 递减策略作为惯性权 重算法； 步骤5： 根据所述预执行时间ETC矩阵、 资源分配CAL矩阵以及任务分配DIS矩阵按照设 定的适应度函数公式计算每 个粒子的适应度值； 步骤6： 更新粒子的速度和位置； 步骤7： 更新全局最优解； 步骤8： 判断是否收敛或达到设定的最大迭代次数， 若是， 则 输出此时的全局最优解， 并 根据所述全局最优解将任务分配至相应的生产节 点中进行生产； 若否， 则返回步骤5继续下 一次搜索过程。 2.根据权利要求1所述的一种基于粒子群算法的遥感产品生产任务调度方法， 其特征 在于， 若连续多次搜索过程中的最优适应度值均不变， 则认 为粒子群算法陷入局部最优， 此 时执行Naive  Acceptance规则来跳出局部最优； 所述Naive  Acceptance规则是指： 当新的 全局最优解的适应度值优于 当前全局最优解的适应度值， 则接受新的全局最优解； 反之， 则 生成随机数p， 若p≥0.5， 则接受新的全局最优解； 其中， 新的全局最优解的确 定方式为： 在 设定的迭代范围内， 选取次优解作为 新的全局最优解。 3.根据权利要求1所述的一种基于粒子群算法的遥感产品生产任务调度方法， 其特征 在于， 若连续多次搜索过程中的最优适应度值均不变， 则认 为粒子群算法陷入局部最优， 此 时执行任务交换规则来跳出局部最优； 所述任务交换规则具体包括： 将当前的全局最优解表示为任务分配矩阵， 根据任务分配矩阵和ETC矩阵的对应关系， 确定各个生产 节点的任务完成时间， 并将所有生产节点的任务完成时间构成任务完成时间 矩阵， 并从中进一步确定最大任务完成时间Xmax、 最小任务完成时间Tmin、 以及分配在生产节 点Rmax中的任务在生产节点Rmin中具有最小任务预执行时间的任务Task； 其中， Rmax是指与 Tmax对应的生产节 点， Rmin是指与Tmin对应的生产节 点； 所述生产节 点的任务完成时间等于其 上所有任务的任务执 行时间之和； 假设将任务Task分配至生产节点Rmin中， 若此时生产节点Rmin的任务完成时间小于Tmax， 则将任务Task分配至生产 节点Rmin中， 并更新得到任务分配矩阵和任务完成时间矩阵； 若此 时生产节点Rmin的任务完成时间不小于Tmax， 则从任务完成时间矩阵的值中进一步确定次小 的任务完成时间， 并将其作为新的最小任务完成时间Tmin以重新进 行任务交换， 若遍历 完所权　利　要　求　书 1/2 页 2 CN 115357357 A 2有的最小任务完成时间均不能进 行任务交换， 则从任务完成时间矩阵的值中进一步确定次 大的任务完成时间， 并将其作为 新的最大任务完成时间Tmax以重新进行任务交换。 4.根据权利要求1所述的一种基于粒子群算法的遥感产品生产任务调度方法， 其特征 在于， 步骤1中， 设定任务集合Task＝{T1， T2， ...， Tm}， 其中将任务Ti的信息表示为： Ti＝ {TaskID， OrderID， taskTyp e}， i＝1， 2， ...， m； 其中TaskID、 OrderID、 taskTyp e分别表示任 务ID、 任务对应的订单ID、 任务类型； 设定生产节点集合Node＝{N1， N2， ...， Nn}， 其中每个生产节点Nj均包括节点IP和生产能 力信息， j＝1， 2， . ..， n。 5.根据权利要求4所述的一种基于粒子群算法的遥感产品生产任务调度方法， 其特征 在于， 所述 生产能力 信息包括CPU的运 算能力、 RAM内存大小、 磁 盘存储空间和网络带宽 。 6.根据权利要求1所述的一种基于粒子群算法的遥感产品生产任务调度方法， 其特征 在于， 整个任务调度过程中， 同一个任务 不能分配到 两个以上生产节点上 执行。 7.根据权利要求1所述的一种基于粒子群算法的遥感产品生产任务调度方法， 其特征 在于， 各个生产节点之间并行生产； 同一个生产节点上 的不同任务之间的关系是非抢先式 的。 8.根据权利要求1所述的一种基于粒子群算法的遥感产品生产任务调度方法， 其特征 在于， 步骤2中还包括： 根据历史数据动态更新不同任务在不同生产 节点的任务预执行时间 从而动态更新所述ETC矩阵。 9.根据权利要求1所述的一种基于粒子群算法的遥感产品生产任务调度方法， 其特征 在于， 步骤5中， 所述 适应度函数公式为： 其中， β1和β2表示预先给定的调整系数且β1+β2＝1， 若β1>β2， 则表示调度过程中更加侧 重计算所要花费的时间， 若β1<β2， 则表示调度过程中更加 侧重计算所要消耗的资源。权　利　要　求　书 2/2 页 3 CN 115357357 A 3