خوارزمية كوفمان-غراهام

الموسوعة الحرة

خوارزمية كوفمان-غراهام هي خوارزمية لترتيب عناصر مجموعة مرتبة جزئيًا في سلسلة من المستويات. تختار الخوارزمية ترتيبًا بحيث يُخصص العنصر الذي يلي عنصرًا آخر في الترتيب لمستوى أدنى، وبحيث لا يتجاوز عدد عناصر كل مستوى حدًا ثابتًا للعرض W. عندما يكون W = 2 ، تستخدم الخوارزمية أقل عدد ممكن من المستويات المختلفة، وعمومًا تستخدم على الأكثر 2 - 2/ W ضعف عدد المستويات اللازمة.

سُميت هذه الخوارزمية نسبةً إلى إدوارد ج. كوفمان الابن ورونالد غراهام ، اللذين نشراها عام ١٩٧٢ لتطبيقها في جدولة ورش العمل . في هذا التطبيق، تُمثل المهام العناصر المراد ترتيبها، ويُمثل الحد W عدد المهام التي يُمكن جدولتها في أي وقت، بينما يصف الترتيب الجزئي العلاقات الشرطية بين المهام. الهدف هو إيجاد جدول زمني يُنجز جميع المهام في أقل وقت إجمالي. لاحقًا، استُخدمت الخوارزمية نفسها في رسم المخططات ، كوسيلة لوضع رؤوس المخطط الموجه في طبقات ذات عرض ثابت بحيث تكون معظم أو جميع الحواف موجهة نحو الأسفل باستمرار.

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

بيان المشكلة وتطبيقاتها

في نسخة مسألة جدولة ورش العمل التي تحلها خوارزمية كوفمان-غراهام، تُعطى مجموعة من n مهمة J1 ، J2 ، ...، Jn ، بالإضافة إلى نظام قيود أسبقية Ji < Jj ، مما يعني وجوب إتمام المهمة Ji قبل بدء المهمة Jj . يُفترض أن كل مهمة تستغرق وحدة زمنية واحدة لإتمامها. تتمثل مهمة الجدولة في تخصيص كل مهمة من هذه المهام لفترات زمنية على نظام مكون من W معالجًا متطابقًا، مع تقليل زمن إنجاز المهمة (الوقت من بداية المهمة الأولى حتى إتمام المهمة الأخيرة). بشكل مجرد، تُحدد قيود الأسبقية ترتيبًا جزئيًا للمهام، لذا يمكن إعادة صياغة المسألة على أنها تخصيص عناصر هذا الترتيب الجزئي لمستويات (فترات زمنية) بحيث تحتوي كل فترة زمنية على عدد من المهام يساوي عدد المعالجات على الأكثر ( W عنصرًا على الأكثر لكل مستوى)، مع مراعاة قيود الأسبقية. كان هذا التطبيق هو الدافع الأصلي لكوفمان وغراهام لتطوير خوارزميتهما. [ 1 ] [ 2 ]

في إطار رسم المخططات الطبقية الذي حدده سوجياما وتاجاوا وتودا (1981) [ 3 ] يكون المدخل عبارة عن مخطط موجه ، ويتم إنشاء رسم المخطط في عدة مراحل: [ 4 ] [ 5 ]

  1. يتم اختيار مجموعة أقواس التغذية الراجعة ، ويتم عكس حواف هذه المجموعة، من أجل تحويل المدخلات إلى رسم بياني موجه غير دوري مع (إن أمكن) عدد قليل من الحواف المعكوسة.
  2. تُعطى رؤوس الرسم البياني إحداثيات y صحيحة بحيث يكون لكل ضلع إحداثي أعلى لرأس البداية من رأس النهاية، مع وجود W رأسًا على الأكثر تشترك في نفس الإحداثي y . وبهذه الطريقة، ستكون جميع أضلاع الرسم البياني الموجه غير الدوري ومعظم أضلاع الرسم البياني الأصلي موجهة نحو الأسفل بشكل متسق.
  3. يتم إدخال رؤوس وهمية داخل كل حافة بحيث تربط الحواف المقسمة جميعها أزواجًا من الرؤوس الموجودة في مستويات متجاورة من الرسم.
  4. ضمن كل مجموعة من الرؤوس التي لها نفس الإحداثي y ، يتم تبديل الرؤوس من أجل تقليل عدد التقاطعات في الرسم الناتج، ويتم تعيين إحداثيات x للرؤوس بما يتوافق مع هذا التبديل.
  5. يتم رسم رؤوس وحواف الرسم البياني مع تحديد الإحداثيات الخاصة بها.

