ݺߣ

ݺߣShare a Scribd company logo

تقليل الزمن الكلي للجدولة في نماذج تدفق الأعمال

•
•
I
Ibrahim Ahmed Badi

الهدف من الورقة هو تقليل الزمن الكلي للجدولة في نماذج تدفق الأعمال Flow shop scheduling

1 of 20
Download to read offline
‫الع‬ ‫وتطبيقات‬ ‫نظريات‬ ‫حول‬ ‫األول‬ ‫السنوي‬ ‫المؤتمر‬‫لوم‬ ‫والحيوية‬ ‫األساسية‬ ‫للجدولة‬ ‫الكلي‬ ‫الزمن‬ ‫تقليل‬ ‫األعمال‬ ‫تدفق‬ ‫نماذج‬ ‫في‬ ‫د‬.‫د‬ ،‫بادي‬ ‫أحمد‬ ‫إبراهيم‬.‫أ‬ ،‫عبدالشاهد‬ ‫محمد‬ ‫علي‬.‫التريكي‬ ‫الفيتوري‬ ‫أحمد‬ ‫الهندسة‬ ‫كلية‬-‫مصراتة‬ ‫جامعة‬
‫الجدولةĬ ‫قطارات‬ ‫طائرات‬
‫الجدولةĬ ‫تخصيص‬‫الموارد‬‫المتاحة‬‫على‬‫األوامر‬‫اإلنتاجية‬‫أو‬‫على‬‫األعمال‬‫واألنش‬‫طة‬ ،‫الالزمة‬‫أو‬‫على‬‫خدمة‬‫مجموعة‬‫من‬‫المستهلكين‬.
‫الجدولةĬ 10 20 2,4 1018 3,628,800 ‫الممكنة‬ ‫الحلول‬ ‫عددĬ
‫جدولة‬ ‫إيجاد‬ ‫هو‬ ‫المطلوب‬‫فعالية‬ ‫أكثر‬ ‫الجدولةĬ
‫الجدولةĬ ‫نظام‬ ‫نظام‬ ‫الجدولةĬ ‫القيود‬ ‫المفروضة‬ ‫نظام‬ ‫على‬ ‫الجدولةĬ ‫مخرجات‬ ‫نظام‬ ‫الجدولةĬ ‫متغيرات‬ ‫القرار‬ ‫لنظام‬ ‫الجدولةĬ ‫معيار‬ ‫األداء‬ ‫لنظام‬ ‫الجدولةĬ ‫مدخالت‬ ‫نظام‬ ‫الجدولةĬ
‫للجدولة‬ ‫العامة‬ ‫المعاييـر‬ ‫المعيار‬‫الوصف‬‫الهدف‬ ‫لتصنيع‬ ‫الكلي‬ ‫الزمن‬‫الدف‬‫عة‬ ‫الطلبية‬ ‫أو‬ Makespan time ‫مجموعة‬ ‫تستغرقه‬ ‫الذي‬ ‫الزمن‬‫من‬ ‫األعمال‬‫الطلبية‬ ‫أو‬‫في‬‫العملية‬‫التص‬‫نيعية‬. ‫تقليل‬‫الكلي‬ ‫الزمن‬‫للتص‬‫نيع‬ Minimize Makespan time ‫التدفق‬ ‫زمن‬ Flow time ‫الطلبي‬ ‫أو‬ ‫العمل‬ ‫يستغرقه‬ ‫الذي‬ ‫الزمن‬‫في‬ ‫ة‬ ‫اإلنتاجية‬ ‫الورشة‬ ‫أو‬ ‫المحطة‬. ‫التدفق‬ ‫زمن‬ ‫معدل‬ ‫تقليل‬ Minimize Average Flow time ‫العمل‬ ‫إتمام‬ ‫في‬ ‫التأخير‬ ‫مدة‬ ‫الطلبية‬ ‫أو‬ Tardiness* ‫إتما‬ ‫زمن‬ ‫به‬ ‫يزيد‬ ‫الذي‬ ‫الزمن‬ ‫مقدار‬ ‫وهو‬‫م‬ ‫عن‬ ‫الطلبية‬ ‫أو‬ ‫العمل‬‫تاريخ‬‫االستحق‬‫اق‬. ‫يتجاو‬ ‫التي‬ ‫األعمال‬ ‫عددĬ ‫تقليل‬‫ز‬ ‫الطلبي‬ ‫أو‬ ‫العمل‬ ‫إتمام‬ ‫زمن‬ ‫فيها‬‫ة‬. ‫الزمني‬ ‫الفارق‬ Lateness ‫العمل‬ ‫إنجاز‬ ‫زمن‬ ‫بين‬ ‫ما‬ ‫الفرق‬‫وبين‬ ‫االستحقاق‬ ‫تاريخ‬. ‫الفارق‬ ‫معدل‬ ‫تقليل‬ ‫الزمني‬. *‫إذا‬‫أنجز‬‫العمل‬‫قبل‬‫تاريخ‬‫االستحقاق‬,‫فإن‬‫مقدار‬‫التجاوز‬(‫مدة‬‫التأخير‬)‫يساوي‬‫صفرا‬.
‫اإلنتاجية‬ ‫العمليات‬ ‫جدولة‬ ‫نماذج‬ ‫الواحدة‬ ‫اآللة‬ ‫نموذج‬ ‫المتوازية‬ ‫اآلالت‬ ‫نموذج‬ ‫األعمال‬ ‫تدفق‬ ‫نموذج‬ ‫العمل‬ ‫قوائم‬ ‫نموذج‬
‫الجدولةĬ
‫الواحدة‬ ‫اآللة‬ ‫نموذج‬ Job 1: p1=5, d1=7, w1=3 Job 2: p2=3, d2=6, w1=2 Job 3: p3=6, d3=11, w1=4 1 2 3 Total weighted completion time= 3*5+2*8+4*14=87 No. of tardy jobs=2 Total tardiness=2+3=5 Total weighted completion time= 3*5+2*14+4*11=87 No. of tardy jobs=1 Total tardiness=8 3 21
‫التسلسالت‬ ‫بين‬ ‫المقارنة‬ Sequence TWCt NtJ Tt 1-2-3 87 2 5 1-3-2 87 1 8 2-1-3 86 2 4 2-3-1 92 1 7 3-1-2 85 2 12 3-2-1 84 1 10
‫األعمال‬ ‫تدفق‬ ‫نموذج‬ ‫خوارزميات‬ ‫تدفق‬ ‫نموذج‬ ‫األعمال‬ ‫خوارزمية‬ ‫مايزا‬(𝐹𝑚||𝐶 𝑚𝑎𝑥) ‫خوارزمية‬ ‫نواز‬(𝐹𝑚||𝐶 𝑚𝑎𝑥) ‫خوارزمية‬ ‫كامبل‬(𝐹𝑚||𝐶 𝑚𝑎𝑥) ‫خوارزمية‬ ‫جونسون‬ (𝐹2||𝐶 𝑚𝑎𝑥)
‫جدولة‬‫تدفق‬‫األعمال‬‫باستخدام‬‫خوارزمية‬Nawaz 𝐹𝑚 || 𝐶 𝑚𝑎𝑥 )) .1‫حساب‬‫مجموع‬‫أوقات‬‫تشغيل‬‫األعمال‬‫على‬‫اآلالت‬‫من‬‫خالل‬‫المعادلة‬𝑃𝑗 = 𝑖=1 𝑚 𝑝𝑖𝑗. ‫حيث‬𝑝𝑖𝑗‫هو‬‫الوقت‬‫الالزم‬‫لتشغيل‬‫العمل‬j‫على‬‫اآللة‬i. .1‫ترتيب‬‫األعمال‬‫ترتيبا‬‫تنازليا‬‫من‬‫المعادلة‬.𝑃j .2‫اختيار‬‫األعمال‬‫من‬‫المركزين‬‫األول‬‫والثاني‬‫من‬‫قائمة‬‫الخطوة‬2،‫وإيجاد‬‫أفضل‬‫تسلسل‬ ‫لتشغيل‬‫هذه‬‫األعمال‬‫عن‬‫طريق‬‫حساب‬‫زمن‬‫التنفيذ‬‫الكلي‬(𝐶 𝑚𝑎𝑥)‫لكال‬‫التسلسلين‬ ‫المحتملين‬. ‫ال‬‫تتغير‬‫المواقف‬‫النسبية‬‫لهذه‬‫األعمال‬‫لكال‬،‫التسلسلين‬‫تعيين‬k = 3. .1‫اختيار‬‫العمل‬‫في‬‫الموقع‬k‫من‬‫قائمة‬‫أنشأت‬‫في‬‫الخطوة‬2‫وإيجاد‬‫أفضل‬‫تسلسل‬‫عن‬ ‫طريق‬‫وضعها‬‫في‬‫جميع‬‫المواقع‬‫المحتملة‬k‫في‬‫تسلسل‬‫جزئي‬‫وجد‬‫في‬‫الخطوة‬ ،‫السابقة‬‫دون‬‫تغيير‬‫المواقف‬‫بالنسبة‬‫لبعضها‬‫البعض‬‫من‬‫األعمال‬‫المخصص‬‫ة‬‫بالفعل‬. ‫عددĬ‫التكرارات‬‫عند‬‫هذه‬‫الخطوة‬‫يساوي‬k. .1‫إذا‬‫كان‬k = n،‫إيقاف‬‫تعين‬‫خالف‬‫ذلك‬k = k + 1‫وانتقل‬‫إلى‬‫الخطوة‬4.
‫لخوارزمية‬ ‫جانت‬ ‫خارطة‬‫جونسون‬ ‫لـقاعدة‬ ‫جانت‬ ‫خارطة‬𝐹𝐼𝐹𝑂 ‫جانت‬ ‫خارطة‬
‫البر‬ ‫الرئيسية‬ ‫الواجهة‬‫نامج‬
‫للبرن‬ ‫الفرعية‬ ‫الواجهة‬‫امج‬
‫الفرعية‬ ‫الواجهة‬‫للبرن‬‫امج‬
‫النتائج‬ ‫بين‬ ‫المقارنة‬
.1‫درجة‬‫تعقيد‬‫الحل‬‫تعتمد‬‫على‬‫عددĬ‫األعمال‬‫واآلالت‬. .2‫العمل‬‫على‬‫استخدام‬‫الحاسوب‬‫الستالم‬‫وإدخال‬‫المعلومات‬‫المتعلقة‬ ‫بأوامر‬‫العمل‬‫لضمان‬‫تسليمها‬‫حسب‬‫تواريخ‬‫استحقاقها‬. .3‫خوارزمية‬Nawaz‫تعطي‬‫حال‬‫أفضل‬‫من‬‫باقي‬‫الخوارزميات‬‫خاصة‬ ‫عند‬‫درجة‬‫تعقيد‬‫أكثر‬‫للمسألة‬. ‫الخالصة‬ ‫الهندسة‬ ‫بكلية‬ ‫لطلبة‬ ‫تخرج‬ ‫مشاريع‬ ‫نتاج‬ ‫هي‬ ‫الورقة‬-‫هي‬ ‫والمشاريع‬ ،‫اإلنتاج‬ ‫جدولة‬ ‫مجال‬ ‫في‬ ‫مصراتة‬ ‫جامعة‬: ‫هللا‬ ‫فتح‬ ‫وعبدهللا‬ ‫بادي‬ ‫خليفة‬ ‫و‬ ‫شلغوم‬ ‫الحسين‬ ‫للطلبة‬ ،‫التصنيعية‬ ‫للعمليات‬ ‫اإلنتاج‬ ‫جدولة‬ ‫المتوازية‬ ‫اآلالت‬ ‫في‬ ‫اإلنتاج‬ ‫جدولة‬:‫درميش‬ ‫وفارس‬ ‫فكرون‬ ‫علي‬ ‫للطلبة‬ ،‫دراسية‬ ‫حالة‬ ‫المال‬ ‫بيت‬ ‫ومحمد‬ ‫ارفيدة‬ ‫ومحمد‬ ‫المديني‬ ‫علي‬ ‫للطلبة‬ ،‫الفواقد‬ ‫لتقليل‬ ‫القيمة‬ ‫خارطة‬ ‫مفهوم‬ ‫استخدام‬
‫على‬ ‫شكرا‬ ‫االستماع‬ ‫حسن‬

More Related Content

تقليل الزمن الكلي للجدولة في نماذج تدفق الأعمال