تُعدّ مشكلة الإسناد من أكثر مشاكل التحسين التوافقي شهرة. إليك مثال: افترض أن مجموعة من العمال تحتاج إلى أداء مجموعة من المهام، وأن هناك تكلفة لكل عامل ومهمة مقابل تعيين العامل للمهمة. تكمن المشكلة في تكليف كل عامل بمهمة واحدة على الأكثر، مع عدم وجود موظفين يؤدون نفس المهمة، مع تقليل التكلفة الإجمالية.
يمكنك تصور هذه المشكلة من خلال الرسم البياني أدناه، حيث يوجد أربعة عمال وأربع مهام. تمثل الحواف جميع الطرق الممكنة لتعيين العاملين للمهام. التسميات الموجودة على الحواف هي تكاليف تعيين العمال للمهام.
تتجاوب المهمة مع مجموعة فرعية من الحواف، حيث يكون لكل عامل حافة واحدة تؤدي إليها على الأكثر، ولا يوجد عاملان لديهم حواف تؤدي إلى نفس المهمة. موضح أدناه مهمة واحدة محتملة.
التكلفة الإجمالية للمهمة هي 70 + 55 + 95 + 45 = 265.
يوضّح القسم التالي كيفية حلّ مسألة مهمة، وذلك باستخدام كل من أداة حلّ MIP وأداة حلّ CP-SAT.
أدوات أخرى لحل مشكلات المهام
توفر OR-Tools أيضًا بعض الأدوات الأخرى لحل مشكلات المهام، والتي يمكن أن تكون أسرع من أدوات حل MIP أو CP:
ومع ذلك، يمكن لهذه الأدوات حل أنواع بسيطة من مشكلات المهام الدراسية فقط. بالنسبة إلى أدوات الحلّ العامة التي يمكنها معالجة مجموعة كبيرة من المشاكل (وتكون سريعة بما يكفي لمعظم التطبيقات)، ننصح باستخدام أدوات حلّ MIP وCP-SAT.