寻求实现均匀负载分配并最小化重平衡的知名算法

你的场景属于动态负载均衡+最小迁移重平衡的经典问题，已有多个经过验证的成熟算法，无需自行从零实现：

一、初始分配算法 #

• 最佳适应递减（Best Fit Decreasing, BFD）：将所有进程按资源占用量从大到小排序，依次把进程分配到剩余容量最接近进程需求的服务器。该算法在装箱问题（你的场景可归类为动态可变装箱）中有严格的理论证明，能保证初始分配的负载失衡率控制在较低范围，完全符合你给出的初始分配示例需求。

二、动态重平衡算法 #

当失衡率超过阈值时，可选择以下算法实现最小迁移的负载均衡：

• 贪心局部重平衡算法：仅针对负载超出上限（平均负载×失衡阈值）和低于下限（平均负载÷失衡阈值）的服务器组操作。从高负载服务器中挑选能让目标低负载服务器负载最接近平均水平的进程迁移，优先选择小资源占用的进程（灵活性更高）。每次迁移都会严格降低整体失衡率，且能证明不会因算法本身导致进程反复迁移——只有外部进程变化（增删、资源占用调整）才会触发下一次重平衡。
• 稳定匹配重平衡算法：基于稳定婚姻问题的思路，让进程和服务器双向匹配：进程优先选择能让自身所在服务器负载更均衡的目标，服务器优先接收能填补自身负载缺口的进程。最终的分配状态是帕累托最优的，即不存在任何进程迁移能进一步优化均衡性，因此不会出现短时间内需要再次迁移同一进程的情况。
• 阈值触发的增量重平衡：这是云原生调度的常用方案，不做全局重新分配，只针对失衡的服务器对进行调整，每次只解决当前最严重的失衡点，最小化迁移开销，完全适配你每小时检查触发的模式。

三、日常新进程分配策略 #

你提到的“非重平衡期间新进程分配至负载最低服务器”属于贪心最小负载分配，这是行业通用的日常维持策略，能有效减少重平衡的触发频率，无需额外调整。

正确性证明相关 #

• 贪心重平衡的核心逻辑是每次迁移都严格降低整体失衡度，因此不会出现算法导致的循环迁移；
• 稳定匹配的结果是稳定状态，不存在任何进程-服务器对有动机触发再次迁移，从根源避免了反复调整。

内容的提问来源于stack exchange，提问作者dhythhsba