كلها مشاكل الجدولة NP-بجد ؟

Question

أعرف أن هناك بعض مشاكل الجدولة الى ان هناك NP-hard/NP-complete ...ومع ذلك ، فإن أيا منهم وذكر في مثل هذه الطريقة أن تظهر هذه الحالة أيضا NP.

إذا كان لديك مجموعة من المهام مقيدة إلى startAfter, startBy, ، مدة كل محاولة استخدام واحد من الموارد ...يمكنك حل أي جدول أو تحديد أنه لا يمكن حلها دون شاملة البحث ؟

إذا كان الجواب "آسف بال ، ولكن هذا هو NP-complete" ما يمكن أن يكون أفضل ارشادي(s؟) استخدام و هل هناك طرق لتقليل الوقت الذي يستغرقه أ) حل جدول ب) تحديد لا حل الموعد المحدد.

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

ياي مجمع الأسئلة!

Answer 1

الجزء الأصعب من معظم مشاكل الجدولة في الحياه الحقيقيه يحصل على موثوقية ومجموعة كاملة من القيود. إذا أخذنا مثال إنشاء جدول زمني للجامعة:

• البروفيسور أ لن يستيقظ في الصباح ، فهو في الكثير من اللجان ، لكن لا أحد يخبر المكتب الجدول الزمني عن هذا النوع من القيد
• يحتاج القسم 1 إلى الجدول الزمني بحلول بداية الفصل الدراسي ، ومع ذلك ، فإن القسم 2 الذي يستخدم نفس الغرف غير راغب في اتخاذ قرار بشأن الدورات التي سيتم تشغيلها إلا بعد وصول جميع الطلاب
• إلخ

ثم تحتاج إلى نظام جدولة يمكن أن يتعامل مع التغييرات ، لذلك عندما يتم تغيير قيود واحدة في اللحظة الأخيرة ، لا يتعين عليك تغيير الجدول الزمني الكامل.

يتم تجاهل كل ما سبق عادة في الأوراق البحثية حول أنظمة الجدولة. بالنسبة لاكتمال NP لمشكلة جدولة معينة ، في الحياة الحقيقية لا تهتم كما لو أنه لم يكتمل NP ، فمن غير المحتمل أن تكون قادرًا على تحديد ماهية "الحل الأفضل" ، فهو جيد جدًا بما فيه الكفاية.

يرى http://www.asap.cs.nott.ac.uk/watt/resources/university.html للحصول على قائمة بالأوراق التي قد تساعد في البدء ؛ لا يزال هناك العديد من الدكتوراه في برنامج الجدولة.

Answer 2

غالبًا ما تكون جيدة خوارزميات التقريب لمشاكل التحسين NP-Hard/كاملة مثل الجدولة. يمكنك تقليص ملاحظات الدورة التي كتبها أحمد أبو سافيا خوارزميات التقريب للجدولة أو مختلف أوراق.

بمعنى ما ، تتم جميع تشفير المفاتيح العامة بمشاكل "أقل صعوبة" مثل العوملة جزئيًا لأن مشاكل NP-Hard توفر الكثير من الحالات السهلة. إنها نفس اكتمال NP هي التي تجعلهم "صعبًا أخلاقياً" مما يمنحهم أيضًا الكثير من المشكلات السهلة ، والتي غالباً ما تندرج ضمن بعض الأخطاء المحددة من الأمثل.

هناك نظرية أعمق ل صلابة التقريب التي تناقش حدود خوارزميات التقريب.

Answer 3

يمكنك استخدام البرمجة الديناميكية لحل بعض هذه الأشياء. خوارزميات الجشع تتبادر أيضا إلى الذهن. نظرية الجدولة عميقة وجميلة على حد سواء ، لكن هذين اللذين أجده سيحلان معظم المشكلات التي واجهتها. ربما كنت محظوظا.

Answer 4

ماذا تقصد مع Startby؟

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

Answer 5

هنا هو واحد هو أن لا.

جدول مجموعة من الوظائف i= 1,2...ن على جهاز واحد الذي يأخذ كل الوقت t(i) حيث أن متوسط وقت الانتظار هو الحد الأدنى.

الحل:نوعا من أجل زيادة t(i).O(n log n)

قائمة جيدة هنا

Answer 6

النظر في مشكلة الجدولة الموجودة في الفئة P:

المدخلات: قائمة الأنشطة التي تشمل وقت البدء ووقت الانتهاء.

فرز وقت الانتهاء.

حدد العناصر الأولى من هذه القائمة المصنفة للعثور على الحد الأقصى من الأنشطة التي يمكنك جدولةها في وقت معين.

يمكنك إضافة تحذيرات مثل: يجب أن تنتهي جميع الأنشطة في الساعة 5 مساءً ، في هذه الحالة أثناء العمل من خلال القائمة ، توقف بمجرد الوصول إلى نشاط ينتهي بعد هذا الوقت.