CN112862207B - 针对机器调整时间未知且序列相关的任务调度求解方法 - Google Patents

Abstract

本发明公开了一种针对机器调整时间未知且序列相关的任务调度求解方法，包括：构建任务加工前机器调整时间相关的特征变量集以及预测模型；确定待求解问题的约束，根据问题实际特点进行编码得到问题的可行解；随机生成任务的初始调度顺序，对当前任务顺序下各个任务的机器调整时间预测，计算初始调度顺序下的目标函数值；产生新的任务调度顺序，再次对当前任务顺序下各个任务的机器调整时间进行预测，计算新的任务顺序下的目标函数值；通过目标函数增量的比较，选择下次迭代时的初始任务顺序解，重复迭代直至满足预设的终止条件，最终得到任务的最优调度顺序。本发明针对机器调整时间未知且序列相关的任务调度能够快速实现任务调度的优化求解。

Description

针对机器调整时间未知且序列相关的任务调度求解方法

技术领域

本发明涉及任务调度求解领域，具体涉及一种结合集成学习算法与启发式算法的混合算法，适用于机器调整时间未知且序列相关的任务调度问题求解。

背景技术

制造业是国民经济的支柱性产业，大多数制造业开始往智能制造、智能工厂方向转型升级。随着企业车间设备信息化程度不断提高，可用于进行生产优化分析的数据不断增加，为研究及运营人员掌握生产过程中的不确定因素提供了数据支撑。

在生产过程当中，其中较大的一项不确定因素为任务加工前的机器调整时间，如测试任务中的“打工况”时间，或热处理中的预热时间。其中，不少机器的调整时间还与任务序列高度相关：若改变加工任务的顺序，则机器的调整时间将有较大的变化。在传统的生产中，该时间的估计大概依据技术人员的经验，存在较大的不确定因素。这对进行JIT生产、估计交货时间、充分利用分时电价政策等运营优化，带来较大的阻碍。

关于任务调度问题作为广泛存在工业生产领域的经典问题，长期以来被众多学者所研究，提出了许多共性的问题及解决方法。而随着现代社会的发展，许多共性问题中个性化需求部分应用传统解决方法已经无法奏效。比如在任务调度过程中，经常会遇到机器调整时间不确定且序列相关的问题，在传统解决方法中，往往将调整时间设置为服从某种特定分布函数进行处理，与实际情况存在一定出入，导致调度结果不能满足企业实际需求；比如以降低企业能耗成本为主要目标的生产调度问题也被众多企业所关注，但由于被人员经验限制或者任务中的某些参数不能确定，导致企业无法得到最优的任务调度顺序，无法有效降低企业能耗成本。

现有技术存在的缺陷如下：

1.由于待加工任务的机器调整时间未知(其变化曲线不能用常规分布描述，需要根据历史数据进行预测)且随任务序列相关，工作人员难以准确把握任务完成时间，导致在实际情况中对任务排序大都依靠经验，无法使任务调度方案达到时间或成本最低，从而造成企业生产过程中的浪费及低效。

2.如何有效地运用数据预测方法解决数学规划中参数不确定性问题，是近年来许多专家研究的重点领域。目前来说，较多的研究及应用大多把预测及优化设置为两个单独模块，其求解思路均为先完成预测，再进行优化，两个阶段之间较少关联。

发明内容

针对机器调整时间未知且随序列相关的任务调度问题，本发明的目的是提供一种针对机器调整时间未知且序列相关的任务调度求解方法，能够快速实现任务调度的优化求解。

为了实现上述任务，本发明采用以下技术方案：

一种针对机器调整时间未知且序列相关的任务调度求解方法，包括：

步骤1，根据企业历史数据，筛选出与任务加工前机器调整时间相关的特征变量集；构建关于任务加工前机器调整时间的预测模型并保存；

步骤2，确定待求解问题的约束，根据问题实际特点进行编码得到问题的可行解；

步骤3，随机生成得到任务的初始调度顺序，对当前任务顺序下各个任务的机器调整时间进行预测，计算初始调度顺序下的目标函数值；

步骤4，产生新的任务调度顺序，再次对当前任务顺序下各个任务的机器调整时间进行预测，计算新的任务顺序下的目标函数值；

步骤5，比较当前任务顺序与前一次任务顺序下的目标函数增量；

步骤6，如果选择接受所述新的任务调度顺序作为新解，那么将新的任务调度顺序作为下次迭代时的初始任务顺序解；

否则继续采用原来的初始调度顺序作为下次迭代时的初始任务顺序解；

步骤7，重复迭代步骤3-6步骤直到满足预设的终止条件，最终得到任务的最优调度顺序。

进一步地，步骤1所述的预测模型为基于集成学习算法所建立的预测模型；步骤3、步骤4中采用集成学习算法对当前任务顺序下各个任务的机器调整时间进行预测，步骤4中采用启发式算法产生新的任务调度顺序。

进一步地，所述步骤1包括：

步骤1.1，对企业提供的历史数据进行清洗、探索性、相关性及显著性分析后，结合预测任务及企业实际业务可行性分析，筛选出与任务加工前机器调整时间的特征变量集；

步骤1.2，根据筛选出的特征变量集，构建关于集成学习算法的子预测模型个数为Z的子预测模型集合作为预测模型；

步骤1.3，将所有子预测模型集合预测值求取平均值即为最后机器调整时间P的预测输出值。

进一步地，所述步骤2包括：

步骤2.1，设定待求解问题在任务调度顺序为U_w下的目标函数值minf(U_w)；

步骤2.2，确定待求解问题约束，至少包括：

约束1：

其中，M＝{1,2,…,m}表示机器集合；N＝{1,2,…,n}表示任务集合；

表示0-1变量，如果机器k先后连续加工任务i与j为1否则为0；

约束2：

约束3：

其中，n+1表示机器的终止状态；

约束4：

约束5：

其中，t_ci表示任务i的完工时间；s_ij表示先后连续加工任务i与j同一机器的调整时间，t_j表示任务j的加工时间；

约束6：

其中，t_c0表示每一台机器在其初始状态都可以使用，s_0j表示加工首个任务不需要进行调整。

步骤2.3，根据待求解问题的特点进行编码，得到问题的可行解，即任务的调度顺序。

进一步地，所述求解方法应用于空调测试调度任务中时，所述步骤1包括：

对空调测试实验中心提供的多条具有代表性的实际空调测试数据进行清洗、探索性、相关性及显著性分析，并结合预测任务及企业实际业务可行性分析后，得到一个9维的与测试任务打工况时间P相关的特征变量集Q＝{q₁,q₂,…,q₉}，分别为当前测试任务打工况前实验台内干球温度q₁、当前测试任务打工况前实验台内湿球温度q₂、当前测试任务打工况前实验台外干球温度q₃、当前测试任务打工况前实验台外湿球温度q₄、当前测试任务要求内干球温度q₅、当前测试任务要求内湿球温度q₆、当前测试任务要求外干球温度q₇、当前测试任务要求外湿球温度q₈、实验台制冷量q₉；

根据筛选出的特征变量集Q，构建关于XGBoost集成学习算法数量为Z的决策树集合{T₁(q),T₂(q),…,T_z(q)}，每棵决策树预测的打工况时间值为T_z(q)；

将所有决策树集合预测的打工况时间值求取平均值后即为最终测试任务打工况时间P的预测输出值

进一步地，所述求解方法应用于空调测试调度任务中时，所述步骤2.2包括：

确定关于空调测试任务调度问题约束，如下式所示；

约束1：

其中，M＝{1,2,…,m}表示实验台集合；N＝{1,2,…,n}表示空调测试任务集合；

表示0-1变量，如果实验台k先后连续测试任务i与j为1否则为0；

约束2：

约束3：

其中，n+1表示试验台的终止状态；

