sampling – random

parallel

Kolisch

۱۳٫۶۶

sampling – random

serial

Kolisch

۱۴٫۲۲

۱٫۸۸

Our research

serial

ASO

۴-۴-۳)مسائل با ۹۰ و ۱۲۰ فعالیت

برای سری ۹۰ فعالیت ۴۸۰ و برای سری ۱۲۰ فعالیت، ۶۰۰ مساله در سایت PSBLIB موجود است. الگوریتم ASO طراحی شده توانسته به جواب بهینه ۳۱۱ مساله از ۴۸۰ مساله موجود برای سری ۹۰ فعالیت و ۱۰۵ مساله از ۶۰۰ مساله موجود برای سری ۱۲۰ فعالیت دست یابد. درصد انحراف از کران پایین برای سری ۹۰ فعالیت ۸۲/۲ درصد و برای سری ۱۲۰ فعالیت ۳۷/۶ درصد است. نتایج کامل مسائل نمونه برای سری ۹۰ فعالیت در پیوست ۳ و برای سری ۱۲۰ فعالیت در پیوست ۴ آورده شده ­اند.با توجه به پایین بودن درصد انحراف در ۹۰ و ۱۲۰ فعالیت، کارایی الگوریتم بهینه سازی جامعه نامنظم را میتوان مشاهده کرد.

(( اینجا فقط تکه ای از متن درج شده است. برای خرید متن کامل فایل پایان نامه با فرمت ورد می توانید به سایت feko.ir مراجعه نمایید و کلمه کلیدی مورد نظرتان را جستجو نمایید. ))

فصل پنجم
نتیجه‌گیری و پیشنهادات آتی

۵-۱)نتیجه گیری کلی

در این پایان نامه، ابتدا مساله زمانبندی پروژه تحت شرایط محدودیت منابع در حالت چند نوع منبعی، به طور کامل تشریح شده است و در ادامه الگوریتم ASO و چگونگی عملکرد آن معرفی شده است. سپس به طراحی یک الگوریتم ASO کارا جهت حل مساله RCPSP پرداخته شده است. تمرکز اصلی در طراحی این الگوریتم، استفاده از سیاست­ها و همسایگی­های متنوع برای الگوریتم، برای بالا بردن کارایی آن است. الگوریتم طراحی شده بر روی چهار سری از مسائل نمونه که توسط نرم­افزار پروجن تولید شده، آزمایش شده و براساس خروجی الگوریتم نتایج کلی زیر بدست آمده است.
همانطور که مشاهده می­ شود، برخی از پروژه­ ها انحراف بسیار کمی (در برخی مقدار این انحراف، صفر است) از جواب بهینه دارند. در حالی که برای برخی دیگر، این انحراف بسیار زیاد می­باشد. علت این امر را می­توان در مقدار پارامترهای متغیری که برای هر پروژه، تعریف می­ شود، پیدا کرد. کولیش و اسپرچر اشاره کردند که با افزایش NC، مساله ساده­تر شده و حل آن توسط الگوریتم، راحت­تر انجام می­گیرد. بالعکس، افزایش ضریب منبع سبب مشکل­تر شدن مساله می­ شود و کاملا واضح است که با افزایش RS یعنی قدرت منبع نیز مساله را ساده­تر می­نماید.
بر این اساس و با توجه به اینکه مسائل بر اساس ترکیبات مختلف پارامترهای متغیر، تولید شده ­اند، در مواردی که مساله کمترین مقدار NC و RS و بیشترین مقدار RF را داراست، تعداد دفعاتی که الگوریتم به جواب بهینه رسیده است بسیار کم بوده ( در برخی مثال­ها، الگوریتم هیچگاه به جواب بهینه دست نیافته است) و لذا بیشترین انحراف از مقدار بهینه در این مسائل می­باشد. واضح است که کمترین انحراف نیز در مواردی است که مساله بیشترین مقدار NC و RS و کمترین مقدار RF را داراست ( در این حالت الگوریتم در بسیاری از حالتها به جواب بهینه دست یافته است).
نکته­ای که در اینجا باید به آن اشاره شود اینست که ASO نیز مانند بسیاری از الگوریتم­های فراابتکاری دیگر، نتایج بهتری را نسبت به روش­های مبتنی بر قوانین اولویت، می­دهد. علت این امر همانطور که قبلا نیز اشاره شد به خاطر ماهیت الگوریتم­های فراابتکاری است و اینکه این الگوریتم­ها معمولا از اطلاعات مربوط به جواب­های بدست آمده جهت تولید جواب­های بعدی، بهره می­برند، در حالی که روش­های مبتنی بر قوانین اولویت، هر جوابی را بطور مستقل تولید می­ کنند. با این وجود بایستی تاکید کرد که استفاده از یک روش فراابتکاری به تنهایی تضمینی برای رسیدن به جواب بهینه نمی ­باشد.
به طور کلی جهت حل مساله برنامه­ ریزی پروژه تحت شرایط محدودیت منابع، دو دسته از روش­ها وجود دارند. روش­های دقیق و روش­های فراابتکاری. برای مسائلی با مقیاس کوچک، روش­های دقیق، همواره جواب بهینه را بدست می­آورند، اما با بزرگ شدن مساله، این روش­ها کارایی خود را از دست می­ دهند. این در حالی است که روش­های فراابتکاری در مسائل بزرگ، براحتی می­توانند جواب را پیدا کنند، اما این روش­ها بهینگی جواب را تضمین نمی­کنند.

