2 - 4 - 12  تتابع N من الأعمال في ورشة تدفق لماكنتين : قاعدة جونسون  

Sequencing N Jobs On A Two-Machine Flow Shop: Johnson's Rule

ان ورشة التدفق الانسيابي (Flow Shop) في ورشة عمل تصل إليها عدة أعمال لها نفس المسار التشغيلي ، تكون جميعها جاهزة للمعالجة بنفس التتابع على ماكنتين أو مرکزي عمل متعاقبين ، حيث أن كل عمل يجب ان يُعالج أولاً على الماكنة الأولى ومن ثم على الماكنة الثانية ، وان تكون أوقات التشغيل أو المعالجة الفعلية أوالمتوقعة لكل عمل على كل ماكنة معروفة مسبقاً ، ففي الوقت الذي يكون وقت الإكمال الكلي (Makespan Time) عند جدولة ماكنة واحدة فقط هو نفسه بغض النظر عن القاعدة المختارة لتحديد تتابع الأعمال للمعالجة، فإنه في جدولة ماكنتين في ورشة تدفق فإن وقت الاكمال الكلي يختلف بإختلاف القاعدة المُستخدمة لتحديد التتابع ، لذلك يجب أن يكون هدف تحديد تتابع الأعمال على ماكنتين هو ايجاد التتابع الذي يقلل وقت الإكمال الكلي .

إن إيجاد التتابع الذي يقلل وقت الإكمال الكلى سيحقق :         

1 - إكمال مجموعة الأعمال بأقل وقت ممكن، وهو الوقت الذي تقضيه جميع الأعمال في ورشة التدفق منذ بدء معالجة العمل الأول وحتى إكمال العمل الأخير.          

2 ـ تعظيم مستوى الاستخدام لورشة التدفق المؤلفة من ماكنتين : حيث إن تقليل وقت الإكمال الكلي واستخدام الماكنة الأولى باستمرار لحين إكمال العمل الأخير سيقلل الوقت العاطل على الماكنة الثانية .   

3 - لقد طور جونسون (S . M . JOHNSON ) عام 1954 خوارزمية سميت بـ "قاعدة  جونسون" تساعد على إيجاد التتابع على ماكنتين  متتابعتين، إذ يتم بناء هذا التتابع من جهتيـن : من الأمام (اليمين) ومن الخلف (اليسار) باتجاه الوسط ، إن قاعدة جونسون تستنـد إلى افتراض وجود مجموعة معروفة من الأعمال ، لها مسارات تشغيلية متماثلة ،  ويجب أن ينجز العمل على الماكنة الأولى أولاً ثم على الماكنة الثانية، كل عمل منها له وقت تشغيل (معالجة) معروف على الماكنة، وأن يكون كل عمل متوفراً وجاهزاً لبدء المعالجة أو التشغيل على الماكنة الأولى . 

خطوات خوارزمية جونسون : هناك خمس خطوات يجب أن تُتبع عند استخدام خوارزمية جونسون لبناء التتابع الذي يقلل وقت الإكمال الكلي إلى أدنى ما يمكن، وهي : 

1- ادرج الأعمال، و أوقات التشغيل / المعالجة لكل عمل على الماكنة الأولى وعلى الماكنة الثانية.

2 - أوجد العمل الذي له اقصر وقت تشغيل/ معالجة على أي من الماكنتين من بين الأعمال التي لم تُجدول لحد الآن.

3 - إذا كان اقصر وقت للتشغيل يقع على الماكنة الأولى، ضع العمل المناظر له في التتابع المبكر أو الأول من اليمين (أي في مقدمة التتابع ولكن بعد أي عمل قد خُصص من قبل في مقدمة التابع)، وإذا كان هذا الوقت (الأقصر) يقع على الماكنة الثانية، ضع العمل المناظر له في التتابع الأخير من اليسار (أي في نهاية التتابع ولكن قبل أية أعمال أخرى قد خصصت من قبل في نهاية التتابع). وفي حالة تساوي وقت التشغيل لعمليـن على نفس الماكنة، يتم اختيار العمل الذي يقابله اقل وقت تشغيل على الماكنة الأخرى أولاً. أما إذا كان وقت التشغيل لعمل معين متساوٍ على كلا الماكنتين ، فيمكن عشوائياً وضعه في التتابـع المبكر (من اليمين) أو في التتابع الأخير (من اليسار). 

 4 - احذف العمل الذي يتم جدولته من المنافسة.         