约束4：

约束5：

其中，t_ci表示空调测试任务i的完工时间，s_ij表示先后连续测试任务i与j同一实验台的打工况时间，t_j表示空调测试任务j的测试时间；

约束6：

其中，t_c0表示每一台实验台在其初始状态都可以使用，s_0j表示进行首个任务测试时不需要进行调整；

约束7：

其中，d表示待测试空调集合中的待测试空调，l_d表示该待测空调的任务数量；

约束8：

其中，

表示第d个待测试空调在实验台k上进行测试时，先进行焓差实验任务后进行空调组装任务，H_d表示第d个待测试空调任务集合；

约束9：

其中，a_d表示第d个待测试空调的组装任务；

表示0-1变量，如果任务i在实验台k上进行测试为1否则为0；b_d,l-1表示第d个待测试空调的第l-1个焓差实验任务。

进一步地，所述求解方法应用于空调测试调度任务中时，所述步骤2.3包括：

(1)所述空调测试任务调度问题包含2个子问题：实验台分配和空调测试任务排序；采用两段式编码方式，将2个子问题编码在一起来表示问题的一个可行解；

(2)实验台分配的编码方式为插入式编码，多个个任务集随机排序后在中间任意位置插入一个数字即可将多个待测试的空调分配到两个实验台上进行测试，其中如果各个实验台上任务分配不均匀则会有多余费用惩罚；

(3)每台被测空调之间采取分段式编码，对测试任务编码采用整数编码，将每一个测试任务用一个数字代替。

与现有技术相比，本发明具有以下技术特点：

1.本发明针对生产过程中机器调整时间未知且与生产序列相关的任务调度问题，提出一种新的混合求解算法。该算法主要依赖于企业的生产大数据而非人工经验实现对任务调度问题的优化求解。

2.本发明运用了数据挖掘与数学规划相结合的手段，相应的提出了一种结合集成学习算法与启发式算法的混合算法，其通过数据预测手段不仅可以精准预测任务加工前的机器准备时间，而且在算法迭代过程中，集成学习算法与启发式算法采用并行处理方式进行求解，加快了问题的求解速度，提高了企业生产效率和管理水平。

附图说明

图1为本发明方法的流程示意图；

图2为本发明方法应用到空调测试任务实施例中的调度流程图；

图3为本发明实施例的应用结果对比图。

具体实施方式

本发明主要应用于机器调整时间未知且与序列相关的任务调度问题，此类问题可以具体描述为：企业在生产制造过程中，存在一台或者多台具备加工所有任务的机器，所有机器处于初始状态时便可以对所有任务进行加工，加工一旦开始不能半途中断该操作；每个任务的加工要求已知且确定，每一台机器在加工不同的任务时机器调整时间未知且与任务的加工顺序有关；最终确定每一台机器上的任务加工顺序以实现优化目标。

其中，制约着问题求解的主要因素为“任务加工前机器调整时间不确定且随序列相关”，对于求解该问题来说，如果采用目前常用的求解思路，则需要列举出全部可行的任务调度顺序，及预测全部顺序下各个任务的机器调整时间，不仅增大任务计算量还使得问题变的更加复杂，所以需要进一步通过有效的算法进行解决。

本发明提出一种针对机器调整时间未知且序列相关的任务调度求解方法，该方法是一种结合集成学习算法与启发式算法的混合算法，下面对该算法作进一步详细说明。

由于机器调整时间未知且随序列相关的调度问题具有较高的复杂性，针对该种企业的共性问题，本发明提出的结合集成学习算法与启发式算法的混合算法，主要分为两个部分：基于集成学习算法的数据预测部分和基于启发式算法的求解部分，两部分之间采用并行处理方式对问题进行求解，在求解效率和精度方面都有了很大的提高。

该算法具体流程和流程中出现的相关变量符号如下所示：

步骤1，根据企业历史数据，筛选出与任务加工前机器调整时间P相关的特征变量集Q；构建关于任务加工前机器调整时间P的集成学习算法预测模型并保存。

