基于混合蛙跳算法的协同工业设计平台任务调度方法

摘要

本发明公开了一种基于混合蛙跳算法的协同工业设计平台任务调度方法，其特征在于，包括：步骤1、初始化种群；步骤2、计算适应度，并按照适应度降序排列；步骤3、子种群划分；步骤4、组内寻优；步骤5、判断是否达到子种群迭代次数，未达到则重复上述过程，达到了则重新划分种群，进行解空间分组重构；步骤6、判断当前解空间是否满足终止条件，不满足则继续计算，满足则算法终止，输出最优解。本发明的特点是：可实现最优调度，使得项目花费最少，且最大程度缩短工期。

说明书

技术领域

本发明涉及协同工业设计平台相关技术领域，具体涉及一种基于混合蛙跳算法的协同工业设计平台任务调度方法。

背景技术

协同工业设计平台采用基于设计云（公有云或私有云）的人机协同设计模式，一个基于云的工业设计项目的工作分为并行任务和串行任务，如图2所示，零件建模到模型组装是基础的并行任务，一般由设计人员手动完成；渲染和资源优化是人机协同完成的；变量绑定、动画设计、仿真控制到工艺分析，由设计人员完成。由于项目各阶段工作的工时消耗不尽相同，参与云设计的人员效率也不一致，其中人工费用按工时结算，代理程序使用费用按耗时电费结算，因此需要根据项目进度需求，实时分配任务给设计人员和代理程序，实现最优调度，使得项目花费最少，且最大程度缩短工期。

发明内容

本发明的目的在于克服上述不足问题，提供一种基于混合蛙跳算法的协同工业设计平台任务调度方法。

本发明为实现上述目的所采用的技术方案是：基于混合蛙跳算法的协同工业设计平台任务调度方法，其特征在于，包括：

步骤1、初始化种群：按照协同工业设计项目管理的经验数据，初步设定一定数量的符合约束函数的可行解，每一只青蛙就是一个符合约束函数的一个解；

步骤2、计算每一只青蛙的适应度，并将所有青蛙按照适应度降序排列；

步骤3、子种群划分：随机的将可能的解分散到各个解空间中并按其适应度排序；

步骤4、设定组内寻优更新次数上限，在该次数之内，进行模糊进化，基于最大蛙跳步长随机生成新解，当前最差解与新解分别对应适应度的差的绝对值<=取更优解时使用的模糊区间时，系统认为新解是一个更优解，利用最差解更新策略更新最差解，若在组内寻优更新最大次数内未找到最优解，那么基于最大蛙跳步长随机生成一个新解替换原有最差解，不考虑适应度大小比较，直接跳出组内寻优；

步骤5、判断是否达到子种群迭代次数，未达到则重复上述过程，达到了则重新划分种群，进行解空间分组重构；

步骤6、判断当前解空间是否满足终止条件，不满足则继续计算，满足则算法终止，输出最优解。

所述约束函数包括约束函数1、约束函数2、约束函数3；

约束函数1：针对某个协同工业设计的项目，包含n项工作W

D = DW

DW为计划设定的可接受的工作时长

而某项工作Wn又可以被分解为wn个任务T，T将由设计人员或代理程序来执行，即分配给设计人员或代理程序的任务，至少要持续保持达到M分钟以上，才能确保任务有效，设DT为某个任务T的持续时间：

DT>= M

任务数量最大值约束：

wn <= DWn / M + 1

基于任务计算项目总耗时：

