گسترش ساختمان دادهی خط زمانی برای الگوریتم پالایش نه اولین انه آخرین در محدودیت گسسته

سال انتشار: 1399
نوع سند: مقاله کنفرانسی
زبان: فارسی
مشاهده: 268

فایل این مقاله در 7 صفحه با فرمت PDF قابل دریافت می باشد

استخراج به نرم افزارهای پژوهشی:

لینک ثابت به این مقاله:

شناسه ملی سند علمی:

CEITCONF04_021

تاریخ نمایه سازی: 13 تیر 1400

چکیده مقاله:

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

نویسندگان

حامد فهیمی

استادیاردانشکده علوم ریاضی و کامپیوتر دانشگاه شهید چمران اهواز،