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

أ)خوارزمية كاسر 1 قاعدة ترتيب (ن) عمل على آلتين Sequencing N Jobs on two Machines

إن تسلسل مرور الأعمال على آلتين (بالتسلسل( يأخذ الشكل التالي :

وإجراءات تطبيق هذه القاعدة هي التالية :

1- نشكل مصفوفة من ثلاثة صفوف و (ن) عامود ، ثم نضع في الصف الأول الأعمال وفي الصف الثاني الأزمنة اللازمة لمعالجة الأعمال على الآلة (1) .كما نضع في الصف الثالث الأزمنة اللازمة لمعالجة الأعمال على الآلة (2).

2- نختار العمل الذي يستغرق أقل زمن معالجة على الآلة الأولى حتى نقلل الوقت العاطل على الآلة الثانية إلى أدنى حد ممكن. في حالة عدم حجز الآلة الثانية لأية أعمال أخرى. ويشترط في هذا الاختيار أن يكون زمن المعالجة على الآلة الأولى أقل من زمن المعالجة على الآلة الثانية لنفس العمل كي لا يزداد الوقت العاطل على الآلة الثانية بمقدار الفرق بين زمن المعالجة على الآلة الأولى وزمن المعالجة على الآلة الثانية.

3- نختار العمل الثاني الذي لا يكون زمن معالجته على الآلة الأولى أكبر مباشرة من زمن معالجة العمل السابق المختار على الآلة الثانية، إذا لم يوجد نأخذ الذي يساويه، فإذا لم يوجد نأخذ الزمن الأصغر منه مباشرة.

4 - نكرر الخطوة رقم (3) حتى ننهي ترتيب تسلسل كافة الأعمال.

مثال (11-5)

لدينا مجموعة الأعمال (أ، ب، ج، د، هـ) يجب أن تعالج على الآلة الأولى أولاً ثم الثانية.

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

بتطبيق القاعدة (أ) المقترحة على المثال أعلاه نلاحظ ما يلي :

ــ زمن المعالجة الأقل على الآلة (1) يعود للعمل (ب) وهو (3)، وبالمقارنة مع زمن المعالجة على الآلة (2) لنفس العمل نلاحظ أنه الأصغر لأن الزمن اللازم على الآلة (2) هو (6)، فنختار العمل (ب)، ويكون الأول في الترتيب ويصبح الترتيب كما في الجدول الآتي:

نقارن الآن زمن المعالجة للعمل (ب) على الآلة (2) ومقدارها (6) مع أزمنة معالجة الأعمال الباقية على الآلة رقم (1) ونختار العمل الذي يكون زمن معالجته أكبر مباشرة من (6) وهو هنا العمل (هـ) وزمن معالجته على الآلة رقم (1) هو (7). فنختار العمل (هـ) ويكون الثاني في الترتيب. كما في الجدول الآتي:

ونكرر العملية السابقة ونلاحظ أن زمن معالجة (هـ) على الآلة (2) هو (12)، وبالمقارنة مع الأزمنة الباقية لمعالجة الأعمال على الآلة رقم (1) نرى أنها أصغر منه فنختار الأصغر مباشرة، وهو العمل (د)، وزمن المعالجة على الآلة رقم (1) هو (10) ويصبح الترتيب كما يلي :

نكرر العملية السابقة، ونلاحظ أن زمن المعالجة (د) على الآلة (2) هو (7)، وبالمقارنة مع أزمنة المعالجة للأعمال الباقية على الآلة رقم (1) نجد أن زمن المعالجة الأكبر مباشرة هو زمن (ج) وهو (8) ، فنختار العمل (ج) ، ويصبح العمل الرابع. ويكون الترتيب الأمثل في نهاية هذه العملية كما يلي :

وباستخدام خرائط Gantt لتحديد الزمن الإجمالي للمعالجة الشكل (1) نرى أن الزمن الإجمالي لمعالجة هذه الأعمال على الآلتين مقداره (35) يوم وهو أقل زمن ممكن لمعالجة جميع الأعمال.

ب ـ خوارزمية كاسر 2 : قاعدة ترتيب (ن) عمل على ثلاث آلات Sequencing N jobs on Three machines

أن تسلسل الأعمال في هذه القاعدة يأخذ الشكل الآتي :

وإجراءات تطبيق هذه القاعدة هي الخطوات التالية :

1 - تشكيل مصفوفة من أربعة صفوف و (ن) عامود . نضع في الصف الأول الأعمال، وفي الصف الثاني والثالث والرابع الأزمنة اللازمة لمعالجة الأعمال على الآلات رقم (1) و (2) و (3) على الترتيب.

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

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

مثال (11-6) :

لدينا أربعة أعمال يتوجب معالجتها على ثلاث آلات ،بالتسلسل والأزمنة اللازمة لمعالجة هذه الأعمال على الآلات الثلاث بالأيام توضحها المصفوفة الآتية :

بتطبيق القاعدة (ب) المقترحة على المثال أعلاه نلاحظ ما يلي:

ــ العمل الذي يحتاج إلى أقل زمن معالجة على الآلة رقم (1) هو (ب)، وهو أصغر من زمن المعالجة على الآلة رقم (3) لذلك نختار العمل (ب)، ويكون ترتيبه الأول.

ــ بعد أن تم ترتيب العمل (ب) أولاً نلاحظ أن زمن المعالجة على الآلة (3) هو (7)، وبمقارنة هذا الزمن مع أزمنة المعالجة الباقية على الآلة رقم (2) نلاحظ أن كافة الأزمنة الباقية هي أصغر منه، ولذلك نأخذ الأصغر منه مباشرة وهو زمن معالجة (أ) ومقداره (5) ويتم على الآلة رقم (2). ويتم وضع العمل (أ) الثاني في الترتيب. 

ــ نقارن زمن معالجة العمل (أ) على الآلة رقم (3) مع باقي الأزمنة على الآلة رقم (2) فنلاحظ أنها جميعها أصغر من زمن معالجة العمل (أ) على الآلة رقم (3) ومقداره (9) فنأخذ العمل الذي زمن معالجته أصغر مباشرة على الآلة رقم (2)، وهذا العمل هو (ج) وزمن المعالجة هو (4) على الآلة رقم (2) فيتم وضع العمل (ج) الثالث في الترتيب.

ــ يبقى العمل (د) أخيراً فنضعه الرابع في الترتيب، وبذلك نصل إلى الترتيب الأمثل، وكما في الجدول الآتي :

ومقدار الزمن الإجمالي لمعالجة الأعمال على الآلات الثلاث (43) يوم، وكما يتضح ذلك من مخططات جانت Gantt الشكل رقم (2H)

ت ـ خوارزمية كاسر 3 : قاعدة ترتيب (ن) عمل على (م) آلة Sequencing N jobs on machines

أن تسلسل الأعمال في هذه الحالة يأخذ الشكل الآتي :

تقوم هذه القاعدة على نفس إجراءات القاعدة (ب) شريطة أن تكون المقارنة بين أزمنة آخر آلة والآلة التي قبلها مباشرة .

مثال (11-7)

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

بتطبيق إجراءات القاعدة (ج) نلاحظ ما يلي :

• نبدأ بالعمل الذي يتطلب أقل زمن معالجة على الآلة رقم (1) شريطة أن يكون أقل من زمن المعالجة على الآلة الأخيرة آلة رقم (5) . وهنا نرى أن العمل الذي يحقق ذلك هو (ب) حيث زمن معالجته على الآلة رقم (1) هو (6) وعلى الآلة رقم (5) هو (10). نضعه في الترتيب أولاً ثم نقارن بين زمن معالجته على الآلة رقم (5) مع أزمنة المعالجة للأعمال الباقية على الآلة رقم (4) ونختار الأكبر مباشرة وهو زمن معالجة العمل (أ) ويساوي ،(11) فنختار العمل (أ) ويكون ترتيبه الثاني.

• نقارن بين زمن معالجة العمل (أ) على الآلة رقم (5) وأزمنة الأعمال المتبقية على الآلة رقم (4) ونختار الأكبر مباشرة. وإذا لم يوجد نختار الذي يساويه، ونلاحظ أنه العمل (د) حيث أن زمن معالجته على الآلة رقم (4) هو (12)، لذلك نضع العمل (د) الثالث في الترتيب.

• نقارن بين زمن معالجة العمل (د) على الآلة رقم (5) ، وأزمنة الأعمال المتبقية على الآلة رقم (4)، ونختار أكبرها مباشرة. وهنا لا يوجد فنأخذ العمل الذي زمن معالجته على الآلة (4) أصغر مباشرة ، وهو هنا العمل (ج) وزمن معالجته على الآلة رقم (4) هو (8) ونضع العمل (ج) الرابع في الترتيب.

بقي العمل الأخير وهو (هـ) نضعه في آخر الترتيب، ويصبح الترتيب المثالي على الشكل التالي: