VMScheduling/docs/赛题介绍.md

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

在百万级的宿主机规模环境下，资源调度/管理系统显得愈发重要，如何在保证数据中心业务运行性能的同时，提高资源利用率，降低基础设施的成本是我们要考虑的核心问题。

此次赛题来自阿里巴巴生产环境中的一个子场景，并做了相应的简化。优秀的解决方案会对我们解决这个场景以及其它场景下的问题带来极大的启发。我们期待优秀的你和你的团队能够投入进来！

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

1赛题描述

共约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的实例的数目