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

Question

نظرة عامة

تصنيع العملية (على النقيض من التصنيع المنفصل) يركز على إنتاج البضائع المستمرة مثل النفط. التخطيط عادة ما يكون قابل للحل عن طريق البرمجة الخطية، ويمكن تقديم القيود التي يمكن تقديمها لبلدام ميل.

صياغة المشكلة

تتكون المشكلة من

• تسلسل فترات زمنية متتالية $ t \ in \ {1، \ dots، n_t \} $ ، كل مع بداية ونهاية $ (s_t، e_t) $ وطول $ l_t= e_t-s_t $ . الوسائل المتتالية $ e_ {t}= s_ {t + 1} $ لجميع $ t \ in \ {1، \ النقاط، N_T-1 \} $ .
• قائمة من النوع من السلع التي يتم إنتاجها: $ j \ in \ {1، ...، n_j \} $
• طلب كل نوع من أنواع جيدة في الوقت الفاصل الزمني $ d_ {j، t} $ .
• قائمة خطوط الإنتاج $ i \ в {1، \ dots، n_i} $
• توفر خطوط الإنتاج في الوقت الفاصل الزمني $ a_ {i، t} $ . $ a_ {i، t} $ هي ثنائية - سواء كانت متاحة أم لا.
• سرعة التصنيع لكل خط إنتاج لكل السلع $ v_ {i، j} $ .
• وقت الإعداد من نوع واحد من السلع إلى أخرى $ {j، j '} $ .
• السعر لاستخدام خط الإنتاج (التأجير المستندة إلى التأجير)، عد في الدقيقة $ c_ {i} $

الهدف هو التخطيط لخطوط الإنتاج حتى يتم تغطية الطلب وسعر التأجير ضئيل.

ملاحظات:

• يمكن أن يكون وقت الإعداد أقصر أو أطول أو يساوي طول الفواصل الزمنية
• من المقبول أن خط الإنتاج لن يعمل الفاصل الزمني طوال الوقت إذا تم اكتمال العرض عاجلا
• يمكن أن يبدأ الإعداد إلى إنتاج جيد آخر في أي وقت، وليس بالضرورة في بداية الفاصل الزمني.

مثال

هناك خطين إنتاج، أي، $ n_i= 2 دولار وهناك نوعان من السلع، أي $ n_j= 2 دولار .

لدينا فواصل زمنية، I.E. $ n_t= 2 $ ، كل منها لديه جدد من ساعة واحدة. قل أن المرء يبدأ في الساعة 1 مساء، والثاني في الساعة 2 مساء.

الطلب هو:

• $ d_ {1،1}= 1.1 $
• $ d_ {1،2}= 1 $
• $ d_ {2،1}= 1 $
• $ d_ {2،2}= 0.5 $

تشغيل خطوط الإنتاج هي:

• $ c_ {1}= c_ {2}= 1 $ USD / دقيقة

جميع أوقات الإعداد الممكنة هي 30 دقيقة، I.E.:

• li> $ {j، j '}= 0.5 $ لجميع $ j، j' $ حيث $ j \ neq j '$ .

السرعات هي:

• $ v_ {1،1}= 1.1 $
• $ v_ {1،2}= 1.5 $
• $ v_ {2،1}= 1 $
• $ v_ {2،2}= 1 $

من الواضح أنه يتم استيفاء الطلب إذا كان السطر الأول ينتج النوع الأول من البضائع في كلا الفواصل الزمنية والخط الثاني ينتج النوع الثاني. التكلفة 204.55. انظر الحل هنا:

ومع ذلك، قد يكون من المغري تبديلها. الخط 1 هو أكثر كفاءة بكثير للنوع الثاني من البضائع (1.5). إذا لم يكن هناك وقت الإعداد، فسنحصل على التكلفة 180 دولار أمريكي. ومع ذلك، هذا غير ممكن.

السؤال

ما هي الخوارزمية لجدولة عملية التصنيع هذه على النحو الأمثل؟

إجابة موضع ترحيب حتى لو كانت ستقوم بتحديد الطريقة والنهج (MILP، SAT، CSP، ...).

الأفكار فيرا

• إذا تم إصلاح طول الفواصل الزمنية، فسيقول 1 ساعة وسيتم تعريف وقت الإعداد من حيث هذه الوحدات، كما يقول 2 ساعة. بعد ذلك، قد يكون من قيلولة SAT / CSP.
• فكرة هي استخدام خوارزمية تطورية من شأنها أن: تتكون من سلسلة من الأنشطة مع الطفرات (إضافة نشاط، حذف النشاط، نشاط إطالة) و CrossOver (مزيج خطين بطريقة عشوائية).

Answer 1

نحن نستخدم الفهرس $ k $ للوقت مثل $ k \ in [s_1، e_ {n_t}] $

نقدم المتغيرات التالية:

$ \ ell ^ {i، k} $ - خط $ i $ $ مستأجرة في الخط $ k $

$ \ alpha ^ {i، k} _ {j، j '} $ - مؤشر ثنائي للخط $ I $ هو التبديل من $ J إلى $ J '$ في وقت $ K $ .

$ p ^ {i، k} _j $ - مؤشر ثنائي للخط $ i $ $ هو إنتاج جيدة $ J في الوقت $ k $ .

$ h ^ {i،} _j $ - المؤشر الثنائي الذي الخط $ I $ هو في انتظار إنتاج جيدة $ J $ في الوقت $ k $

$ g ^ {i، k} _j $ - كمية الناتجة عن الخط $ i $ $ for جيد $ J $ في الوقت $ k $ (إما $ v_ {i، j} $ أو $ 0 $ )

ثم الهدف هو تقليل $ \ sum_ {i، k} c_i \ ell ^ {i، k} $ عرضة للقيود:

قيود لكل $ i، k $ :

• يمكن فقط التبديل إلى 1 جيد في وقت واحد: $ \ textrm {at-mond-1} \ alpha ^ {i، k} _ {j، j '} $ < / span>
• يمكن فقط جعل 1 جيد في وقت واحد: $ \ textrm {at-mond-1} p ^ {i، k} _j $
• يمكن أن تعقد فقط ل 1 جيد في وقت واحد: $ \ textrm {at-mond-1} h ^ {i، k} _j $
• إذا إنتاج، لا تبديل: $ \ bigvee_j p ^ {i، k} _j \ rawrow \ neg \ bigwedge_ {j، j '} \ alpha ^ {i، k} _ {J، J '} $
• استئجار IFF المنتجة أو التبديل: $ \ ell ^ {i، k} \ leftrightrow \ bigvee_ {j، j '} \ alpha ^ {i، k} _ {j، J '} \ Vee \ bigvee_j p ^ {i، k} _j $
• لا تتضمن التأجير تعقد بعضها جيدا: $ \ neg \ ell {i، k} \ rawrow \ bigvee_j h ^ {i، k} _j $ < / لى>

containts لكل $ i، k، j $ :

• توليد فقط إذا تم إنتاج: $$ p ^ {i، k} _j \ charearrow g ^ {i، k} _j= v_ {i،} $$ $$ \ neg p ^ {i، k} _j \ charearrow g ^ {i، k} _j= 0 $
• عند إيقاف الإنتاج، يجب أن تعقد على الفور لنفس جيد أو التبديل إلى جيد آخر (ل $ k ): $ p ^ ^ {i، k} _j \ wedge \ neg p ^ {i، k + 1} _j \ rawrow h ^ {i، k + 1} _j \ vee \ bigvee_ { J '} \ Alpha ^ {I، K + 1} _ {J، J'} $
• إذا كان إنتاج أو عقد في يجب أن تكون $ k + 1 $ قد تم إنتاجها أو عقد أو تبديل في $ k < E_ {n_t} $ : $ p ^ {i، k + 1} _j \ vee h ^ {i، k + 1} _j \ charearrow p ^ {i، k} _j \ vee h ^ {i، ك} _j \ vee \ bigvee_ {j '} \ alpha ^ {i، k} _ {j'، j} $

قيود لكل $ i، k :

• عند التبديل، يجب أن تبديل فترة طويلة بما فيه الكفاية: $ (p ^ {i، k} _j \ vee h ^ {i، k} _j) \ wedge \ alpha ^ {i، k + 1} _ {j، j '} \ rawrow \ bigwedged_ {k '= k + 2} ^ {\ min (k + _ {j، j'}، e_ {n، t})} \ alpha ^ {i، k '} _ {j، j' } $

قيود لكل $ d_ {j، t} $ :

• $ \ sum_ {k= s_t} ^ {e_t} \ sum_i g ^ {i، k} _j \ geq d_ {j، t} $