جدولة المهام المتسلسلة/المتوازية الجشعة

Question

لدينا N المهام التي تحتاج إلى جدولة للمعالجة.تتكون كل مهمة من جزأين تحتاج إلى تنفيذها بالترتيب.يتم حراسة أول واحد من قبل موتكس ، وبالتالي مهمة واحدة فقط يمكن تنفيذ هذا الجزء في وقت واحد.الجزء الثاني لا يوجد لديه مثل هذا القيد وأي عدد من المهام يمكن تنفيذ هذا في نفس الوقت.للمهمة i نحن نعرف كم من الوقت يحتاج إلى قضاء في كل جزء ، وهي م_i بالنسبة للجزء حراسة ، و_i للجزء الذي يمكن تنفيذه بالتوازي.

تكمن المشكلة في العثور على تبديل للمهام بحيث يتم تقليل الوقت اللازم لتنفيذها جميعا.

يقول حدسي أن هذا يمكن حلها مع خوارزمية الجشع ، عن طريق جدولة المهام في تنازلي_i النظام.

على سبيل المثال بالنظر إلى المهام مع:
m₁ = 3 ، أ₁ = 9
m₂ = 2 ، أ₂ = 7
m₃ = 6 ، أ₃ = 10

الحل الأمثل هو التقليب 3 ، 1 ، 2.

ومع ذلك ، لدي مشكلة في إثبات أن الحل الجشع هو الأمثل.أي أفكار حول كيفية القيام بذلك?

Answer 1

لدي دليل فوضوي جدا.أنا متأكد من أنه يمكن تنظيف هذا بقليل من العمل.اسمحوا لي أن أعرف إذا كنت بحاجة لي لتبسيط الدليل.

من أجل الإثبات ، يتيح إعادة ترتيب جميع المصطلحات مثل ذلك a أ_1 \ جق أ_2 \جق أ_3 \ لدوتس$.دعونا f و (1) ، و (2) ، \ لدوتس ، و (ن)$ كن بعض الجدول الزمني.إجمالي الوقت المستغرق في أي جدول $f$ يعطى من خلال ما يلي.T ر (و) = \ماكس \{م_ {و(1)} + أ_ {و(1)} ، م_{و(1)} + م_{و(2)} + أ_{و(2)} ، \لدوتس ، \مجموع _ {أنا = 1}^ن م _ {و(ط)} + أ _ {و(ن)}\} a.

من أجل التناقض ، افترض أن طريقتك الجشعة ليست الحل الأمثل.يوجد بعض الجدول الزمني i \ فايi مثل ذلك T تي (معرف) > تي (\فاي)$ (هنا $Id$ هي الهوية).اختر $k$ مثل ذلك sum \ مجموع_{أنا = 1}^ك م _ {أنا} + أ_ ك = ر (معرف)$.دعونا $h$ يكون أصغر عدد من هذا القبيل \ \ {1، \ لدوتس ، ك\} \ مجموعة فرعية \ {\فاي (1) ، \ لدوتس ، \ فاي (ح)\}}.لاحظ أن i \ فاي (ح) \ ليق ك k.لأن \ \ {1، \ لدوتس ، ك\} \ مجموعة فرعية \ {\فاي (1) ، \ لدوتس ، \ فاي (ح)\}}, sum \ مجموع _ {أنا = 1} ^ ح م _ {\فاي (أنا)} \ جيق \ مجموع _ {أنا = 1} ^ ك م_i.لأن a أ_1 \ جق أ_2 \جق \ لدوتس$, ، نحن نعلم ذلك a أ_ {\فاي (ح)} \ جيك أكk.وهذا يعني أن sum\مجموع _ {أنا = 1}^ك م_ي + أ_ك \ ليق\مجموع _ {أنا = 1}^ح م _ {\فاي(أنا)} + أ _ {\فاي(ح)}} لكن T ر (معرف) = \ مجموع_{أنا = 1}^ك م_ي + أ_ك \ليق \ مجموع_{أنا = 1} ^ ح م _ {\فاي (أنا)} + أ _ {\فاي (ح)} \ ليق ر (\فاي)$.هذا تناقض.