جدولة ورش العمل

جدولة ورش العمل ، أو مشكلة ورش العمل ( JSP )، أو مشكلة جدولة ورش العمل ( JSSP ) ، هي مسألة تحسين في علوم الحاسوب وبحوث العمليات . وهي شكل من أشكال جدولة الوظائف المثلى . في مسألة جدولة الوظائف العامة، لدينا n وظيفة J1 _، J2 _، ... ، Jn ذات _أوقات معالجة متفاوتة، والتي يجب جدولتها على m آلة ذات قدرات معالجة متفاوتة، مع محاولة تقليل زمن الإنجاز الكلي - _وهو المدة الإجمالية للجدولة (أي حتى انتهاء معالجة جميع الوظائف). في الشكل المحدد المعروف باسم جدولة ورش العمل ، تتكون كل وظيفة من مجموعة من العمليات O1 _، O2 _، ... ، On التي يجب معالجتها بترتيب محدد (يُعرف بقيود الأسبقية ). لكل عملية آلة محددة يجب معالجتها عليها، ولا يمكن معالجة سوى عملية واحدة في الوظيفة في وقت معين . ومن أساليب التخفيف الشائعة ورشة العمل المرنة ، حيث يمكن معالجة كل عملية على أي آلة من مجموعة معينة (الآلات في كل مجموعة متطابقة).      

استُمدّ الاسم في الأصل من جدولة المهام في ورشة عمل ، لكنّ هذا المفهوم له تطبيقات واسعة تتجاوز هذا النوع من الحالات. وهو مسألة معروفة في مجال التحسين التوافقي، وكان أول مسألة تخضع للتحليل التنافسي ، الذي قدّمه غراهام عام 1966. ^{[ 1 ]} وتُعزى أفضل حالات هذه المسألة، لنموذج أساسي ذي هدف زمني، إلى تايلارد. ^{[ 2 ]}

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

توجد العديد من الاختلافات في هذه المشكلة، بما في ذلك ما يلي:

• يمكن أن تحتوي الآلات على نسخ مكررة (ورشة عمل مرنة مع آلات مكررة) أو أن تنتمي إلى مجموعات من الآلات المتطابقة (ورشة عمل مرنة). ^{[ 3 ]}
• قد تتطلب الآلات فترة فاصلة معينة بين المهام أو عدم وجود وقت ضائع.
• يمكن أن تحتوي الآلات على إعدادات تعتمد على التسلسل.
• يمكن أن تكون دالة الهدف هي تقليل وقت الإنجاز، ومعيار L _p ، والتأخير، وأقصى تأخير ، وما إلى ذلك. ويمكن أن تكون أيضًا مشكلة تحسين متعددة الأهداف.
• يجب إنجاز بعض المهام قبل البدء في مهام أخرى (انظر سير العمل )، وقد تتضمن الأهداف معايير متعددة. ^{[ 4 ]}
• يمكن أن ترتبط مجموعة من الوظائف بمجموعة مختلفة من الآلات.
• أوقات معالجة حتمية (ثابتة) أو أوقات معالجة احتمالية.

بما أن مسألة البائع المتجول هي مسألة صعبة من نوع NP ، فإن مسألة ورشة العمل ذات الإعداد المعتمد على التسلسل هي أيضاً مسألة صعبة من نوع NP، لأن مسألة البائع المتجول هي حالة خاصة من مسألة ورشة العمل ذات وظيفة واحدة (البائع في مسألة البائع المتجول) والآلات (المدن في مسألة البائع المتجول). ^{[ 5 ]}

يُعد الرسم البياني الانفصالي ^{[ 6 ]} أحد النماذج الشائعة المستخدمة لوصف حالات مشكلة جدولة ورش العمل. ^{[ 7 ]}

يمكن صياغة المسألة رياضياً على النحو التالي:

يترك${\displaystyle M=\{M_{1},M_{2},\dots ,M_{m}\}}$و${\displaystyle J=\{J_{1},J_{2},\dots ,J_{n}\}}$لنفترض أن لدينا مجموعتين منتهيتين . ونظرًا للأصول الصناعية لهذه المسألة، فإن${\displaystyle \displaystyle M_{i}}$تُسمى هذه الآلات و${\displaystyle \displaystyle J_{j}}$تُسمى هذه الوظائف .