في هذا الإطار، تتضمن عملية تحديد الإحداثي y تجميع عناصر مجموعة مرتبة جزئيًا (رؤوس الرسم البياني، مع مراعاة ترتيب الوصول على مجموعة الرؤوس) في طبقات (مجموعات من الرؤوس لها نفس الإحداثي y )، وهي المشكلة التي تحلها خوارزمية كوفمان-غراهام. [ 4 ] على الرغم من وجود مناهج بديلة لخوارزمية كوفمان-غراهام في خطوة الترتيب الطبقي، إلا أن هذه البدائل عمومًا إما أنها لا تستطيع تحديد حد أقصى لعرض المستوى أو أنها تعتمد على إجراءات برمجة عددية معقدة . [ 6 ]

بصورة أكثر تجريدًا، يمكن صياغة كلتا المشكلتين كمسألة تتكون فيها المدخلات من مجموعة مرتبة جزئيًا وعدد صحيح W. والمخرجات المطلوبة هي إسناد أعداد صحيحة إلى عناصر المجموعة المرتبة جزئيًا بحيث، إذا كان x < y زوجًا مرتبًا من عناصر مترابطة في الترتيب الجزئي، فإن العدد المُسند إلى x يكون أصغر من العدد المُسند إلى y ، بحيث لا يتجاوز عدد العناصر التي تُسند إليها نفس العدد W ، مع تقليل الفرق بين أصغر وأكبر عدد مُسند.

الخوارزمية

تُنفذ خوارزمية كوفمان-غراهام الخطوات التالية. [ 4 ]

  1. يمكن تمثيل الترتيب الجزئي من خلال اختزاله المتعدي أو علاقة التغطية ، وهو رسم بياني موجه غير دوري G يحتوي على حافة من x إلى y عندما يكون x < y ، ولا يوجد عنصر ثالث z في الترتيب الجزئي بحيث يكون x < z < y . في تطبيقات رسم الرسوم البيانية لخوارزمية كوفمان-غراهام، قد لا يكون الرسم البياني الموجه غير الدوري الناتج هو نفسه الرسم البياني الذي يتم رسمه، وفي تطبيقات الجدولة، قد لا يحتوي على حافة لكل قيد أسبقية للمدخلات: في كلتا الحالتين، يزيل الاختزال المتعدي الحواف الزائدة غير الضرورية لتحديد الترتيب الجزئي.
  2. أنشئ ترتيبًا طوبولوجيًا للرسم البياني G بحيث تُرتَّب الرؤوس ترتيبًا معجميًا وفقًا لمجموعة مواقع جيرانها الجدد. وللقيام بذلك، أضف الرؤوس واحدًا تلو الآخر إلى الترتيب، وفي كل خطوة اختر رأسًا v لإضافته بحيث يكون جميع جيرانه الجدد جزءًا من الترتيب الجزئي، وبحيث يكون أحدث جار جديد مُضاف لـ v أقدم من أحدث جار جديد مُضاف لأي رأس آخر يمكن إضافته مكان v . إذا كان لرأسين نفس أحدث جار جديد مُضاف، فإن الخوارزمية تحسم التعادل لصالح الرأس الذي يكون ثاني أحدث جار جديد مُضاف له أقدم، وهكذا.
  3. قم بتعيين رؤوس الرسم البياني G إلى مستويات بترتيب عكسي للترتيب الطوبولوجي الذي تم إنشاؤه في الخطوة السابقة. لكل رأس v ، أضف v إلى مستوى أعلى بخطوة واحدة على الأقل من أعلى مستوى لأي جار صادر لـ v ، ولا يحتوي بالفعل على W عنصرًا، ويكون هذا المستوى منخفضًا قدر الإمكان مع مراعاة هذين القيدين.

تحليل

جودة المخرجات

