شکل ۳-۲ فلوچارت Elitist TLBO[39]

فصل چهارم:
حل مسئله
۴-۱ مقدمه
مسئله زمان بندی پروژه با منابع محدود پیشینه ای بیش از ۴۰ سال دارد. این مسئله تعمیمی از مسئله کار-خرید^[۵۵] می­باشد و یک مسئله NP-HARD است. برای حل این مسئله دو رویکرد روش­های دقیق و ابتکاری وجود دارند[۴۰]. حل مصادیق واقعی این مسئله به دلیل پیچیـدگی، گستردگی و دشواری با روش­های دقیق نظیر برنامه ریزی­ریاضی، برنامه ریزی پویا و یا شاخه و کران غیر عملی است[۴۱]. البته در ادبیات موضوع کاربرد روش­های دقیق در حل مصادیق کوچکتر این مسئله نیز گزارش شده­است. به عنوان نمونـه, دکرو و همکاران در خصوص برنامه‌ریزی ریاضی[۴۲]، اکملی و همکاران[۴۳]، همچنین کاروترز و همکاران[۴۴]، در خصوص روش­های شمارشی مثل برنامه ریزی پویا، پتروویچ[۴۵]؛ دمیولمیستر و همکاران[۴۶] در خصوص روش­های شاخه و کران به این مسئله پرداخته­اند. به دلیل ناکارآمد بودن روش­های دقیق، اکثر مسائل واقعی زمان­بندی پروژه با منابع محدود با رویکردهای ابتکاری حل می‌شوند. بسیاری از رویکردهای ابتکاری حل مسئله برنامه ریزی پروژه با منابع محدود در سال ۲۰۰۶ میلادی مورد بررسی قرار گرفتند[۴۷]. آنها این رویکردها را در چهار گروه با عناوین زیر دسته بندی کردند :
(( اینجا فقط تکه ای از متن درج شده است. برای خرید متن کامل فایل پایان نامه با فرمت ورد می توانید به سایت feko.ir مراجعه نمایید و کلمه کلیدی مورد نظرتان را جستجو نمایید. ))

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

جدول ۴-۱ سیرتکاملی حل مسئله زمانبندی پروژه با منابع محدود

۴-۲ سوابق اخیر حل مسئله زمانبندی پروژه با منابع محدود
در سال­های اخیر الگوریتم­های فراابتکاری زیادی برای حل مسائل پیچیده RCPSP ارائه شده­است. در ادامه به برخی از این الگوریتم­ها می­پردازیم.

• الگوریتم پرندگان با الهام از رفتار جمعی پرندگان و ماهی‌ها و بکارگیری مفاهیم الگوریتم‌های تکاملی, معرفی شد. در این الگوریتم، تعدادی ذره که راه حل­های کاندیدای مسئله هستند، یک ازدحام را تشکیل می‌دهند. این ذرات در فضای مسئله حرکت کرده و براساس نتایج فردی خود و نتایج جمعی سعی می­ کنند تا راه حل بهینه در فضای جستجو را بیابند. این روش بوسیله ابعاد و غیرخطی بودن مسئله، خیلی تحت تأثیر قرار نگرفته و نتایج خوبی در محیط‌های استاتیک, نویزی و محیط­های بطور پیوسته در حال تغییر می‌گیرد. این ویژگی‌ها به علاوه سادگی پیاده‌سازی، عدم الزام بر پیوستگی تابع هدف و توانایی وفق دادن به محیط پویا باعث شده که این الگوریتم در حوزه‌های بسیار مختلفی بکار برده شود. در سال ۲۰۰۸ زنگ و همکارانش الگوریتم بهبود یافته پرندگان را برای مسئله RCPSP بکار برده­اند[۵۸]. در سال ۲۰۰۸ نیز جاربویی و همکارانش الگوریتم ترکیبی پرندگان برای این مسئله بکار گرفته­اند[۵۹].

