algorithm - 一维装箱问题的 MBS 算法（最小 bin slack）

Question

我正在努力解决一维装箱问题，作为初始种群，我将从 MBS 的生成器粒子开始。我在网上寻找 MBS （最小 bin slack）算法，但找不到。请问有人可以帮我吗？

Answer 1

MBS' 是基于以下步骤的 MBS（Minimum Bin Slack ）启发式的改进：

• 在每个步骤中，都会尝试找到一组尽可能适合垃圾箱容量的物品（包装）。
• 从这个意义上说，MBS 类似于解决装配线平衡问题的霍夫曼算法。
• 在每个阶段，保留到目前为止未分配给箱的 n' 个项目的列表 I'，按大小的降序排序。
• 每次确定包装时，所涉及的项目都会被放入一个箱中并从 I' 中取出，并保留排序顺序。
• 该过程以 I'= I 开始，并在列表 I' 为空时结束。
• 每个包装都是在一个搜索过程中确定的，该过程测试列表 I' 上所有可能的项目子集，这些子集最大程度地适合 bin 的容量。
• 采用留下最小松弛的子集；如果算法找到一个完全填满箱子的子集，则停止搜索，并且在这种状态下没有更好的打包可能。
• 搜索从更大尺寸的物品开始，即从 I' 的开头，因为尺寸相对较大的物品通常更难装入垃圾箱，因此，应该首先尝试包装它们。

【MBS算法】 http://i.stack.imgur.com/jUltR.png

MBS'：

• 它与 MBS 相同，只是它使用了加速算法的初始化过程。
• 建议对 MBS 进行以下修改：在调用单包装搜索过程之前，选择一个项目（种子）并将其永久固定在包装中。
• 这是可以做到的，因为无论如何，每件物品都必须放在垃圾箱中。
• 种子的一个好的选择是最大尺寸的项目，即列表 Z' 上的第一个项目。
• 这将在搜索过程中在 bin 中留下最少的空间来填充，从而缩短处理时间。
• 此外，求解过程将被迫首先使用更大、更麻烦的项目。