多维度资源分配问题，在系统调度中是经常遇到的一个问题，比如，集群中有cpu，mem，ssd等资源，每个作业需要的每个维度的资源不一样，如何分配集群中的资源给哪些job才能够使得集群的资源利用率最大呢？这就是比较典型的资源分配问题。对于一些需要一定执行时间的job，这个问题的优化目标还会牵扯到最小化总的执行之间以及让各个job等待处理的时间尽量的平均，即公平性。
下面主要介绍论文《Multi-dimensional Resource Integrated Scheduling In a Shared Data Center》中的一些思想方法。

论文主要关注分配率的问题，即如何分配job才能够使得整机的资源利用率最佳，这个对于服务部署类很有借鉴作用。当部署服务的时候，比如通过k8s来部署服务，这类服务一般为常驻服务，即没有特殊情况，会一直存活，没有所谓的job执行时间（换句话说，job执行时间也就是永远，除非job出故障）。对于这类服务，一般服务本身都会说明对资源的需求，比如内存=2GB，cpu=2核，ssd=500GB。那么如何调度job才能够使得机器的资源利用率最高呢？

问题引入

假设一个机器拥有12 CPU core，12GB memory，12TB disk。我们写成<12,12,12>。现在有4个待分配的任务，每个任务对资源的需求分别描述为如下所示：app1=<6,2,2>， app2=<5,4,8>, app3=<4,6,2>, app4=<2,2,6>。那么如何安排这几个app到这个机器上面，能够使得这个机器的资源利用率最大呢？

下面对比一下如下两种调度策略：

S1:FIFO，显然只能够调度app1和app2，因为这两个app对cpu的资源需求都比较大。这样调度的话就会浪费mem和disk的资源。如下所示：

S2:按照对资源的需求来调度，这就是作者的核心思想，实时计算哪种资源是稀缺的，哪种资源是比较充足的，根据此来调度。后面会详细讲述，但是假设我们调度app4，app3，app1的话，则资源利用率明显要高于S1。

建模

R=<r₁,r₁,r_i … r_m>：设一个数据中心的资源为R，一共有m个维度的资源，比如cpu，mem，disk等等，第i个资源用资源r_i来表述，则数据中心的资源R=< r₁,r₂,r_i … r_m >
AP=< AP₁, AP₂…AP_N > :AP_j：假设任务中共有n个应用任务，每个任务记为AP_j。
w_j：任务j对资源的需求，比如任务j对资源i的需求记为w_ij，则w_j= < w_1j, w_2j, w_ij … w_mj >
u_j：任务AP_j的个数。即有多少个待调度的AP_j任务。
A=< x₁, x₂ … x_n >：一种调度策略，调度了x_j的AP_j的任务。

有了上面几个