جدولة خط الإنتاج

الموسوعة الحرة
لائحة ورشة التدفق

جدولة التدفق هي مسألة تحسين في علوم الحاسوب وبحوث العمليات ، وهي نوع من أنواع جدولة المهام المثلى . في مسألة جدولة المهام العامة، لدينا n مهمة J1 ، J2 ، ... ، Jn ذات أوقات معالجة متفاوتة، والتي يجب جدولتها على m آلة ذات قدرات معالجة متفاوتة، مع محاولة تقليل زمن الإنجاز الكلي - وهو المدة الإجمالية للجدولة (أي حتى انتهاء معالجة جميع المهام). في النوع المحدد المعروف باسم جدولة التدفق ، تحتوي كل مهمة على m عملية بالضبط. يجب تنفيذ العملية رقم i من المهمة على الآلة رقم i . لا يمكن لأي آلة تنفيذ أكثر من عملية واحدة في وقت واحد. لكل عملية من عمليات كل مهمة، يتم تحديد وقت التنفيذ.   

يُعدّ جدولة التدفق المتسلسل حالةً خاصةً من جدولة ورش العمل، حيث يُطبّق ترتيبٌ دقيقٌ لجميع العمليات على جميع الوظائف. ويمكن تطبيق جدولة التدفق المتسلسل على مرافق الإنتاج كما يُطبّق على تصميمات الحوسبة . ومن أنواع مسائل جدولة التدفق المتسلسل الخاصة مسألة جدولة التدفق المتسلسل التبادلية ، حيث يكون ترتيب معالجة الوظائف على الموارد هو نفسه في كل خطوة لاحقة من خطوات المعالجة.

في الترميز القياسي ذي الحقول الثلاثة لمسائل جدولة الوظائف المثلى ، يُرمز إلى متغير التدفق المتسلسل بالحرف F في الحقل الأول. على سبيل المثال، المسألة التي يُرمز إليها بـ " F3|صأناج{\displaystyle p_{ij}}|جالأعلى{\displaystyle C_{\max }}"هي مشكلة تدفق 3 آلات مع أوقات معالجة موحدة، حيث يكون الهدف هو تقليل الحد الأقصى لوقت الإنجاز."

التعريف الرسمي

يوجد m آلة و n مهمة. تحتوي كل مهمة على m عملية بالضبط . يجب تنفيذ العملية رقم i من المهمة على الآلة رقم i . لا يمكن لأي آلة تنفيذ أكثر من عملية واحدة في الوقت نفسه. يتم تحديد وقت تنفيذ كل عملية من عمليات كل مهمة.

يجب تنفيذ العمليات ضمن مهمة واحدة بالترتيب المحدد. تُنفذ العملية الأولى على الجهاز الأول، ثم (بعد انتهاء العملية الأولى) تُنفذ العملية الثانية على الجهاز الثاني، وهكذا حتى العملية رقم m . مع ذلك، يمكن تنفيذ المهام بأي ترتيب. تكمن المشكلة في تحديد الترتيب الأمثل، أي الترتيب الذي يحقق أقصر زمن إجمالي ممكن لتنفيذ جميع المهام.

قياسات أداء التسلسل (γ)

يمكن صياغة مشكلة التسلسل على أنها تحديد تسلسل S بحيث يتم تحسين هدف واحد أو عدة أهداف من أهداف التسلسل.

  1. متوسط ​​زمن التدفق،∑(wأنا)Fأنا{\displaystyle \sum (w_{i})F_{i}}
  2. مدة الإنجاز، C max
  3. (متوسط) التأخير،∑(wأنا)تيأنا{\displaystyle \sum (w_{i})T_{i}}
  4. ....

يمكن الاطلاع على مناقشة مفصلة لقياس الأداء في مالاكوتي (2013). [ 1 ]

تعقيد جدولة عمليات الإنتاج المتدفقة

كما قدم غاري وآخرون (1976)، [ 2 ] فإن معظم امتدادات مسائل جدولة تدفق الإنتاج هي مسائل صعبة من نوع NP، وقليل منها يمكن حله بشكل أمثل في O(nlogn)؛ على سبيل المثال، يمكن حل F2|prmu|C max بشكل أمثل باستخدام قاعدة جونسون . [ 3 ]

