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

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

کلیدواژه ها:

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