• الگوریتم ژنتیک بصورت گسترده در حل این مسئله بکار رفته­است. هر راه حل بوسیله یک کروموزم مشخص می­گردد. هر کروموزم دارای چند ژن است. ژن­ها بصورت رشته­هایی هستند که برای نمایش قوانین اولویت و نمایش حالت و زمان انجام هر فعالیت بکار می­روند. ژن­های مربوط به کروموزم اولیه بصورت تصادفی انتخاب می­گردند. عملگرهای الگوریتم ژنتیک (تقاطع و جهش( برای بدست آوردن و حفظ کردن کروموزم­های خوب استفاده می­گردند و مشخصات هر نسل را برای نسل بعد نگهداری می­ کنند. سعی می­گردد، فضای بیشتری از پاسخ­های ممکن کاوش گردند و بهترین از نظر تابع هدف را پیدا کنند. در سال ۲۰۰۹ مندس و همکارانش الگوریتم ژنتیک مبتنی بر کلید تصادفی را برای حل مسئله RCPSP بکار برده­اند[۶۰].

• الگوریتم زنبور براساس رفتارکلونی زنبورها عمل می­ کند. در الگوریتم زنبور هر منبع غذایی نشان دهنده یک جواب شدنی مسئله می­باشد. مقدار شهد هر منبع غذایی متناظر با مقدار تابع هدف جواب شدنی می­باشد. سه نوع زنبور در این الگوریتم تعریف می­گردد. زنبورهای راهنما، آن دسته از زنبورهایی هستند که نسبت به دیگر زنبورها از موقعیت بهتری برخوردارهستند. زنبورهای سرباز زنبورهایی هستند که به صورت تصادفی در همسایگی زنبورهای راهنما به دنبال منبع غذایی می­گردند. در نهایت زنبورهای دسته سوم به صورت تصادفی منابع غذایی جدید را جستجو می­ کنند. هر چرخه الگوریتم شامل سه گام اساسی می­باشد. گام اول انتخاب زنبورهای راهنما می­باشد. گام دوم، فرستادن زنبورهای سرباز در همسایگی زنبورهای راهنما برای پیدا کردن منابع غذایی جدید،گام سوم فرستادن زنبورهای کاوشگر به صورت تصادفی به دنبال منابع غذایی جدید می­باشد. در پیاده­سازی الگوریتم زنبورها در مسئله RCPSP از یک لیست اولویت استفاده می­ شود. هر زنبور نشان دهنده یک موقعیت در فضای جستجو می­باشد. اگر مسئله n فعالیت داشته­باشد آنگاه زنبورها در یک فضای n بعدی حرکت می­ کنند. هر موقعیت بعنوان یک لیست اولویت در نظر گرفته می­ شود. هر عنصر این لیست یک فعالیت را نمایندگی می­ کند و مقدار متناظر با آن عنصر، اولویت آن فعالیت را مشخص می­ کند. بردار موقعیت هر زنبور، مقادیر اولویتn فعالیت را مشخص می­ کنند. در الگوریتم مصنوعی زنبورها نیز سه نوع زنبور داریم. زنبورهای کارگر، زنبورهایی می­باشند که با در نظر گرفتن منابع غذایی شناخته شده قبلی خود به دنبال پیدا کردن یک منبع غذایی جدید می­گردند. زنبورهای ناظر با بهره گرفتن از اطلاعاتی که زنبورهای کارگر در اختیارشان می­گذارند، به دنبال منبع غذایی جدید می­باشند. در نهایت زنبورهای دسته سوم به صورت تصادفی منابع غذایی جدید را جستجو می­ کنند. در سال ۲۰۱۱ اکبری و همکارانش الگوریتم زنبورهای مصنوعی را برای حل مسئله RCPSP بکار برده­اند[۶۱]. الگوریتم گروهی زنبورها درسال ۲۰۱۰ توسط اکبری ارائه­گردید. این الگوریتم تلفیقی از الگوریتم پرندگان و الگوریتم مصنوعی زنبورها می­باشد. در این الگوریتم سه نوع زنبور تعریف می­گردد: زنبورهای کارگر، زنبورهای ناظر و زنبورهای کاوشگر. زنبورهای کارگر، زنبورهایی می­باشند که با در نظر گرفتن منابع غذایی شناخته شده قبلی خود و بهترین جواب یافته شده تاکنون توسط خود زنبور و بهترین جواب یافت شده تاکنون دربین تمامی زنبورها، به دنبال پیداکردن یک منبع غذایی جدید می­گردند. زنبورهای ناظر به استفاده از اطلاعاتی که زنبورهای کارگر در اختیارشان می­گذارند و با در نظر گرفتن منابع غذایی شناخته شده قبلی خود، به دنبال منبع غذایی جدید می­باشند. در نهایت زنبورهای کاوشگر به صورت تصادفی در همسایگی خودشان منابع غذایی جدید را جستجو می­ کنند. در سال ۲۰۱۱ اکبری و زیارتی و ضیغمی الگوریتم­های زنبور، زنبور مصنوعی و گروهی زنبورها را برای حل RCPSP بکار گرفتند و کارایی آنها را با هم مقایسه نمودند[۳]. این الگوریتم­ها پاسخ­های رقابت­پذیری با دیگر الگوریتم­ها را ارائه می­ دهند. در سال ۲۰۱۲ نیز ضیغمی و اکبری الگوریتم زنبور مصنوعی را با الگوریتم ژنتیک پیوند زدند و برای حل مسئله RCPSP استفاده­کردند[۶۲].

• الگوریتم کرم شب­تاب براساس روشنایی یک گروه از کرم شب تاب طراحی شده است. نور چشمک زن برای یک کرم شب­تاب حیاتی است و برای یافتن غذا و جفت­گیری و محافظت در مقابل شکارچیان از آن استفاده می­ کند.کرم­های شب­تاب به سمت­ مکانهای با نور بیشتر جذب می­شوند. کرمی که درخشندگی کمتری دارد به سمت کرمی که درخشندگی بیشتری دارد جذب می­ شود. اگر کرم شب­تابی درخشنده­تر از کرم مورد نظر نباشد، بطور تصادفی حرکت می­ کند. روشنایی با افزایش فاصله نیز کاهش می­یابد. میزان روشنایی نور چشمک­زن بعنوان تابع هدف در نظر گرفته می­ شود. در حل مسئله RCPSP هر کرم شب تاب یک زمانبندی برای مسئله را نشان می­دهد. مسئله­ای با n فعالیت دارای کرم­های شب­تاب با فضای جستجوی n بعدی است. هر موقعیت بعنوان یک لیست اولویت در نظر گرفته می­ شود و هر عنصر این لیست یک فعالیت را نمایندگی می­ کند و مقدار متناظر با آن، اولویت آن فعالیت را مشخص می­ کند. بردار موقعیت هر کرم شب­تاب، مقادیر اولویت n فعالیت را مشخص می­ کنند. این الگوریتم برای حل مسئله RCPSP دارای سه فاز اصلی است. در فاز اول کرم­های شب­تاب در فضای جستجوی تصادفی قرار می­گیرند. یعنی یک مجموعه از زمانبندی­های تصادفی، شروع کننده الگوریتم است. در فاز دوم، زمانبندی­های اولیه بصورت تکراری بهبود داده می­شوند تا به شرط پایان برسیم و در فاز سوم، بهترین زمانبندی پیدا شده بوسیله گروه کرم شب­تابها به عنوان نتیجه نهایی بازگشت داده می­ شود. در سال ۲۰۱۲ سنایی و اکبری الگوریتم کرم شب­تاب را برای حل مسئله RCPSP بکار برده­اند[۶۳].

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

۳
۲

شکل ۴-۱ شبکه فعالیت­های متناظر با مثال ۴-۱[۶۲]