指派作業
透過集合功能整理內容
你可以依據偏好儲存及分類內容。
指派問題是最著名的組合最佳化問題之一。舉例說明：假設一組工作站需要執行一組工作，每個工作站和工作都需要付費給該工作站。問題是將每個工作站指派至最多一項工作，但不要有兩個工作站執行相同的工作，同時將總費用降到最低。
您可以按照以下圖表視覺化呈現這個問題，其中有四個工作站和四個工作。邊緣代表了將工作站指派給工作的所有可能方式。邊緣上的標籤是將工作站指派給工作的費用。
指派會與邊緣部分相對應，其中每個工作站都位於最遠的邊緣，且沒有兩個工作站有邊緣可連至同一工作。下方顯示 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 (世界標準時間)。"],[[["\u003cp\u003eThe 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.\u003c/p\u003e\n"],["\u003cp\u003eThis problem can be visualized using a graph where edges represent worker-task assignments and edge labels represent the cost of each assignment.\u003c/p\u003e\n"],["\u003cp\u003eOR-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.\u003c/p\u003e\n"]]],["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"],null,["# Assignment\n\nOne of the most well-known combinatorial optimization problems is the\n[*assignment problem*](https://en.wikipedia.org/wiki/Assignment_problem). Here's an example: suppose a group of workers needs to perform a set of tasks, and for\neach worker and task, there is a cost for assigning the worker to the task.\nThe problem is to assign each worker to at most one task, with no two workers\nperforming the same task, while minimizing the total cost.\n\nYou can visualize this problem by the graph below, in which there are four\nworkers and four tasks. The edges represent all possible ways to assign workers\nto tasks. The labels on the edges are the costs of assigning workers to tasks.\n\nAn assignment corresponds to a subset of the edges, in which each worker has at\nmost one edge leading out, and no two workers have edges leading to the same\ntask. One possible assignment is shown below.\n\nThe total cost of the assignment is `70 + 55 + 95 + 45 = 265`.\n\nThe [next section](/optimization/assignment/assignment_example) shows how solve\nan assignment problem, using both the MIP solver and the CP-SAT solver.\n\n### Other tools for solving assignment problems\n\nOR-Tools also provides a couple of other tools for solving assignment problems,\nwhich can be faster than the MIP or CP solvers:\n\n- [Linear sum assignment solver](/optimization/assignment/linear_assignment)\n- [Minimum cost flow solver](/optimization/flow/assignment_min_cost_flow)\n\nHowever, these tools can only solve simple types of assignment problems.\nSo for general solvers that can handle a wide variety of problems (and are fast\nenough for most applications), we recommend the MIP and CP-SAT solvers."]]