يترك${\displaystyle \displaystyle \ {\mathcal {X}}}$تشير إلى مجموعة جميع عمليات التخصيص المتسلسلة للوظائف للآلات، بحيث يتم تنفيذ كل وظيفة بواسطة كل آلة مرة واحدة فقط؛ العناصر${\displaystyle x\in {\mathcal {X}}}$يمكن كتابتها على النحو التالي${\displaystyle n\times m}$المصفوفات، في أي عمود${\displaystyle \displaystyle i}$يعرض قائمة بالمهام التي تقوم بها الآلة${\displaystyle \displaystyle M_{i}}$سوف يفي بالغرض، بالترتيب. على سبيل المثال، المصفوفة

${\displaystyle x={\begin{pmatrix}1&2\\2&3\\3&1\end{pmatrix}}}$

يعني ذلك أن الآلة${\displaystyle \displaystyle M_{1}}$سيقوم بالوظائف الثلاث${\displaystyle \displaystyle J_{1},J_{2},J_{3}}$بالترتيب${\displaystyle \displaystyle J_{1},J_{2},J_{3}}$، بينما الآلة${\displaystyle \displaystyle M_{2}}$سوف يتم إنجاز المهام بالترتيب${\displaystyle \displaystyle J_{2},J_{3},J_{1}}$.

لنفترض أيضاً أن هناك دالة تكلفة ما${\displaystyle C:{\mathcal {X}}\to [0,+\infty ]}$يمكن تفسير دالة التكلفة على أنها "إجمالي وقت المعالجة"، وقد يكون لها تعبير ما بدلالة الأوقات.${\displaystyle C_{ij}:M\times J\to [0,+\infty ]}$، تكلفة/وقت الآلة${\displaystyle \displaystyle M_{i}}$للقيام بالعمل${\displaystyle \displaystyle J_{j}}$.

تتمثل مشكلة ورشة العمل في إيجاد توزيع للوظائف${\displaystyle x\in {\mathcal {X}}}$بحيث${\displaystyle \displaystyle C(x)}$هو الحد الأدنى، أي أنه لا يوجد${\displaystyle y\in {\mathcal {X}}}$بحيث${\displaystyle \displaystyle C(x)>C(y)}$.

يمكن تعريف كفاءة الجدولة لجدول زمني من خلال نسبة إجمالي وقت خمول الآلة إلى إجمالي وقت المعالجة كما يلي:

