MBS'一維箱包裝標誌（最小箱鬆弛）的算法

Question

我正致力於解決1D箱包裝問題，並且作爲初始人羣，我將開始使用MBS的發生器顆粒。 我在網上查找MBS'（最小bin slack）算法，但找不到它。 請有人可以幫我嗎？

Answer 1

的MBS」是MBS的改善（最小的二進制懈怠），其是基於以下步驟啓發式：

• 在每一步，一個試圖ND科幻一組項目（包裝），儘可能符合垃圾箱容量。
• 從這個意義上講，MBS與Ho ff mann的解決裝配線平衡問題的算法很相似。
• 在每個階段，保留未分配到目前爲止的n個物品的清單I'，按照大小的降序排序。
• 每次確定包裝時，涉及的物品都放在一個箱子中，並從I'中移除，保留排序順序。
• 該過程以I'= I開始，當列表I'變空時結束。
• 每個包裝都是在一個搜索過程中確定的，該過程測試列表I'上所有可能的子項目，這些子項目最大限度地滿足箱子的容量。
• 採用最小松弛的子集;如果算法找到一個完全填滿垃圾箱的子集，搜索就會停止，並且在這種狀態下沒有更好的包裝。
• 搜索從較大尺寸的項目開始，即從I'開始，因爲相對較大尺寸的物品通常更難以包裝在垃圾箱中，因此應該首先嚐試打包它們。

[MBS算法] http://i.stack.imgur.com/jUltR.png

MBS」：

• 這是相同的MBS不同之處在於它使用加快算法的初始化過程。
• 提出了對MBS的以下修改：在調用單包裝搜索過程之前，選擇一個項目（種子）並永久固定在包裝中。
• 可以這樣做，因爲每件物品都必須放在箱子裏。
• 種子的好選擇是最大尺寸的項目，即列表Z'上的第一個。
• 這樣會在搜索過程中留出垃圾箱中最小的空間，從而縮短處理時間。
• 此外，解決過程將被迫使用更大的，因此更多的麻煩，首先項目。