步骤2，确定待求解问题的约束，根据问题实际特点进行编码得到问题的可行解。

步骤3，随机生成得到任务的初始调度顺序U₀，利用集成学习算法对当前任务顺序下各个任务的机器调整时间P进行预测，根据上述步骤可知P_j＝s_ij；计算初始调度顺序下的目标函数值f(U₀)。

步骤4，利用启发式算法产生新的任务调度顺序U₁，再次调用集成学习算法对当前任务顺序下各个任务的机器调整时间P进行预测，计算新的任务顺序下的目标函数值f(U₁)。

步骤5，比较当前任务顺序与前一次任务顺序下的目标函数增量df＝f(U₁)-f(U₀)；

步骤6，如果选择接受新的任务顺序U₁作为新解，那么将新解U₁作为下次算法迭代时的初始任务顺序解U₀＝U₁；如果不接受新的任务顺序U₁作为新解，那么继续采用原来的初始任务顺序U₀作为下次算法迭代时的初始任务顺序解U₀＝U₀。

步骤7，重复迭代步骤3-6步骤直到满足算法预设的终止条件，最终得到任务的最优调度顺序。

其中，所述步骤1的具体包括：

步骤1.1，对企业提供的历史数据进行清洗、探索性、相关性及显著性分析后，结合预测任务及企业实际业务可行性分析，筛选出与任务加工前机器调整时间P相关的特征变量集Q＝{q₁,q₂,…,q_g}。

步骤1.2，根据筛选出的特征变量集Q，构建关于集成学习算法子预测模型个数为Z的子预测模型集合{T₁(q),T₂(q),…,T_z(q)}，其中第z个子预测模型的机器调整时间预测值为T_z(q)。

步骤1.3，将所有子预测模型集合预测值求取平均值即为最后机器调整时间P的预测输出值

在上述技术方案中，所述步骤2的具体包括：

步骤2.1，设定待求解问题在任务调度顺序为U_w下的目标函数值minf(U_w)。

步骤2.2，确定待求解问题约束，至少包括以下约束：

约束1：

该式表示每个任务只能在一台机器上加工一次，不能半途中断也不能更换机器。

约束2：

该式确定参与首个加工任务的编号。

约束3：

该式确定参与最后一个加工任务的编号。

约束4：

该式表示任务在相应加工序列中存在确定性的先后关系。

约束5：

该式表示在每一台机器所加工的任务中，两个连续任务之间的完工时间关系。

约束6：

该式表示每一台机器在其初始状态都可以使用，且加工首个任务不需要进行调整。

步骤2.3，根据待求解问题的特点进行编码，得到问题的可行解，即任务的调度顺序。

实施例：

将本发明算法应用于空调测试行业中关于空调测试任务的调度问题，通过对空调测试任务进行合理的安排，进一步降低实验台的总耗电费用来说明本发明所提算法的有效性。

应用背景介绍：

新空调投入市场前进行需针对不同环境工况进行大量焓差实验，其中，焓差实验的准备(“打工况”)时间难以确定且会随测试任务顺序改变而发生变化，该企业拥有多个实验台可以进行空调测试任务，如何确定每个实验台上的空调最优任务测试顺序及当前顺序下的任务打工况时间，使得实验台的耗电费用最小，其具体应用流程及流程中出现的相关变量符号如下所示：

步骤1，根据企业历史数据，筛选出与任务打工况时间P相关的特征变量集Q；构建关于任务测试前打工况时间P的XGBoost集成学习算法预测模型，并保存，具体过程如下：

