خوارزمية لإنشاء جدول زمني للمدرسة

StackOverflow https://stackoverflow.com/questions/2177836

  •  24-09-2019
  •  | 
  •  

سؤال

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

أعتقد أنه ربما لا توجد خوارزمية دقيقة لذلك ، ولكن ربما يعرف شخص ما تقريب جيد أو تلميحات لتطويره.

هل كانت مفيدة؟

المحلول

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

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

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

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

  • تحديد وترتيب كل القيود المعروفة
  • تقليل مساحة المشكلة ، من خلال توفير مجموعة من إضافي القيود.
    قد يبدو هذا غير بديهي ولكن على سبيل المثال من خلال توفير جدول أولي مملوء جزئيًا (على سبيل المثال ما يقرب من 30 ٪ من الزمنات الزمنية) ، بطريقة تفي بالكامل بجميع القيود ، وبالنظر إلى هذا الجدول الجزئي غير قابل للتغيير ، فإننا نقول بشكل كبير الوقت/المساحة اللازمة لإنتاج حلول المرشح.
    هناك طريقة أخرى للمساعدة الإضافية وهي على سبيل المثال "إضافة مصطنعة" لإضافة قيد يمنع تدريس بعض الموضوعات في بعض الأيام من الأسبوع (إذا كان هذا جدولًا أسبوعيًا ...) ؛ يؤدي هذا النوع من القيود إلى تقليل مساحات المشكلة/الحل ، دون ، عادةً ، باستثناء عدد كبير من المرشحين الجيدين.
  • التأكد من أن بعض قيود المشكلة يمكن حسابها بسرعة. غالبًا ما يرتبط هذا باختيار نموذج البيانات المستخدم لتمثيل المشكلة ؛ تتمثل الفكرة في أن تكون قادرًا على الاطلاع بسرعة على بعض الخيارات.
  • إعادة تعريف المشكلة والسماح ببعض القيود لكسر ، عدة مرات ، (عادة نحو العقد النهائية للرسم البياني). الفكرة هنا هي إما الإزالة بعض من قيود ملء الفتحات القليلة الأخيرة في الجدول ، أو للحصول على برنامج مولد الجدول التلقائي يتوقف عن إكمال الجدول الزمني بأكمله ، وبدلاً من ذلك ، فإن تزويدنا بقائمة من عشرات المرشحين المعقولين أو نحو ذلك. غالبًا ما يكون الإنسان في وضع أفضل لإكمال اللغز ، كما هو موضح ، من المحتمل أن يكسر بعض المواقف ، باستخدام المعلومات التي لا يتم مشاركتها عادةً مع المنطق الآلي (على سبيل المثال ، يمكن كسر قاعدة الرياضيات في فترة ما بعد الظهر " بالنسبة لفئة "الرياضيات والفيزياء المتقدمة" ؛ أو "من الأفضل كسر أحد متطلبات السيد جونز من واحد من MS Smith ...-))

في قراءة هذه الإجابة ، أدركت أنها خجولة تمامًا من توفير استجابة محددة ، لكنها أقل امتلاءًا للاقتراحات العملية. آمل أن تكون هذه المساعدة ، مع ما هو ، بعد كل شيء ، "مشكلة صعبة".

نصائح أخرى

هذه فوضى. فوضى ملكية. للإضافة إلى الإجابات ، كاملة جدًا بالفعل ، أريد أن أشير إلى تجربتي العائلية. كانت والدتي معلمة وكانت تشارك في هذه العملية.

تبين أن وجود جهاز كمبيوتر للقيام بذلك ليس من الصعب فقط الترميز لكل SE ، بل إنه أمر صعب أيضًا لأن هناك شروطًا يصعب تحديدها لبرنامج كمبيوتر مسبقًا. أمثلة:

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

كما ترون ، فإن المشكلة ليست NP-COMPLETE ، إنها np-insane.

إذن ما يفعلونه هو أن لديهم طاولة كبيرة مع إدراج بلاستيكية صغيرة ، وهم يحركون الأوعية حولها حتى يتم الحصول على نتيجة مرضية. إنهم لا يبدأون أبدًا من الصفر: يبدأون عادةً من الجدول الزمني للعام السابق وإجراء تعديلات.

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