۵-۲)پیشنهادات

تحقیقات پیشنهادی برای آینده در دو دسته ارائه می­ شود:

• تعریف مسائل جدید مرتبط و بررسی آنها با الگوریتم ASO

• استفاده از روش­های فراابتکاری دیگر برای حل مساله مورد بررسی

در ادامه به توضیح هر دسته به طور جداگانه می­پردازیم.

۵-۲-۱)تعریف مسائل جدید مرتبط و بررسی آنها با الگوریتم ASO

همانطور که مشاهده شد، الگوریتم ASO که جدیدا توسط جاوید (۲۰۱۱) معرفی شده، کارایی بسیار خوبی نسبت به بسیاری از الگوریتم­هایی که پیشتر برای مساله مورد بررسی معرفی شده بودند، عمل کرد. دلیل این امر را می­توان در وسعت سیاست­هایی که الگوریتم ASO می تواند از آنها استفاده کرد، دانست. در واقع الگوریتم ASO، الگوریتمی است که هم از قدرت جستجوی گسترده الگوریتم­های جمعیت محور استفاده می­ کند و هم از خاصیت جستجوی سریع و جهتدار الگوریتم­های جستجوی محلی. با کمی دقت مشاهده می شود، می­توان با محدود کردن الگوریتم در حالات خاص آن را به الگوریتم­های دیگر تبدیل کرد. برای مثال با در نظر گرفتن جمعیت با اندازه یک، الگوریتم ASO به الگوریتم­های جستجوی محلی تبدیل می­ شود. در بخش ۳-۴ نحوه تبدیل الگوریتم ASO به الگوریتم PSO را دیدیم. الگوریتم ASO همچنین نوعی الگوریتم ژنتیک نیز می­باشد که عملگرهای تقاطع و جهش آن با همسایگی­های تعریف شده در بخش۳-۳-۴ بدست می­آیند.در این پایان نامه مساله برنامه­ ریزی پروژه در حالت محدود بودن منابع و حالت چند منبعی بررسی شد. این مساله را می­توان در حالت کلیتری که علاوه بر منابع تجدید پذیر، منابع غیر قابل تجدید نیز موجودند، بررسی کرد. حالت چند مدی کنترل پروژه نیز از حالت­هایی است که می ­تواند با توسعه الگوریتم معرفی شده در این پایان نامه بررسی و حل شود. از نتایج بدست آمده از حالت تک مدی و تنها با منابع تجدید پذیر پیش ­بینی می­ شود، الگوریتم ASO بتواند برای این مسائل نیز جواب­های خوبی تولید کند.

۵-۲-۲)استفاده از روش­های فراابتکاری دیگر برای حل مساله مورد بررسی

مساله RCPSP برای اولین بار در سال ۱۹۶۹، توسط پریتسکر [۶] با بهره گرفتن از یک مدل برنامه­ ریزی صفرویک مدل و حل شد. از آن پس تاکنون این مساله توسط روش­ها و الگوریتم­های دقیق و غیر دقیق فراوانی مورد آزمایش تحلیل­گران علوم کامپیوتر قرار گرفته است. اما با مشاهده سایت رسمی کنترل پروژه PSBLIB می­بینیم با وجود الگوریتم­های فراوان برای حل مساله، جواب­های بدست آمده برای نمودهای مساله به صورت پیوسته در حال بهبود می­باشند.
با توجه به نتایج قابل قبول الگوریتم ASO طراحی شده در این تحقیق، بررسی و بازبینی الگوریتم طراحی شده برای موثرتر کردن هر چه بیشتر آن با بهره گرفتن از تعریف سیاست­ها و همسایگی­های بیشتر و بررسی آنها، از جمله پیشنهاداتی است که می­توان برای طراحی الگوریتم­های جدید، ارائه داد.
ترکیب الگوریتم ASO با دیگر الگوریتم­های فراابتکاری از جمله جستجوی ممنوع در گام­های میانی الگوریتم ASO، با توجه به نتایج خوب الگوریتم­های ترکیبی در مسائل مختلف پیش ­بینی می­ شود باعث کاراتر شدن الگوریتم طراحی شده شود. بررسی این ادعا می ­تواند با طراحی الگوریتم ذکر شده در تحقیقات آینده مورد بررسی قرار گیرد.
منابع و مآخذ
منابع انگلیسی:

• Demeulmeester, E. K. & Horroelen, W. S. (2002). Project Scheduling: A research Handbook, Springer.

• Blazewicz, J., Lenstra, J.K., and A.H.G. Rinnooy Kan, “Scheduling Subject to Resource Constraints: Classification and Complexity”, Discrete Applied Mthematics, 5(1983), PP. 11-24. Evalutionary Computation (CEC), June 5-8, New Orlens, LA, pp. 2586-2592, 2011.

• Ahmadi-Javid, A., Anarchic society optimization: A Human-inspired method, Proceeding of IEEE Congress on