步骤1.1，对该空调测试实验中心提供的多条具有代表性的实际空调测试数据进行清洗、探索性、相关性及显著性分析后，结合预测任务及企业实际业务可行性分析后，最终得到一个9维的与测试任务打工况时间P相关的特征变量集Q＝{q₁,q₂,…,q₉}，分别为当前测试任务打工况前实验台内干球温度q₁、当前测试任务打工况前实验台内湿球温度q₂、当前测试任务打工况前实验台外干球温度q₃、当前测试任务打工况前实验台外湿球温度q₄、当前测试任务要求内干球温度q₅、当前测试任务要求内湿球温度q₆、当前测试任务要求外干球温度q₇、当前测试任务要求外湿球温度q₈、实验台制冷量q₉。

步骤1.2，根据筛选出的特征变量集Q，构建关于XGBoost集成学习算法数量为Z的决策树集合(子预测模型集合){T₁(q),T₂(q),…,T_z(q)}，每棵决策树预测的打工况时间值为T_z(q)。

步骤1.3，将所有决策树集合预测的打工况时间值求取平均值后即为最终测试任务打工况时间P的预测输出值

步骤2，确定企业进行空调测试任务的约束，对问题进行编码处理得到关于空调测试任务调度顺序的可行解；具体过程如下：

步骤2.1，设定关于空调测试调度问题的目标函数值minf(U_w)；即找到最优的空调测试任务顺序使得实验台总耗电费用成本最低；

步骤2.2，确定关于空调测试任务调度问题约束，如下式所示；

约束1：

该式表示每个任务只能在一台实验台上测试一次，不能半途中断也不能更换实验台。

约束2：

该式表示确定参与首个测试任务的编号。

约束3：

该式表示确定参与最后一个测试任务的编号。

约束4：

该式表示任务在相应测试序列中存在确定性的先后关系。

约束5：

该式表示在每一台实验台所测试的任务中，两个连续测试任务之间的完工时间关系。

约束6：

该式表示每一台实验台在其初始状态都可以使用，且进行首个任务测试时不需要进行调整。

约束7：

该式表示空调测试任务集合个数、待测试空调个数与总测试任务之间关于数量的等式关系。

约束8：

该式表示空调在进行焓差实验任务前，必须进行安装任务，将待测试空调安装到相应实验台上。

约束9：

该式表示待空调一经安装到相应实验台上直到完成其所有测试任务前不可拆卸；

步骤2.3，根据问题特点进行编码，得到问题的可行解，即测试任务的调度顺序，其具体步骤如下：

(1)该实施例包含2个子问题：实验台分配和空调测试任务排序。因此，本发明采用两段式编码方式，将2个子问题编码在一起来表示本问题的一个可行解。假设有4台待测试的空调(1-4)被分配到2个实验台进行测试，4个空调的测试任务数量分别为5，6，4，5(包含测试前将空调安装到实验台的组装任务)，根据此编码方式可得到的一个可行解如下所示：

(2)实验台分配的编码方式为插入式编码，4个任务集随机排序后在中间任意位置插入一个数字(-1)即可将4个待测试的空调分配到两个实验台上进行测试，其中如果各个实验台上任务分配不均匀则会有多余费用惩罚。

(3)每一台被测试的空调进行的测试任务数量不等，根据实际情况，每台待测试空调被安装到相应实验台直到完成所有测试任务前不可拆卸，只能在当前实验台完成全部测试任务，所以每台被测空调之间采取分段式编码，对测试任务编码采用整数编码，将每一个测试任务用一个数字代替。如上述可行解中空调1中将要进行5个测试任务，于是将该空调待进行测试的任务编码为1-5的数字组合。

步骤3，利用模拟退火算法(SA，Simulated Annealing)对问题进行求解，取初始温度T₀足够大，令T＝T₀，随机生成得到任务的初始调度顺序U₀，调用XGBoost算法对当前测试任务顺序下各个任务的打工况时间P进行预测，根据上述步骤可知P_j＝s_ij；计算初始测试任务顺序下的实验台总耗电费用值f(U₀)，对于当前温度T，重复步骤4-7。

步骤4，对当前任务加工顺序U₀随机扰动产生一个新的空调测试任务顺序U₁，再次调用XGBoost预测模型对当前测试任务顺序下各个测试任务的打工况时间P进行预测，计算新的测试任务顺序下的实验台总耗电费用f(U₁)。