ألقِ نظرة على أطر 2 مفتوحة المصدر المستخدمة من قبل بعض المتسابقين النهائيين:

  • JBOSS OPTAPLANNER (جافا ، المصدر المفتوح)
  • وحدة (جافا ، المصدر المفتوح) - المزيد للجامعات

كانت إحدى مهام بلدي نصف المدة هي توليد طاولة المدارس الوراثية.

الجدول بأكمله هو "كائن حي". كانت هناك بعض التغييرات والتحذيرات على نهج الخوارزميات الوراثية العامة:

  • تم وضع قواعد لـ "الجداول غير القانونية": فصلين في نفس الفصل الدراسي ، ودرس واحد يدرس مجموعتين في نفس الوقت وما إلى ذلك. واعتبرت هذه الطفرات قاتلة على الفور وتم نشر "كائن" جديد بدلاً من "المتوفى" على الفور. تم إنشاء المبدئي من خلال سلسلة من المحاولات العشوائية للحصول على واحدة قانونية (إذا كان لا معنى لها). لم يتم حساب الطفرة المميتة نحو عدد الطفرات في التكرار.

  • كانت طفرات "التبادل" أكثر شيوعًا من "تعديل" الطفرات. كانت التغييرات فقط بين أجزاء من الجين والتي كانت منطقية - لا يوجد استبدال المعلم مع الفصل الدراسي.

  • تم تعيين مكافآت صغيرة لتجميع ساعتين معًا ، لتعيين نفس الفصول الدراسية العامة بالتسلسل لنفس المجموعة ، للحفاظ على ساعات عمل المعلم وتحميل الفصل المستمر. تم تعيين مكافآت معتدلة لإعطاء الفصول الدراسية الصحيحة للموضوع المعطى ، والحفاظ على ساعات الفصل في السندات (الصباح أو بعد الظهر) ، وكذا. وكانت المكافآت الكبيرة لتعيين العدد الصحيح للموضوع المعطى ، مع عبء العمل للمعلم وما إلى ذلك.

  • يمكن للمعلمين إنشاء جداول عبء العمل الخاصة بهم من "تريد العمل ثم" ، "حسنًا للعمل بعد ذلك" ، "لا يحب العمل بعد ذلك" ، "لا يمكن العمل بعد ذلك" ، مع تعيين الأوزان المناسبة. كانت 24 ساعة كاملة ساعات عمل قانوني باستثناء الليل كانت غير مرغوب فيها للغاية.

  • وظيفة الوزن ... أوه نعم. كانت وظيفة الوزن ضخمة ، منتج وحشي (كما هو الحال في الضرب) من الأوزان المعينة للميزات والخصائص المحددة. كانت شديدة الانحدار للغاية ، وهي عقار واحد قادرة بسهولة على تغييره بترتيب من حيث الحجم لأعلى أو لأسفل - وكان هناك مئات أو الآلاف من الخصائص في كائن واحد. وقد أدى ذلك إلى أعداد ضخمة للغاية حيث أن الأوزان ، وكنتيجة مباشرة ، تحتاج إلى استخدام مكتبة Bignum (GMP) لإجراء الحسابات. بالنسبة لثلاثة اختبار صغيرة من حوالي 10 مجموعات و 10 معلمين و 10 فصول دراسية ، بدأت المجموعة الأولية مع ملاحظة من 10^-200 شيء وانتهت مع 10^+300 شيء. كان غير فعال تمامًا عندما كان أكثر مسطحًا. أيضا ، نمت القيم مسافة أوسع بكثير مع "المدارس" الأكبر.

  • وقت الحساب ، كان هناك فرق ضئيل بين عدد قليل من السكان (100) على مدى وقت طويل وكبار السكان (10K+) على مدى أجيال أقل. الحساب على نفس الوقت الذي ينتج عنه نفس الجودة.

  • سيستغرق الحساب (في حوالي 1 جيجا هرتز وحدة المعالجة المركزية) حوالي 1 ساعة لتحقيق الاستقرار بالقرب من 10^+300 ، مما يولد جداول زمنية تبدو لطيفة للغاية ، لحالة اختبار 10x10x10 المذكورة.

  • يمكن بسهولة أن تكون المشكلة قابلة للاسترداد من خلال توفير منشأة للشبكات التي من شأنها أن تتبادل أفضل العينات بين أجهزة الكمبيوتر التي تعمل بالحساب.

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

