التخطيط والجدولة الزمنية
يعمل التخطيط والجدولة الزمنية على توسيع نطاق التخطيط للتعامل مع الإجراءات التي تستغرق وقتًا، وقد تتزامن، وتستهلك موارد محدودة، مما ينتج عنه خطط لا تحدد فقط ما يجب فعله، بل تحدد أيضًا متى يجب فعله.
Definition
ينتج التخطيط الزمني خطة تكون فيها الإجراءات ذات مدة وقد تتداخل، وتخضع لقيود زمنية وموارد؛ وتخصص الجدولة أوقات بدء (وموارد) لمجموعة من الأنشطة بحيث يتم تلبية جميع القيود، مثل الترتيب والمواعيد النهائية والقدرات.
Scope
يغطي هذا الموضوع التخطيط والجدولة مع الوقت والموارد الصريحة: الإجراءات المستمرة، التزامن والقيود الزمنية، تمثيل وحل شبكات القيود الزمنية (مثل مشكلة الزمن البسيط) وجبر فترات ألين، ودمج التخطيط مع جدولة الأنشطة المقيدة بالموارد. ويتناول كيفية الاستدلال على جدوى الوقت والموارد جنبًا إلى جنب مع اختيار الإجراءات. يتم تناول التخطيط الكلاسيكي الخالي من الموارد في المواضيع ذات الصلة.
Core questions
- كيف يتم تمثيل الإجراءات المستمرة وشروط بدايتها ونهايتها؟
- كيف يتم نمذجة القيود الزمنية بين الأحداث والتحقق من اتساقها؟
- كيف يتم تخصيص الموارد المحدودة بين الأنشطة المتزامنة؟
- كيف يتم الجمع أو الفصل بين التخطيط (تحديد الإجراءات) والجدولة (تحديد متى)؟
Key concepts
- الإجراءات المستمرة
- التزامن والتداخل
- القيود الزمنية
- مشكلة الزمن البسيط
- جبر فترات ألين
- قيود الموارد
- الجدولة
- المواعيد النهائية والمدة الكلية
Key theories
- شبكات القيود الزمنية
- يمكن تمثيل القيود الزمنية الكمية بين النقاط الزمنية كشبكة يتم حساب اتساقها وأضيق حدودها بكفاءة لمشكلة الزمن البسيط، مما يوفر العمود الفقري للاستدلال الزمني للعديد من المخططين والمجدولين.
- جبر الفترات للزمن النوعي
- يلتقط جبر فترات ألين العلاقات النوعية المحتملة بين الفترات الزمنية (قبل، أثناء، يتداخل، وهكذا) ويدعم الاستدلال حول المعرفة الزمنية عندما تكون الأوقات الدقيقة غير معروفة.
- دمج التخطيط مع الجدولة
- تتطلب المشكلات الواقعية اختيار الإجراءات وتخصيص الأوقات والموارد لها معًا؛ وتتعامل نظرية التخطيط الآلي مع الإجراءات المستمرة، والتزامن، وقيود الموارد كامتدادات تربط اختيار الإجراءات بالجدولة القائمة على القيود.
Clinical relevance
يعد التخطيط والجدولة الزمنية ضروريين في عمليات المركبات الفضائية والعربات الجوالة، وجدولة التصنيع والمشاريع، وجدولة النقل والطواقم، وأي بيئة يجب فيها تنسيق الأنشطة الموقوتة والمتزامنة والمحدودة الموارد؛ وقد قامت مثل هذه الأنظمة بتخطيط عمليات لمهام فضائية حقيقية.
History
تم إضفاء الطابع الرسمي على الاستدلال الزمني النوعي بواسطة جبر فترات ألين (1983)، وشبكات القيود الزمنية الكمية بواسطة ديشتر وميري وبيرل (1991). وقد مكنت هذه الأسس، جنبًا إلى جنب مع نماذج الإجراءات المستمرة التي أضيفت إلى PDDL في أوائل العقد الأول من القرن الحادي والعشرين، المخططين الزمانيين المستخدمين في تطبيقات مثل التحكم الذاتي في المركبات الفضائية.
Key figures
- James F. Allen
- Rina Dechter
- Judea Pearl
- Itay Meiri
- Nicola Muscettola
Related topics
Seminal works
- dechter1991
- allen1983
Frequently asked questions
- ما الفرق بين التخطيط والجدولة؟
- يقرر التخطيط الإجراءات التي يجب اتخاذها لتحقيق الأهداف، بينما تقرر الجدولة متى تحدث تلك الإجراءات والموارد التي تستخدمها، بالنظر إلى قيود الترتيب والقدرة. تتطلب العديد من المشكلات الحقيقية كليهما، ويدمج التخطيط الزمني اختيار الإجراءات مع توقيت واستدلال الموارد.
- ما هي مشكلة الزمن البسيط؟
- مشكلة الزمن البسيط هي شبكة قيود زمنية يحد فيها كل قيد الفرق بين نقطتين زمنيتين بفاصل زمني. يمكن حساب اتساقها وأضيق الحدود الضمنية بكفاءة، مما يجعلها جوهرًا عمليًا للاستدلال الزمني في المخططين والمجدولين.