التكليف
تُعدّ
مشكلة الإسناد من أكثر مشاكل التحسين التوافقي شهرة. إليك مثال: افترض أن مجموعة من العمال تحتاج إلى أداء مجموعة من المهام، وأن هناك تكلفة لكل عامل ومهمة مقابل تعيين العامل للمهمة.
تكمن المشكلة في تكليف كل عامل بمهمة واحدة على الأكثر، مع عدم وجود موظفين
يؤدون نفس المهمة، مع تقليل التكلفة الإجمالية.
يمكنك تصور هذه المشكلة من خلال الرسم البياني أدناه، حيث يوجد أربعة عمال وأربع مهام. تمثل الحواف جميع الطرق الممكنة لتعيين
العاملين للمهام. التسميات الموجودة على الحواف هي تكاليف تعيين العمال للمهام.
تتجاوب المهمة مع مجموعة فرعية من الحواف، حيث يكون لكل عامل حافة واحدة تؤدي إليها على الأكثر، ولا يوجد عاملان لديهم حواف تؤدي إلى نفس المهمة. موضح أدناه مهمة واحدة محتملة.
التكلفة الإجمالية للمهمة هي 70 + 55 + 95 + 45 = 265.
يوضّح القسم التالي كيفية حلّ مسألة مهمة، وذلك باستخدام كل من أداة حلّ MIP وأداة حلّ CP-SAT.
توفر OR-Tools أيضًا بعض الأدوات الأخرى لحل مشكلات المهام،
والتي يمكن أن تكون أسرع من أدوات حل MIP أو CP:
ومع ذلك، يمكن لهذه الأدوات حل أنواع بسيطة من مشكلات المهام الدراسية فقط.
بالنسبة إلى أدوات الحلّ العامة التي يمكنها معالجة مجموعة كبيرة من المشاكل (وتكون سريعة بما يكفي لمعظم التطبيقات)، ننصح باستخدام أدوات حلّ MIP وCP-SAT.
إنّ محتوى هذه الصفحة مرخّص بموجب ترخيص Creative Commons Attribution 4.0 ما لم يُنصّ على خلاف ذلك، ونماذج الرموز مرخّصة بموجب ترخيص Apache 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"]]
