ارائه‌ی الگوریتم های پالایش نوین تعمیم یافته به مسائل زمانبندی استوار

مساله‌ی ارضای محدودیت یکی از موضوعات عمیق پژوهشی در حوزه‌ی هوش مصنوعی می باشد و مسائل زمانبندی را می توان در قالب این مساله تعبیر نمود. از آن جا که مسائل ارضای محدودیت در حالت کلی np-سخت هستند، کاهش زمان موردنیاز برای حل آن ها به طور چشمگیری مورد توجه قرار گرفته است. برنامه سازی محدودیتی تکنیکیست که نقشی موثر در برآورده نمودن چنین هدفی و به ویژه شیوه ای موثر برای مدل کردن و حل مسائل زمانبندی در مقیاس بزرگ ارائه می کند. در عمل ممکن است به علل متفاوت از جمله از کارافتادگی منابع، اضافه شدن فعالیت های جدید، عدم دسترسی به ابزار لازم در زمان های خاص و ... در اجرای فعالیت ها تاخیر ایجاد شود. از طرفی در صورت رخ دادن چنین شرایطی در بسیاری از کاربردهای عملی محاسبه‌ی زمانبندی مجدد امکان پذیر نیست. بنابراین یافتن یک زمانبندی استوار که در آن اجرای همراه با تاخیر حداکثر تعداد مشخصی از مجموع فعالیت ها بر روی منبعی با ظرفیت معین همچنان اعتبار زمانبندی یافت شده را حفظ می کند حائز اهمیت ویژه است. در این پژوهش به طور دقیق تر محیطی را در نظر می گیریم که در آن اجرای حداکثر تعداد r تا از مجموع n فعالیت (r ≤ n)ممکن است با تعویق همراه باشد. سپس با بهره گیری از تکنیک های مسائل ارضای محدودیت الگوریتم های پالایش شناخته شده با عناوین تست بررسی بار اضافی و یال-یابی را برای محدودیت تجمعی مرتبط با مسائل زمانبندی در محیط های تاخیرپذیر تعمیم می دهیم. تحلیل الگوریتم های به دست آمده نشان می دهد که پیچیدگی الگوریتم های ارائه شده‌ی ما نیز متناسب با r می باشد. همچنین نتایج تجربی روی یک مجموعه داده‌ی شناخته شده نشان می دهد که الگوریتم های ما منجر به پالایش قوی تر و نتیجتا هرس شدن بیش تر فضای جستجو می شوند.