阿里巴巴全球调度算法大赛

https://tianchi.aliyun.com/competition/introduction.htm?spm=5176.100066.0.0.6acd33afqgdgz0&raceId=231663

在初赛的基础上，增加了以下内容：

在线任务的迁移限制

迁移将更遵循实际，采取多轮并发执行，每一轮并发迁移为多个迁移命令同时执行，一个迁移命令将采取先新建后删除的方式。例如：

1,inst1,A
1,inst2,A
2,inst3,B

为_两阶段_迁移计划。在第一轮中，inst1和inst2迁移到了机器A上，这个是分两个阶段执行的：第一阶段，将同时在机器A上新建inst1、inst2实例，新建成功后再将inst1、inst2在原来所属的机器删除旧实例，并执行下一轮（inst3到机器B）。

若出现迁移失败，则直接退出在线任务调度阶段。

迁移限制：每轮迁移没有命令数量限制，但限制轮数小于等于k（暂定k=3）。

离线任务调度

初赛仅涉及在线任务的调度，实际场景我们常常需要在离线任务混部才能获得最高的资源利用率。

定义一个离线任务(job_info.x.csv)为：

离线任务id, cpu占用, mem占用, 实例数, 执行时间, 前驱任务id列表

其中

执行时间的单位为分钟。对应到在线任务的cpu/mem曲线的98个点，分别代表该在线任务在[0, 15)、[15, 30)、...、[1455, 1470)时刻的资源用量
每个离线任务的最早启动时刻，必须大于其所有前驱任务的所有实例执行完成的时刻t
在一个完整周期[0, 1470)内，所有离线任务的所有实例必须全部被执行完成离线任务不允许迁移
- 对于一个离线任务，只有当其所有的instance都执行完毕，这个离线任务才可以被认为是执行完成
所以最终的提交结果分为两个部分：
在线任务阶段： 迁移轮数, 在线任务实例id, 目标宿主机id
离线任务阶段： 离线任务id, 目标宿主id, 启动时刻, 启动实例数量

一旦开始离线任务的调度，便不允许继续进行在线任务的调度。

评分修改

原评分公式中的a，由a=10，修改为

a=(1+该机器上部署的在线任务inst数量)

赛题数据说明

复赛有a, b, c, d, e一共5份赛题，每份赛题包含5份数据，其中：

app_interference.csv、app_resources.csv为5份赛题的公用数据
instance_deploy.x.csv、job_info.x.csv、machine_resources.x.csv为第x份赛题对应的独有数据

最终提交结果按a,b,c,d,e的顺序拼接，以#分割。

下面是一个例子：

1, inst1, machine_a
task_1, machine_a, 10, 31
#
1, inst1, machine_b
2, inst2, machine_c
task_1, machine_c, 10, 28

复赛排行榜中，选手的分数为五份赛题答案得分的总和。

为复赛胜出的准备

参加决赛资格由复赛成绩决定，复赛成绩的主要依据是排名，但也包括赛事导师对排名靠前选手的线下代码审核。为了让选手更好的准备复赛之后的提交，我们有如下建议：

请按照我们初赛描述中推荐的方式整合您的代码 (link)
请准备一个简短报告，至少包括
- 您对赛题的理解和解题思路
- 最后得出方案的计算环境的配置和计算时间（硬件、软件、时间等）
- 任何您想说的话
复赛结束时（2018.09.07），我们会按照选手提交的复赛成绩，结合初赛时候的一些表现，在复赛结束时要求指定的选手提交代码和报告。如果不在规定的时间提交，视作放弃，但我们真诚的希望出色的选手可以和我们分享您的成果。如果有选手没有被邀请提交代码和报告，我们也欢迎您毛遂自荐，我们的导师会看您的代码和报告，并给出答复意见。

初赛赛题描述

重要更新：

7月26日，我们对初赛赛制进行了更新，具体的：

* 我们新开放了新一个版本的数据（Data_B），之前的数据称之为Data_A，作用于初赛

*Data_B和Data_A描述的是两个独立的问题。Data_B和Data_A的格式一致，只有数值不同，主要目的是为了防止参赛选手设计针对Data_A过拟合的算法（经我们测试，通用算法无需修改就可以算出合法的解，但Data_B有更多优化空间）

* 由于添加Data_B导致的提交结果的变化，见下面的“提交结果”部分。简单的说，新的提交方式中，参赛选手还是提交一份答案，其格式为

<Data_A的解>

<Data_B的解>

* 评分机制会有相应修改，并在7月30日作用于排行榜。修改后的评分公式为：final_score = 0.5*(score(Data_A)+score(Data_B))；针对Data_A和Data_B的评分机制score函数，与更新前保持一致，具体见“执行与评分（初赛）”部分；进入复赛的条件保持不变（见“赛制介绍”）

* 对于此次更新给各位选手带来的不便我们感到十分抱歉，但会尽力为选手提供最好的参赛体验。更多关于赛题更新的说明可以参考：https://tianchi.aliyun.com/forum/new_articleDetail.html?spm=5176.8366600.0.0.52f3311fT3qWk6&raceId=231663&postsId=5802

