جدولة العمل الأمثل

📅 آخر تحديث: ٢٩ يوليو ٢٠٢٦
✍️ نُشر في: ٢٩ يوليو ٢٠٢٦
📷 يحتوي على 69 صور
الموسوعة الحرة

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

تتعدد مسائل جدولة المهام المثلى، وتختلف في طبيعة المهام، وطبيعة الآلات، والقيود المفروضة على الجدول الزمني، ودالة الهدف. وقد قدم رونالد غراهام ، ويوجين لولر ، ويان كاريل لينسترا ، وألكسندر رينوي كان، تدوينًا ملائمًا لمسائل الجدولة المثلى . [ 1 ] [ 2 ] يتكون هذا التدوين من ثلاثة حقول: α ​​و β و γ . يمكن أن يكون كل حقل قائمة من الكلمات مفصولة بفواصل. يصف الحقل α بيئة الآلة، و β خصائص المهمة وقيودها، و γ دالة الهدف. [ 3 ] منذ تقديمه في أواخر سبعينيات القرن الماضي، شهد هذا التدوين توسعًا مستمرًا، وأحيانًا بشكل غير متسق. ونتيجة لذلك، تظهر اليوم بعض المسائل بتدوينات مختلفة في العديد من الأبحاث.

الوظائف أحادية المرحلة مقابل الوظائف متعددة المراحل

في مسائل جدولة المهام المثلى الأبسط، تتكون كل مهمة j من مرحلة تنفيذ واحدة، مع وقت معالجة محدد p j . أما في المتغيرات الأكثر تعقيدًا، فتتكون كل مهمة من عدة مراحل تنفيذ، والتي يمكن تنفيذها بالتتابع أو بالتوازي.

بيئات الآلات

في مشاكل جدولة المهام أحادية المرحلة ، توجد أربع فئات رئيسية من بيئات الآلات:

  • 1 : جدولة الآلة الواحدة . توجد آلة واحدة فقط.
  • P : جدولة الآلات المتطابقة . هناكم{\displaystyle m}الآلات المتوازية، وهي متطابقة. وظيفةج{\displaystyle j}يستغرق الأمر وقتاًصج{\displaystyle p_{j}}على أي جهاز مُجدول له.
  • س : جدولة الآلات الموحدة . هناكم{\displaystyle m}آلات متوازية، ولها سرعات محددة مختلفة. وظيفةج{\displaystyle j}على الجهازأنا{\displaystyle i}يستغرق الأمر وقتاًصج/sأنا{\displaystyle p_{j}/s_{i}}.
  • R : جدولة الأجهزة غير المرتبطة . هناكم{\displaystyle m}الآلات المتوازية، وهي غير مرتبطة ببعضها – جوبج{\displaystyle j}على الجهازأنا{\displaystyle i}يستغرق الأمر وقتاًصأناج{\displaystyle p_{ij}}.

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

