DCOS群集资源分配非常困难 [英] DCOS cluster resource allocation is np-hard

问题描述

在 DCOS 文档中进行了说明

决定在哪里运行进程以最佳利用群集资源是 困难，实际上是NP困难."

"Deciding where to run processes to best utilize cluster resources is hard, NP-hard in-fact."

我不否认这听起来是正确的，但是在某处有证据吗?

I don't deny that that sounds right, but is there a proof somewhere?

推荐答案

资源的最佳利用是容器包装问题:

在垃圾箱包装问题中，必须将不同体积的物体放在 包装到一定数量的箱子或容器中，每个箱子或容器的体积为V 一种减少使用的垃圾箱数量的方法.在计算中 复杂性理论，这是一个组合的NP难题.决定 问题(确定对象是否适合指定数量的垃圾箱) 是NP完整的.

In the bin packing problem, objects of different volumes must be packed into a finite number of bins or containers each of volume V in a way that minimizes the number of bins used. In computational complexity theory, it is a combinatorial NP-hard problem. The decision problem (deciding if objects will fit into a specified number of bins) is NP-complete.

我们有n维空间，其中每个维度都对应一种资源类型.每个要计划的任务都有由所需资源定义的特定数量.另外，任务可以具有稍微改变原始任务的约束，但是我们可以将此约束视为附加的离散维度.任务是按照最大程度地减少松弛资源并防止碎片的方式安排任务.

We have n-dimension space where every dimension corresponds with one resource type. Each task to be scheduled has specific volume defined by required resources. Additionally task can have constraints that slightly change original task but we can treat this constraints as an additional discrete dimension. The task is to schedule tasks in a way to minimize slack resources and so prevent fragmentation.

例如 Marathon 使用的是第一拟合算法，该算法近似于Allogrithm，但还算不错:

For example Marathon uses first fit algorithm which is approximation allogrithm but is not that bad:

这是一个非常简单的贪婪近似算法.该算法以任意顺序处理项目.对于每个项目，它都会尝试将项目放置在可以容纳该项目的第一个箱柜中.如果未找到垃圾箱，它将打开一个新垃圾箱，并将该物品放入新垃圾箱中.

This is a very straightforward greedy approximation algorithm. The algorithm processes the items in arbitrary order. For each item, it attempts to place the item in the first bin that can accommodate the item. If no bin is found, it opens a new bin and puts the item within the new bin.

很容易证明该算法达到的近似因子为2，即该算法使用的bin数量不超过最佳bin数量的两倍.

It is rather simple to show this algorithm achieves an approximation factor of 2, that is, the number of bins used by this algorithm is no more than twice the optimal number of bins.

这篇关于DCOS群集资源分配非常困难的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！