المصفوفات الأساسية للخوارزميات المقترحة

تبنى الخوارزميات المقترحة لجدولة (ن) عمل على (م) آلة تتطلب مروراً متسلسلاً على الآلات على استخدام المصفوفات كقاعدة بيانات لجدولة الأعمال، وهذه المصفوفات هي التالية :

1- مصفوفة البيانات الأولية : تحتوي هذه المصفوفة على بيانات أولية عن الأعمال، والآلات والأزمنة اللازمة لمعالجة كل عمل على كل آلة وتتشكل من صفوف بعدد الآلات الموجودة في النظام ــ حيث أن كل آلة تحجز صف واحد- ومن أعمدة بعدد الأعمال الواجب معالجتها والتي تتطلب مروراً متسلسلاً على كافة الآلات الموجودة في النظام ــ حيث أن كل عمل يحجز عامود واحد والخلايا تمثل أزمنة معالجة كل عمل على كل آلة والشكل العام لهذه المصفوفة كما يلي:

حيث أن م = آلة ع = عمل ز = زمن معالجة ع _س على م _س.

2 ـ مصفوفة الترتيب المثالي : تحتوي هذه المصفوفة على نفس بيانات مصفوفة البيانات الأولية، لكن مع اختلاف ترتيب البيانات في الأعمدة حيث يتبع ترتيبها لترتيب الأعمال (الترتيب المثالي) في النظام ، والذي يتم تحديده باتباع قواعد الترتيب المعروفة والمعروضة سابقاً.

الخوارزميات المقترحة

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

خوارزمية كاسر رقم (1)

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

مثال رقم (3)

الجدول التالي يبين الأعمال والأزمنة اللازمة لمعالجة كل منها على الآلات الموجودة في النظام :

خطوات إعداد مصفوفة البدء :

أ ـ نضع بيانات الجدول أعلاه على شكل مصفوفة وبحيث تخصص الصفوف للآلات والأعمدة للأعمال ، ونحصل بالتالي على مصفوفة البيانات الأولية، وتأخذ هذه المصفوفة الشكل التالي:

ب ـ نقوم بتحويل مصفوفة البيانات الأولية أعلاه إلى مصفوفة ترتيب، وذلك باستخدام خوارزمية CDS ، ويكون الترتيب المثالي لتسلسل مرور الأعمال حسب هذه الخوارزمية كما يلي ،ب، أ، د، ج، هـ. وتصبح مصفوفة الترتيب كما يلي:

نقوم بإعداد مصفوفه البدء، وذلك بمعالجة بيانات مصفوفة الترتيب بالخطوات التالية :

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

حيث أن:

ز ب م₁ ع _س = زمن بدء معالجة العمل (س) على الآلة الأولى وتكون النتيجة تطبيق هذه الخطوة كما يلي:

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

3 - نكمل خلايا المصفوفة باتباع الخطوات التالية:

أ) نضيف زمن المعالجة للعمل الأول على الآلة الثانية إلى زمن البدء للعمل الأول على الآلة الثانية أو زمن البدء للعمل الثاني على الآلة أيهما أكبر. وهكذا دواليك حتى آخر خلية في الصف الثاني.

ب) نضيف زمن المعالجة للعمل الأولى على الآلة الثالثة إلى زمن البدء للعمل الأول على الآلة الثالثة أو زمن البدء للعمل الثاني على الآلة الثانية أيهما أكبر. وهكذا دواليك حتى آخر خلية في الصف الثالث.

ت) يتم ملئ خلايا باقي الصفوف باتباع نفس القاعدة حتى نحصل على مصفوفة البدء لمعالجة الأعمال على الآلات.

وتكون نتيجة هذه الخطوات الثلاث كما يلي :

وبالتالي فإن مصفوفة البدء تكون كما يلي :

أهمية مصفوفة البدء :

إن إعداد مصفوفة البدء لإنجاز (ن) عمل على (م) آلة الموجودة في النظام يحقق الكثير من الفوائد، مثل:

1- جدولة أزمنة البدء لكل عمل على كل آلة ، ويمكن ترجمة هذه الجدولة بسهولة على أجندة إدارة الإنتاج والعمليات في المنظمة.

2- تحديد الزمن النهائي لإنجاز كافة الأعمال على كل الآلات الموجودة في النظام، وذلك بإضافة زمن المعالجة في الخلية م _ن ع _ن إلى زمن بدء العمل الأخير على الآلة الأخيرة، وهي الخلية م _ن ع _ن. وفي مثالنا السابق رقم (3) فإن زمن المعالجة م _ن ع _ن 5 ساعات وزمن البدء في هذه الخلية هو 72 ساعة. وبالتالي فإن الزمن النهائي الإجمالي لمعالجة (ن) عمل على (م) آلة في مثالنا  هي 5 + 72=77 ساعة.

3- تفيد في أعمال الرقابة على إنجاز الأعمال، وذلك من خلال ما يلي :

أ- أي عمل يبدأ بعد تاريخ البدء يكون متأخر، ويتطلب تدخل الإدارة لتسريع إنجاز الأعمال على الآلات اللاحقة.

ب ـ أي عمل يبدأ قبل تاريخ البدء يكون مبكر، ولا يتطلب تدخل الإدارة.

ج- اختبار مثولية الحلول التي تقدمها خوارزمية CDS دون الحاجة لاستخدام مخططات جانت، وسوف نوضح ذلك لاحقاً.

مواضيع ذات صلة

اخـتبـار مثاليـة الحـلـول باستـخـدام مـصفوفـات الـبـدء والانتهـاء

تطبيقات الخوارزميات المقترحة في اختبار مثاليـة الحلول التي تقدمها قاعدة جونسون وخوارزمية CDS

خوارزميـة مـصفوفـة الأزمنة العاطلـة باستخـدام مصفوفـة البـدء والانتهـاء

خـوارزميـة تحـويـل مصـفوفـة التـرتـيـب إلـى مـصفوفـة إنـهـاء وأهميـتها

خـوارزميـة كـاسـر المـنصـور والطـرائـق والـوسائـل السابـقة (قـاعـدة جـونـسـون و خوارزمية CDS)

أسـلـوب التـحمـيـل الـمحـدود لـمـراكـز الإنـتـاج

نظرية التخصيص Assignment Method وتحميل مراكز الإنتاج loading (أسلوب التحميل غير المحدود)

خـوارزمـيات كـاسـر المـنصور لـترتـيب (ن) عـمل علـى (م) آلـة

خـوارزمـية CDS لتـرتـيـب (ن) عـمـل عـلـى م آلـة

قواعد ترتیب (ن) عمل على (م) آلة Sequencing N Jobs on M Machines (قاعدة جونسون Johnson s Rule)

قـواعـد تـرتـيب الأعـمـال Priority Rules and Techniques (قـواعـد أولـويـة الأعمـال الـسريعـة)

جـدولـة العـمليـات (مفـهوم الجـدولـة وأهـدافـهـا)