指派作業
指派問題是最著名的組合最佳化問題之一。舉例說明:假設一組工作站需要執行一組工作,每個工作站和工作都需要付費給該工作站。問題是將每個工作站指派至最多一項工作,但不要有兩個工作站執行相同的工作,同時將總費用降到最低。
您可以按照以下圖表視覺化呈現這個問題,其中有四個工作站和四個工作。邊緣代表了將工作站指派給工作的所有可能方式。邊緣上的標籤是將工作站指派給工作的費用。

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

指派項目的總費用為 70 + 55 + 95 + 45 = 265
。
下一節說明如何使用 MIP 解析器和 CP-SAT 解析工具解決作業問題。
OR-Tools 也提供幾種其他工具來解決作業問題,速度可能比 MIP 或 CP 解題工具更快:
不過,這些工具只能解決簡單的作業問題類型。
因此,對於可處理各種問題的一般解題工具,對大多數應用程式來說都非常快,我們建議使用 MIP 和 CP-SAT 解析工具。
除非另有註明,否則本頁面中的內容是採用創用 CC 姓名標示 4.0 授權,程式碼範例則為阿帕契 2.0 授權。詳情請參閱《Google Developers 網站政策》。Java 是 Oracle 和/或其關聯企業的註冊商標。
上次更新時間:2024-08-09 (世界標準時間)。
[null,null,["上次更新時間:2024-08-09 (世界標準時間)。"],[[["The assignment problem focuses on optimally assigning workers to tasks to minimize the total cost, where each worker is assigned at most one task and no task is assigned to multiple workers."],["This problem can be visualized using a graph where edges represent worker-task assignments and edge labels represent the cost of each assignment."],["OR-Tools offers various solvers like MIP, CP-SAT, Linear Sum Assignment, and Minimum Cost Flow, but MIP and CP-SAT are recommended for their versatility and efficiency in handling a broader range of assignment problems."]]],["The content describes the assignment problem, a combinatorial optimization challenge where workers are assigned to tasks to minimize total cost. Each worker is assigned to at most one task, and each task is done by at most one worker. The example shows how the problem can be represented graphically, with edges representing possible assignments and their costs. The total cost is calculated by adding up the costs of the assigned edges. OR-Tools offer multiple tools to solve such problems, among which the MIP and CP-SAT are the most general.\n"]]