• طرح نمایش لیست اولویت فعالیتها ^[۱۲۰]

• طرح نمایش بر اساس قانون اولویت^[۱۲۱]

• طرح نمایش کلید تصادفی^[۱۲۲]

• طرح نمایش بردار انتقالی^[۱۲۳]

• طرح نمایش برنامه زمانبندی^[۱۲۴]

۲-۴-۲)انواع عملگرهای همسایگی

در حالت کلی دو نوع عملگر همسایگی یکانی^[۱۲۵] و عملگر همسایگی دودویی^[۱۲۶] داریم که هر کدام از آنها دارای انواعی به شرح ذیل است که ما فقط عناوین آنها را آورده و علاقه مندان برای مطالعه بیشتر به مرجع ]۱[مراجعه فرمایند:

۲-۴-۲-۱)عملگر همسایگی یکانی

بعضی از انواع آن به صورت ذیل است:

• عملگر همسایگی تبادل جفتی^[۱۲۷]

• عملگر همسایگی انتقالی^[۱۲۸]

• عملگر همسایگی تغییری^[۱۲۹]

۲-۴-۲-۲)عملگر همسایگی دودویی

بعضی از انواع آن به صورت ذیل است :

• عملگر ادغام یک نقطه ای^[۱۳۰]

• عملگر ادغام دو نقطه ای^[۱۳۱]

• عملگر ادغام یکنواخت^[۱۳۲]

در هر الگوریتم ابتکاری بهبود دهنده و یا الگوریتم فراابتکاری همیشه سه جزء باید مشخص شود تا طرز رویکرد ما در بکارگیری الگوریتم مشخص شود. اول نوع طرح تولید زمانبندی که جواب شدنی اولیه را برای شروع جستجو به ما میدهد و که ما دو نوع مهم طرح تولید زمانبندی سریالی و موازی را در بالا توضیح دادیم. دوم نوع طرح نمایش جوابها که ما بعضی انواع مهم آن را در بالا ذکر کردیم. سوم نوع عملگرهای همسایگی که ما بعضی از انواع مهم آن را در بالا ذکر کردیم. با ترکیب این سه جزء و انتخاب یک نوع الگوریتم فراابتکاری درواقع ما یک نوع مسیر حل خاص را برای جستجوی فضای جواب، میتوانیم پیشنهاد بدهیم.

۲-۵)الگوریتم های فراابتکاری

