機器調度問題

Question

我有一個組合問題，因此：

給你N個測試人員。

每臺測試儀是M種不同類型之一。

每臺測試儀都可以配置爲使用P個不同配置中的一個。 。

您爲L許多產品進行測試，

每個產品只能在特定測試儀類型測試，

每個產品只能由測試儀來測試被配置爲與特定CONFIGS。一些配置可以應用於多種產品。 任何測試人員都可以在生產過程中更改其配置，但在測試儀配置中的每次更改都會產生額外的時間U。 每個批次都有很大的尺寸決定了它的測試時間，問：

現在我需要提出很多調度算法，以便完成所有批次測試的時間最短。

解決這類問題的最佳方法是什麼？

Answer 1

它可以模擬成一個Job-Shop問題（JSP）與安裝時間在那裏作業大小爲1。不幸的是它會很難找到一個最佳的時候作業數> 10

有很多免費包含Job-Shop的求解器實現作爲示例問題： 如果您使用的是C++，Gecode是很好的。如果您可以自由選擇，ECLiPSe Prolog包含JSP的源代碼。

如果你可以用一個良好解決方案（而不是一個最優），我建議使用一個貪婪算法（對於JSP，貪心算法給出通常在最佳的10％的溶液做的 - 我有一些經驗這個）。我會考慮一個並回到這裏（問題是所謂的「安裝時間限制」，即來自更改測試儀配置的限制）。