aqizhoua/-

队伍：永远享受兜风的感觉

数据集特点：

线上第一次给数据集有一定的规律（每个400单位时间增加一个任务）可以根据这个去减少超时的任务数量。但是受到ai分类准确率的影响，用本地数据具体做的时候可以试试将执行时间改成准确率影响后的执行时间

构造得分函数:

赛题变动后，得分函数:（亲和性 + 不超时) / 最晚完成任务的时间

解题思路

在尝试性提交几次后，发现最小化完成任务的最晚时间是主要影响因子，所以我的前提就是让在机器上运行的所有任务的总执行时间趋于平均。

考虑亲和性：

以所有用户的第一个任务按照类型进行分类，并以小根堆保存同一类型任务的总执行时间。并将每个机器的预执行时间也以小根堆保存，每次取出小根堆堆顶的机器和同一类型的所有任务进行分配（具体计算执行时间要注意到同一个用户的所有任务只能在一个机器上执行）。实际在优化时需要放出几个后面几个类型的任务，不按照同一类型所有分配原则，而是单个任务分配原则，更能使得总执行时间趋于平均。

机器上调度：

我的权重是在尽量保持亲和性的基础上，再考虑不超时任务。打个比方现在在机器一上有个类型一的批量任务，需要在整个批量任务上进行划分（主要根据截至时间调整）进行分段调度。遇到超时的任务放在这个批量的末尾。

用户后续任务的处理

我在做的时候是开了三个堆，按照一定的参数指标放入不同的堆中，并且需要考虑堆中任务执行的优先级（这个过程也需要调参）

后续可优化的地方：

赛后和某佬交流后，发现可以用反悔贪心的方式来做，因为给的时间限制是4秒，可以设置个学习率来自调整一些参数，每次得到一个调度序列后根据得分函数找出最优的调度策略。