ما هي الخوارزمية لتعيين التحولات (مشكلة التحسين المنفصلة)

Question

أقوم بتطوير تطبيق يقوم بتعيين الورديات على النحو الأمثل للممرضات في المستشفى.وأعتقد أن هذا هو البرمجة الخطية مشكلة مع المتغيرات المنفصلة، ​​وبالتالي ربما NP-hard:

• لكل يوم، لكل ممرضة (ca.15-20) يتم تعيين التحول
• هناك عدد صغير (ca.6) مناوبات مختلفة
• هناك عدد كبير من القيود ومعايير التحسين، سواء فيما يتعلق بيوم ما أو فيما يتعلق بالموظف، على سبيل المثال:
  • يجب أن يكون هناك حد أدنى لعدد الأشخاص المعينين لكل وردية كل يوم
  • تتداخل بعض الورديات بحيث يكون من المقبول أن يكون هناك شخص واحد أقل في الوردية المبكرة إذا كان هناك شخص يقوم بالمناوبة المتوسطة
  • يفضل بعض الأشخاص التحول المبكر، والبعض الآخر يفضل التحول المتأخر، ولكن يلزم إجراء حد أدنى من التغييرات في الورديات للحصول على أجر أعلى للعمل في الورديات.
  • لا يُسمح لشخص واحد بالعمل في نوبة متأخرة في يوم واحد وفي نوبة مبكرة في اليوم التالي (بسبب لوائح الحد الأدنى لوقت الراحة)
  • فترات أسبوع العمل المخصصة للاجتماع (تختلف باختلاف الأشخاص)
  • ...

لذا يوجد بشكل أساسي عدد كبير (20*30 = 600) من المتغيرات التي يمكن لكل منها أن يأخذ عددًا صغيرًا من القيم المنفصلة.

حاليًا، خطتي هي استخدام نسخة معدلة خوارزمية الحد الأدنى من الصراعات

• ابدأ بمهام عشوائية
• لديك وظيفة اللياقة البدنية لكل شخص وكل يوم
• حدد الشخص أو اليوم الذي لديه أسوأ قيمة للياقة البدنية
• حدد بشكل عشوائي إحدى المهام لذلك اليوم/الشخص وقم بتعيينها على القيمة التي تؤدي إلى قيمة اللياقة المثلى
• كرر حتى يتم الوصول إلى الحد الأقصى لعدد التكرارات أو لا يمكن العثور على أي تحسين لليوم/الشخص المحدد

أي أفكار أفضل؟أنا قلق إلى حد ما من أنها سوف تتعثر في المستوى الأمثل المحلي.هل يجب أن أستخدم شكلاً من أشكال محاكاة الصلب؟أو لا تفكر فقط في التغييرات في متغير واحد في كل مرة، بل على وجه التحديد تبديل التحولات بين شخصين (المكون الرئيسي في الخوارزمية اليدوية الحالية)؟أريد تجنب تصميم الخوارزمية وفقًا للقيود الحالية نظرًا لأن تلك القيود قد تتغير.

يحرر: ليس من الضروري إيجاد الحل الأمثل بدقة؛يتم إعداد القائمة يدويًا حاليًا، وأنا متأكد تمامًا من أن النتيجة أقل من المستوى الأمثل في معظم الأوقات - ولا ينبغي أن يكون من الصعب التغلب على ذلك.من المؤكد أن التعديلات والتجاوزات اليدوية على المدى القصير ستكون ضرورية أيضًا، لكنني لا أعتقد أن هذا سيكون مشكلة؛يجب أن يؤدي وضع علامة على المهام السابقة واليدوية على أنها "ثابتة" إلى تبسيط المهمة عن طريق تقليل مساحة الحل.

Answer 1

هذه مشكلة يصعب حلها بشكل جيد.هناك العديد من الأوراق الأكاديمية حول هذا الموضوع وخاصة في بحوث العمليات المجال - انظر على سبيل المثال أوراق قائمة الممرضات 2007-2008 أو فقط ابحث في Google عن "أبحاث عمليات قائمة الممرضات".يعتمد التعقيد أيضًا على جوانب مثل:كم يوما لحلها؟ما نوع "الطلبات" التي يمكن للممرضة تقديمها؟هي القائمة "دورية"؛هل هي خطة طويلة المدى أم أنها تحتاج إلى التعامل مع "إصلاح" القائمة قصيرة المدى مثل المرض والمقايضات وما إلى ذلك.