هذه المشكلة أكثر صرامة مما يبدو.

كما أشار الآخرون ، هذه مشكلة NP-Complete ، ولكن دعونا نحلل ما يعنيه ذلك.

في الأساس ، هذا يعني أنه يجب عليك النظر في جميع المجموعات الممكنة.

لكن "انظر إلى" لا يخبرك كثيرًا بما عليك القيام به.

من السهل توليد جميع المجموعات الممكنة. قد ينتج عنه كمية كبيرة من البيانات ، ولكن لا ينبغي أن تواجه الكثير من المشكلات في فهم مفاهيم هذا الجزء من المشكلة.

المشكلة الثانية هي الحكم على ما إذا كانت مجموعة ممكنة ممكنة جيدة أو سيئة أو أفضل من الحل "الجيد" السابق.

لهذا تحتاج أكثر من مجرد "هل هو حل ممكن".

على سبيل المثال ، هل يعمل المعلم نفسه 5 أيام في الأسبوع لمدة X Weeks على التوالي؟ حتى لو كان هذا حلاً عملًا ، فقد لا يكون حلاً أفضل من التناوب بين شخصين حتى يقوم كل معلم أسبوع واحد لكل منهما. أوه ، أنت لم تفكر في ذلك؟ تذكر ، هذا هو الأشخاص الذين تتعامل معهم ، وليس مجرد مشكلة تخصيص الموارد.

حتى إذا كان بإمكان أحد المعلمين العمل بدوام كامل لمدة 16 أسبوعًا على التوالي ، فقد يكون ذلك حلًا دون المستوى الأمثل مقارنةً بحل تحاول فيه البديل بين المعلمين ، ومن الصعب للغاية بناء هذا النوع من التوازن في البرامج.

لتلخيص ، فإن إنتاج حل جيد لهذه المشكلة سيكون يستحق الكثير ، لكثير من الناس. وبالتالي ، فليس من السهل الانهيار وحلها. كن مستعدًا لمشاركة بعض الأهداف التي ليست 100 ٪ وتطلق عليها "جيدة بما يكفي".

تحديث: من التعليقات ... يجب أن يكون لها الاستدلال أيضًا!

سأذهب مع Prolog ... ثم استخدم Ruby أو Perl أو شيء لتنظيف الحل الخاص بك في شكل أجمل.

teaches(Jill,math).
teaches(Joe,history).

involves(MA101,math).
involves(SS104,history).

myHeuristic(D,A,B) :- [test_case]->D='<';D='>'.
createSchedule :- findall(Class,involves(Class,Subject),Classes),
                  predsort(myHeuristic,Classes,ClassesNew),
                  createSchedule(ClassesNew,[]).
createSchedule(Classes,Scheduled) :- [the actual recursive algorithm].

أنا (لا يزال) في عملية القيام بشيء مشابه لهذه المشكلة ولكن باستخدام نفس المسار الذي ذكرته للتو. Prolog (كلغة وظيفية) يجعل حل المشكلات NP-Hard أسهل.

غالبًا ما تستخدم الخوارزميات الوراثية لمثل هذه الجدولة.

وجد هذا المثال (جعل جدول الفصل باستخدام الخوارزمية الجينية) الذي يطابق متطلباتك بشكل جيد.

فيما يلي بعض الروابط التي وجدتها:

الجدول الدراسي - يسرد بعض المشاكل المعنية

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

جدولة المرافق والأدوات

خوارزمية الجدول الزمني الخاص بي ، والتي تم تنفيذها في FET (برنامج مجاني جدول زمني ، http://lalescu.ro/liviu/fet/ ، تطبيق ناجح):

الخوارزمية هي الإرشاد. أسميته "تبادل العودية".

الإدخال: مجموعة من الأنشطة A_1 ... A_N والقيود.

الإخراج: مجموعة من الأوقات TA_1 ... TA_N (الفتحة الزمنية لكل نشاط. يتم استبعاد الغرف هنا ، من أجل البساطة). يجب أن تضع الخوارزمية كل نشاط في فترة زمنية ، مع احترام القيود. كل TA_I يتراوح بين 0 (T_1) و MAX_TIME_SLOTS-1 (T_M).

القيود:

C1) أساسية: قائمة من أزواج الأنشطة التي لا يمكن أن تكون متزامنة (على سبيل المثال ، A_1 و A_2 ، لأن لديهم نفس المعلم أو نفس الطلاب) ؛