مشکل اساسی روش های حلی که از ترکیب الگوریتمهای ابتکاری سازنده و سپس بهبوددهنده برای حل مسائل NP-hard وجود دارد عدم توانایی آنها در فرار از جواب بهینه محلی ونیز وابستگی زیاد کیفیت جواب نهایی به کیفیت جواب اولیه است. ازآنجاییکه الگوریتمهای ابتکاری بهبوددهنده به دنبال جوابهای بهتر در همسایگی جواب فعلی میباشند در صورت قرار گرفتن در یک نقطه بهینه محلی هیچ رویکردی برای فرار از این بهینه محلی وجود ندارد. برای رفع این مشکل در چند دهه اخیر الگوریتمهای فراابتکاری جای الگوریتمهای ابتکاری بهبوددهنده را گرفته اند به این دلیل که این الگوریتمها به گونه ای طراحی شده اند که در تکرارهای پی درپی بتوانند از دام جواب بهینه محلی بگریزند و در نتیجه میتوان الگوریتمهای فراابتکاری را الگوریتمهای ابتکاری بهبوددهنده اصلاح شده نامید. الگوریتمهای فراابتکاری مجموعه یک سری استراتژیهای کلی است که رویه های بهبود جواب را هدایت میکند و موجب میشود که در مجموع جواب بهبود یافته و به سمت جواب بهینه سراسری میل کنیم. رویه های بهبود جواب که توسط استراتژیهای کلی تعیین و هدایت میشود، میتواند خود رویه های پیچیده بهینه سازی برای رفتن از یک جواب به جواب دیگر و یا رفتن یک جمعیت جواب به جمعیت جواب دیگر باشد. نکته مهمی که باید مد نظر بگیریم این است که این الگوریتمها هر کدام برای مسئله خاص و درشرایطی خاص قابل پیاده سازی است تا کارایی لازم را از خود نشان بدهد. ازآنجاییکه به تجربه معلوم شده است که هر یک از الگوریتمهای فراابتکاری در کدام مسائل دارای کارایی مناسب از لحاظ زمان و هزینه است، کسانیکه در استفاده از این الگوریتمها تجربه لازم را ندارند برای جلوگیری از اتلاف زمان وهزینه باید با متخصصین و افراد باتجربه در زمینه الگوریتمهای فراابتکاری مشاوره داشته باشند تا برای مسئله مورد نظر خود کاراترین الگوریتم انتخاب کنند. در یک تقسیم بندی کلی میتوان الگوریتمهای فراابتکاری را به دو دسته الگوریتمهای فراابتکاری مبتنی بر یک جواب^[۱۳۳] و الگوریتمهای مبتنی بر جمعیت^[۱۳۴] تقسیم بندی کرد. در الگوریتمهای مبتنی بر یک جواب که درواقع همان جستجوی محلی بدون ترس از به دام افتادن در جوابهای بهینه محلی است، فرایند جستجو فقط یک جواب را تغییر میدهد در حالیکه در الگوریتمهای مبتنی بر یک جمعیت در حین جستجو یک جمعیت از جوابها در حال تغییر به صورت همزمان هستند. الگوریتمهای فراابتکاری مبتنی بر یک جمعیت دارای انواع مختلفی هستند که یکی از انواع مهم آنها الگوریتمهای فراابتکاری تکاملی^[۱۳۵] است که این دسته از اصل تکامل در طبیعت برای حل مسائل الهام گرفتند. اصل تکامل در طبیعت به شکل تنازع بقا میان گونه های مختلف مشهود است به این معنا که هر گونه در طبیعت برای ادامه بقا تلاش میکند و گونه ای که قویتر است شانس بیشتری برای ادامه حیات و تولید- مثل را دارد. ایده به کاربردن اصول تکامل در طبیعت برای حل مسائل، به دهه ۱۹۴۰میلادی برمیگردد به طوریکه در اوایل سال ۱۹۴۸ دانشمندی به نام تورینگ^[۱۳۶] روش جستجوی تکاملی^[۱۳۷] را پیشنهاد داد. الگوریتمهای فرابتکاری تکاملی در ابتدا به دلیل هزینه بالای اجرایشان با اقبال کمی مواجه شدند اما در دو دهه اخیر گسترش قابل توجهی یافتند که دلیل این امر افزایش قدرت محاسباتی رایانه هاست. از مشهورترین روش های الگوریتمهای تکاملی میتوان به الگوریتم ژنتیک^[۱۳۸] و برنامه ریزی تکاملی^[۱۳۹] و استراتژی تکاملی^[۱۴۰] و برنامه ریزی ژنتیک^[۱۴۱] اشاره کرد که الگوریتم ژنتیک از همه آنها مشهورتر و پرکاربردتر است.. نوع دیگر از الگوریتمهای فراابتکاری مبتنی برجمعیت، میتوان به الگوریتمهای فراابتکاری مبتنی بر هوش جمعی^[۱۴۲] است که از رفتار جمعی گونه ها در طبیعت نظیر مورچگان و زنبورها و پرندگان و حشرات دیگر الهام گرفته است. مهمترین ویژگی الگوریتمهای مبتنی بر هوش جمعی که آن را از دیگر الگوریتمها متمایز میکند همکاری غیرمستقیم اجزا در این الگوریتمها است. از جمله موفقترین الگوریتمهای فراابتکاری مبتنی بر هوش جمعی میتوان به الگوریتم فراابتکاری بهینه سازی دسته پرندگان^[۱۴۳] و الگوریتم فراابتکاری کلونی زنبورها^[۱۴۴] و الگوریتم فراابتکاری کلونی مورچگان^[۱۴۵] رامیتوان نام برد. از الگوریتمهای فراابتکاری مبتنی بر یک جواب که بسیار معروف هستند میتوان به الگوریتم فراابتکاری جستجوی ممنوع^[۱۴۶] و الگوریتم فراابتکاری آنیل شبیه سازی شده^[۱۴۷] و جستجوی محلی هدایت شده^[۱۴۸] و جستجوی محلی تکرار شونده^[۱۴۹] را نام برد. در ادامه بعضی از الگوریتمهای فراابتکاری یاد شده را توضیح داده و ادبیات موضوع آنها را در حل مسئله زمانبندی پروژه با محدودیت منابع به صورت خلاصه تشریح میکنیم.

۲-۵-۱)الگوریتم ژنتیک