步骤5，比较两种任务顺序下的实验台耗电费用增量df＝f(U₁)-f(U₀)。

步骤6，如果df≤0,则选择接受新的测试任务顺序U₁作为新解，那么将新解U₁作为下次算法迭代时的初始测试任务顺序解U₀＝U₁；否则，计算U₁的接受概率exp(-df/T)，T是当前温度。随机产生(0,1)区间上均匀分布的随机数rand，若exp(-df/T)>rand，也接受U₁作为新的当前解U₀＝U₁，否则保留当前解U₀，即继续采用原来的初始测试任务顺序U₀作为下次算法迭代时的初始测试任务顺序解U₀＝U₀。

步骤7，如果满足设定的终止条件则输出当前解U₀作为最优解，结束程序。

步骤8，T逐渐减少，然后转步骤3。

步骤9，经过以上步骤，最终得到实验台总耗电费用最小的空调测试任务调度顺序。

本实施例的实验结果：

图3为针对该实施例的实验中心测试任务日常安排方案与应用本方案的费用对比图，本发明随机选取10个实际案例分别计算其相对应实验台电费进行验证。其中在该企业日常空调测试安排方案中，测试任务的顺序都是按照测试人员的经验判断，测试顺序无法达到最优，相邻两项之间测试任务的环境参数差值相对较大，从而使得每个测试任务的打工况时间普遍较长，整个实验台耗电费用处于一个较高水平。

本方案针对以上情形，应用所提出的结合集成学习算法与启发式算法的混合算法后，相邻两项之间测试任务的环境参数差值相对减小，测试任务打工况时长缩短，使得实验台电费得到了优化，其中最大电费优化比例为34.3％，最小电费优化比例为13.3％，平均电费优化比例为23％。

以上实施例仅用以说明本申请的技术方案，而非对其限制；尽管参照前述实施例对本申请进行了详细的说明，本领域的普通技术人员应当理解：其依然可以对前述各实施例所记载的技术方案进行修改，或者对其中部分技术特征进行等同替换；而这些修改或者替换，并不使相应技术方案的本质脱离本申请各实施例技术方案的精神和范围，均应包含在本申请的保护范围之内。

Claims (1)

1.一种针对机器调整时间未知且序列相关的任务调度求解方法，其特征在于，包括：

步骤1，根据企业历史数据，筛选出与任务加工前机器调整时间相关的特征变量集；构建关于任务测试前打工况时间P的XGBoost集成学习算法预测模型并保存；所述的预测模型为基于集成学习算法所建立的预测模型；所述求解方法应用于空调测试调度任务中时，所述步骤1包括：

步骤1.1对空调测试实验中心提供的多条具有代表性的实际空调测试数据进行清洗、探索性、相关性及显著性分析，并结合预测任务及企业实际业务可行性分析后，得到一个9维的与测试任务打工况时间P相关的特征变量集Q＝{q₁,q₂,…,q₉}，分别为当前测试任务打工况前实验台内干球温度q₁、当前测试任务打工况前实验台内湿球温度q₂、当前测试任务打工况前实验台外干球温度q₃、当前测试任务打工况前实验台外湿球温度q₄、当前测试任务要求内干球温度q₅、当前测试任务要求内湿球温度q₆、当前测试任务要求外干球温度q₇、当前测试任务要求外湿球温度q₈、实验台制冷量q₉；

步骤1.2，根据筛选出的特征变量集Q，构建关于XGBoost集成学习算法数量为Z的决策树集合{T₁(q),T₂(q),…,T_z(q)}，每棵决策树预测的打工况时间值为T_z(q)；

步骤1.3，将所有决策树集合预测的打工况时间值求取平均值后即为最终测试任务打工况时间P的预测输出值；

步骤2，确定企业进行空调测试任务的约束，对问题进行编码处理得到关于空调测试任务调度顺序的可行解；具体过程如下：