في مشاكل جدولة المهام متعددة المراحل ، توجد خيارات أخرى لبيئات الآلات:

  • O : مشكلة المتجر المفتوح . كل وظيفةج{\displaystyle j}يتكون منم{\displaystyle m}العملياتياأناج{\displaystyle O_{ij}}لأنا=1،...،م{\displaystyle i=1,\ldots ,m}يمكن جدولة العمليات بأي ترتيب. العمليةياأناج{\displaystyle O_{ij}}يجب معالجة ذلك من أجلصأناج{\displaystyle p_{ij}}الوحدات الموجودة على الآلةأنا{\displaystyle i}.
  • F : مشكلة التدفق في خط الإنتاج . كل وظيفةج{\displaystyle j}يتكون منم{\displaystyle m}العملياتياأناج{\displaystyle O_{ij}}لأنا=1،...،م{\displaystyle i=1,\ldots ,m}يتم تحديد مواعيدها بالترتيب المذكور . العمليةياأناج{\displaystyle O_{ij}}يجب معالجة ذلك من أجلصأناج{\displaystyle p_{ij}}الوحدات الموجودة على الآلةأنا{\displaystyle i}.
  • ج : مشكلة ورش العمل . كل وظيفةج{\displaystyle j}يتكون مننج{\displaystyle n_{j}}العملياتياكج{\displaystyle O_{kj}}لك=1،...،نج{\displaystyle k=1,\ldots ,n_{j}}، على أن يتم تحديد مواعيدها بهذا الترتيب. العمليةياكج{\displaystyle O_{kj}}يجب معالجة ذلك من أجلصكج{\displaystyle p_{kj}}وحدات على جهاز مخصصμكج{\displaystyle \mu _{kj}}معμكج≠μك′ج{\displaystyle \mu _{kj}\neq \mu _{k'j}}لك≠ك′{\displaystyle k\neq k'}.

خصائص الوظيفة

يُفترض أن جميع أوقات المعالجة أعداد صحيحة. مع ذلك، في بعض الأبحاث القديمة، يُفترض أنها أعداد نسبية.

  • صأنا=ص{\displaystyle p_{i}=p}، أوصأناج=ص{\displaystyle p_{ij}=p}: وقت المعالجة متساوٍ لجميع المهام.
  • صأنا=1{\displaystyle p_{i}=1}، أوصأناج=1{\displaystyle p_{ij}=1}: وقت المعالجة يساوي وحدة زمنية واحدة لجميع المهام.
  • رج{\displaystyle r_{j}}: يتم تحديد وقت إصدار لكل مهمة لا يمكن جدولتها قبله، والقيمة الافتراضية هي 0.
  • متصل-رج{\displaystyle {\text{online-}}r_{j}}مشكلة عبر الإنترنت. تُعلن الوظائف عند نشرها. انظر جدولة الوظائف عبر الإنترنت .
  • دج{\displaystyle d_{j}}يُحدد لكل مهمة تاريخ استحقاق. الفكرة هي أن تُنجز كل مهمة قبل تاريخ استحقاقها، وهناك غرامة على المهام المتأخرة. تُحدد هذه الغرامة في قيمة الهدف. وجود خصائص المهمةدج{\displaystyle d_{j}}يُفترض ذلك ضمنيًا ولا يُشار إليه في اسم المسألة، إلا إذا كانت هناك بعض القيود، على سبيل المثالدج=د{\displaystyle d_{j}=d}، بافتراض أن جميع مواعيد الاستحقاق تساوي تاريخًا معينًا.
  • د¯ج{\displaystyle {\bar {d}}_{j}}يُحدد لكل مهمة موعد نهائي صارم. يجب إنجاز كل مهمة قبل الموعد النهائي المحدد.
  • pmtn : يمكن إيقاف المهام مؤقتًا واستئنافها، ربما على جهاز آخر. ويُشار إليها أحيانًا بالرمز ' prmp'.'.
  • مقاسج{\displaystyle {\text{size}}_{j}}تأتي كل مهمة بعدد من الأجهزة التي يجب جدولة تنفيذها عليها في نفس الوقت. القيمة الافتراضية هي 1. هذا مُعامل مهم في نوع جدولة المهام المتوازية .

علاقات الأسبقية

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

  • prec : لا توجد قيود مفروضة على علاقات الأسبقية.
  • السلاسل : كل وظيفة هي سابقة لوظيفة واحدة أخرى على الأكثر، وتسبقها وظيفة واحدة أخرى على الأكثر.
  • الشجرة: يجب أن تستوفي علاقات الأسبقية أحد القيدين.
    • intree: كل عقدة هي سلف لوظيفة واحدة أخرى على الأكثر.
    • الشجرة الخارجية: تسبق كل عقدة مهمة واحدة أخرى على الأكثر.
  • الغابة المتعارضة: إذا تم تقسيم الرسم البياني لعلاقات الأسبقية إلى مكونات متصلة ، فإن كل مكون متصل يكون إما شجرة داخلية أو شجرة خارجية.
  • الرسم البياني sp: الرسم البياني لعلاقات الأسبقية هو رسم بياني متوازي متسلسل .
  • الارتفاع المحدود : يتم تحديد طول أطول مسار موجه بقيمة ثابتة. (المسار الموجه هو سلسلة من المهام حيث تكون كل مهمة، باستثناء الأخيرة، سابقة للمهمة التالية في السلسلة).
  • ترتيب المستويات : لكل وظيفة مستوى، وهو طول أطول مسار موجه يبدأ من تلك الوظيفة. كل وظيفة ذات مستوىك{\displaystyle k}يُعدّ سلفًا لكل وظيفة ذات مستوىك-1{\displaystyle k-1}.
  • ترتيب الفترات : كل مهمةx{\displaystyle x}له فترة [ s( x , e( x )) ووظيفةx{\displaystyle x}وهو سلف لـy{\displaystyle y}إذا وفقط إذا كانت نهاية فترةx{\displaystyle x}أقل تمامًا من بداية الفترة لـy{\displaystyle y}.=

في حال وجود علاقة أسبقية، يمكن افتراض وجود فترات تأخير . فترة التأخير بين مهمتين هي مقدار الوقت الذي يجب انتظاره بعد اكتمال المهمة الأولى قبل بدء المهمة الثانية. بعبارة أخرى، إذا كانت المهمة i تسبق المهمة j، فإنجأنا+ℓأناج≤Sج{\displaystyle C_{i}+\ell _{ij}\leq S_{j}}يجب أن يكون ذلك صحيحاً. إذا لم يكن هناك تأخير زمنيℓأناج{\displaystyle \ell _{ij}}إذا تم تحديد قيمة معينة، يُفترض أنها صفر. يمكن أن تكون فترات التأخير سالبة أيضًا. تعني فترة التأخير السالبة أن المهمة الثانية يمكن أن تبدأ قبل وقت محدد من انتهاء المهمة الأولى.

  • ℓ : يكون التأخير الزمني هو نفسه لكل زوج من المهام.
  • ℓأناج{\displaystyle \ell _{ij}}قد تختلف فترات التأخير بين أزواج الوظائف المختلفة.

تأخيرات في النقل

  • تجك{\displaystyle t_{jk}}بين اكتمال العمليةياكج{\displaystyle O_{kj}}وظيفةج{\displaystyle j}على الجهازك{\displaystyle k}وبدء العمليةياك+1،ج{\displaystyle O_{k+1,j}}وظيفةج{\displaystyle j}على الجهازك+1{\displaystyle k+1}هناك تأخير في النقل لا يقل عنتجك{\displaystyle t_{jk}}وحدات.
  • تجكل{\displaystyle t_{jkl}}بين اكتمال العمليةياكج{\displaystyle O_{kj}}وظيفةج{\displaystyle j}على الجهازك{\displaystyle k}وبدء العمليةيال،ج{\displaystyle O_{l,j}}وظيفةج{\displaystyle j}على الجهازل{\displaystyle l}هناك تأخير في النقل لا يقل عنتجكل{\displaystyle t_{jkl}}وحدات.
  • تك{\displaystyle t_{k}}تأخير النقل المرتبط بالآلة. بين إتمام العمليةياكج{\displaystyle O_{kj}}وظيفةج{\displaystyle j}على الجهازك{\displaystyle k}وبدء العمليةياك+1،ج{\displaystyle O_{k+1,j}}وظيفةج{\displaystyle j}على الجهازك+1{\displaystyle k+1}هناك تأخير في النقل لا يقل عنتك{\displaystyle t_{k}}وحدات.
  • تكل{\displaystyle t_{kl}}تأخير النقل الذي يعتمد على زوج الآلات. بين اكتمال العمليةياكج{\displaystyle O_{kj}}وظيفةج{\displaystyle j}على الجهازك{\displaystyle k}وبدء العمليةيال،ج{\displaystyle O_{l,j}}وظيفةج{\displaystyle j}على الجهازل{\displaystyle l}هناك تأخير في النقل لا يقل عنتكل{\displaystyle t_{kl}}وحدات.
  • تج{\displaystyle t_{j}}تأخير في النقل مرتبط بالوظيفة. بين إتمام العمليةياكج{\displaystyle O_{kj}}وظيفةج{\displaystyle j}على الجهازك{\displaystyle k}وبدء العمليةيال،ج{\displaystyle O_{l,j}}وظيفةج{\displaystyle j}على الجهازل{\displaystyle l}هناك تأخير في النقل لا يقل عنتج{\displaystyle t_{j}}وحدات.

قيود متنوعة

  • rcrc : يُعرف أيضًا باسم إعادة التدوير أو ورشة العمل المرنة. الوعد علىμ{\displaystyle \mu }يتم رفعها وبالنسبة لبعض الأزواجك≠ك′{\displaystyle k\neq k'}ربما كان لديناμكج=μك′ج{\displaystyle \mu _{kj}=\mu _{k'j}}بمعنى آخر، من الممكن إسناد عمليات مختلفة لنفس المهمة إلى نفس الآلة.
  • بدون انتظار : العمليةياك+1،أنا{\displaystyle O_{k+1,i}}يجب أن تبدأ العملية بالضبط عند بدء التشغيلياك،أنا{\displaystyle O_{k,i}}يكتمل. بمعنى آخر، بمجرد انتهاء عملية من عملية ما، يجب أن تبدأ العملية التالية فورًا. ويُشار إليها أحيانًا بـ " nwt" .
  • لا يوجد وضع الخمول : لا يجوز لأي آلة أن تكون خاملة بين بداية تنفيذها الأول ونهاية تنفيذها الأخير.
  • مقاسج{\displaystyle {\text{size}}_{j}}: تنفيذ مهام متعددة المعالجات على أجهزة متوازية متطابقة. تنفيذ المهمةج{\displaystyle j}يتم ذلك في نفس الوقتمقاسج{\displaystyle {\text{size}}_{j}}الآلات المتوازية.
  • يصلحج{\displaystyle {\text{fix}}_{j}}مهام المعالجات المتعددة. كل وظيفةج{\displaystyle j}يتم توفيرها مع مجموعة من الآلاتيصلحج⊆{1،...،م}{\displaystyle {\text{fix}}_{j}\subseteq \{1,\ldots ,m\}}ويحتاج إلى كل هذه الآلات في آن واحد للتنفيذ. ويُشار إليه أحيانًا بالرمز "MPT".
  • مج{\displaystyle M_{j}}آلات متعددة الأغراض. لكل مهمةج{\displaystyle j}يجب جدولة ذلك على جهاز واحد من مجموعة معينةمج⊆{1،...،م}{\displaystyle M_{j}\subseteq \{1,\ldots ,m\}}ويُشار إليه أحيانًا بالرمز M j .

دوال الهدف

عادةً ما يكون الهدف هو تقليل قيمة موضوعية معينة. أحد الاختلافات هو الترميز∑يوج{\displaystyle \sum U_{j}}حيث يتمثل الهدف في زيادة عدد المهام التي تُنجز قبل الموعد النهائي. ويُطلق على هذا أيضًا اسم الإنتاجية . ويمكن جمع قيمة الهدف، مع إمكانية ترجيحها بأوزان أولوية معينة.wج{\displaystyle w_{j}}لكل وظيفة.

  • - : يُشار إلى غياب قيمة الهدف بشرطة واحدة. وهذا يعني أن المشكلة تكمن ببساطة في وضع جدول زمني قابل للتنفيذ، يفي بجميع القيود المعطاة.
  • جج{\displaystyle C_{j}}: وقت إنجاز المهمةج{\displaystyle j}.جالأعلى{\displaystyle C_{\max }}هو أقصى وقت للإنجاز؛ ويُعرف أيضًا باسم مدة الإنجاز . أحيانًا نهتم بمتوسط ​​وقت الإنجاز (متوسط ​​1/2).جج{\displaystyle C_{j}}على جميع قيم j )، والذي يُشار إليه أحيانًا بـ mft (متوسط ​​وقت الانتهاء). [ 4 ]
  • Fج{\displaystyle F_{j}}زمن تدفق المهمة هو الفرق بين وقت إنجازها ووقت إصدارها، أيFج=جج-رج{\displaystyle F_{j}=C_{j}-r_{j}}.
  • لج{\displaystyle L_{j}}التأخير . كل وظيفةج{\displaystyle j}يتم تحديد موعد استحقاقدج{\displaystyle d_{j}}تأخر العملج{\displaystyle j}يُعرَّف بأنهجج-دج{\displaystyle C_{j}-d_{j}}. أحيانالالأعلى{\displaystyle L_{\max }}يُستخدم هذا المصطلح للدلالة على جدوى حل مشكلة ذات مواعيد نهائية. في الواقع، باستخدام البحث الثنائي ، فإن تعقيد نسخة الجدوى يُعادل تقليل قيمة .لالأعلى{\displaystyle L_{\max }}.
  • يوج{\displaystyle U_{j}}الإنتاجية : يتم تحديد موعد نهائي لكل مهمةدج{\displaystyle d_{j}}هناك ربح لكل وحدة عمل يتم إنجازها في الوقت المحدد، أييوج=1{\displaystyle U_{j}=1}لوجج≤دج{\displaystyle C_{j}\leq d_{j}}و يوج=0{\displaystyle U_{j}=0}وإلا. أحيانًا يكون معنىيوج{\displaystyle U_{j}}يتم عكس ذلك في الأدبيات، وهو أمر مكافئ عند النظر في نسخة القرار من المشكلة، ولكنه يحدث فرقًا كبيرًا بالنسبة للتقريبات.
  • تيج{\displaystyle T_{j}}التأخير . كل وظيفةج{\displaystyle j}يتم تحديد موعد استحقاقدج{\displaystyle d_{j}}تأخر العملج{\displaystyle j}يُعرَّف بأنهتيج=الأعلى{0،جج-دج}{\displaystyle T_{j}=\max\{0,C_{j}-d_{j}\}}.
  • هـج{\displaystyle E_{j}}التبكير . كل وظيفةج{\displaystyle j}يتم تحديد موعد استحقاقدج{\displaystyle d_{j}}. التبكير في الحصول على الوظيفةج{\displaystyle j}يُعرَّف بأنههـج=الأعلى{0،دج-جج}{\displaystyle E_{j}=\max\{0,d_{j}-C_{j}\}}يُعد هذا الهدف مهماً لجدولة الإنتاج في الوقت المناسب.

