خوارزمية الجدول الزمني للمعلم
https://stackoverflow.com/questions/210635
-
03-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russianسؤال
هذه مشكلة كانت تدور في ذهني منذ فترة طويلة.كوني ابنًا لمعلم ومبرمج، خطر لي ذلك في وقت مبكر...لكني مازلت لم أجد حلاً لها.
إذن هذه هي المشكلة.يحتاج المرء إلى إنشاء جدول زمني للمدرسة، وذلك باستخدام بعض القيود.وتنقسم هذه بشكل عام إلى فئتين:
الشيكات الصحية
- لا يستطيع المعلم تدريس فصلين في نفس الوقت
- لا يجوز للطالب متابعة درسين في نفس الوقت
- يجب أن يحصل بعض المعلمين على يوم إجازة واحد على الأقل خلال الأسبوع
- يجب تغطية جميع أيام الأسبوع بالجدول الزمني
- يجب أن يكون للموضوع X ساعات محددة بالضبط كل أسبوع
- ...
التفضيلات
- يجب أن يكون جدول كل معلم مضغوطًا قدر الإمكان (أي:يجب أن يعمل المعلم طوال ساعات اليوم على التوالي دون توقف إن أمكن)
- يجب أن يكون المعلمون الذين لديهم أيام عطلة قادرين على التعبير عن تفضيلاتهم في أي يوم
- يجب أن يكون المعلمون الذين يعملون بدوام جزئي قادرين على التعبير عن تفضيلهم للعمل في بداية اليوم الدراسي أو نهايته.
- ...
الآن، بعد بضع سنوات من عدم العثور على حل (وتعلم شيء أو اثنين في هذه الأثناء...)، أدركت أن هذه تنبعث منها رائحة مشكلة NP-hard.
هل ثبت أنه NP-hard؟
هل لدى أي شخص فكرة عن كيفية كسر هذا الشيء؟
انظر الى هذا السؤال جعلني أفكر في هذه المشكلة، وما إذا كانت الخوارزميات الجينية ستكون قابلة للاستخدام في هذه الحالة.ومع ذلك، سيكون من الصعب جدًا تغيير الاحتمالات مع الحفاظ على قواعد التحقق من السلامة.كما أنه ليس من الواضح بالنسبة لي كيفية التمييز بين المتطلبات غير المتوافقة.
إضافة صغيرة لتحديد المشكلة بشكل أفضل.ينطبق هذا على الفصول الدراسية ذات نمط المدرسة الإيطالية حيث يرتبط جميع الطلاب بفصول مختلفة (على سبيل المثال:السنة الأولى القسم أ) ويتنقل المعلمون بين الفصول.جميع الطلاب من نفس الفصل لديهم نفس الجدول الزمني، وليس لديهم خيار بشأن الدروس التي سيحضرونها.
المحلول
أنا أحد المطورين الذين يعملون على جزء الجدولة من نظام معلومات الطلاب.خلال نهجنا الأصلي في مشكلة الجدولة، قمنا بالبحث في الخوارزميات الجينية لحل مشاكل رضا القيد، وعلى الرغم من نجاحنا في البداية، فقد أدركنا أن هناك حلًا أقل تعقيدًا للمشكلة (بعد حضور ورشة عمل الجدولة المدرسية)
يعمل تنفيذنا الحالي بشكل رائع، ويستخدم القوة الغاشمة مع الاستدلالات الذكية للحصول على جدول زمني صالح في فترة زمنية قصيرة.يتم أولاً إنشاء الجدول الرئيسي (تخصيص الفصول الدراسية للمعلمين)، مع الأخذ في الاعتبار جميع القيود التي يواجهها كل معلم مع تقليل احتمالية حدوث تعارضات بين الطلاب (بناءً على طلبات المقرر الدراسي الخاصة بهم).ثم يتم جدولة الطلاب في الفصول الدراسية باستخدام نفس الطريقة.
يتيح لك القيام بذلك جعل الجهاز ينشئ جدولًا رئيسيًا أولاً، ثم يقوم الإنسان بتعديله إذا لزم الأمر.
التنفيذ الحالي للمجدول مكتوب بلغة Perl، ولكن الخيارات الأخرى التي قمنا بزيارتها في وقت مبكر كانت Prolog وCLIPS (نظام خبير)
نصائح أخرى
هذه مشكلة رسم الخرائط:تحتاج إلى تعيين كل ساعة في الأسبوع ولكل معلم نشاطًا (التدريس لفصل معين أو ساعة مجانية).
تقسيم المشكلة:
- أنشئ قائمة بالمعلمين والفصول والتفضيلات، ثم اسمح للمستخدم بملء بعض التفضيلات على الخريطة ليكون بمثابة نقطة بداية.
- خذ بشكل عشوائي عنصرًا واحدًا من القائمة ووضعه في موضع خالي عشوائي على الخريطة إذا لم يعبر أي شيكات عقلانية حتى تصبح القائمة فارغة.إذا لم تتمكن في أي تكرار معين من وضع عنصر على الخريطة دون اجتياز فحص السلامة، فقم بتغيير موقعين على الخريطة وحاول مرة أخرى.
- عندما تمتلئ الخريطة، حاول تغيير المواضع على الخريطة لتحسين النتيجة.
في الخطوتين 2 و3، اعرض كل تكرار للمستخدم:العناصر المتبقية في القائمة، والمواضع على الخريطة، والحركة المحسوبة التالية، والسماح للمستخدم بالتدخل.
لم أحاول ذلك، ولكن هذا سيكون نهجي الأولي.
لقد عالجت مشكلات تخطيط/جدولة مماثلة في الماضي، وتقنية الذكاء الاصطناعي التي غالبًا ما تكون مناسبة لهذه الفئة من المشكلات هي "الاستدلال القائم على القيود".
إنها في الأساس طريقة القوة الغاشمة مثلما اقترح لورينتي، لكن النهج يتضمن تطبيق القيود بترتيب فعال للتسبب في فشل الحلول غير الممكنة بسرعة - لتقليل العمليات الحسابية المطلوبة.
يعرض البحث في Google "الاستدلال القائم على القيد" الكثير من الموارد حول التقنية وتطبيقها على مشكلات الجدولة.
الإجابة على سؤالي الخاص:
يستخدم مشروع FET الذي ذكره gnud هذه الخوارزمية:
بعض الكلمات عن الخوارزمية:فيت يستخدم خوارزمية إرشادية ، ووضع الأنشطة بدورها ، بدءا من أصعبها.إذا لم تستطع ابحث عن حل يوجهك إلى الأنشطة المستحيلة المحتملة ، لذلك يمكنك تصحيح الأخطاء.الخوارزمية أنشطة المقايضة بشكل متكرر إذا كان ذلك ممكن من أجل إفساح المجال ل نشاط جديد ، أو ، في الحالات القصوى ، ترتيب التراجعات والمفاتيح تقييم.الكود المهم موجود في SRC / المحرك / توليد .cpp.يرجى إرسال بريد إلكتروني لي للحصول على التفاصيل أو الانضمام إلى البريد قائمة.تحاكي الخوارزمية تشغيل جدول زمني بشري ، أنا فكر.
قادتني متابعة "الاستدلال القائم على القيد" الذي تقوده شركة Stringent Software على ويكيبيديا هؤلاء الصفحات التي تحتوي على فقرة مثيرة للاهتمام:
حل القيد الرضا المشكلة في مجال محدود هي NP-مشكلة كاملة بشكل عام.أظهرت الأبحاث عددا من الحالات الفرعية متعددة الحدود ، معظمها تم الحصول عليها عن طريق تقييد إما المجالات أو القيود المسموح بها أو الطريقة التي يمكن بها وضع القيود على المتغيرات.وقد البحوث أيضا العلاقة الراسخة بين مشكلة رضا القيد مع مشاكل في مجالات أخرى مثل المحدودة نظرية النموذج وقواعد البيانات.
هذا يذكرني بهذا مشاركة مدونة حول جدولة مؤتمر, ، مع شرح بالفيديو هنا.
كيف سأفعل ذلك:
هل يشمل السكان شيئين:
- من يقوم بالتدريس في أي صف (أتوقع أن يقوم المعلمون بتدريس مادة واحدة).
- ما يأخذه الفصل في فترة زمنية محددة.
بهذه الطريقة لا يمكن أن يكون لدينا صراعات (مدرس في مكانين، أو فصل يحتوي على مادتين في نفس الوقت).
ستشمل وظيفة اللياقة البدنية ما يلي:
- كم عدد الفترات الزمنية التي يمنحها كل معلم في الأسبوع.
- كم عدد الفترات الزمنية المتاحة للمعلم في نفس اليوم (لا يمكن أن يكون لديهم يوم كامل للتدريس، يجب أن يكون هذا أيضًا متوازنًا).
- كم عدد الفترات الزمنية لنفس الموضوع في الفصل الدراسي في نفس اليوم (لا يمكنهم قضاء يوم كامل في الرياضيات!).
ربما خذ الانحراف المعياري لهم جميعًا حيث يجب أن يكونوا متوازنين.
لست متأكدًا مما إذا كان هذا يغطي نفس الأرضية @ البرامج الصارمة أجب (لأن الاسم مختلف قليلاً)، ولكن لديّ صديقان جيدان جدًا يقومان بالبحث في مجال برمجة القيد.يعد إنشاء الجداول الزمنية أحد تطبيقات أبحاثهم.
الدكتور كريس جيفرسون أنشأت برنامجا يسمى تابع التي يمكنك تنزيلها من SourceForge، وهي أداة سريعة جدًا لحل مشكلات قيود القوة الغاشمة مكتوبة بلغة C++
أعتقد أنك قد تفتقد بعض القيود.
قد يفضل المرء، حيثما أمكن ذلك، تعيين معلمين في الفصول الدراسية التي تم اعتمادهم فيها.
قد يشك المرء في أن الفئات المطلوبة وعدد الموظفين المتوقع في كل منها سيكون كبيرًا.
أعتقد أن المكان المناسب للبدء هو إدراج جميع القيود الخاصة بك، ومعرفة بنية البيانات لتمثيلها.
ثم قم بإنشاء نوع من المحركات لبناء حل تجريبي، ثم تقييمه من حيث ملاءمته وفقًا للقيود.
يمكنك بعد ذلك إلقاء جزء من الخوارزميات الجينية الممتعة عليها، ومعرفة ما إذا كان بإمكانك زيادة اللياقة البدنية بمرور الوقت مع اختلاط الجينات.
ابدأ بمجموعة صغيرة من القيود، وزدها كلما رأيت النجاح (إذا رأيت النجاح)
قد تكون هناك طريقة لأخذ القيود وربطها معًا بشيء مثل خوارزمية البرمجة الخطية.
أنا موافق.يبدو وكأنه تحدي ممتع
واحدة من أسوأ صفحات الويب مفتوحة المصدر على الإطلاق، لكن المشروع يبدو واعدًا:http://www.lalescu.ro/liviu/fet/
النهج القائم على الويب:
phpScheduleIt (ليس خاص بالمدرسة)
النظر إلى هذا السؤال جعلني أفكر حول هذه المشكلة ، وما إذا كان ستكون الخوارزميات الجينية قابلة للاستخدام في هذه الحالة.ومع ذلك سيكون جميلا من الصعب تحور الاحتمالات أثناء الحفاظ على قواعد فحص العقل.كما أنه ليس من الواضح بالنسبة لي كيف تمييز المتطلبات غير المتوافقة.
الخوارزميات الجينية مناسبة تمامًا لمشاكل مثل هذه.بمجرد التوصل إلى تمثيل لائق للكروموسوم (في هذه الحالة، ربما يكون ناقلًا يمثل جميع فتحات الفئة المتاحة) تكون قد قطعت معظم الطريق للوصول إلى هناك.
لا تقلق بشأن الحفاظ على فحوصات السلامة أثناء مرحلة الطفرة.الطفرة عشوائية.ينتمي كل من التحقق من الصحة والتفضيل إلى مرحلة الاختيار.من شأن فشل فحص السلامة العقلية أن يقلل بشكل كبير من لياقة الفرد، في حين أن التفضيل الفاشل لن يؤدي إلا إلى انخفاض طفيف في اللياقة البدنية.
المتطلبات غير المتوافقة هي مشكلة مختلفة تمامًا.إذا كانت غير متوافقة تمامًا، فستحصل على سكان لا يتقاربون على أي شيء مفيد.
حظ سعيد.كوني ابن لأب يعاني من هذا النوع من المشاكل هو ما أخذني إلى مجموعة البحث التي انتهى بي الأمر فيها ...
عندما كنت طفلاً، قام والدي بتعيين حكام مباريات في دوري رياضي محلي، وكان هذا يحتوي على قائمة طويلة مماثلة من القيود وحاولت أن أكتب شيئًا للمساعدة.عندما وصلت إلى الجامعة، استخدمته كمشروع في سنتي النهائية واستقرت في النهاية على تنفيذ مونت كارلو (باستخدام نموذج التلدين المحاكى).
الفكرة الأساسية هي أنه إذا لم يكن NP، فهو قريب جدًا، لذا بدلاً من افتراض وجود حل، سأبدأ في العثور على الأفضل خلال إطار زمني محدد.أود أن أزن كل القيود مع تكاليف كسرها:سيكون لفحوصات السلامة تكاليف باهظة، وستكون للتفضيلات تكاليف أقل (ولكنها تزداد لمزيد من فترات الراحة، لذا فإن كسرها مرة واحدة سيكون أقل من نصف تكلفة كسرها مرتين).
الفكرة الأساسية هي أنني بدأت بحل "عشوائي" وحددت تكلفته؛ثم قاموا بإجراء تغييرات عن طريق تبديل عدد صغير من المهام، وإعادة تقييمها، ثم قبول التغيير أو رفضه بشكل احتمالي.
بعد آلاف التكرارات، أصبحت أقرب إلى الحل المقبول.
صدقني، مع ذلك، أن هذا النوع من المشاكل لديه مجموعات بحثية تنتج شهادات الدكتوراه، لذا فأنت في صحبة جيدة جدًا.
قد تجد أيضًا بعض الاهتمام في مجال البرمجة الخطية، على سبيل المثال. بسيط وما إلى ذلك وهلم جرا.
نعم، أعتقد أن هذا هو NP كامل - أو على الأقل للعثور على الحل الأمثل هو NP كامل.
لقد عملت على مشكلة مماثلة في الكلية عندما أخبرت والد أحد الأصدقاء (الذي كان مدرسًا) أنني أستطيع حل مشاكل الجدولة الخاصة به إذا لم يجد برنامجًا مناسبًا لها (كان هذا في عام 1990 أو نحو ذلك)
لم يكن لدي أي فكرة عما أقحمت نفسي فيه.ولحسن الحظ بالنسبة لنا، كل ما كان علي فعله هو إيجاد حل واحد يناسب القيود.لكن في الاختبار الذي أجريته كنت دائمًا قلقًا بشأن تحديد ما إذا كان هناك حل على الإطلاق.لم يكن لديه الكثير من القيود مطلقًا واستخدم البرنامج أساليب استدلالية مختلفة وتتبعًا خلفيًا.كان الكثير من المرح.
أعتقد أن بيل جيتس عمل أيضًا على نظام مثل هذا في المدرسة الثانوية أو الكلية لمدرسته الثانوية.لست متأكدا بالرغم من ذلك.
حظ سعيد.لقد اختفت جميع ملاحظاتي ولم أتمكن مطلقًا من تنفيذ حل يمكنني تسويقه.لقد كان مشروعًا متخصصًا قمت بإعادة برمجته عندما تعلمت لغات جديدة (Basic، Scheme، C، VB، C++)
استمتع بها
أرى أن هذه المشكلة يمكن حلها بواسطة برنامج Prolog عن طريق توصيلها بقاعدة بيانات ويمكن للبرنامج أن يجعل الجدول الزمني نظرًا لمجموعة من القيود التي تقرأ "ABT"