ایده اصلی الگوریتم ژنتیک از نظریه تکامل داروین^[۱۵۰](۱۸۵۹) الهام گرفته شده است ولی الگوریتم ژنتیک به شکل کنونی اش توسط جان هلند^[۱۵۱] (۱۹۷۵) در دانشگاه میشیگان ابداع شده است. الگوریتم ژنتیک جزء الگوریتمهای فراابتکاری مبتنی بر جمعیت است که از طبیعت الهام گرفته شده است و در رده الگوریتمهای تکاملی است. الگوریتم ژنتیک یکی از کاراترین روش های بهینه سازی مسائل ترکیبی است که اساس آن بر انتخاب طبیعی^[۱۵۲] (عامل اصلی تکامل زیستی) و برخی مفاهیم علم ژنتیک الهام گرفته شده است. در این روش برای بهینه سازی تابع هدف(تابع برازندگی^[۱۵۳]) مسئله در هر مرحله از یک جمعیت^[۱۵۴] اولیه کروموزومها^[۱۵۵] (افراد^[۱۵۶]) که در حقیقت پاسخهای اولیه مسئله میباشد، به یک جواب جدید از کروموزومها و یا یک نسل^[۱۵۷] جدید که در حقیقت پاسخ ثانویه مسئله مفروض میباشد، میرسیم. بنابراین با تکرار این عملیات و تولید جمعیت جدید از جمعیت قبلی در هر مرحله و در نتیجه رسیدن به نسلهای موفقتر، جمعیت به سمت یک پاسخ بهینه در حال حرکت است. در الگوریتم ژنتیک در هر مرحله برای یک رسیدن از یک جمعیت به جمعیت نسل بعد، از سه عملگر ادغام^[۱۵۸] و جهش^[۱۵۹] و انتخاب^[۱۶۰] استفاده میکنیم. در این الگوریتم برای داشتن یک جمعیت اولیه(جواب اولیه) میتوان هم به صورت تصادفی و هم با بهره گرفتن از الگوریتمهای ابتکاری سازنده استفاده کرد که تولید جمعیت اولیه به صورت تصادفی در الگوریتم ژنتیک متداولتر است. نوع طرح نمایش فعالیتها و نوع طرح زمانبندی اولیه و نوع عملگرهای مورد استفاده دراین الگوریتم، در کارایی آن بسیار موثر است و تغییرات در هر کدام میتواند رسیدن به جواب نزدیک به بهینه را سرعت بخشد. در استفاده از الگوریتم ژنتیک برای مسئله زمانبندی پروژه با محدودیت منابع در ادبیات موضوع میتوان به موارد ذیل اشاره کرد: لی^[۱۶۱] و کیم^[۱۶۲](۱۹۹۶) از یک الگوریتم ژنتیک بر اساس طرح نمایش کلید تصادفی و طرح تولید زمانبندی موازی برای حل مسئله RCPSP استفاده کردند، آنها از عملگر ادغام یک نقطه ای برای تولید جوابهای جدید استفاده کردند]۱۵[. از دیگر کارهای انجام شده میتوان به تلاش کوهلمورگن^[۱۶۳] (۱۹۹۹)اشاره کرد که از یک الگوریتم ژنتیک بر اساس طرح نمایش کلید تصادفی و طرح تولید زمانبندی سریالی برای حل مسئله RCPSP استفاده کرد، او از یک عملگر ادغام دو نقطه ای برای تولید جوابهای جدید استفاده کرد]۱۶[. آلکارز^[۱۶۴] و مارتو^[۱۶۵] (۲۰۰۱)، الگوریتم ژنتیک بر اساس روش نمایش جدید لیست فعالیتها با حالت زمانبندی استفاده کردند و برای تولید زمانبندی از طرح تولید زمانبندی سریالی با قانون اولویت LFT برای حل مسئله RCPSP استفاده کردند، آنها در یک طرح ابتکاری یک ژن اضافه به لیست نمایش فعالیتها اضافه کردند که مشخص میکرد که در زمانبندی از روش پیشرو یا پسرو استفاده شده است، آنها هم زمانبندی پیشرو و هم زمانبندی پسرو را در هر تولید زمانبندی سریالی پیاده سازی میکردند و هر کدام که زمان تکمیل پروژه بهینه تری داشت از آن استفاده و در ژن آخر با یک کروموزوم با نماد b برای جهت زمانبندی پیشرو و f برای جهت زمانبندی پسرو نمایش میدادند که این روش جدید طرح نمایش را طرح نمایش لیست فعالیتها با حالت زمانبندی نامیدند، آنها از سه عملگر ادغام جدید به نامهای عملگر ادغام مجموعه اولویت^[۱۶۶] و عملگر ادغام پیشرو- پسرو^[۱۶۷] و عملگر ادغام پیشرو- پسروی دو نقطه ای^[۱۶۸] استفاده کردند و علاوه بر آن از عملگر ادغام جدید هارتمن (۲۰۰۱) که در مرجع ]۱۷[ آمده است استفاده کرده است و همه این عملگرهای ادغام جدید را با هم مقایسه کرده است، نوع جدید نمایش فعالیتها این امکان به آنها داد که این سه نوع عملگر ادغام جدید را معرفی کنند، در نمونه گیریهای انجام شده توسط آنها الگوریتم پیشنهادی آنها بر همه الگوریتمهای قبلی که برای حل مسئله RCPSP استفاده شده است به جواب بهینه بهتری رسیده است و از همه آنها برتر است]۱۸[. یکی از معروفترین کارها در این بخش توسط هارتمن (۲۰۰۲) صورت گرفته است، الگوریتم ژنتیک معرفی شده توسط وی در زمره یکی از بهترین الگوریتمهای فراابتکاری ارائه شده برای حل مسئه RCPSP به شمار میرود. او برای ایجاد لیست اولیه فعالیتها از دو قانون اولویت مهم LFT و LST به طور همزمان استفاده کرد و شانس انتخاب هر کدام را برابر با ۵۰% قرار داد، او برای نمایش جواب از طرح نمایش لیست فعالیتها استفاده کرد و با ابتکاری جدید یک ژن به ابتدای این لیست کروموزوم اضافه کرد، که این ژن تعیین میکند که از طرح تولید زمانبندی سریالی یا موازی استفاده کنیم، در حالت کلی نمیتوان برتری این دو رو ش معروف را در تولید زمانبندی بر یکدیگر اثبات کرد، به دلیل اینکه هارتمن نشان داد که هر یک از این روش های تولید زمانبندی در حالت خاصی بر دیگری برتری دارد، او تصمیم گرفت از هر دو طرح تولید زمانبندی در جای مناسب خودش که او کشف کرده بود استفاده کند. الگوریتم فراابتکاری جدید او که به الگوریتم ژنتیک خودتطبیقی^[۱۶۹] معروف شد که در نمونه گیری انجام شده توسط او بر همه الگوریتمهای فراابتکاری مورد استفاده برای حل مسئله RCPSP به جوابهای بهینه بهتری رسید]۱۹[. از دیگر تلاشها در این حیطه میتوان به تلاش توکلو^[۱۷۰] (۲۰۰۲) اشاره کرد که او از یک الگوریتم ژنتیک برای حل مسئله RCPSP استفاده کرد که در آن عملگرها به صورت مستقیم بر روی زمانبندی عمل میکردندو از آنجاییکه عملگرهای ژنتیک ممکن است نسل جدید نشدنی به وجود بیاورند، او در ابتکاری جدید برای جلوگیری از ایجاد جوابهای ناموجه از یک تابع جریمه^[۱۷۱] استفاده کرد]۲۰[. هیندی^[۱۷۲] و همکارانش (۲۰۰۲) یک الگوریتم ژنتیک بر اساس طرح نمایش لیست فعالیتها و طرح تولید زمانبندی سریالی استفاده کردند، آنها از یک عملگر ادغام با حفظ ترتیب ^[۱۷۳] مشابه آنچه هارتمن در منبع ]۱۷[ استفاده کرد بهره جستند، آنها برای تولید جواب اولیه شدنی از مکانیسم نمونه گیری بر اساس قانون اولویت LFT ^[۱۷۴] مشابه منبع ]۱۷[ بهره بردند]۲۱[. کلهو^[۱۷۵] و تاوارز^[۱۷۶] (۲۰۰۳) الگوریتم ژنتیکی معرفی کردند که از طرح نمایش لیست فعالبها و طرح تولید زمانبندی سریالی استفاده میکرد، آنها یک عملگر ادغام جدید را بر روی لیست فعالیتها پیشنهاد کردند که به عملگر ادغام تابعی دیراتصال^[۱۷۷] معروف شد. عملگر ادغام تابعی دیر اتصال یک خصوصیت منحصر به فرد به این صورت داشت که در ابتدا با پذیرش جواب والد پدر و در ادامه هر جفت همسایگی مجاور که دارای ترتیبی وارونه در جواب والد مادر نسبت به والد پدر را داشت با هم تعویض میکرد]۲۲[. گنکالوز^[۱۷۸] و مندز^[۱۷۹] (۲۰۰۳) الگوریتم ژنتیک با طرح نمایش کلید تصادفی و طرح تولید زمانبندی موازی اصلاح شده^[۱۸۰] برای حل مسئله RCPSP استفاده کردند. در طرح تولید زمانبندی موازی اصلاح شده نیمه نخست ورودیها لیست نمایش بر اساس انتخاب فعالیتها و نیمه دوم ورودیهای لیست نمایش بر اساس زمان تاخیر بود]۲۳[. مندز و همکارانش (۲۰۰۹) الگوریتم ژنتیک بر پایه کلید تصادفی^[۱۸۱] برای حل مسئله RCPSP ارائه کردند، آنها برای طرح تولید زمانبندی از زمانبندی فعال پارامتریک^[۱۸۲] که نخستین بار توسط گنکالوز و بیرائو^[۱۸۳] (۱۹۹۹) ابداع شد و در منبع ]۲۴[ آمده است استفاده کردند، در طرح تولید زمانبندی فعال پارامتریک هم خصوصیات زمانبندی بدون تاخیر و هم زمانبندی فعال به صورت همزمان در این طرح آمده است. مندز نشان داد که طرح تولید زمانبندی فعال پارامتریک هم بر طرح تولید زمانبندی سریالی و هم بر طرح تولید زمانبندی موازی برتری دارد، آنها نتیجه گرفتند که روش پیشنهادی آنها در مقایسه با بهترین الگوریتمهای فراابتکاری به کاررفته برای مسئله RCPSP به نتایج قابل قبولی رسیده است]۲۵[.

۲-۵-۲)الگوریتم جستجوی ممنوع