توجد أيضاً متغيرات ذات أهداف متعددة ، لكنها أقل دراسة بكثير. [ 2 ]

أمثلة

فيما يلي بعض الأمثلة على المسائل المحددة باستخدام الرموز المذكورة أعلاه. [ 1 ]

  • P2∥جالأعلى{\displaystyle P_{2}\parallel C_{\max }}– تخصيص كل منن{\displaystyle n}يتم توزيع المهام على إحدى الآلتين المتطابقتين بهدف تقليل إجمالي وقت المعالجة على الآلتين إلى أدنى حد. هذه نسخة مُحسَّنة من مسألة التقسيم.
  • 1|prec|لالأعلى{\displaystyle L_{\max }}– تخصيص العمليات ذات القيود العامة على الأسبقية لجهاز واحد، مما يقلل من أقصى تأخير.
  • R|pmtn|∑جأنا{\displaystyle \sum C_{i}}– إسناد المهام إلى عدد متغير من الآلات المتوازية غير المرتبطة، مما يسمح بالمقاطعة، وتقليل وقت الإنجاز الإجمالي.
  • ج3|صأناج=1{\displaystyle p_{ij}=1}|جالأعلى{\displaystyle C_{\max }}– مشكلة ورشة عمل مكونة من 3 آلات مع أوقات معالجة موحدة، حيث يكون الهدف هو تقليل الحد الأقصى لوقت الإنجاز.
  • P|مقاسج|جالأعلى{\displaystyle P\mid {\text{size}}_{j}\mid C_{\max }}– إسناد المهام إلىم{\displaystyle m}تُجرى العمليات على آلات متطابقة بالتوازي، حيث تتطلب كل مهمة عددًا من الآلات التي يجب جدولة تنفيذها عليها في الوقت نفسه، مما يقلل من الحد الأقصى لوقت الإنجاز. انظر جدولة المهام المتوازية .