الخوارزمية التي تصفها هي إرشادي يقترب.قد تجد أنه يمكنك تعديله ليعمل بشكل جيد في حالة معينة من المشكلة، ولكن بمجرد تغيير "شيء ما"، فقد لا يعمل بشكل جيد (على سبيل المثال.الأمثل المحلي، ضعف التقارب).

ومع ذلك، قد يكون هذا النهج كافيًا وفقًا لاحتياجات عملك الخاصة - على سبيل المثال.ما مدى أهمية الحصول على أفضل الحل، هو أن مخطط المشكلة الذي تصفه من المتوقع أن يظل كما هو، وما هي المدخرات المحتملة (الأموال والموارد)، وما مدى أهمية إدراك الممرضة لجودة قوائمهم، وما هي الميزانية لهذا العمل وما إلى ذلك.

Answer 2

أم، هل تعلم أن بعض من يحلون ILP يقومون بعمل جيد جدًا؟جرب AIMMS أو Mathematica أو مجموعة أدوات البرمجة GNU!إن 600 متغير هو بالطبع أكثر بكثير مما يمكن لنظرية Lenstra حله بسهولة، ولكن في بعض الأحيان تتمتع أدوات حل ILP هذه بمقبض جيد وفي AIMMS، يمكنك تعديل استراتيجية التفرع قليلاً.بالإضافة إلى ذلك، هناك تقدير سريع جدًا بنسبة 100% لـ ILPs.

Answer 3

لقد قمت مؤخرًا بحل مشكلة تعيين الورديات لمصنع تصنيع كبير.حاولنا أولاً إنشاء جداول عشوائية بحتة وإرجاع أي جدول اجتاز is_schedule_valid اختبار - الخوارزمية الاحتياطية.وكان هذا، بطبيعة الحال، بطيئا وغير محدد.

بعد ذلك جربنا الخوارزميات الجينية (كما اقترحت)، لكننا لم نتمكن من العثور على وظيفة لياقة جيدة تغلق أي حل قابل للتطبيق (لأن أصغر تغيير يمكن أن يجعل الجدول بأكمله صحيحًا أو خاطئًا - لا توجد نقاط تقريبًا).

أخيرًا اخترنا الطريقة التالية (التي عملت بشكل رائع!):

1. قم بترتيب مجموعة الإدخال بطريقة عشوائية (أيالوظائف، المناوبة، الموظفين، الخ.).
2. أنشئ صفًا صالحًا وأضفه إلى جدولك المؤقت.
3. إذا لم يكن من الممكن إنشاء صف صالح، فقم بالتراجع (وزيادة) الصف الأخير الذي تمت إضافته.
4. قم بتمرير الجدول الجزئي إلى وظيفة تقوم بالاختبار could_schedule_be_valid, أي هل يمكن أن يكون هذا الجدول صالحًا إذا تم ملء الصفوف المتبقية بطريقة محتملة
5. لو !could_schedule_be_valid, ، ما عليك سوى التراجع (وزيادة) المجموعة المضافة في (2).
6. لو schedule_is_complete, return schedule
7. غوتو (2)

يمكنك بناء تحول جزئي تدريجيًا بهذه الطريقة.والفائدة هي أن بعض الاختبارات ذات الجدول الزمني الصحيح يمكن إجراؤها بسهولة في الخطوة 2 (الاختبارات المسبقة)، ويجب أن يبقى البعض الآخر في الخطوة 5 (الاختبارات اللاحقة).

حظ سعيد.لقد أهدرنا أيامًا في تجربة أول خوارزميتين، لكننا حصلنا على الخوارزمية الموصى بها والتي تولد جداول صالحة على الفور في أقل من 5 ساعات من التطوير.

كما دعمنا التثبيت المسبق واللاحق للمهام التي تحترمها الخوارزمية.أنت ببساطة لا تقوم بترتيب تلك الفتحات بشكل عشوائي في الخطوة 1.ستجد أن الحلول لا يجب أن تكون قريبة من المستوى الأمثل.الحل الذي نقدمه هو O(N*M) كحد أدنى ولكن يتم تنفيذه بلغة PHP(!) في أقل من نصف ثانية لمصنع التصنيع بأكمله.الجمال هو في استبعاد الجداول الزمنية السيئة بسرعة باستخدام الجيد could_schedule_be_valid امتحان.