الگوریتم جستجوی ممنوع توسط گلوور^[۱۸۴] (۱۹۸۹) به وجود آمد. این الگوریتم در واقع از روش نزولی با تندترین شیب الگو گرفته است و میتوان آن را حالت اصلاح شده روش نزولی با تندترین شیب نامید که به وسیله ترفندهایی از افتادن در دام بهینه محلی می گریزد. الگوریتم جستجوی ممنوع با بهره گرفتن از حافظه کوتاه مدت^[۱۸۵] و حافظه بلند مدت^[۱۸۶] انعطاف پذیری بیشتری در عملیات جستجو ایجاد کرده و مسئله را از نقطه بهینه محلی دور و در جهت دستیابی بهینه سراسری حرکت میکند. در الگوریتم جستجوی ممنوع یکی از راهکارها برای فرار از نقطه بهینه محلی این است که برای برخی حرکتهای غیر بهبود دهنده اجازه حرکت به آن نقاط داده میشود. یک الگوریتم جستجوی ممنوع تقریبا مانند الگوریتمهای جستجوی محلی کار میکند با ابن تفاوت که برای جلوگیری از ایجاد دور و تسلسل در جوابها و افتادن در دام بهینه محلی از مفهومی به نام لیست ممنوع^[۱۸۷] نیز استفاده میکنند. فهرست لیست ممنوع حاوی تعدادی از جوابهای مسئله است که در هر مرحله، حرکت به آنها ممنوع است حتی اگر بهترین جواب در همسایگی جواب فعلی باشد. این فهرست ممنوع در هر مرحله به روزرسانی میشود. تعیین اندازه لیست ممنوع بسیار مهم در این الگوریتم است به این دلیل که لیست ممنوع طولانی ،سرعت اجرای الگوریتم را کاهش میدهد ولی بهینگی آن را افزایش میدهد و از طرف دیگر لیست ممنوع کوتاه سرعت اجرای الگوریتم را افزایش میدهد اما احتمال ایجاد دور و تسلسل به خاطر افتادن در دام بهینگی محلی افزایش می بابد. از کارهای انجام شده در دو دهه اخیر که از الگوریتم فراابتکاری جستجوی ممنوع برای حل مسئله زمانبندی پروژه با محدودیت منابع استفاده شد میتوان به تلاش پینسون^[۱۸۸] و همکارانش (۱۹۹۴) اشاره کرد که یک روش فراابتکاری جستجوی ممنوع را معرفی کردند که درآن از طرح نمایش لیست فعالیتها و طرح تولید زمانبندی سریالی استفاده میکردند. آنها از سه عملگر همسایگی متفاوت به نامهای عملگر تبادلات زوجی^[۱۸۹] و عملگر تبادلات سراسری^[۱۹۰] و عملگر انتقال^[۱۹۱] استفاده کردند]۱[. توماس^[۱۹۲] و سالهی^[۱۹۳] (۱۹۹۸) یک روش جستجوی ممنوع را برای حل مسئله RCPSP ارائه کردند که از عملگرها به صورت مستقیم بر روی زمانبندی استفاده میکردند، آنها سه حرکت متفاوت برای جستجوی همسایگی معرفی کردند. از آنجاییکه نتایج زمانبندی با این عملگرهای ممکن است نشدنی باشد آنها از یک رویه اصلاحی که زمانبندی نشدنی را به زمانبندی شدنی تبدیل میکرد استفاده کردند]۲۶[. کلین^[۱۹۴] (۲۰۰۰) یک روش جستجوی ممنوع واکنشی^[۱۹۵] برای حل مسئله RCPSP با محدودیت منابعی که دارای زمان های متفاوت است گسترش داد، در این روش او از طرح نمایش لیست فعالیتها و طرح تولید زمانبندی ابتکاری سریالی استفاده کرد، او از یک عملگر همسایگی جدید مشابه آنچه بار^[۱۹۶] و همکارانش (۱۹۹۸) در منبع]۲۷[ استفاده کردند بهره جست]۲۸[.
نونوبه^[۱۹۷] و ایبراکی^[۱۹۸] (۲۰۰۲) یک روش جستجوی ممنوع برای حالات مختلف مسئله RCPSP پیشنهاد دادند که ما فقط خصوصیاتی از تلاش آنها ، که مربوط به مسالهRCPSP کلاسیک است را در این مقاله در نظر میگیریم، در این روش از طرح نمایش لیست فعالیتها و طرح تولید زمانبندی سریالی استفاده میشود. او از یک عملگر همسایگی ویژه کاهشی^[۱۹۹] برای جستجوی محلی استفاده کرد]۲۹[. نای^[۲۰۰] وهمکارانش (۲۰۰۸) از یک الگوریتم جستجوی ممنوع برای مسئله RCPSP استفاده کرد، آنها از قانون اولویت کوچکترین مقدار شناوری در مرحله اول الگوریتم ابتکاری سازنده استفاده کرد.آنها از عملگر همسایگی درج^[۲۰۱] و عملگر همسایگی جا به جایی^[۲۰۲] برای حرکت از یک نقطه به نقاط همسایگی دیگر استفاده کردند. آنها در انتها نتیجه گرفتند که روش TS پیشنهادی آنها نسبت به روش های الگوریتم ژنتیک و الگوریتم آنیل شبیه سازی شده، به جوابهای بهتری برای حل مسئله RCPSP می رسد]۳۰[.

۲-۵-۳)الگوریتم آنیل شبیه سازی شده