赛题在6月11日有一次更新（赛题描述和数据），6月7日上线的赛题已经彻底下线，请所有参赛同学以你当前看到的版本赛题为准，7月初开始的评测工作将以目前版本为准。由此给各位选手带来的不便，深感歉意。但我们相信，目前这个版本的赛题无论对于初学者还是资深的研究者，都是很有趣的。

1赛题描述

7月26日添加了一份新的数据（Data_B_xxxx），下面的赛题描述同时适用于之前版本的数据（Data_A_xxxx）和更新的数据（Data_B_xxxx），基于二者共同作用的评分机制见上面的“重要更新”部分。注意，Data_A和Data_B描述的是两个独立的问题，只是格式一样。

共约6K台宿主机（machine），包含了若干种型号，约68K个任务实例（instance），其中一部分已经部署在宿主机上，还有一部分没有被部署。

要求：设计调度算法，在满足要求约束的前提下，通过将全部未被调度的任务实例调度到宿主机上以及腾挪部分已经部署的实例的方式，得到最优的部署方案。最优部署方案指实际使用宿主机数目尽可能少，且宿主机负荷不能过高。请参考“执行与评分（初赛）”部分来获得更多关于最优部署方案的说明。

在解释数据格式、约束条件之前，为防止概念混淆，先给出几个定义，全文出现的概念以此定义为准。

实例（instance）：一个实例是可以被调度到一个机器上的对象，在实际生产中，一个实例可以是一个docker容器

应用分组（App）:一个应用分组包括很多实例（instance）。属于同一个App下的所有实例，具备相同的约束条件。一个实例能且只能属于一个应用分组

机器（Machine）：机器是集群中的服务器，一个实例被可以被调度到一个机器上

1.1约束描述

任务实例到宿主机的分配，需要满足下列约束：

·每个实例都标明了CPU、memory、disk此3个维度的资源需求，其中CPU、memory以分时占用曲线的形式给出，在任意时刻，任意一个宿主机A上，所有部署在宿主机A上的实例的任意资源都不能超过宿主机A的该资源容量

·另外还有P、M、PM三类资源，定义了应用实例的重要程度，任意一台宿主机上的部署数目不能超过该类型宿主机能够容纳的重要应用数目上限

·混部集群时刻处于复杂的干扰环境中，所以我们需要满足一些规避干扰约束，一条规避干扰约束被描述为<APP_A, APP_B, k>，代表若一台宿主机上存在APP_A类型的实例，则最多能部署k个APP_B类型的实例。注意，k可能为0。APP_A和APP_B也可能代表同一个APP（e.g. <APP_A, APP_A, k>），代表同一台机器上最多可以部署的该APP的实例的数目

1.2数据描述

问题一共包含四份数据表：instance_deploy.csv, app_resources.csv, machine_resources.csv, app_interference.csv

**instance_deploy.csv ** o实例id

o实例所属应用

o实例所属宿主机:

§注：当前未分配的实例，实例所属宿主机列为空

**·app_resources.csv ** o应用id

ocpu分时占用曲线（每个点由< | >隔开）

omem分时占用曲线（每个点由< | >隔开）

odisk申请量（标量）

oPM

**·machine_resources.csv ** o宿主机id

ocpu规格

omem规格

odisk规格

oP上限

oM上限

oPM上限

**·app_interference.csv ** o应用id1

o应用id2

o最大部署量

1.3结果提交

1.3.5推荐的复赛提交格式（暂定）

在第二阶段比赛（复赛）接近尾声时，我们会要求排行榜排名前10的队伍提交针对复赛题目的计算出迁移方案的代码，进行线下评测。迁移方案和线下评测的标准会在“评价标准”中说明，如果参赛队伍不能提供代码、或者提交代码与结果不匹配，相应的排行榜成绩无效。

注1:提交文件夹结构

·project

·|--README.md

·|--data

·|--code

· |-- main.py or main.ipynb or <其它语言代码>

·|--submit

· |-- submit_20180203_040506.csv

注2:提交文件文件名代码

·# java for example

·import datetime

·data.to_csv(("../submit/submit_"+datetime.datetime.now().strftime('%Y%m%d_%H%M%S') + ".csv"), header=None, index=False)

1.4你可以用这份数据设计其它算法

下面的要求不是比赛的一部分，但同样是数据中心资源调度关心的目标。爱好者可以根据这份数据设计以下面需求之一为目的的调度算法。我们十分欢迎您与我们交流您的想法！

1.同样是上述数据和问题，设计在线调度算法。所谓在线调度算法，是待调度的任务顺序地被调度器调度，而调度器不知道待调度任务序列中靠后的任务的信息。实践中，在线算法只能接近，但很难达到离线算法的效果。

2.让算法更robustness。实际环境中，大量数据为建模预估产生的模型化数据，例如赛题中的cpu, mem分时占用曲线，如何在预估数据存在偏差的前提进行问题求解，或者如何在已知决策模型的前提下调整预估方法，也是充满挑战的问题。

3.其它任何你能想到的使用这份数据可以设计的问题和算法。如果你对这个有兴趣，我们相信你会对我们第二阶段的比赛更加有兴趣，请保持关注并一定参加我们的正式比赛！

复赛赛题.md 11 KB Permalink History Raw