حل دوال متعددة المعايير لمسائل جدولة الماكنة

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

أ.د. فائز حسن علي – رئيسا
أ.م.د. فضاء عثمان سمير – عضوا
أ.م.د. هدى حمودي عمران – عضوا
أ.م.د. ميساء جليل محمد عضوا
أ.م.د. عراق طارق عباس عضوا
أ.م.د. بيداء عطية خلف عضوا ومشرفا

ويهدف البحث الى تقديم نماذج وتقنيات رياضية جديدة لتوليد حلول تقريبية ومثلى لحل مسائل متعددة المعايير ومتعددة الاهداف لـ SMSP.

ولتحقيق هذا الهدف، يتم النظر في الأهداف المحددة التالية:

1 – إجراء دراسة استقصائية حول أدوات وطرق حل مسائل جدولة الماكنة، لاستكشاف نموذجين جديدين متعددة المعايير و ونموذجين جديدين متعددة الأهداف.

و من SMSP.

2- من أجل تحسين والتحقق من أداء النماذج المقترحة، تمت مناقشة واشتقاق بعض الحالات الخاصة وقواعد الهيمنة لهذه المشاكل.

3- اقتراح حد أدنى وأعلى جديد لطريقة BAB لحل المسائل الأربع.

4- اقتراح طريقتين تقريبية حدسية جديدة تتسم بالكفاءة والفعالية لحل النماذج متعددة الأهداف ومتعددة المعايير لـ SMSP.

5- استخدام و تطبيق خوارزميتين فوق الحدسية (Mate-Heuristic)(أمثليه السرب الجسمي (PSO) وخوارزمية مستعمرة النحل (BCA)) لحل النماذج متعددة الأهداف والمتعددة المعايير لـ SMSP.

6-اقترح خوارزمية هجينة جديدة من أمثليه السرب الجسمي وخوارزمية مستعمرة النحل (BCA-PSO)) تم استخدامها لحل مسائل متعددة المعايير و المتعددة الاهداف لمشاكل جدولة الماكنة.

مستخلص البحث :

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

لذلك، اقتراحنا في الاطروحة نموذجين رياضيين جديدين متعدد المعايير (ثلاثي المعايير) ودالة متعددة الأهداف لمشكلة جدولة الآلة الواحدة. نموذج الأول يشير الى تقليل إجمالي اوقات الانجاز ، اجمالي الاعمال المتأخرة ، والحد الأقصى لوقت التبكير( ) لماكنة واحدة. يتم الاشارة اليه ب و . بينما النموذج الثاني يهدف الى تقليل وقت الإنجاز الاجمالي وإجمالي وقت التبكير والحد الأقصى لوقت التأخير ويتم الاشارة إليه بـ 1// و بالاضافة الى ذلك, من كل نموذج ثلاثي المعايير ( TCMSP ) لمسألة جدولة الماكنة تم اشتقاق مسالة الفرعية وهي:

1// و 1// يتم الاشارة لها و على التوالي.

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

(( , , , and )

وثلاث خوارزميات فوق الحدسية (Mate-Heuristic)(أمثليه السرب الجسمي (PSO) وخوارزمية مستعمرة النحل (BCA) و خوارزمية هجينة جديدة مقترحه من أمثليه السرب الجسمي وخوارزمية مستعمرة النحل (BCA-PSO)) تم استخدامها لحل مسائل متعددة المعايير و المتعددة الاهداف لمشاكل جدولة الماكنة.

وأخيرًا، تم إجراء دراسة محاكاة لمقارنة ودراسة أداء خوارزميات Meta-Heuristics مع الطرق التامة الحدسية من حيث الدقة و زمن التنفيذ. تم تنفيذ جميع الخوارزميات باستخدام لغة MATLAB R2019a وتم تنفيذها على وحدة المعالجة المركزية Intel (R) Core (TM) i7-2630 QM بسرعة 2.00 جيجا هرتز وذاكرة الوصول العشوائي (RAM) سعة 16.00 جيجا بايت. أظهرت النتائج أن الخوارزمية الهجينة المقترحة تعطي حلولاً جيدة و وقت التنفيذ قليلا مقارنة ببقية الطرق حل مسائل 8000 عمل. وأهم النتائج التي تم التوصل إليها هي كما يلي:


				Exact Method
11	11	11	11	CEM
				BAB
15	19	15	20	BAB(WODR)
17	50	30	70	BAB(WDR)
				Heuristic Methods
–	–	–	5000
–	–	–	4000
–	–	4000	–
–	–	4000	–
–	5000	–	–
–	5000	–	–
4000	–	–	–
4000	–	–	–
				Meta-Heuristic Methods
4000	4000	4000	4000	Particle Swarm Optimization (PSO)
3000	3000	3000	3000	Bee Colony Algorithm (BCA)
				Hybrid Algorithm
8000	7000	8000	7000	(BCA-PSO)

التوصيات:

1- لقد قدمنا الاقتراحات والتوصيات التالية لإجراء مزيد من البحث:

2- استخدام UB و LB جديد لخوارزمية BAB يمكن استخدامه لإثبات كفاءته في إيجاد الحل الأمثل لـ MCF.

3- يمكن دراسة المشكلات الأكثر تعقيدًا باستخدام بيئات مختلفة للآلات و/ أو يمكن استكمال المشكلات المقترحة بقيود، مثل تاريخ الإصدار ، ووقت الإعداد , ، والإيقاف المسبق.

يمكن أيضًا اقتراح المشكلات التالية للتحقيق فيها.