برنامهریزی و زمانبندی زمانی
برنامهریزی و زمانبندی زمانی، برنامهریزی را برای مدیریت اقداماتی که زمانبر هستند، ممکن است به صورت همزمان اجرا شوند و منابع محدودی را مصرف کنند، گسترش میدهند و برنامههایی را تولید میکنند که نه تنها «چه کاری انجام شود» بلکه «چه زمانی انجام شود» را نیز مشخص میکنند.
Definition
برنامهریزی زمانی، برنامهای را تولید میکند که در آن اقدامات دارای مدت زمان هستند و ممکن است همپوشانی داشته باشند، مشروط به محدودیتهای زمانی و منابع؛ زمانبندی، زمانهای شروع (و منابع) را به مجموعهای از فعالیتها اختصاص میدهد تا تمام محدودیتها، مانند ترتیب، مهلتها و ظرفیتها، برآورده شوند.
Scope
این موضوع برنامهریزی و زمانبندی را با زمان و منابع صریح پوشش میدهد: اقدامات زماندار، همزمانی و محدودیتهای زمانی، نمایش و حل شبکههای محدودیت زمانی (مانند مسئله زمانی ساده) و جبر بازهای آلن، و ادغام برنامهریزی با زمانبندی فعالیتهای با منابع محدود. این موضوع به چگونگی استدلال در مورد امکانسنجی زمانی و منابع در کنار انتخاب اقدام میپردازد. برنامهریزی کلاسیک بدون منابع خالص در موضوعات مرتبط مورد بررسی قرار میگیرد.
Core questions
- چگونه اقدامات زماندار و شرایط شروع و پایان آنها نمایش داده میشوند؟
- چگونه محدودیتهای زمانی بین رویدادها مدلسازی و از نظر سازگاری بررسی میشوند؟
- چگونه منابع محدود بین فعالیتهای همزمان تخصیص داده میشوند؟
- چگونه برنامهریزی (تصمیمگیری در مورد اقدامات) و زمانبندی (تصمیمگیری در مورد زمان) با هم ترکیب یا از هم جدا میشوند؟
Key concepts
- اقدامات زماندار
- همزمانی و همپوشانی
- محدودیتهای زمانی
- مسئله زمانی ساده
- جبر بازهای آلن
- محدودیتهای منابع
- زمانبندی
- مهلتها و زمان تکمیل
Key theories
- شبکههای محدودیت زمانی
- محدودیتهای زمانی کمی بین نقاط زمانی را میتوان به عنوان یک شبکه نمایش داد که سازگاری و دقیقترین کرانهای آن برای مسئله زمانی ساده به طور کارآمد محاسبه میشود و ستون فقرات استدلال زمانی بسیاری از برنامهریزها و زمانبندها را فراهم میکند.
- جبر بازهای برای زمان کیفی
- جبر بازهای آلن روابط کیفی ممکن بین بازههای زمانی (قبل، در طول، همپوشانی و غیره) را به تصویر میکشد و از استدلال در مورد دانش زمانی در زمانی که زمانهای دقیق ناشناخته هستند، پشتیبانی میکند.
- ادغام برنامهریزی با زمانبندی
- مسائل واقعبینانه نیازمند انتخاب اقدامات و اختصاص همزمان زمان و منابع به آنها هستند؛ نظریه برنامهریزی خودکار، اقدامات زماندار، همزمانی و محدودیتهای منابع را به عنوان گسترشهایی در نظر میگیرد که انتخاب اقدام را با زمانبندی مبتنی بر محدودیتها پیوند میدهد.
Clinical relevance
برنامهریزی و زمانبندی زمانی در عملیات فضاپیما و مریخنورد، برنامهریزی تولید و پروژه، برنامهریزی حمل و نقل و خدمه، و هر محیطی که فعالیتهای زمانبندی شده، همزمان و با منابع محدود باید هماهنگ شوند، ضروری هستند؛ چنین سیستمهایی عملیات برنامهریزی شدهای برای ماموریتهای فضایی واقعی داشتهاند.
History
استدلال زمانی کیفی توسط جبر بازهای آلن (1983) و شبکههای محدودیت زمانی کمی توسط دچر، میری و پرل (1991) رسمیسازی شدند. این مبانی، همراه با مدلهای اقدام زماندار که در اوایل دهه 2000 به PDDL اضافه شدند، برنامهریزهای زمانی را قادر ساختند که در کاربردهایی مانند کنترل خودمختار فضاپیما استفاده شوند.
Key figures
- James F. Allen
- Rina Dechter
- Judea Pearl
- Itay Meiri
- Nicola Muscettola
Related topics
Seminal works
- dechter1991
- allen1983
Frequently asked questions
- تفاوت بین برنامهریزی و زمانبندی چیست؟
- برنامهریزی تصمیم میگیرد که برای دستیابی به اهداف چه اقداماتی انجام شود، در حالی که زمانبندی تصمیم میگیرد که آن اقدامات چه زمانی رخ دهند و از چه منابعی استفاده کنند، با توجه به محدودیتهای ترتیب و ظرفیت. بسیاری از مسائل واقعی به هر دو نیاز دارند و برنامهریزی زمانی، انتخاب اقدام را با استدلال زمانبندی و منابع ادغام میکند.
- مسئله زمانی ساده چیست؟
- مسئله زمانی ساده یک شبکه محدودیت زمانی است که در آن هر محدودیت، تفاوت بین دو نقطه زمانی را با یک بازه محدود میکند. سازگاری آن و دقیقترین کرانهای ضمنی را میتوان به طور کارآمد محاسبه کرد، که آن را به یک هسته عملی برای استدلال زمانی در برنامهریزها و زمانبندها تبدیل میکند.