ایده اولیه این الگوریتم که بعدها مبنای پیدایش الگوریتم آنیل شبیه سازی شده شد اولین بار توسط متروپلیس^[۲۰۳] (۱۹۵۳) بر اساس فرایند آنیل مواد در علم ترمودینامیک آماری مطرح گردید. در علم ترمودینامیک آماری رابطه بین ساختار اتمی، آنتروپی و دما در طول فرایند آنیل یک ماده مورد مطالعه قرار میگیرد. فرایند آنیل با ماده ای در وضعیت گداخته آغاز شده و سپس به تدریج دمای ماده کاهش می یابد. در هر دما ماده مجاز به رسیدن به تعادل گرمایی می باشد. دما در مراحل اولیه نباید سریع کاهش یابد زیرا برخی کاستیها در ماده پیدا شده و ماده به وضعیت کمینه انرژی نخواهد رسید. الگوریتم آنیل شبیه سازی شده نیز از این فرایند توضیح داده شده الگوبرداری کرده است. الگوریتم آنیل شبیه سازی شده توسط پاتریک^[۲۰۴] و همکارانش (۱۹۸۳) که همه آنها متخصصانی در زمینه فیزیک آماری بودندبه وجود آمد. این الگوریتم از روش نزولی با تندترین سرعت استفاده کرده است و با بهبود این روش از افتادن در دام بهبنه محلی می گریزد. این خاصیت مهم آنیل شبیه سازی شده به این دلیل است که در این الگوریتم حرکتهای غیر بهبوددهنده نسبت یه جواب فعلی با احتمال کمی پذیرفته میشود. خاصیت بسیار مهم دیگر آنیل شبیه سازی شده آن است که با بکارگیری برنامه های آنیلی پیچیده به سمت جواب بهینه سراسری همگرا است. الگوریتم آنیل شبیه سازی شده یک جستجوی فراابتکاری ساده و اثربخش در حل مسائل بهینه سازی ترکیبی است که در حل مسائل پیوسته نیز گسترش یافته است. الگوریتم آنیل شبیه سازی شده بر خلاف الگوریتم جستجوی ممنوع یک الگوریتم بدون حافظه است به این معناکه در این الگوریتم مکانیزمی برای ذخیره اطلاعات در طول جستجو وجود ندارد. یکی از حسن های مهم الگوریتم آنیل شبیه سازی شده پیاده سازی ساده و آسان آن برای مسائل مختلف است. از الگوریتم فرابتکاری آنیل شبیه سازی شده برای حل مسئله RCPSP میتوان به تلاشهای سامپسون^[۲۰۵] و ویس^[۲۰۶] (۱۹۹۳) اشاره کرد که آنها از طرح نمایش بردار انتقالی برای نمایش جوابها و نیز عملگرهای تغییر استفاده کردند]۱[. همچنین لی^[۲۰۷] و کیم^[۲۰۸] (۱۹۹۶) یک روش آنیل شبیه سازی شده معرفی کردند که طرح نمایش آنها بر مبنای طرح نمایش کلید تصادفی استوار بود و از طرح تولید زمانبندی موازی برای تولید جوابهای اولیه استفاده کردند، آنها از عملگر تبادل زوجی برای جستجوی همسایگی سود بردند]۱[. از مهمترین کارهای انجام شده که میتوان آن را کاراترین روش آنیل شبیه سازی شده برای حل مسئله RCPSP میتوان به تلاشهای والس^[۲۰۹] و همکارانش (۲۰۰۵) ، اشاره کرد که آنها در طرح تولید زمانبندی از روش ابتکاری بهبوددهنده پیشرو-پسرو^[۲۱۰] استفاده کردندکه این روش توسط تورموس^[۲۱۱] و لووا^[۲۱۲] (۲۰۰۱) به وجود آمد که میتوان آن را در منبع ]۳۱[ به صورت کامل مطالعه کرد اما ما در اینجا به شرح مختصری از بهبوددهنده پیشرو-پسرو میپردازیم، در این روش ابتکاری در هر مرحله از طرح تولید زمانبندی موازی یا سریالی برای تولید یک زمانبندی برای نمونه گیری براساس قانون اولویت LFT استفاده میشود، در انتقال پسرو فعالیتها از راست به چپ و در دیرترین زمان شدنی زمانبندی میشود سپس در انتقال پیشرو فعالیت از چپ به راست ودر زودترین زمان شدنی، زمانبندی میشوند. آنها برای تعریف همسایگی از تعریف همسایگی والس و همکارانش (۲۰۰۳) که در منبع]۳۲[ به طور کامل توضیح داده شده است استفاده کردند. در این همسایگی تعریف شده، انتخاب فعالیت بعدی باید براساس ترتیب فعالیتهای جواب اولیه ویا برطبق نمونه گیری تصادفی از فعالیتها، صورت پذیرد، آنها نتیجه گرفتند که روش آنیل شبیه سازی شده پیشنهادی آنها دارای بهترین کیفیت جواب از لحاظ بهینگی نسبت به روش های قبلی پیشنهادی آنیل شبیه سازی شده در حل مسئله RCPSP است]۳۳[.

۲-۵-۴)الگوریتم دسته پرندگان