يوفر تايلارد مسائل معيارية جوهرية لجدولة ورش العمل المتدفقة، وورش العمل المفتوحة، وورش العمل الخاصة. [ 4 ]

طرق الحل

يمكن تصنيف الطرق المقترحة لحل مشاكل جدولة تدفق الإنتاج إلى خوارزميات دقيقة مثل التفرع والتقييد وخوارزميات استدلالية مثل الخوارزمية الجينية .

تقليل مدة الإنجاز، C max

يمكن حل F2|prmu|C max و F3|prmu|C max بشكل أمثل باستخدام قاعدة جونسون [ 3 ] ولكن في الحالة العامة لا توجد خوارزمية تضمن أمثلية الحل.

يحتوي خط الإنتاج المتدفق على n مهمة متاحة في وقت واحد عند الزمن صفر، ويتم معالجتها بواسطة آلتين موصولتين على التوالي مع مساحة تخزين غير محدودة بينهما. زمن معالجة جميع المهام معروف بدقة. المطلوب هو جدولة n مهمة على الآلات لتقليل زمن إنجاز جميع المهام. فيما يلي قاعدة جونسون لجدولة المهام في خط إنتاج متدفق مكون من آلتين.

في الجدول الأمثل، تسبق المهمة i المهمة j إذا كان الحد الأدنى لـ (p1i , p2j ) أقل من الحد الأدنى لـ (p1j , p2i ) . حيث يمثل p1i زمن معالجة المهمة i على الآلة 1، ويمثل p2i زمن معالجة المهمة i على الآلة 2. وبالمثل، يمثل p1j و p2j زمن معالجة المهمة j على الآلة 1 والآلة 2 على التوالي.

بالنسبة لخوارزمية جونسون:

لنفترض أن p 1j هو وقت معالجة المهمة j على الآلة 1
و p 2j هو وقت معالجة المهمة j على الآلة 2

خوارزمية جونسون:

  1. النموذج set1 الذي يحتوي على جميع الوظائف التي يكون فيها p 1j < p 2j
  2. بالنسبة للمجموعة الثانية التي تحتوي على جميع الوظائف التي يكون فيها p 1j > p 2j ، يمكن وضع الوظائف التي يكون فيها p 1j = p 2j في أي من المجموعتين.
  3. شكّل التسلسل كما يلي:
    (i) يتم تنفيذ الوظائف في المجموعة 1 أولاً في التسلسل ويتم تنفيذها بترتيب تصاعدي لـ p 1j (SPT)
    (ii) الوظائف في المجموعة 2 تتبع ترتيبًا تنازليًا لـ p 2j (LPT). يتم كسر التعادلات بشكل عشوائي.

يُشار إلى هذا النوع من الجداول الزمنية باسم جدول SPT(1)–LPT(2).

يقدم مالاكوتي (2013) مناقشة مفصلة لطرق الحل المتاحة. [ 1 ]

انظر أيضاً

مراجع

  1. 1 2 مالاكوتي، ب (2013). أنظمة العمليات والإنتاج ذات الأهداف المتعددة. جون وايلي وأولاده. ISBN 978-1-118-58537-5.
  2. ↑ غاري، إم آر؛ جونسون، دي إس؛ سيثي، رافي (1976). "تعقيد جدولة التدفقات وجدولات ورش العمل". رياضيات بحوث العمليات . 1 (2): 117-129 . doi : 10.1287/moor.1.2.117 .
  3. 1 2 جونسون، إس إم (1954). "جداول الإنتاج المثلى ذات المرحلتين والثلاث مراحل مع تضمين أوقات الإعداد". مجلة البحوث اللوجستية البحرية الفصلية . 1 (1): 61-68 . doi : 10.1002/nav.3800010110 .
  4. ↑ تايلارد، إي. (يناير 1993). "معايير مرجعية لمشاكل الجدولة الأساسية" . المجلة الأوروبية لبحوث العمليات . 64 (2): 278-285 . doi : 10.1016/0377-2217(93)90182-M .