C2) الكثير من القيود الأخرى (المستبعدة هنا ، من أجل البساطة).

خوارزمية الجدول الزمني (التي سميتها "تبديل العودية"):

  1. فرز الأنشطة ، الأكثر صعوبة أولاً. ليست خطوة حرجة ، ولكن تسرع الخوارزمية ربما 10 مرات أو أكثر.

  2. حاول وضع كل نشاط (A_I) في فتحة زمنية مسموح بها ، باتباع الترتيب أعلاه ، واحد تلو الآخر. ابحث عن فتحة متوفرة (T_J) لـ A_I ، حيث يمكن وضع هذا النشاط فيما يتعلق بالقيود. إذا كانت هناك المزيد من الفتحات متوفرة ، فاختر واحدة عشوائية. إذا لم يكن أي منها متاحًا ، فقم بمبادلة العودية:

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

    ب. اختر فتحة (T_J) مع أدنى عدد من الأنشطة المتضاربة. قل قائمة الأنشطة في هذه الفتحة تحتوي على 3 أنشطة: A_P ، A_Q ، A_R.

    ج. ضع A_I في T_J وجعل A_P ، A_Q ، A_R غير مخصصة.

    د. حاول بشكل متكرر وضع A_P ، A_Q ، A_R (إذا لم يكن مستوى العودية أكبر من اللازم ، على سبيل المثال 14 ، وإذا كان العدد الإجمالي للمكالمات العودية التي يتم حسابها منذ الخطوة 2) على A_I ، فإن A_I ليس كبيرًا جدًا ، على سبيل المثال 2*N) ، كما في الخطوة 2).

    ه. إذا وضعت بنجاح A_P ، A_Q ، A_R ، رجوع مع النجاح ، وإلا حاول فتحات زمنية أخرى (انتقل إلى الخطوة 2 ب) واختر أفضل فترة زمنية تالية).

    F. إذا تمت تجربة جميع (أو عدد معقول) من الفتحات الزمنية دون جدوى ، فإن العودة دون نجاح.

    ز. إذا كنا في المستوى 0 ، ولم نحقق أي نجاح في وضع A_I ، فضعه كما في الخطوات 2 B) و 2 C) ، ولكن بدون عودة. لدينا الآن 3 - 1 = 2 أنشطة أخرى لوضعها. انتقل إلى الخطوة 2) (يتم استخدام بعض الطرق لتجنب ركوب الدراجات هنا).

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

تصف هذه الورقة مشكلة الجدول الزمني للمدرسة ونهجها في الخوارزمية جيدًا: "تطوير المنهج-وهو جدولة تفاعلية قائمة على القيد للمدارس والكليات.[بي دي إف

يخبرني المؤلف أن برنامج المنهج لا يزال يتم استخدامه/تطويره هنا: http://www.scientia.com/uk/

أنا أعمل على محرك جدولة يستخدم على نطاق واسع وهو يفعل هذا بالضبط. نعم ، إنه NP-Complete ؛ تسعى أفضل الأساليب إلى تقريب الحل الأمثل. وبطبيعة الحال ، هناك الكثير من الطرق المختلفة لإيما هو الحل "الأفضل" - هل من المهم أن يكون مدرسك سعداء بجداولهم ، أو أن يدخل الطلاب في جميع فصولهم ، على سبيل المثال؟

السؤال الأكثر أهمية المطلق الذي تحتاج إلى حله مبكرًا هو ما الذي يجعل طريقة واحدة لجدولة هذا النظام أفضل من الآخر؟ هذا هو ، إذا كان لدي جدول زمني مع السيدة جونز لتدريس الرياضيات في الثامنة والسيد سميث تدرس الرياضيات في التاسعة ، هل هذا أفضل أو أسوأ من واحد مع كل منهما تدريس الرياضيات في 10؟ هل هو أفضل أم أسوأ من واحد مع تعليم السيدة جونز في الثامنة والسيد جونز التدريس في 2؟ لماذا ا؟

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