D =(W1DT

+(WnDT

D >= (w1 + w2 + … + wn) * M

约束函数2：针对每个任务T，令H为参与的设计人员数，Dh为人工工时，P为参与的代理程序线程数，Dp为代理程序执行时间，人员效率指标为Kh，代理程序性能指标为Kp，单个任务分配的最多人员数为Mh、最大线程数为Mp：

Dh = Kh / H

Dp = Kp / P

WnDT = Kh

H <= Mh

P <= Mp

当参与人员越少或者分配的代理程序线程数越少，任务执行耗时就越长，反之任务执行速度快，但费用可能会更高

约束函数3：设人工工时费率为Ch、电费折算率为Cp，那么单个任务费用：

CT = Dh * Ch + Dp * Cp

项目总费用为：

C = Ch * (W1Kh

+ Ch * (W2Kh

+ …

+ Ch * (WnKh

+ Cp * (W1Kp

+ Cp * (W2Kp

+ …

+ Cp * (WnKp

C < MC

MC为项目总预算。

适应度的函数设定为：

F(W, DT, H, P) = [Sigma(WiDT

其中i=1到n，wi <= DWi / M + 1。

本发明的特点是：可实现最优调度，使得项目花费最少，且最大程度缩短工期。

附图说明

此处所说明的附图用来提供对本发明的进一步理解，构成本发明的一部分，本发明的示意性实施例及其说明用于解释本发明，并不构成对本发明的不当限定。

图1是本发明的流程图。

图2是基于云的工业设计项目的任务示意图。

具体实施方式

如图1所示，本发明为一种基于混合蛙跳算法的协同工业设计平台任务调度方法，包括：

步骤1、初始化种群：种群规模就是算法每次迭代的得到解的数量，按照协同工业设计项目管理的经验数据，初步设定一定数量的符合约束函数的可行解，每一只青蛙就是一个符合约束函数的一个解，即设定子种群数，以及算法的迭代深度；

所述约束函数包括约束函数1、约束函数2、约束函数3；

约束函数1：针对某个协同工业设计的项目，包含n项工作W

D = DW

DW为计划设定的可接受的工作时长，即某项工作的最大允许时长

而某项工作Wn又可以被分解为wn个任务T，T将由设计人员或代理程序来执行，即分配给设计人员或代理程序的任务，至少要持续保持达到M分钟（最短执行时间）以上，才能确保任务有效，设DT为某个任务T的持续时间：

DT>= M

任务数量最大值约束：

wn <= DWn / M + 1

基于任务计算项目总耗时：

D =(W1DT

+(WnDT

D >= (w1 + w2 + … + wn) * M

约束函数2：针对每个任务T，令H为参与的设计人员数，Dh为人工工时，P为参与的代理程序线程数，Dp为代理程序执行时间，人员效率指标为Kh（经验值），代理程序性能指标为Kp（经验值），单个任务分配的最多人员数为Mh、最大线程数为Mp：

Dh = Kh / H

Dp = Kp / P

WnDT = Kh

H <= Mh

P <= Mp

当参与人员越少或者分配的代理程序线程数越少，任务执行耗时就越长，反之任务执行速度快，但费用可能会更高；

约束函数3：设人工工时费率为Ch（经验值）、电费折算率为Cp（经验值），那么单个任务费用：

CT = Dh * Ch + Dp * Cp

项目总费用为：

C = Ch * (W1Kh

+ Ch * (W2Kh

+ …

+ Ch * (WnKh

+ Cp * (W1Kp

+ Cp * (W2Kp

+ …

+ Cp * (WnKp

C < MC（项目总预算）；

步骤2、计算每一只青蛙的适应度，并将所有青蛙按照适应度降序排列；

算法中适应度的函数设定为：

F(W, DT, H, P) = [Sigma(WiDT

其中i=1到n，wi <= DWi / M + 1 ；

步骤3、子种群划分：随机的将可能的解分散到各个解空间中并按其适应度排序，看起来像是青蛙从一个群跳到另一个群；

步骤4、为使算法不陷入死循环，设定组内寻优更新次数上限，在该次数之内，进行模糊进化，基于最大蛙跳步长随机生成新解，当前最差解与新解分别对应适应度的差的绝对值<=取更优解时使用的模糊区间时，系统认为新解是一个更优解，利用最差解更新策略更新最差解，若在组内寻优更新最大次数内未找到最优解，那么基于最大蛙跳步长随机生成一个新解替换原有最差解，不考虑适应度大小比较，直接跳出组内寻优；

步骤5、判断是否达到子种群迭代次数，未达到则重复上述过程，达到了则重新划分种群，进行解空间分组重构；

步骤6、判断当前解空间是否满足终止条件，不满足则继续计算，满足则算法终止，输出最优解，算法结束。

本发明是基于混合蛙跳（SFLA）算法，依据协同工业设计平台的任务特点配置SFLA初始参数，同时调用历史项目管理数据库中的任务调度数据和当前项目实时产生的缓存数据，对在诸多约束条件下的系统适应度进行实时分析计算，从而得到一套优化的协同工业设计平台任务调度方案。

本发明的算法核心在于如何调度平衡人机任务数量，在项目预算允许下，最大程度缩短工期，同时将历史调度的参数配置作为经验方案保存到历史数据库中，以供下次算法初始化可行解时调用，形成调度知识库，指导适应度函数和更新规则的选择，避免出现局部最优而导致得不到最优的调度方案。

使用时，项目管理员可以根据项目需求配置相应的项目预算、项目计划、工作分解（分解为任务）、任务最短有效周期、人员数、人员效率指标、代理程序可用线程数、代理程序执行性能、人工工时费率、电费折算率等参数，并在对设计人员和代理程序的任务分配调度之前，初始化输入样本空间、分组数、每组青蛙个数、局部迭代次数、混合迭代次数、实现次数、解的最大移动步长等参数，这些对应着算法中所需要的参数，后台算法就可以利用实时调用缓存数据进行计算分析，最终可以在短时间内得到一套优化的任务分配调度方案。在计算过程中，系统页面会实时的显示出每次实验得到最佳的蛙群适应值，所有计算结束后得到蛙群适应值的平均值，最后得到项目剩余执行的最短时间，即最优实时任务调度方案。

以上所述，仅为本发明较佳的具体实施方式，但本发明的保护范围并不局限于此，任何熟悉本技术领域的技术人员在本发明披露的技术范围内，根据本发明的技术方案及其发明构思加以等同替换或改变，都应涵盖在本发明的保护范围之内。