5 - اعد الخطوات 2-4 للأعمال المتبقية التي لم تُجدول لحد الآن، على أن يتم بناء التتابع نحو الداخل مبتدأ من كلا طرفي التتابع حتى تُجدول جميع الأعمال. 

إن قاعدة جونسون تضع الأعمال التي لها اقصر الأوقات في الماكنة الأولى في بداية التتابع لكي تسمح باشتغال /انهماك الماكنة الثانية بالإنتاج بسرعة. وحالما تنتهي الماكنة الأولى من معالجة جميع الأعمال ، فان الأعمال التي تنتظر المعالجة على الماكنة الثانية تكون لها اقصر الأوقات لذلك يمكن تقليل وقت الإكمال الكلي إلى أدنى ما يمكن . وسيتم تطبيق قاعدة جونسون من خلال مثال محلول (12-2) وكما مبين في أدناه. 

مثال (12-2): تطبيق قاعدة جونسون :

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

المطلوب /

1 . تحديد تتابع الاعمال باستخدام قاعدة جونسون لتقليل وقت الاكمال الكلي والوقت العاطل .

2 . رسم خارطة جانت (Gantt Chart) لكل مركز عمل لتمثيل وقت الاكمال الكلي لكل عمل في المركزين .

الحـل :

1 ــ بتطبيق قاعدة جـونسون ، يكون الهدف اختيار التتابع الذي يقلل وقت الإكمال الكلي للأعمال وفقاً للخطوات الآتية :

1 . نبحث عن اقصر وقت تشغيل ، فنجد انه يعود للعمل B ويقع في مركز العمل الثاني (وقت التشغيل 2 ساعة). ولأن أقصر وقت تشغيل يقع في مركز العمل الثاني فأن العمل B يُجدول في نهاية التتابع ويُحذف من المنافسة القادمة : 

2 . نجد ان اقصر وقت تشغيل ثاني يعود للعمل E وهو (6) ساعات. ولكونه وقت تشغيل متساوً لنقص العمل في كلا مركزي العمل، فأننا نستطيع أن تختار عشوائياً وضعه أما في بداية التتابع أو في نهاية التتابع. دعنا نختار وضعه في بداية التتابع ومن ثم يُحذف من المنافسة القادمة

3. في الخطوة القادمة ، نجد أن العملين C , A متساويين بأقصر وقت تشغيل ثالث وهو (8) ساعات. ويقع العمل A في مركز العمل الأول ويقع العمل C في مركز العمل الثاني ، لذلك نضع العمل A في التتابع المبكر والعمل C في التتابع المتأخر .  

 4 . العمل الأخير الذي ينبغي أن يُجدول هو العمل D فيوضع في المركز المتبقي الأخير في وسط التتابع، وبذلك يصبح تتابع الأعمال كالآتي :   

وبذلك تكون أوقات التابع للأعمال الخمسة على مركزي العمل هي كالآتي:

2 ــ باستخدام خارطة جنت (Gantt chart) لتمثيل هذا التتابع كما مبينة في الشكل (11-2) يظهر إن وقت الاكمال الكلي للأعمال الخمسة قد بلغ (56) ساعة، وان الوقت العاطل لمركز العمل الثاني قد بلغ (10) ساعات (6+2+2 = 10 ساعات). وان مركز العمل الاول سيكون عاطلاً عن العمل بعد الساعة (54) اذا لم يستقبل اعمالاً اخرى جديدة . وان مركز العمل الثاني سيكون عاطلاً عن العمل بعد الساعة (56) اذا لم يستقبل اعمالاً اخرى جديدة .

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

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

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

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

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

المصفوفات الأساسية للخوارزميات المقترحة ( خـطوات إعـداد مـصفوفـة البـدء و أهميتـها)

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

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

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

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

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

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

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