الگوریتم ژنتیک مبتنی بر خوشه بندی در حل مسایل زمانبندی پروژه چند حالته

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

کلیدواژه ها:

الگوریتم تکاملی ، بهینه سازی چند هدفه ، خوشه بندی ، زمان بندی پروژه چند حالته با منابع محدود ، زمان بندی سه جهته.