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

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

کلیدواژه ها:

مساله ارضای محدودیت ، برنامه سازی محدودیتی ، زمانبندی استوار ، الگوریتم های پالایش