یکی دیگر از الگوریتمهای فراابتکاری مبتنی بر جمعیت، الگوریتم بهینه سازی دسته پرندگان است که درسال ۱۹۹۵ توسط کندی^[۲۱۳] و ابرهارت^[۲۱۴] ابداع شد که در رده الگوریتمهای هوش جمعی است. در این روش از رفتار جمعی ارگانیزمهای طبیعی نظیر پرندگان و ماهی ها در یافتن منطقه ای با غذای کافی الهام گرفته شده است. در این گونه اجتماع ها بدون وجود کنترل مرکزی یک رفتار، یک رفتار هماهنگ شده بین اجزای جمعیت وجود دارد. به بیان ساده تر گروهی از پرندگان را در نظر بگیرید که به صورت تصادفی در فضای مشخص به دنبال غذا هستند و فقط یک تکه غذا در این فضای جستجو وجود دارد و هیچ پرنده ای مکان دقیق آن را نمیداند اما هر پرنده میزان فاصله خود را از آن تکه غذا در هر مرحله میداند اکنون با دانستن این فرضیات بهترین استراتژی برای یافتن غذا چگونه تعریف میشود. یک استراتژی موثر میتواند این باشد که همه پرنده ها، از پرنده ای که به تکه غذا نزدیکتر است در حرکت بعدی خود تبعیت کند. الگوریتم بهینه سازی دسته پرندگان به نام الگوریتم بهینه سازی تجمعی ذرات هم معروف است که در سالهای اخیر به صورت موفق برای حل مسئله بهبنه سازی مختلف مورد استفاده قرار گرفته است. برای تشریح ریاضی وار الگوریتم بهینه سازی دسته پرندگان یک اجتماع شامل N ذره(پرنده) را در نظر بگیرید که در یک فضای D بعدی در حال پرواز هستند. هر جزء(پرنده) i ، یک جواب کاندید برای مسئله است و با بردار x_i فضای جستجو، نمایش داده میشود. هر جزء(پرنده) دارای موقعیت و سرعت مخصوص به خود است که جهت پرواز و سرعت حرکت آن را نشان میدهد. برای حل مسئله بهینه سازی از مزایای همکاری میان اجزاء(پرندگان) در این الگوریتم استفاده شده است. هر جزء(پرنده) i ، از بهترین موقعیت مشاهده شده توسط خود و نیز بهترین موقعیت مشاهده شده توسط کل جمعیت آگاه است و با توجه به این دو مورد مکان کنونی و سرعت خود را انتخاب میکند. الگوریتم بهینه سازی دسته پرندگان یک الگوریتم حافظه دار است بدیت معنا در هر مرحله مسیر حرکت ذرات(پرندگان) بر اساس تجارب قیلی جمعیت تعیین میگردد. از دیگر خصوصیات این الگوریتم میتوان به همگرایی سریع به جواب بهینه و محدود بودن تعداد پارامترهای الگوریتم اشاره کرد. از آنجاییکه الگوریتم بهینه سازی دسته پرندگان، جستجو را به طور مستقیم با بهره گرفتن از تابع هدف انجام میدهد میتوان را آن برای بهینه سازی توابع هدف مشتق ناپذیر استفاده کرد. در این الگوریتم مسئله انقراض و جایگزینی نسلها مانند الگوریتم ژنتیک، وجود ندارد که این خود باعث زمان و حافظه مورد نیازکم، برای اجرای این الگوریتم میشود. در الگوریتم بهینه سازی دسته پرندگان امکان توازن بین جستجوی فردی و سراسری با تنظیم مناسب پارامترها وجود دارد که این یک حسن بسیار بزرگ است. در زمینه کاربرد الگوریتم بهینه سازی دسته پرندگان برای حل مسئله RCPSP میتوان به موارد ذیل اشاره کرد. ژانگ^[۲۱۵] و همکارانش (۲۰۰۵) یک رویکرد مبتنی بر الگوریتم بهینه سازی دسته پرندگان را که در آن از دو رویکرد برای نمایش ذرات(پرندگان) استفاده میشد برای حل مسئله RCPSP استفاده کردند. آنها از دو طرح نمایش به نامهای طرح نمایش بر اساس اولویت^[۲۱۶] و طرح نمایش بر اساس توالی فعالیت^[۲۱۷] استفاده کردند که در طرح نمایش اول جواب حاصل همیشه موجه است اما در طرح نمایش دوم امکان تولید جوابهای غیرموجه نیز وجود دارد، بنابراین آنها یک مکانیزم ابتکاری با الگوریتم بهینه سازی دسته پرندگان ترکیب کردند تا منجر به تولید جوابهای موجه گردد. در هر دو طرح نمایش، ذرات(پرندگان) با بهره گرفتن از طرح تولید زمانبندی سریالی به یک برنامه زمانبندی تبدیل میشدند، آنها نتیجه گرفتند که در طرح نمایش ذرات(پرندگان) به صورت توالی فعالیتها به جواب بهینه بهتری نسبت به طرح نمایش بر اساس اولویت، حاصل شده است]۳۴[. چن^[۲۱۸] و همکارانش (۲۰۱۰) الگوریتم بهینه سازی دسته پرندگان را برای حل مسئله RCPSP توسعه دادند. در روش مورد استفاده آنها ذرات(پرندگان) بیانگر شروع فعالیتها هستند، برای هر فعالیت بر اساس مقادیر ذرات(پرندگان) یک احتمال انتخاب تعریف میشود تا اولویت مرتیط با هر ذره ای(پرنده ای) برای زمانبندی فعالیتها به دست آید، در هر تکرار فعالیتها از روش زمانبندی دو جهته که به صورت تصا فی انتخاب میشوند زمانبندی میشوند، در حین تعیین زمانبندی شروع فعالیتها از جستجوی محلی با گزینه های تاخیر^[۲۱۹] برای جلوگیری از به دام افتادن در بهینه محلی استفاده میشود، همچنین آنها روش مسیر بحرانی را برای افزایش قدرت الگوریتم برای یافتن جوابهای موجه با الگوریتم بهینه سازی دسته پرندگان ترکیب کردند. نتایج آزمایشات آنها نشان میدهد که الگوریتم بهینه سازی دسته پرندگان ترکیبی آنها، از الگوریتم بهینه سازی دسته پرندگان معمولی بهتر بوده و نیز نسبت به الگوریتم بهینه سازی کلونی مورچه گان در یافتن جوابهای بهینه، نتایج بهتری را حاصل میکنند]۳۵[.

۲-۵-۵)الگوریتم بهینه سازی جامعه نامنظم

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