步骤2.1，设定关于空调测试调度问题的目标函数值minf(U_w)；即找到最优的空调测试任务顺序使得实验台总耗电费用成本最低；

步骤2.2，确定关于空调测试任务调度问题约束，如下式所示；

约束1：

其中，M＝{1,2,…,m}表示实验台集合；N＝{1,2,…,n}表示空调测试任务集合；

表示0-1变量，如果实验台k先后连续测试任务i与j为1，否则为0；

约束2：

其中，

表示0-1变量，如果实验台k先后连续测试任务0与j为1，否则为0；

约束3：

其中，n+1表示试验台的终止状态测试任务；

表示0-1变量，如果实验台k先后连续测试任务j与n+1为1，否则为0；

约束4：

其中，

表示0-1变量，如果实验台k先后连续测试任务j与i为1，否则为0；

约束5：

其中，t_ci表示空调测试任务i的完工时间，s_ij表示先后连续测试任务i与j同一实验台的打工况时间，t_j表示空调测试任务j的测试时间；

约束6：

其中，t_c0表示每一台实验台在其初始状态都可以使用，s_0j表示进行首个任务测试时不需要进行调整；

约束7：

其中，d表示待测试空调集合中的第d个待测试空调，D＝{1,2,…,d}；l_d表示待测空调的任务数量；

约束8：

其中，

表示第d个待测试空调在实验台k上进行测试时，先进行焓差实验任务后进行空调组装任务，H_d表示第d个待测试空调的任务集合；

约束9：

其中，a_d表示第d个待测试空调的组装任务，

表示0-1变量；

表示0-1变量，如果任务o在实验台k上进行测试为1，否则为0；o＝b_d,1、b_d,2…b_d,l-1；b_d,l-1表示第d个待测试空调的第l-1个焓差实验任务；

步骤2.3，根据问题特点进行编码，得到问题的可行解，即测试任务的调度顺序，其具体步骤如下：

(1)空调测试任务调度问题包含2个子问题：实验台分配和空调测试任务排序；采用两段式编码方式，将2个子问题编码在一起来表示问题的一个可行解；

(2)实验台分配的编码方式为插入式编码，多个任务集随机排序后在中间任意位置插入一个数字即可将多个待测试的空调分配到两个实验台上进行测试，其中如果各个实验台上任务分配不均匀则会有多余费用惩罚；

(3)每台被测空调之间采取分段式编码，对测试任务编码采用整数编码，将每一个测试任务用一个数字代替；

步骤3，利用模拟退火算法对问题进行求解，令T＝T₀，T₀为初始温度；随机生成得到任务的初始调度顺序U₀，调用XGBoost算法对当前测试任务顺序下各个任务的打工况时间P进行预测；计算初始测试任务顺序下的实验台总耗电费用值f(U₀)，对于当前温度T，重复步骤4-7；

步骤4，对初始调度顺序U₀随机扰动产生一个新的空调测试任务顺序U₁，再次调用XGBoost预测模型对当前测试任务顺序下各个测试任务的打工况时间P进行预测，计算新的测试任务顺序下的实验台总耗电费用f(U₁)；

步骤5，比较两种任务顺序下的实验台耗电费用增量df＝f(U₁)-f(U₀)；

步骤6，如果df≤0，则选择接受新的空调测试任务顺序U₁作为新解，那么将U₁作为下次算法迭代时的初始调度顺序；否则，计算新的空调测试任务顺序U₁的接受概率exp(-df/T)，T是当前温度；

随机产生(0,1)区间上均匀分布的随机数rand，若exp(-df/T)>rand，接受U₁作为新的当前初始调度顺序，否则保留当前初始调度顺序U₀，即继续采用原来的初始测试任务顺序U₀作为下次算法迭代时的初始测试任务顺序解；

步骤7，如果满足设定的终止条件则输出当前初始调度顺序U₀作为最优解，最终得到任务的最优调度顺序。

Images