متغيرات أخرى

  • جميع المتغيرات المذكورة أعلاه حتمية ، حيث تكون جميع البيانات معروفة للمخطط. وهناك أيضاً متغيرات عشوائية ، حيث لا تكون البيانات معروفة مسبقاً، أو يمكن أن تتغير بشكل عشوائي. [ 2 ]
  • في لعبة موازنة الأحمال ، تُنسب كل مهمة إلى وكيل استراتيجي، له الحق في تحديد وقت تنفيذ مهمته. قد لا يكون توازن ناش في هذه اللعبة مثاليًا. وقد قيّم أومان ودومب [ 5 ] عدم كفاءة التوازن في العديد من ألعاب موازنة الأحمال.

انظر أيضاً

مراجع

  1. 1 2 غراهام، آر إل؛ لولر، إي إل؛ لينسترا، جيه كيه؛ رينوي كان، إيه إتش جي (1979). "التحسين والتقريب في التسلسل والجدولة الحتمية: دراسة استقصائية" (ملف PDF) . وقائع معهد البحوث المتقدمة حول التحسين المنفصل وتطبيقات الأنظمة التابع للجنة علوم الأنظمة في حلف شمال الأطلسي وندوة التحسين المنفصل . إلسيفير. الصفحات  (5) 287-326.
  2. 1 2 3 يوجين ل. لولر، جان كاريل لينسترا، ألكسندر هـ. ج. رينوي كان، ديفيد ب. شمويز (1993-01-01). "الفصل 9: التسلسل والجدولة: الخوارزميات والتعقيد" . كتيبات في بحوث العمليات وعلوم الإدارة . 4 : 445-522 . doi : 10.1016/S0927-0507(05)80189-6 . ISBN 9780444874726ISSN 0927-0507​​ {{cite journal}}: صيانة CS1: أسماء متعددة: قائمة المؤلفين ( رابط )
  3. ↑ ب. تشين، سي إن بوتس، وجي جي ووجينجر . "مراجعة لجدولة الآلات: التعقيد، والخوارزميات، والتقريب". دليل التحسين التوافقي (المجلد 3) (المحرران: د.-ز. دو وب. باردالوس)، 1998، دار نشر كلوير الأكاديمية. 21-169. ISBN 0-7923-5285-8(HB) 0-7923-5019-7 (مجموعة)
  4. ↑ هورويتز، إليس؛ ساهني، سرتاج (1976-04-01). "خوارزميات دقيقة وتقريبية لجدولة المعالجات غير المتطابقة" . مجلة ACM . 23 (2): 317-327 . doi : 10.1145/321941.321951 . ISSN 0004-5411 . S2CID 18693114 .  
  5. ↑ أومان، يوناتان؛ دومب، يائير (2010). "كفاءة باريتو وكفاءة باريتو التقريبية في توجيه وموازنة الأحمال" . في: كونتوغيانيس، سبيروس؛ كوتسوبيا، إلياس؛ سبيراكيس، بول ج. (محررون). نظرية الألعاب الخوارزمية . سلسلة محاضرات في علوم الحاسوب. برلين، هايدلبرغ: سبرينغر. ص 66-77 . doi : 10.1007/978-3-642-16170-4_7 . ISBN  978-3-642-16170-4.
  • Scheduling zoo (من تأليف كريستوف دور، سيغريد كنست، داميان بروت، أوسكار سي فاسكيز): أداة عبر الإنترنت للبحث عن مشكلة جدولة مثالية باستخدام الترميز.
  • نتائج التعقيد لمشاكل الجدولة (بقلم بيتر بروكر، سيغريد كنست): تصنيف لمشاكل الجدولة المثلى حسب ما هو معروف عن تعقيد وقت التشغيل الخاص بها.