فصل سوم
معرفی مسئلهRCPSP و الگوریتم ASO

مقدمه

شکل کلاسیک مسئله ی زمانبندی پروژه با محدودیت منابع به علت کاربرد فراوان و داشتن خواص مفید در تجزیه و تحلیل مسائل زمانبندی به وفور مورد استفاده قرار میگیرد. در مدل RCPSP فرض بر آن است که برای هر فعالیت پروژه فقط یک حا لت اجرا وجود دارد، مسئله مورد بررسی ما یک پروژه با n فعالیت حقیقی و دو فعالیت مجازی است که تنها رابطه تقدمی FS^min = ۰ ، بین فعالیتها وجود دارد و هر فعالیت برای اجرا فقط به منابع تجدیدپذیر نیازمند است. طول اجرای فعالیت j ام برابر با d_j و مقداری قطعی در مسئله مورد بررسی ما است. میزان نیاز فعالیت j ام در هر پریود زمانی به منبع kR برابر با r_jk است. فرض میکنیم که از منبع تجدیدپذیر kR در هر پریود زمانی مقدار AR_k واحد موجود است. در مسئله مورد بررسی ما مقادیر r_jk و AR_k مقادیری ثابت ، صحیح و مثبت هستند. تابع هدف مسئله RCPSP یافتن یک زمانبندی است که هم از نظر روابط تقدمی و هم از نظر محدودیت منابع موجه بوده و دارای کمترین طول زمانبندی باشد. برای آشنایی بهتر با مسئله RCPSP در ادامه دو مدل مفهومی و یک مدل به روش برنامه ریزی خطی را تشریح میکنیم.