كما أثبت كوفمان وغراهام (1972) في الأصل، فإن خوارزميتهما تحسب التخصيص الأمثل عندما يكون W = 2 ؛ أي لمسائل الجدولة ذات المهام ذات الطول الواحد على معالجين، أو لمسائل رسم المخططات الطبقية التي تحتوي على رأسين على الأكثر في كل طبقة. [ 1 ] كما تجد خوارزمية مشابهة الحل الأمثل لجدولة المهام ذات الأطوال المتغيرة، مما يسمح بمقاطعة المهام المجدولة، على معالجين. [ 7 ] بالنسبة لـ W > 2 ، تستخدم خوارزمية كوفمان-غراهام عددًا من المستويات (أو تحسب جدولًا زمنيًا بمدة إنجاز إجمالية) يقع ضمن عامل 2 − 2/ W من الحل الأمثل. [ 8 ] [ 9 ] على سبيل المثال، عندما يكون W = 3 ، فهذا يعني أنها تستخدم على الأكثر 4/3 من عدد المستويات الأمثل. عندما يكون الترتيب الجزئي لقيود الأسبقية ترتيبًا فاصليًا ، أو ينتمي إلى عدة فئات ذات صلة من الترتيبات الجزئية، فإن خوارزمية كوفمان-غراهام تجد حلاً بأقل عدد من المستويات بغض النظر عن حد عرضه. [ 10 ]

إضافةً إلى إيجاد جداول زمنية ذات مدة إنجاز قصيرة، تعمل خوارزمية كوفمان-غراهام (المعدلة عن العرض المقدم هنا بحيث ترتب الرسم البياني العكسي لـ G ترتيبًا طوبولوجيًا وتضع الرؤوس في أقرب وقت ممكن بدلًا من أبعد وقت ممكن) على تقليل إجمالي وقت التدفق لجداول المعالجين، وهو مجموع أوقات إنجاز المهام الفردية. ويمكن استخدام خوارزمية مشابهة لتقليل إجمالي وقت التدفق لنسخة من المسألة تسمح بمقاطعة المهام. [ 11 ]

تعقيد الخطة

ذكر كلٌّ من كوفمان وغراهام (1972) ولينسترا ورينوي كان ( 1978 ) [ 12 ] أن التعقيد الزمني لخوارزمية كوفمان-غراهام، على ترتيب جزئي ذي n عنصر، هو O ( n² ) . مع ذلك، يُغفل هذا التحليل الوقت اللازم لإنشاء الاختزال المتعدي، والذي من غير المعروف إمكانية تنفيذه ضمن هذا الحد. يُبيّن سيثي (1976) كيفية تنفيذ مرحلة الترتيب الطوبولوجي للخوارزمية في زمن خطي ، استنادًا إلى فكرة تحسين التقسيم . [ 13 ] كما يُبيّن سيثي كيفية تنفيذ مرحلة تعيين المستوى للخوارزمية بكفاءة باستخدام بنية بيانات المجموعة المنفصلة . على وجه الخصوص، مع نسخة من هذه البنية نُشرت لاحقًا بواسطة غابو وتارجان (1985) ، تستغرق هذه المرحلة أيضًا زمنًا خطيًا. [ 14 ]

