带机器合并的任务分配算法优化：最小化CPU总耗时

我需要设计一种算法，将已知RAM需求的任务集分配给已知RAM容量的机器集，仅能将任务分配给满足其RAM需求的机器。

为机器分配任务时会预留部分RAM，例如100 RAM的机器可运行10个10 RAM的任务，或1个50 RAM加2个25 RAM的任务。

可合并机器以获取更大RAM，但不可拆分机器。关键限制：分配给一台机器的任务越多，其完成所有任务的时间呈二次增长。任务需初始一次性分配，无法中途转移，且同时启动执行。

经调研发现该问题与装箱问题、箱覆盖问题类似，但本问题支持机器合并。

• 设机器集M包含n台机器m，每台机器RAM为r：M={r₁m₁, r₂m₂, ... , rₙmₙ}
• 任务集T包含k个任务t，每个任务RAM需求为x：T = {x₁t₁, x₂t₂, ... , xₖtₖ}
• 任务总RAM需求不超过机器总RAM，可相等或更小。
• 任务分配后，机器剩余RAM为r-x，可用于后续分配。
• 单台机器RAM不足时，可多台合并，合并后RAM为各机器RAM之和，支持合并所有机器。
• 单任务单机器执行耗时1单位CPU时间；2任务并行耗时4单位，3任务耗时9单位，n任务并行耗时n²单位。

• 机器不可拆分为更小RAM的子机器，仅可合并或拆分合并状态。
• 任务需初始一次性分配，不可中途转移，同一机器上的任务需并行执行。
• 所有任务分配完成后才启动执行，无法通过串行分配规避二次耗时问题。

设计机器配置（合并或不合并）并分配所有任务，优先级如下：

1. 最小化总CPU耗时（可视为仅一台机器同时运行）；
2. 尽可能减少机器合并次数。

通过具体示例说明：

1. 最差算法：合并所有机器并分配全部任务 #

合并所有机器为m₁m₂m₃，RAM=92+56+15=163，分配全部5个任务，总耗时5²=25单位CPU时间。

结果：25单位CPU时间 👎 #

2. 自研最优算法：大任务匹配大机器 #

1. 将机器集M与任务集T按RAM值降序排序：
   
2. 取T最大任务，检查是否可分配给M最大机器；若不可，合并多台机器直至满足RAM需求。
3. 分配任务后机器剩余RAM更新，将机器-任务元组加入Mₙ集合（n为该机器分配的任务数），保持集合降序排序。
4. 优先从无任务的M₀集合找匹配机器，尝试合并组合；再依次尝试M₁等集合的组合。

执行结果：

形成任务分配森林：

m₂上2个任务耗时2²=4，m₁m₃上3个任务耗时3²=9，总耗时=4+9=13单位CPU时间。

结果：13单位CPU时间（较最差算法提升近一倍）💪 #

寻求更优算法方案？

内容的提问来源于stack exchange，提问作者Pt. Terk