الأشخاص الذين اعتادوا على القيام بذلك يدويًا لا يهتمون إذا استغرق الأمر ساعة - فهم يعلمون فقط أنه ليس عليهم القيام بذلك يدويًا بعد الآن.

Answer 4

مايك،

لا أعرف إذا كنت قد حصلت على إجابة جيدة لهذا السؤال، ولكنني متأكد تمامًا من أن البرمجة المقيدة هي التذكرة.في حين أن GA قد يمنحك إجابة، فإن CP مصمم ليمنحك العديد من الإجابات أو يخبرك إذا لم يكن هناك حل عملي.يجب أن يؤدي البحث عن "برمجة القيود" والجدولة إلى ظهور الكثير من المعلومات.إنها منطقة جديدة نسبيًا وأساليب الإنتاج الأنظف تعمل بشكل جيد في العديد من أنواع المشكلات التي تتعثر فيها طرق التحسين التقليدية.

Answer 5

البرمجة الديناميكية على غرار بيل؟يبدو أن هناك مكانًا لذلك:مشاكل فرعية متداخلة، هياكل أساسية مثالية.

Answer 6

شيء واحد يمكنك القيام به هو محاولة البحث عن التماثلات في المشكلة.على سبيل المثالهل يمكنك التعامل مع جميع الممرضات على قدم المساواة لأغراض المشكلة؟إذا كان الأمر كذلك، فأنت تحتاج فقط إلى النظر في الممرضات بترتيب تعسفي - يمكنك تجنب التفكير في حلول مثل أي ممرضة أنا ومن المقرر قبل أي ممرضة ي أين أنا > ي.(لقد قلت أن الممرضات الفرديات يفضلن أوقات المناوبة، وهو ما يتناقض مع هذا المثال، على الرغم من أن هذا ربما يكون هدفًا أقل أهمية؟)

Answer 7

أعتقد أنه يجب عليك استخدام الخوارزمية الجينية للأسباب التالية:

• هو الأنسب لحالات المشاكل الكبيرة.
• إنه يؤدي إلى تقليل التعقيد الزمني على سعر الإجابة غير الدقيقة (ليس الأفضل في نهاية المطاف)
• يمكنك تحديد القيود والتفضيلات بسهولة عن طريق ضبط عقوبات اللياقة البدنية لتلك التي لم يتم الوفاء بها.
• يمكنك تحديد الحد الزمني لتنفيذ البرنامج.

• تعتمد جودة الحل على مقدار الوقت الذي تنوي قضاءه في حل البرنامج..

  تعريف الخوارزميات الجينية

  دروس الخوارزميات الجينية

  مشروع جدولة الفصل مع GA

ألقِ نظرة أيضًا على:سؤال مماثل و واحدة أخرى

Answer 8

باستخدام برمجة CSP، قمت بإعداد برامج لإعداد قوائم Shitfs تلقائيًا.على سبيل المثال:

1. نظام 2 -DISTS - تم اختباره لـ 100+ ممرض ، و 30 يومًا الأفق الزمني ، 10+ قواعد
2. نظام ثلاثي المناوبات - تم اختباره لأكثر من 80 ممرضة، وأفق زمني 30 يومًا، وأكثر من 10 قواعد
3. نظام 3 نوبات، 4 فرق - تم اختباره لمدة 365 يومًا، أكثر من 10 قواعد،

واثنين من الأنظمة المماثلة.تم اختبارها جميعًا على جهاز الكمبيوتر المنزلي (ثنائي النواة بسرعة 1.8 جيجا هرتز).أوقات التنفيذ كانت دائما مقبولة أي.لمدة 3 / استغرق الأمر حوالي 5 دقائق وذاكرة الوصول العشوائي (RAM) سعة 300 ميجابايت.

كان الجزء الأصعب من هذه المشكلة هو اختيار الحل المناسب واستراتيجية الحل المناسبة.

Answer 9

ميتايورستكس لقد قام بعمل جيد جدًا في المسابقة الدولية لقائمة الممرضات 2010.

للتنفيذ، انظر هذا فيديو يتضمن قائمة ممرضة مستمرة (Java).