۳-۱)ارائه مدل مفهومی مسئله RCPSP

مدل مفهومی مسئله RCPSP به صورت ذیل است:
Minimize S_n+1 (۱)
St :
S₀ = ۰ (۲)
S_j S_i + d_i (i , j) E (3)
_ik AR_k t 0 (4)
i = 0 , 1 , … , n + 1 ; k = 1 , 2 , … , m
در فرمول بالا فعالیت اول و ۱ n+ام مجازی و بقیه فعالیتها حقیقی است. متغیرهای تصمیم S_i زمان شروع فعالیتها را نشان میدهد. در فرمول ۳ مجموعه E ، مجموعه روابط تقدمی بین فعالیتهای پروژه را نشان میدهد. D_i طول مدت فعالیت i ام را نشان میدهد. در فرمول ۴ ، مجموعه S(t) فعالیتهایی را نشان میدهد که در زمان t در حال انجام و پیشرفت هستند. متغیر r_ik میزان نیاز فعالیت i ام به منبع k ام در هر پریود زمانی را نشان میدهد که مقداری قطعی است. AR_k میزان منبع تجدیدپذیر k را در هر پریود زمانی نشان میدهد. معادله ۱ ، تابع هدف مینیمم کردن زمان شروع فعالیت مجازی آخر را نشان میدهد. معادله ۲ نشان میدهد که فعالیت مجازی اول، در زمان صفر شروع میشود. معادله ۳، روابط تقدمی بین فعالیتها را که فقط از نوع FS^min = ۰ است را نشان میدهد. معادله ۴ ، نشان میدهد که در لحظه انجام پروژه هر فعالیت حداکثر به میزان منبع در دسترس تجدیدپذیر میتواند انتخاب خود را انجام دهد. مدل ریاضی مفهومی نمیتواند به طور مستقیم حل شود زیرا هیچ راهی برای معنا کردن مجموعه S(t) که در فرمول ۴ آمده است وجود ندارد بنابراین نیاز به مدل ریاضی که قابلیت حل شدن داشته باشد در دهه ۶۰ میلادی احساس شد که میتوان به مدلهای پریتسکر^[۲۲۵] (۱۹۶۹) ]۳۷[ ، کاپلان^[۲۲۶] (۱۹۸۸) ]۱[، مدل آلوارز- والدز^[۲۲۷] (۱۹۹۳) ]۳۸[، مدل مینگوزی^[۲۲۸] (۱۹۹۸) ]۳۹[و مدل کلین^[۲۲۹] (۲۰۰۰) ]۱[ ، اشاره کرد. این پایان نامه قصد دارد مدل برنامه ریزی ریاضی خطی پریتسکر را که جزء اولین مدلهای ریاضی است در ادامه تشریح کنیم.

۳-۲)ارائه و تبیین مدل ریاضی مبتنی به روش برنامه ریزی خطی از پریتسکر برای حل مسئله RCPSP

مدل ذیل یکی از اولین مدلهای ریاضی جهت حل مسئله RCPSP است که توسط پریتسکر ارائه شده است. در این مدل متغیر صفر و یک y_jt به صورت ذیل تعریف میشود. برای هر فعالیت j J و هر زمان اتمام موجه t [ EST_j , LST_j ] که در آن EST_j و LST_j بر اساس روش CPM به دست میایند. اگر اجرای فعالیت j ام در زمان t شروع شود ، ۱ y_jt =است و در غیر اینصورت ۰ = y_jt است.