${\displaystyle C'=1+{\sum _{i}l_{i} \over \sum _{j,k}p_{jk}}={C.m \over \sum _{j,k}p_{jk}}}$

أين${\displaystyle l_{i}}$يمثل وقت الخمول للآلة i ، وC هو زمن إنجاز جميع العمليات، و m هو عدد الآلات. تعمل هذه الصيغة على توحيد زمن إنجاز جميع العمليات بناءً على عدد الآلات وإجمالي وقت المعالجة، مما يسمح بمقارنة استخدام الموارد عبر حالات جدولة ورش العمل (JSP) ذات الأحجام المختلفة. ^{[ 8 ]}

إحدى المشكلات الأولى التي يجب معالجتها في مسألة جدولة الوظائف هي أن العديد من الحلول المقترحة لها تكلفة لا نهائية: أي، يوجد${\displaystyle x_{\infty }\in {\mathcal {X}}}$بحيث${\displaystyle C(x_{\infty })=+\infty }$في الواقع، من السهل جدًا اختلاق أمثلة على ذلك.${\displaystyle x_{\infty }}$من خلال ضمان حدوث حالة جمود بين جهازين ، بحيث ينتظر كل منهما مخرجات الخطوة التالية للجهاز الآخر.

قدّم غراهام خوارزمية جدولة القوائم عام 1966، وهي خوارزمية تنافسية من الدرجة (2 − 1/m)، حيث m هو عدد الآلات. ^{[ 1 ]} وقد ثبت لاحقًا أنها الخوارزمية المثلى للتشغيل الفوري على آلتين وثلاث آلات. كما أن خوارزمية كوفمان-غراهام (1972) للوظائف ذات الطول الموحد هي أيضًا خوارزمية مثلى لآلتين وتنافسية من الدرجة (2 − 2/m). ^{[ 9 ] [ 10 ]}

في عام 1992، قدم بارتال وفيات وكارلوف وفوهرا خوارزمية تنافسية بنسبة 1.986، ^{[ 11 ]} تلتها خوارزمية تنافسية بنسبة 1.945 من قبل كارغر وفيليبس وتورنغ في عام 1994. ^{[ 12 ]} وفي العام نفسه، قدم ألبرز خوارزمية تنافسية مختلفة بنسبة 1.923. ^{[ 13 ]} أما النتيجة الأكثر شهرة فهي تلك التي حققها فليشر ووال، بنسبة تنافسية بلغت 1.9201. ^{[ 14 ]}

كما حدد ألبرز حدًا أدنى قدره 1.852. ^{[ 15 ]} تلعب حالات تايلارد دورًا رئيسيًا في تطوير جدولة ورش العمل بهدف تقليل وقت الإنجاز.

في عام 1976، أثبت غاري أن هذه المشكلة هي NP-كاملة لـ m > 2، مما يعني أنه لا يمكن حساب الحل الأمثل في وقت متعدد الحدود إلا إذا كان P=NP . ^{[ 16 ]}

في عام 2011، قدم شين تشين وآخرون خوارزميات مثلى للجدولة عبر الإنترنت على جهازين مرتبطين، مما أدى إلى تحسين النتائج السابقة. ^{[ 17 ] [ 18 ]}

استُخدمت تقنيات التعلّم الآلي مؤخرًا للتنبؤ بالمدة الزمنية المثلى لإنجاز مهمة JSP دون الحاجة إلى إنتاج الجدول الزمني الأمثل فعليًا. ^{[ 8 ]} تُظهر النتائج الأولية دقة تصل إلى 80% في تصنيف مهام JSP الصغيرة المُولّدة عشوائيًا بناءً على كفاءة الجدولة المثلى باستخدام التعلّم الخاضع للإشراف.

فيما يلي مثال على مشكلة جدولة ورش العمل المصاغة في لغة AMPL كمشكلة برمجة عددية مختلطة مع قيود مؤشرية:

param N_JOBS ; param N_MACHINES ;قم بتعيين ترتيب الوظائف من 1 إلى عدد الوظائف ( N_JOBS )؛ وقم بتعيين ترتيب الآلات من 1 إلى عدد الآلات (N_MACHINES )؛param ProcessingTime { JOBS , MACHINES } > 0 ;param CumulativeTime { i in JOBS , j in MACHINES } = sum { jj in MACHINES : ord ( jj ) <= ord ( j )} ProcessingTime [ i , jj ];param TimeOffset { i1 in JOBS , i2 in JOBS : i1 <> i2 } = max { j in MACHINES } ( CumulativeTime [ i1 , j ] - CumulativeTime [ i2 , j ] + ProcessingTime [ i2 , j ]);نهاية فار >= 0 ; فار البداية { JOBS } >= 0 ; فار يسبق { i1 في JOBS ، i2 في JOBS : ord ( i1 ) < ord ( i2 )} ثنائي ؛تقليل مدة التنفيذ : نهاية ؛subj to makespan_def { i in JOBS }: end >= start [ i ] + sum { j in MACHINES } ProcessingTime [ i , j ];subj to no12_conflict { i1 in JOBS , i2 in JOBS : ord ( i1 ) < ord ( i2 )}: precedes [ i1 , i2 ] ==> start [ i2 ] >= start [ i1 ] + TimeOffset [ i1 , i2 ];subj to no21_conflict { i1 in JOBS , i2 in JOBS : ord ( i1 ) < ord ( i2 )}: ! precedes [ i1 , i2 ] ==> start [ i1 ] >= start [ i2 ] + TimeOffset [ i2 , i1 ];بيانات ؛param N_JOBS : = 4 ; param N_MACHINES : = 4 ;param ProcessingTime : 1 2 3 4 : = 1 5 4 2 1 2 8 3 6 2 3 9 7 2 3 4 3 1 5 8 ;

• يُعد جدولة التدفق مشكلة مماثلة ولكن بدون القيد المتمثل في وجوب تنفيذ كل عملية على آلة محددة (يتم الاحتفاظ فقط بقيد الترتيب).
• يُعد جدولة المتجر المفتوح مشكلة مماثلة ولكن بدون قيد الترتيب.

• دليل جامعة فيينا للمنهجيات والأنظمة والبرامج الخاصة بالتحسين الديناميكي.
• حالات تايلارد
• بروكر ب. جدولة الخوارزميات . هايدلبرغ، سبرينغر. الطبعة الخامسة. رقم ISBN 978-3-540-24804-0