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

الخوارزمية الجينية هي طريقة بحث تشغيلية يمكن استخدامها لحل مشاكل الجدولة في تخطيط الإنتاج .

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

• مجموعة من المهام التي يجب تنفيذها
• مجموعة محدودة من الموارد التي يمكن استخدامها لإنجاز كل مهمة
• مجموعة من القيود التي يجب استيفاؤها
  • القيود الزمنية – الفترة الزمنية المتاحة لإنجاز المهمة
  • القيود الإجرائية - ترتيب إنجاز كل مهمة
  • قيود الموارد – هل الموارد متاحة؟
• مجموعة من الأهداف لتقييم أداء الجدولة

يُعدّ مكان العمل النموذجي في المصنع مثالاً جيداً على ذلك، حيث يكون من الضروري جدولة المهام التي يجب إنجازها على أي آلات، ومن قبل أي موظفين، وبأي ترتيب وفي أي وقت.

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

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

مع ازدياد عدد الأهداف التي نسعى لتحقيقها، يزداد عدد القيود المفروضة على المشكلة، وبالتالي يزداد تعقيدها. تُعدّ الخوارزميات الجينية مثاليةً لهذا النوع من المشاكل حيث تكون مساحة البحث واسعةً وعدد الحلول الممكنة محدودًا.

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

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

• الخوارزمية الجينية في الاقتصاد
• جدولة ورش العمل
• مراقبة الجودة والخوارزميات الجينية

• وال، م.، خوارزمية جينية لجدولة الموارد المحدودة (ملف PDF)
• ليم، سي.؛ سيم، إي.، تخطيط الإنتاج في بيئة التصنيع/إعادة التصنيع باستخدام الخوارزمية الجينية (PDF)

• تطبيق تجريبي لخوارزمية جينية لحل مسائل البائع المتجول (TSP) ومسائل VRPTW