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

摘要

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

权利要求

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

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

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

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

步骤2，确定企业进行空调测试任务的约束，对问题进行编码处理得到关于空调测试任务调度顺序的可行解；具体过程如下：步骤2.1，设定关于空调测试调度问题的目标函数值minf(Uw)；即找到最优的空调测试任务顺序使得实验台总耗电费用成本最低；

步骤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：

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

约束6：

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

约束7：

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

约束8：

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

约束9：

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

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

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

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

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

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

7；

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

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

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

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

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

说明书

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

技术领域

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

背景技术

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

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

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

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

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

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

发明内容

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

[0027] 约束1：

[0028]

[0029] 其中，M＝{1,2,…,m}表示机器集合；N＝{1,2,…,n}表示任务集合； 表示0‑1变量，如果机器k先后连续加工任务i与j为1否则为0；

[0030] 约束2：

[0031]

[0032] 约束3：

[0033]

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

[0035] 约束4：

[0036]

[0037] 约束5：

[0038]

[0039] 其中，tci表示任务i的完工时间；sij表示先后连续加工任务i与j同一机器的调整时间，tj表示任务j的加工时间；

[0040] 约束6：

[0041]

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

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

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

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

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

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

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

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

[0050] 约束1：

[0051]

[0052] 其中，M＝{1,2,…,m}表示实验台集合；N＝{1,2,…,n}表示空调测试任务集合；表示0‑1变量，如果实验台k先后连续测试任务i与j为1否则为0；

[0053] 约束2：

[0054]

[0055] 约束3：

[0056]

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

[0058] 约束4：

[0059]

[0060] 约束5：

[0061]

[0062] 其中，tci表示空调测试任务i的完工时间，sij表示先后连续测试任务i与j同一实验台的打工况时间，tj表示空调测试任务j的测试时间；

[0063] 约束6：

[0064]

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

[0066] 约束7：

[0067]

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

[0069] 约束8：

[0070]

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

[0072] 约束9：

[0073]

[0074] 其中，ad表示第d个待测试空调的组装任务； 表示0‑1变量，如果任务i在实验台k上进行测试为1否则为0；bd,l‑1表示第d个待测试空调的第l‑1个焓差实验任务。

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

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

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

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

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

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

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

附图说明

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

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

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

具体实施方式

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

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

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

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

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

[0090]

[0091]

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

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

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

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

[0096] 步骤5，比较当前任务顺序与前一次任务顺序下的目标函数增量df＝f(U1)‑f(U0)；

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

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

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

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

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

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

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

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

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

[0106] 约束1：

[0107]

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

[0109] 约束2：

[0110]

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

[0112] 约束3：

[0113]

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

[0115] 约束4：

[0116]

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

[0118] 约束5：

[0119]

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

[0121] 约束6：

[0122]

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

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

[0125] 实施例：

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

[0127] 应用背景介绍：

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

[0129]

[0130]

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

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

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

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

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

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

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

[0138] 约束1：

[0139]

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

[0141] 约束2：

[0142]

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

[0144] 约束3：

[0145]

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

[0147] 约束4：

[0148]

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

[0150] 约束5：

[0151]

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

[0153] 约束6：

[0154]

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

[0156] 约束7：

[0157]

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

[0159] 约束8：

[0160]

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

[0162] 约束9：

[0163]

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

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

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

[0167]

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

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

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

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

[0172] 步骤5，比较两种任务顺序下的实验台耗电费用增量df＝f(U1)‑f(U0)。

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

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

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

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

[0177] 本实施例的实验结果：

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

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

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