مراجع

  1. 1 2 كوفمان، إي جي جونيور ؛ غراهام، آر إل (1972)، "الجدولة المثلى لأنظمة المعالجين" (ملف PDF) ، أكتا إنفورماتيكا ، 1 (3): 200-213 ، doi : 10.1007/bf00288685 ، MR 0334913 ، S2CID 40603807  .
  2. ↑ ليونغ، جوزيف واي-تي (2004)، "بعض خوارزميات الجدولة الأساسية"، دليل الجدولة: الخوارزميات والنماذج وتحليل الأداء ، مطبعة سي آر سي، رقم ISBN 978-1-58488-397-5.
  3. ↑ سوجياما، كوزو؛ تاغاوا، شوجيرو؛ تودا، ميتسوهيكو (1981)، "طرق الفهم البصري لهياكل الأنظمة الهرمية"، معاملات IEEE في الأنظمة والإنسان وعلم التحكم الآلي ، SMC-11 (2): 109-125 ، Bibcode : 1981ITSMC..11..109S ، doi : 10.1109/TSMC.1981.4308636 ، MR 0611436 ، S2CID 8367756  .
  4. 1 2 3 دي باتيستا، جوزيبي؛ إيدز، بيتر ؛ تاماسيا، روبرتو ؛ توليس، يوانيس ج. (1999)، "الفصل 9: رسومات متعددة الطبقات للرسوم البيانية الموجهة"، رسم الرسوم البيانية: خوارزميات لتصور الرسوم البيانية ، برنتيس هول، ص 265-302 .
  5. ↑ باسترت، أوليفر؛ ماتوسزوسكي، كريستيان (2001)، "الرسومات الطبقية للرسوم البيانية الموجهة"، في كوفمان، مايكل؛ فاغنر، دوروثيا (محرران)، رسم الرسوم البيانية: الأساليب والنماذج ، سلسلة محاضرات في علوم الحاسوب، المجلد 2025، سبرينغر-فيرلاغ، الصفحات 87-120 ، doi : 10.1007/3-540-44969-8_5 ، ISBN   978-3-540-42062-0. كما يتضمن باسترت وماتوسزوسكي وصفًا لخوارزمية كوفمان-غراهام؛ ومع ذلك، فإنهم يحذفون مرحلة الاختزال المتعدي للخوارزمية.
  6. ↑ هيلي، باتريك؛ نيكولوف، نيكولا س. (2002)، "كيفية إنشاء طبقات في رسم بياني موجه غير دوري"، رسم الرسوم البيانية: الندوة الدولية التاسعة، GD 2001 فيينا، النمسا، 23-26 سبتمبر 2001، أوراق منقحة ، سلسلة محاضرات في علوم الحاسوب، المجلد 2265، سبرينغر-فيرلاغ، الصفحات 16-30 ، doi : 10.1007/3-540-45848-4_2 ، ISBN   978-3-540-43309-5، MR 1962416 .
  7. ↑ مونتز، آر آر؛ كوفمان، إي جي (1969)، "الجدولة الاستباقية المثلى على أنظمة المعالجين"، معاملات IEEE للحواسيب ، 18 (11): 1014-1020 ، Bibcode : 1969ITCmp.100.1014M ، doi : 10.1109/TC.1969.222573 ، S2CID 206617438 .
  8. ↑ لام، شوي؛ سيثي، رافي (1977)، "تحليل أسوأ الحالات لخوارزميتين للجدولة"، مجلة SIAM للحوسبة ، 6 (3): 518-536 ، doi : 10.1137/0206037 ، MR 0496614 .
  9. ↑ براشي، برتراند؛ تريسترام، دينيس (1994)، "نظرة جديدة على خوارزمية كوفمان-غراهام"، مجلة SIAM للحوسبة ، 23 (3): 662-669 ، doi : 10.1137/S0097539790181889 ، MR 1274650 .
  10. ↑ شاردون، مارك؛ موكريم، عزيز (2005)، "خوارزمية كوفمان-غراهام تحل أنظمة مهام UET ذات الرتب فوق الفاصل الزمني على النحو الأمثل"، مجلة SIAM للرياضيات المتقطعة ، 19 (1): 109-121 ، doi : 10.1137/S0895480101394999 ، MR 2178187 .
  11. ^ كوفمان، على سبيل المثال الابن . سيثورامان، J.؛ Timkovsky، VG (2003)، “الجداول الوقائية المثالية على معالجين”، Acta Informatica ، 39 (8): 597–612 ، دوى : 10.1007/s00236-003-0119-6 ، MR 1996238 ، S2CID 7016804  .
  12. ^ لينسترا، جي كيه ؛ رينوي كان، AHG (1978)، "تعقيد الجدولة في ظل قيود الأسبقية"، بحوث العمليات ، 26 (1): 22-35 ، دوى : 10.1287/opre.26.1.22 ، hdl : 10338.dmlcz/141477 ، JSTOR 169889 ، MR 0462553  .
  13. ↑ سيثي، رافي (1976)، "جدولة الرسوم البيانية على معالجين"، مجلة SIAM للحوسبة ، 5 (1): 73-82 ، doi : 10.1137/0205005 ، MR 0398156 .
  14. ↑ جابو، هارولد ن .؛ تارجان، روبرت إندري (1985)، "خوارزمية خطية الزمن لحالة خاصة من اتحاد المجموعات المنفصلة"، مجلة علوم الحاسوب والأنظمة ، 30 (2): 209-221 ، doi : 10.1016/0022-0000(85)90014-5 ، MR 0801823 .