指派作業

指派問題是最著名的組合最佳化問題之一。舉例說明：假設一組工作站需要執行一組工作，每個工作站和工作都需要付費給該工作站。問題是將每個工作站指派至最多一項工作，但不要有兩個工作站執行相同的工作，同時將總費用降到最低。

您可以按照以下圖表視覺化呈現這個問題，其中有四個工作站和四個工作。邊緣代表了將工作站指派給工作的所有可能方式。邊緣上的標籤是將工作站指派給工作的費用。

指派會與邊緣部分相對應，其中每個工作站都位於最遠的邊緣，且沒有兩個工作站有邊緣可連至同一工作。下方顯示 1 項可能的指派作業。

指派項目的總費用為 70 + 55 + 95 + 45 = 265。

下一節說明如何使用 MIP 解析器和 CP-SAT 解析工具解決作業問題。

其他可用來解決作業問題的工具

OR-Tools 也提供幾種其他工具來解決作業問題，速度可能比 MIP 或 CP 解題工具更快：

• 線性總和解題工具
• 最低費用流程解析工具

不過，這些工具只能解決簡單的作業問題類型。 因此，對於可處理各種問題的一般解題工具，對大多數應用程式來說都非常快，我們建議使用 MIP 和 CP-SAT 解析工具。