غالبًا ما يتم استخدام تمريرة تحسين البحث المحلي "لصقل" الإجابة النهائية للحصول على نتائج أفضل.

لاحظ أننا عادة ما نتعامل مع أنظمة عالية التقييد الموارد في جدولة المدارس. لا تمر المدارس خلال العام مع الكثير من الغرف الفارغة أو المعلمين الذين يجلسون في الصالة بنسبة 75 ٪ من اليوم. النهج التي تعمل بشكل أفضل في البيئات الغنية بالحل لا تنطبق بالضرورة في جدولة المدرسة.

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

حظا طيبا وفقك الله !

يمكنك أن تتجول مع الخوارزميات الوراثية ، نعم. لكن لا يجب عليك :). يمكن أن يكون بطيئًا جدًا ويمكن أن يكون ضبط المعلمات أمرًا رائعًا للغاية وما إلى ذلك.

هناك طرق أخرى ناجحة. كل ما تم تنفيذه في مشاريع مفتوحة المصدر:

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

انظر هنا ل قائمة البرمجيات الزمنية

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

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

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

ariesflag.each do | k2 ، v2 |

            if(TimetableDefinition.find(k2).period.to_i != 0)
                subjectflag.each do |k3,v3|
                    if (v3 == 0)
                        if(getflag_period(periodflag,k2))
                            @teachers=EmployeesSubject.where(subject_name: @subjects.find(k3).name, division_id: division.id).pluck(:employee_id)
                            @teacherlists=Employee.find(@teachers)
                            teacherflag=Hash[teacher_flag(@teacherlists,teacherflag,flag).to_a.shuffle] 
                            teacherflag.each do |k4,v4|
                                if(v4 == 0)
                                    if(getflag_subject(subjectflag,k3))
                                        subjectperiod=TimetableAssign.where("timetable_definition_id = ? AND subject_id = ?",k2,k3)
                                        if subjectperiod.blank?
                                            issubjectpresent=TimetableAssign.where("section_id = ? AND subject_id = ?",section.id,k3)
                                            if issubjectpresent.blank?
                                                isteacherpresent=TimetableAssign.where("section_id = ? AND employee_id = ?",section.id,k4)
                                                if isteacherpresent.blank?
                                                    @finaltt=TimetableAssign.new
                                                    @finaltt.timetable_struct_id=@timetable_struct.id
                                                    @finaltt.employee_id=k4
                                                    @finaltt.section_id=section.id
                                                    @finaltt.standard_id=standard.id
                                                    @finaltt.division_id=division.id
                                                    @finaltt.subject_id=k3
                                                    @finaltt.timetable_definition_id=k2
                                                    @finaltt.timetable_day_id=k1
                                                    set_school_id(@finaltt,current_user)
                                                    if(@finaltt.save)

                                                        setflag_sub(subjectflag,k3,1)
                                                        setflag_period(periodflag,k2,1)
                                                        setflag_teacher(teacherflag,k4,1)
                                                    end
                                                end
                                            else
                                                @subjectdetail=TimetableAssign.find_by_section_id_and_subject_id(@section.id,k3)
                                                @finaltt=TimetableAssign.new
                                                @finaltt.timetable_struct_id=@subjectdetail.timetable_struct_id
                                                @finaltt.employee_id=@subjectdetail.employee_id
                                                @finaltt.section_id=section.id
                                                @finaltt.standard_id=standard.id
                                                @finaltt.division_id=division.id
                                                @finaltt.subject_id=@subjectdetail.subject_id
                                                @finaltt.timetable_definition_id=k2
                                                @finaltt.timetable_day_id=k1
                                                set_school_id(@finaltt,current_user)
                                                if(@finaltt.save)

                                                    setflag_sub(subjectflag,k3,1)
                                                    setflag_period(periodflag,k2,1)
                                                    setflag_teacher(teacherflag,k4,1)
                                                end
                                            end
                                        end
                                    end
                                end
                            end
                        end
                    end
                end
            end
        end
مرخصة بموجب: CC-BY-SA مع الإسناد
لا تنتمي إلى StackOverflow
scroll top