ارایه الگوریتم الکترومغناطیس تلفیقی برای مسأله زمانبندی پروژه با منابع محدود و فعالیت های چند حالته

1- مقدمه

 در مسأله کلاسیک زمانبندی پروژه با منابع محدود (RCPSP) [1] هدف پیدا کردن بهترین برنامه زمانبندی فعالیت‌ها با حداقل زمان اتمام پروژه است. محدودیت‌های پیشنیازی بین فعالیت‌ها و حداکثر مقدار در دسترس هر یک از منابع تجدید‌پذیر در دوره‌های زمانی اجرای پروژه دو دسته محدودیت در زمانبندی فعالیت‌ها در این مسأله هستند که باید در نظر گرفته شوند. هر فعالیت پروژه یک روش اجرایی دارد و زمان فعالیت و نیازمندی‌های لازم برای یک مجموعه از منابع ثابت فرض می‌شود. شبکه پروژه به صورت AON ارایه می‌شود که می‌توان آن را به صورت گراف  نشان داد. در این گراف گره‌ها نشان ‌دهنده فعالیت‌ها و کمان‌ها نمایانگر روابط پیشنیازی هستند. اگر کمان  در شبکه وجود داشته باشد، آنگاه فعالیت  باید قبل از شروع فعالیت  به پایان برسد.

مجموعه فعالیت‌های پروژه را می‌توان به صورت  تعریف کرد که در آن  و فعالیت‌های مجازی شروع و اتمام پروژه هستند. این فعالیت‌ها دارای زمان اجرا و مصرف منابع صفر هستند و در واقع ،نقش واقعه را دارند. در مسأله زمانبندی پروژه با منابع محدود و فعالیت­های چند حالته (یعنی امکان انتخاب روش­های اجرایی مختلف برای فعالیت­ها) (MRCPSP) [2]  (المقربی[3] ، 1977)، برای هر فعالیت مجموعه‌ای از روش‌‌های اجرایی قابل انتخاب می باشد که این موضوع تفاوت اساسی این مسأله با RCPSP است. ضمناً با توجه به وجود روش­های مختلف اجرایی برای هر فعالیت امکان در نظر گرفتن منابع تجدید ناپذیر نیز در این مسأله فراهم شده است. در صورت انتخاب هر یک از روش‌های اجرایی، میزان مصرف منابع تجدید پذیر، منابع تجدید ناپذیر و طول زمان اجرا برای هر فعالیت متفاوت خواهد بود. برای مثال، یک کارگر ممکن است کاری را در 10 ساعت انجام دهد (حالت 1) و در مقابل، دو کارگر همان فعالیت را در 5 ساعت به انجام برسانند (حالت2). شایان ذکر است که این نسبت لزوماً خطی تغییر نمی‌کند و حتی ممکن است منابعی که برای انجام دو روش متفاوت یک فعالیت صرف می‌شوند، با یکدیگر فرق داشته باشند، مثلاً استفاده از ماشین آلات خاصی بتواند زمان انجام فعالیت را حتی تا یک ساعت کاهش دهد (حالت 3). فرض می‌‌شود که زمان اجرای فعالیت‌ها پیوسته است؛ یعنی قطع فعالیت پس از شروع و پیش از اتمام آن امکانپذیر نیست. ضمناً پس از انتخاب روش اجرایی فعالیت، نمی‌توان هنگام انجام فعالیت آن را تغییر داد.

به زبان ریاضی در مسأله زمانبندی پروژه با منابع محدود و فعالیت­های چند حالته، برای هر فعالیت  از شبکه  یک مجموعه  از روش‌های اجرایی در نظر گرفته می‌شود. به محض اینکه فعالیتی در روش  آغاز شد، بدون وقفه و بدون تغییر آن باید پایان یابد. مدت زمان انجام فعالیت  طبق روش  است و برحسب کوچکترین واحد زمانی پروژه تعریف می‌شود. یک مجموعه  از منابع تجدید پذیر و یک مجموعه  از منابع تجدید ناپذیر، آماده به کارگیری به منظور اجرای فعالیت های پروژه هستند.  حد بالای زمان اتمام پروژه بوده، از جمع حداکثر زمان اجرای فعالیت‌ها به دست می‌آید. در واقع، به منظور محاسبه این مقدار فرض می‌شود برای کلیه فعالیت‌ها روش اجرایی انتخاب می‌شود که دارای طولانی‌ترین زمان بوده و هیچ دو فعالیتی همزمان در حال اجرا نبوده باشد و همه فعالیت‌ها در امتداد هم اجرا می‌شوند. فرض می‌شود که از منبع تجدیدپذیر  در هر یک از پریودهای  به میزان  واحد موجود است. همچنین  واحد از منبع تجدید ناپذیر  در کل زمان پروژه در دسترس است. اگر فعالیتام به روشام انجام شود، نیاز به  واحد از منبع تجدیدپذیر  در پریودهای  و  واحد از منبع تجدید ناپذیر نیاز دارد. هدف مدل MRCPSP انجام کلیه فعالیت‌های پروژه در فقط و فقط یکی از روش‌های ممکن است، به گونه‌ای که محدودیت منابع و روابط پیشنیازی ارضا گردیده و کوتاهترین زمان اتمام پروژه حاصل شود.

تاکنون روش‌های متفاوتی برای حل مسأله زمانبندی پروژه با منابع محدود و فعالیت­های چند حالته پیشنهاد شده است که می‌توان آنها را در سه دسته کلی روش‌های دقیق، ابتکاری و فرابتکاری دسته‌بندی نمود.

روش‌‌های دقیق

نخستین روش حل برای این مسأله که رویکرد برنامه ریزی خطی یک مرحله ای و دو مرحله‌ای بود، توسط اسلوینسکی[4] (1980) ارایه شد. تالبوت[5] (1982) و پترسون و همکاران[6] (1989) یک روش شمارشیبرای حل مدل پیشنهاد نمودند. اسپرچر و همکاران[7] (1997)، هارتمن و درکسل[8] (1998) و اسپرچر و درکسل[9] (1998) الگوریتم‌های شاخه و حد ارایه نمودند. ژو و همکاران[10] (2006) یک روش شاخه و برش ارایه نمود. به هرحال هیچ‌کدام از این روش ها نمی‌تواند برای حل مسایل بزرگ استفاده شود زیرا قادر به یافتن جواب بهینه در یک مدت زمان منطقی نیستند. به همین خاطر، روش‌‌های ابتکاری و فرا ابتکاری مورد توجه قرار گرفته‌اند.

روش‌‌های ابتکاری

تالبوت[11] (1982) و اسپرچر و درکسل[12] (1998) پیشنهاد نمودند که برای روش شاخه و حدشان یک حد زمانی قرار دهند. بوکتور[13] (1993) 21 قاعده ابتکاری برای زمانبندی را آزمود و تلفیقی از 5 روش که احتمال بیشتری برای تولید بهترین جواب را داشت، پیشنهاد نمود. اوزدامار و اولوسوی[14] (1994) یک روش بررسی محلی بر مبنای محدودیت ارایه نمود. بوکتور[15] (a1996) یک روش ابتکاری بر مبنای روش محاسبه مسیر بحرانی^[16] ارایه کرد. کولیش و درکسل[17] (1997) یک روش جستجوی محلی با سه فاز پیشنهاد نمود. لووا و همکاران[18] (2006) چندین روش چند مسیره بر اساس قواعد اولویت طراحی نمودند.

روش‌های فراابتکاری

اسلووینسکی و همکاران[19] (1994) یک روش تک مسیره، یک روش چند مسیره و یک روش شبیه سازی تبرید^[20]  ارایه نمودند. بوکتور[21] (b1996) همچنین توسعه روش شبیه سازی تبرید خود برای حالت تک روش اجرایی (حالته) را برای حالت چند روش اجرایی، ولی بدون در نظر گرفتن منابع تجدید ناپذیر ارایه نمود. بولیمن و لکوک[22] (2003) نیز روشی را که به منظور حل مسایل تک روش اجرایی ارایه نموده بودند، با به کارگیری یک روش دو فازی برای حالت چند روش اجرایی گسترش دادند .آنها با استفاده از عملگرهای معرفی شده، در فاز اول، برای فهرستهای روش، همسایه پیدا کرد و سپس در فاز دوم همسایه‌هایی برای فهرست فعالیت‌های مرتبط با آن فهرست روش ایجاد می کنند. جوزفوسکا و همکاران[23] (2001) فرآیند ایجاد جواب همسایه یا مجاور با جواب فعلی را تنها در یک فاز دنبال نمودند. در روش پیشنهادی آنها سه روش تولید جواب همسایه؛ یعنی ایجاد فهرست روش مجاور، فهرست فعالیت مجاور و تلفیقی از دو روش قبلی به صورت تصادفی با احتمال معلوم انتخاب می‌شود.

تا کنون اشکال مختلفی از الگوریتم ژنتیک^[24]  به منظور حل مسأله برنامه ریزی پروژه با منابع محدود و فعالیت­های چند حالته (وجود چند روش اجرایی برای فعالیت ها) ارایه شده است. اوزدامار[25] (1999) یک الگوریتم ژنتیک بر اساس قواعد اولویت ارایه کرد. هارتمن[26] (2001) الگوریتم را بر اساس روش نمایش برنامه زمانبندی به شکل فهرست فعالیت‌ها و فهرست روش­ها ارایه نمود. الکاراز و همکاران[27] (2003) با افزودن یک ژن به منظور نمایش روبه جلو و یا رو به عقب بودن برنامه ریزی، این شیوه را گسترش داد. لووا و جواب­ها و استفاده همکاران[28] (2009) یک الگوریتم ژنتیکی تلفیقی ارایه نمودند. اصلی ترین نوآوری­ها در این روش پیشنهادی، نحوه تخصیص روش ها به فعالیت­ها، محاسبه تابع هدف برای از یک روش بهبود جواب بود. ون پتقم و ونهوک[29] (2010) یک الگوریتم ژنتیک به منظور حل مسأله برنامه­ریزی پروژه در حالت چند روشی و توسعه آن در حالتی که امکان قطع[30] فعالیت‌ها وجود دارد، ارایه نمودند. آنها در این الگوریتم دو جمعیت را در نظر گرفتند. آنها همچنین، با اعمال تغییراتی در روش تولید برنامه زمانبندی سری، فرآیند انتخاب روش اجرایی برای فعالیت را با انتخاب آن روش شدنی که زمان پایان فعالیت را کمینه می­کند، گسترش دادند.

ژانگ و همکاران[31] (2006) یک الگوریتم با استفاده از ویژگی های روش دسته ذرات[32] برای حل مسأله ارایه نمودند. جاربوی و همکاران[33] (2008) الگوریتم اصلی را توسعه داده، آن را به منظور حل مسایل بهینه‌سازی ترکیبیاتی[34] با مقادیر صحیح ارایه نمودند که در مواردی با روش اصلی متفاوت بود. آنها کیفیت بالاتر روش پیشنهادی خود را نسبت به روش ژانگ و همکاران[35] (2006) با مقایسه نتایج نشان دادند.

رنجبر و همکاران[36] (2009) یک روش جستجوی پراکنده تلفیقی[37] را برای حل مسأله DTRTP[38] با چندین نوع منبع (MDTRTP)[39] توسعه دادند. این مسأله حالت خاصی از مسأله MRCPSP است و تنها تفاوت آنها در وجود منابع تجدید ناپذیر است. آنها همچنین، به منظور حل مسأله MRCPSP تغییرات کوچکی نیز در روش حل خود ایجاد نمودند. در روش حل آنها جواب هایی که از نظر منابع تجدید ناپذیر، نشدنی بودند، با استفاده از تابع ارایه شده توسط الکاراز و همکاران[40] (2003) جریمه می‌شوند.

اکثر روش‌های تکاملی از نظر تشکیل جمعیت اولیه و استفاده از عملگرهای تقاطع[41] و جهش[42] به الگوریتم ژنتیک شباهت دارند. داماک و همکاران[43] (2009) یک روش تکاملی[44] وابسته به تفاوت ارایه نمودند. این روش عملگرهای حسابی را با عملگرهای تقاطعی و جهشی کلاسیک ترکیب نموده است. در روش ارایه شده عملگرهای تقاطعی و جهشی به منظور تولید بردارهای آزمایشی جدید که پایه تولید جواب‌های جدید است، استفاده می‌گردد.

2- الگوریتم الکترومغناطیس

این روش که نخستین بار توسط بیربیل و فنگ[45] (2003) پیشنهاد شد، همانند الگوریتم ژنتیک یک روش مبتنی بر جمعیت[46] است. در این روش هر نقطه یک ذره باردار در فضا فرض شده،  مقدار بار آن نیز بر اساس مقدار تابع هدف آن تعیین می‌گردد. پس از تعیین بار هر نقطه از جمعیت، برآیند نیروی وارد بر نقاط و برای حرکت آنها در هر تکرار مشخص می‌گردد. همانند نیروهای الکترومغناطیسی، برآیند نیروی وارد بر هر نقطه، از جمع برداری تمام نیروهای وارد بر آن به دست می‌آید. این روش در برخی موارد تفاوت هایی با تئوری الکترومغناطیس دارد که در تشریح مراحل الگوریتم توضیح داده می‌شود. الگوریتم الکترومغناطیس به منظور حل مسایلی با متغیرهای حقیقی و محدود طراحی شده است. شکل کلی این گونه مسایل در زیر آورده شده است.

(1)                              

که در آنn  بعد مسأله، u_k حد بالا و l_k حد پایین بعد k ام بوده، f(x)  تابعی است که باید حداقل شود.

این الگوریتم شامل چهار فاز اصلی راه اندازی، جستجوی محلی، محاسبه نیروی وارد بر هر ذره و حرکت در برای نیروست که در ادامه به بررسی کامل هر یک از آنها می‌پردازیم.

2-1- راه اندازی

در آغاز الگوریتم الکترومغناطیس، مشابه سایر روش‌های مبتنی بر جمعیت، m نقطه تصادفی از فضای شدنی مسأله انتخاب می‌شود. به منظور تولید یک نقطه تصادفی فرض می‌شود هر مؤلفه نقطه، یک متغیر تصادفی با تابع توزیع یکنواخت بین حد پایین و بالای خود بوده، سپس برای هر مؤلفه یک مقدار تصادفی انتخاب می‌گردد. پس از ایجاد این مجموعه، مقدار تابع هدف برای هر نقطه محاسبه و بهترین نقطه به عنوان x^best  نشان داده می‌شود.

2-2- جستجوی محلی

این مرحله به منظور بررسی فضای اطراف هر یک از نقاط ایجاد شده صورت می‌پذیرد. بیربیل و فنگ[47] (2003) به ارایه یک الگوریتم ساده به منظور جستجوی محلی پرداختند. در روش ارایه شده از سوی آنها، برای هر یک از ابعاد نقاط ایجاد شده، قدمی تصادفی در برای افزایش و یا کاهش بعد مورد نظر برداشته می‌شود. برای این قدم به شکل تصادفی انتخاب می‌شود. همچنین، این قدم حداکثر می تواند با توجه به برای قدم تا حد بالا و یا پایین بعد مورد نظر برداشته شود. پس از اجرای این مرحله، اگر نقطه جدید ایجاد شده تابع هدف بهتری را فراهم آورد، با نقطه قبلی جایگزین شده، فرآیند جستجو برای بعد بعدی دنبال می‌گردد، در غیر این صورت، نقطه اولیه حفظ و جستجو برای همین بعد تکرار می‌گردد. فرآیند جستجو حداکثر به تعدادLSITER مرتبه برای هر بعد تکرار شود.

2-3- محاسبه بردار نیروی کل

بر اساس تئوری الکترومغناطیس، نیرویی که دو ذره باردار بر هم وارد می‌کنند، با مجذور فاصله آنها نسبت عکس و با مقدار بار هر یک از آنها نسبت مستقیم دارد.در این الگوریتم، در هر تکرار بار نقاط بر اساس رابطه زیر تعیین می‌گردد.

(2)

که در آنqⁱ  میزان بار نقطه iام، n تعداد ابعاد مسأله، f(xⁱ) مقدار تابع هدف نقطه iام وf(x^best)   بهترین مقدار تابع هدف در تکرار مربوطه است. بار هر نقطه قدرت جذب یا دفع آن نقطه را تعیین کرده، نقاطی که دارای مقدار تابع هدف بهتری هستند، بار بیشتری خواهند داشت. بنابراین، در هر تکرار بیشترین بار متعلق به x^best خواهد بود. با توجه به فرمول مورد استفاده، بار یک نقطه ممکن است در دو تکرار مختلف متفاوت باشد. نکته قابل توجه اینکه برخلاف بارهای الکتریکی، بار نقاط در این روش هیچ علامتی نداشته، برای نیروی وارد بر هر جفت نقطه پس از مقایسه مقدار تابع هدف آنها تعیین می‌شود. بین هر جفت نقطه، نقطه ای که تابع هدف بهتری دارد، نقطه دیگر را جذب و نقطه ای که تابع هدف بدتری دارد، نقطه دیگر را دفع می کند و در صورتی که توابع هدف برابر باشند، نقاط نیرویی به هم وارد نخواهند کرد. لذا در هر تکرار نقطه‌ای که بهترین مقدار تابع هدف را دارد، سایر نقاط را جذب و نقطه ای که بدترین مقدار تابع هدف را دارد، سایر نقاط را دفع می‌کند. مقدار نیروی وارده از طرف نقطه j بر نقطه i به صورت زیر محاسبه می‌گردد:

(3)

نهایتاً بردار نیروی کل وارد بر هر نقطه از جمع برداری نیروهای وارد بر آن نقطه از طرف سایر نقاط حاصل می‌شود.

(4)

به منظور جلوگیری از همگرا شدن الگوریتم به یک جواب حداقل محلی و یا اصطلاحاً همگرایی زودرس یا پیش از موعد^[48]، بیربیل و همکاران[49] (2005) فاز محاسبه نیروی کل را کمی تغییر دادند. آنها دورترین نقطه از x^best را انتخاب کرده و آن را x^p نامیدند.

  (5)

در این ویرایش جدید از الگوریتم، محاسبه نیروی کل برای همه نقاط به غیر از x^p بدون تغییر مانده، ولی اجزای تشکیل دهنده نیروی کل برای x^p به شکل زیر تغییر می کند تا حداقل یکی از نقاط شانس حرکت به سمت نواحی حذف شده از جمعیت را داشته باشد.

(6)

در رابطه 6، l یک متغیر تصادفی یکنواخت در بازه (1,0) است. علاوه بر تغییر اندازه هر یک از نیروهای وارد بر x^p با ضرب l، برای نیروها نیز ممکن است تغییر کند. به همین منظور، یک متغیر تصادفی دیگر مانند υ انتخاب شده و اگر l<υ باشد؛ آنگاه برای آن نیرو عکس می‌گردد. نکته درخور توجه اینکه هر نقطه‌ای غیر از x^best می تواند به عنوان x^p انتخاب شود. در این روش، دورترین نقطه از بهترین نقطه در تکرار فعلی به عنوان x^p انتخاب شده است، چون نیروی جاذبه بهترین نقطه بر این نقطه کمتر از نیروی جاذبه بر نقاط دیگر است.

2-4- حرکت نقاط در راستای بردار نیروی کل

پس از تعیین بردار نیروی کل برای تمام نقاط، هر یک از نقاط در راستای نیروی وارده به اندازه‌ای که به صورت تصادفی انتخاب می‌شود، حرکت می‌کند. مختصات نقاط جدید از رابطه زیر حاصل می‌شود:

       (7)

در رابطه 7، از تقسیم بردار نیروی کل وارد بر هر نقطه بر اندازه آن، بردار راستای حرکت آن نقطه حاصل می‌شود که اندازه ای برابر با یک دارد. اندازه تصادفی بردار حرکت نیز از ضرب α و NRG حاصل می‌شود. α متغیری تصادفی با تابع توزیع یکنواخت بین صفر و یک بوده و RNG نیز از رابطه زیر به دست می‌آید:

(8)

هر یک از مؤلفه های بردارRNG ، حداکثر حرکت مجاز به سمت u_k یا l_k را برای بعد مربوطه به منظور جلوگیری از تجاوز نقاط از حدود بالا و پایین تعیین می‌کنند. در صورتی که ، حرکتی در بعد مورد نظر نخواهیم داشت. حاصل ضرب α و RNGبرداری است تصادفی که حرکت نقطه با آن شدنی بودن نقطه جدید را تضمین می‌کند. میزان جا به جایی نقاط در راستای نیرو به این علت به شکل تصادفی انتخاب می‌شود که تمامی نقاط در راستای نیرو شانس بررسی را داشته باشند. در هر تکرار،  x^bestتنها نقطه ای است که جابه جا نشده و عیناً به تکرار بعد منتقل می‌شود، بنابراین، می توان از محاسبه نیروهای وارد بر این نقطه چشم پوشی کرد.

گلعلیخانی و همکاران[50] (2009)  روش ترکیبی جدیدی بر اساس روش الکترومغناطیس پیشنهادی بیربیل و همکاران[51] (2005) و روش جستجوی محلی سولیس و وتس[52] (1981) برای مسائل بهینه‌سازی پیوسته ارائه نمودند. همچنین، ویرایش های مختلفی از روش شبه الکترومغناطیس توسط ناجی عظیمی و همکاران[53] (2010) برای حل مسأله پوشش مجموعه و جوادیان و همکاران[54]  (2008و2009) برای حل مسأله فروشنده دوره گرد و زمانبندی تک ماشین استفاده شده است. دبلز و همکاران[55] (2006) نیز ترکیبی از روش الکترومغناطیس و جستجوی پراکنده را برای حل مسأله زمانبندی پروژه با منابع محدود و فعالیت­های چند حالته به کار گرفتند.

3- الگوریتم پیشنهادی به منظور حل مدل

به منظور حل MRCPSP این مسأله به دو زیر مسأله تقسیم شده است. تعیین روش اجرایی هر فعالیت و سپس یافتن بهترین زمانبندی فعالیت‌ها به منظور حداقل نمودن زمان پروژه. با استفاده از روش الکترومغناطیس به هر فعالیت یکی از روش‌‌های ممکن تخصیص پیدا کرده و زمان اجرای هر فعالیت و میزان مورد نیاز از هر منبع با توجه به روش انتخاب شده برای اجرای آن تعیین می‌گردد. پس از آن به صورت تصادفی چند برنامه زمان بندی تولید شده و یک الگوریتم جستجوی محلی هر یک از برنامه ها را بهبود می‌دهد. سپس بهترین برنامه زمانبندی انتخاب و به عنوان زمان تکمیل متناظر با فهرست روش مربوطه گزارش می‌گردد. به منظور نمایش مراحل الگوریتم پیشنهادی، مسأله شماره j1012_1 از مجموعه مثال‌های استاندارد موجود در کتابخانه مسایل زمانبندی پروژه انتخاب و مراحل بر روی آن اعمال می‌گردد. این مجموعه مسایل درhttp://129.187.106.231/psplib در دسترس است. مسأله انتخابی، 10 فعالیت غیر مجازی داشته که زمان هرکدام بین 1 تا 10 بوده و به دو منبع تجدید پذیر و دو منبع تجدید ناپذیر نیاز دارد. در جدول 1 پسنیازهای هر فعالیت، زمان انجام، مصرف منابع آن و سطح در دسترس هر یک از منابع آورده شده است. ضمناً شایان ذکر است، سطح دسترس نخستین منبع تجدید ناپذیر از 54 به 41 و سطح دسترس دومین منبع تجدید ناپذیر از 48 به 35 کاهش داده شده است، زیرا با در نظر گرفتن حدود اصلی، هر فهرست روش تصادفی از نظر مصرف منابع تجدید ناپذیر قابل قبول و شدنی خواهد بود.

جدول 1- اطلاعات مسأله نمونه

3-1- نحوه نمایش جواب ها

در روش پیشنهادی به منظور حل مدل، هر جواب به صورت دو فهرستn  عنصری که n برابر با تعداد فعالیت‌هاست، نشان داده می‌شود. فهرست اول شامل روش‌‌های اجرایی فعالیت‌ها بوده، آن را فهرست روش^[56] می نامیم و با μ نشان می دهیم. در این فهرست عنصر j ام نشان دهنده روش اجرایی فعالیت j ام است. فهرست دوم یک جایگشت شدنی از فعالیت هاست که در آن هر فعالیت پس از تمام پیشنیازهایش ظاهر می‌شود. این فهرست، فهرست فعالیت^[57] نامیده شده، با λ نمایش داده می‌شود. کولیش و هارتمن[58] (1999) به تشریح انواع مختلف نمایش زمانبندی فعالیت‌ها پرداختند. هارتمن و کولیش[59] (2000) بر اساس نتایج حاصل شده از آزمایش‌های صورت گرفته نشان دادند نمایش زمانبندی فعالیت‌ها به شکل فهرست فعالیت بهتر از سایر روش‌ها بوده، به ایجاد نتایج بهتری منجر می‌گردد.

3-2- جمعیت اولیه

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

          (9)

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

                           (10)

بنابراین، یک فهرست روش شدنی است اگر و فقط اگر. در صورتی که فهرست روش ایجاد شده نشدنی باشد، یک الگوریتم جستجوی محلی به منظور شدنی ساختن فهرست روش بر آن اعمال می‌گردد. در این الگوریتم یک فعالیت تصادفی با بیش از یک روش اجرایی انتخاب و روش فعلی آن با یک روش تصادفی دیگر تعویض می‌گردد. اگر فهرست روش جدید به خوبی قبلی بود، یعنی میزان اضافه درخواست برای منابع تجدید ناپذیر افزایش پیدا نکرد، روش انتخاب شده برای فعالیت تثبیت شده و فهرست جدید مبنای ادامه الگوریتم قرار می‌گیرد و در غیر این صورت، ادامه الگوریتم بر روی فهرست روش قبلی اجرا می‌گردد. این الگوریتم تا J (تعداد فعالیت ها) تلاش ناموفق متوالی به منظور کاهش سطح درخواست منابع و یا تا شدنی شدن فهرست روش ادامه پیدا می کند.

3-3- محاسبه تابع هدف

پس از تشکیل جمعیت باید مقدار تابع هدف برای نقاط محاسبه گردد، چرا که مبنای محاسبه بار برای آنها خواهد بود. تابع هدف محاسبه شده برای هر فهرست روش ،C_max  یا همان طول زمان پروژه خواهد بود. مسلماً محاسبه طول پروژه مستقیماً با استفاده از فهرست روش میسر نیست. لذا ابتدا مدت زمان هر فعالیت و مصرف منابع تجدید پذیر برای هر فعالیت بر اساس فهرست روش تعیین گردیده و N برنامه زمان بندی (فهرست فعالیت) به صورت تصادفی بر اساس روش تولید برنامه زمانبندی سری تولید می‌گردد.  هر کدام از این N برنامه زمان بندی توسط یک الگوریتم جستجوی محلی بهبود داده شده و کمترین ‍‍ C_maxبه عنوان تابع هدف فهرست روش گزارش می‌گردد. همان گونه که توضیح داده شد، الگوریتم جستجوی محلی ارایه شده برای شدنی نمودن فهرست­های روش بعد ازJ  تلاش ناموفق متوقف می‌شود، لذا امکان دارد برخی از فهرست­های روش همچنان نشدنی باقی بمانند. چند مدل مختلف می توان با فهرست­های روش نشدنی رفتار نمود. می توان آنها را از جمعیت حذف نمود و یا با فهرست روش شدنی دیگری جایگزین نمود و یا آنها را جریمه کرد. هارتمن[60] (2001) تابع هدفی برای نقاط تعریف کرد که در آن برای نقاط نشدنی جریمه در نظر گرفته شده است. این تابع هدف توسط جوزفوسکا و همکاران[61] (2001) نیز به کار گرفته شد. الکاراز و همکاران[62] (2003) به این نکته اشاره کردند که در تعریف مذکور دو جواب نشدنی مختلف با اضافه درخواست منبع یکسان و طول پروژه مختلف یک مقدار تابع هدف برابر خواهند داشت. به همین جهت، آنها تابع هدف دیگری پیشنهاد گردند. لووا و همکاران[63] (2009) به این موضوع اشاره کردند که در تابع هدف پیشنهادی الکاراز و همکاران[64] (2003) واحدهای زمان مربوط به طول اجرای پروژه و واحد های منبع مربوط به اضافه درخواست با یکدیگر جمع شده اند و این در حالی است که این دو از یک جنس نیستند. به منظور حل این مشکل آنها تابع هدفی را پیشنهاد دادند که در آن متغیرها نرمالیزه شده اند.این تابع هدف از توابع پیشنهادی قبلی منطقی تر به نظر می رسد، اما اولاً مقدار طول پروژه مستقیماً از آن قابل دریافت نبوده؛ ثانیاً امکان دارد یک جواب در دو تکرار مختلف مقادیر تابع هدف متفاوتی به خود بگیرد. ضمناً هرچند مقادیر زمان و منبع پس از نرمال شدن با هم جمع می شوند، اما همچنان از دو جنس متفاوت هستند.

در این مقاله تابع هدف جدیدی پیشنهاد می‌گردد. که در آن تا حد امکان نواقص توابع هدف قبلی بر طرف گردیده است.

(11)

در این تعریف، برای جواب‌های شدنی، طول پروژه به عنوان تابع هدف در نظر گرفته شده است و برای نقاط نشدنی دو عبارت به عنوان جریمه به این مقدار اضافه می‌گردد. مقدار اول، اختلاف حد بالای زمان پروژه و حد پایین آن؛ یعنی طول مسیر بحرانی بر اساس حداقل زمان فعالیت‌هاست و مقدار دوم، با این فرض حاصل می‌شود که اگر نیاز به منابع تجدید ناپذیر بیش از ظرفیت مجاز باشد، اضافه درخواست می‌تواند پس ازحد بالای زمان اتمام پروژه تأمین گردد. لذا مقدار زمان لازم برای تأمین مقدار منبع اضافه از ضرب حداکثر نسبت درخواست منابع در T حاصل می‌شود. در واقع ،این فرض بدین معنی است که اگر برای مثال، حداکثر نیاز به منابع تجدید ناپذیر، 5% بیش از مقدار مجاز باشد، این مقدار می‌تواند با افزایش حد بالای زمان اتمام پروژه به میزان 5% تأمین گردد. بدیهی‌ است اضافه درخواست سایر منابع که کمتر از این مقدار است، در این زمان قابل تأمین خواهد بود

 3-3-1- تولید برنامه زمانبندی

دو روش اصلی برای تولید برنامه زمانبندی در مقالات وجود دارد. تولید برنامه زمانبندی به روش سری[65] (کلی[66]، 1963) و موازی[67] (بدورث و بیلی[68]، 1982). در روش حل پیشنهادی در این مقاله از روش سری استفاده می‌گردد که با روش نمایش برنامه زمانبندی به شکل فهرست فعالیت سازگارتر است. تعداد مراحل این الگوریتم برابر با تعداد فعالیت‌های پروژه است چرا که در هر مرحله دقیقاً یک فعالیت انتخاب و زمانبندی می‌شود. در هر مرحله از این روش کل فعالیت‌ها به سه دسته تقسیم می‌شوند: فعالیت‌هایی که تا این مرحله زمانبندی شده‌اند، فعالیت‌هایی که برای انتخاب و زمانبندی واجد شرایط هستند و فعالیت‌هایی که تا این مرحله زمانبندی نشده‌اند و امکان زمانبندی آنها در این مرحله نیست، چون تمام پیشنیازهای آنها تا قبل از این مرحله زمانبندی نشده‌اند. در هر مرحله، یک فعالیت به صورت تصادفی از بین فعالیت‌های واجد شرایط انتخاب و در زودترین زمان شدنی ممکن از نظر پیشنیازی فعالیت‌ها و سطح در دسترس منابع تجدید پذیر زمانبندی می‌شود. در نخستین مرحله، تنها فعالیتی که می‌تواند انتخاب شود، فعالیت مجازی شروع و در آخرین مرحله هم فعالیت مجازی پایان خواهد بود. پس از انتخاب و زمانبندی کلیه فعالیت‌ها، زمان فعالیت مجازی پایان به عنوان زمان پایان پروژه گزارش می‌گردد. ضمناً خلاصه مراحل زمانبندی شامل ترتیب انتخاب فعالیت‌ها برای زمانبندی، به صورت فهرست فعالیت λ={j₁,j₂,…,j_n} ذخیره می‌گردد. این فهرست نشان می دهد فعالیت j_g در مرحله  gانتخاب و زمانبندی شده است.

3-3-2- بهبود برنامه زمانبندی

مطابق آنچه توضیح داده شد، به منظور محاسبهC_maxبرای یک فهرست روش،  پس از تولید N برنامه زمانبندی تصادفی با استفاده از روش تولید برنامه زمانبندی سری برای آن فهرست روش، تلاش می‌گردد هر یک از این برنامه‌های زمانبندی با استفاده از یک الگوریتم جستجوی محلی بهبود یابد. در پایان، بهترین برنامه زمانبندی با کمترین طول پروژه به عنوان برنامه زمانبندی متناظر آن فهرست روش گزارش می‌گردد. اساس کار الگوریتم جستجوی محلی به این شکل است که با شروع از یکی از آن N برنامه زمانبندی تولید شده سعی می‌گردد، با ایجاد تغییر کوچکی در برنامه، یک برنامه زمانبندی همسایه ایجاد گردد. سپس زمان پایان این برنامه جدید محاسبه و در صورت بهبود جایگزین برنامه قبلی شده و الگوریتم بر روی این برنامه تکرار می‌گردد و در غیر این صورت، برنامه قبلی مبنای ادامه الگوریتم قرار می گیرد. دو روش مختلف به منظور تولید برنامه زمانبندی همسایه به کار گرفته می‌شود.

1) یک فعالیت به صورت تصادفی انتخاب شده و به محلی تصادفی بین آخرین پیشنیاز و نخستین پسنیازش در فهرست منتقل می‌شود. سپس مجموعه فعالیت‌هایی که بین مکان قدیم و مکان جدید آن فعالیت قرار گرفته‌اند، به اندازه یک جایگاه به سمت جایگاه قدیم حرکت داده می‌شوند. اگر فعالیت انتخاب شده مجاور آخرین پیشنیاز و نخستین پسنیازش باشد، امکان حرکت نداشته و فعالیت دیگری به منظور حرکت انتخاب می‌گردد.

2) دو فعالیت مجاور به صورت تصادفی انتخاب شده و در صورتی که فعالیت اول پیشنیاز فعالیت دوم نباشد، جا به جا می‌شوند.

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

شکل 2- مراحل بهبود فهرست فعالیت ها

در شکل شماره 2-الف یک برنامه زمانبندی تصادفی برای فهرست روش به دست آمده در شکل 1 تولید شده است. در شکل شماره 2-ب یک برنامه زمانبندی همسایه به روش اول برای آن تولید شده و چون برنامه تولید شده بهتر از قبلی است، جایگزین آن گردیده است. در شکل شماره 2-ج به کمک الگوریتم دوم برای این برنامه جدید یک برنامه همسایه تولید شده و چون موجب بهبود گردیده، پذیرفته شده است.

3-4- جستجوی محلی

این مرحله از الگوریتم پیشنهادی می‌تواند در هر تکرار برروی یک یا چند یا حتی همه فهرست­های روش به منظور پیدا کردن جواب‌هایی بهتر از جواب فعلی با جستجو در همسایگی آنها اعمال گردد. با شروع از یک فهرست روش، یک جواب همسایه برای آن پیدا می‌شود. فهرست روش همسایه تنها در صورتی مورد قبول قرار  می‌گیرد که از نظر مقدار درخواست منابع تجدید ناپذیر شدنی باشد. برای این فهرست روش همسایه، بهترین برنامه زمانبندی با حداقل زمان اتمام پروژه به روش گفته شده تعیین می‌گردد. اگر فهرست روش حاصل شده بهتر از فهرست روش اولیه باشد جایگزین آن شده و الگوریتم بر روی این فهرست روش تکرار می‌شود و در غیر این صورت، فهرست روش قبلی مبنای ادامه الگوریتم قرار می گیرد.

3-5- محاسبه بردار نیروی کل

به منظور نمایش مراحل باقی مانده از الگوریتم، جدول 2 یک جمعیت نمونه با پنج فهرست روش را ارایه می‌کند.  برای هر فهرست روش بهترین برنامه زمانبندی به شیوه توضیح داده شده ایجاد و زمان پایان پروژه برای آن گزارش می‌گردد.

جدول 2-یک جمعیت نمونه با پنج فهرست روش

فهرست­های روش متغیر و زمان های اتمام پروژه به عنوان مقادیر تابع هدف در نظر گرفته می‌شوند. فهرست فعالیت­ها تنها به عنوان واسطه‌ای برای تعیین زمان اتمام پروژه متناظر با هر فهرست روش عمل می‌کنند. نقطه سوم بهترین مقدار تابع هدف را داشته، بنابراین در x^bestذخیره می‌گردد. بر اساس محاسبه فاصله نقاط از x^best دورترین نقطه ازx^best که نقطه دوم است، به عنوان x^p در محاسبات بعدی لحاظ می‌گردد. البته، نقاط دیگری نیز می‌تواند به عنوان x^p انتخاب گردد، اما یکی از بهترین انتخاب‌ها همان دورترین نقطه از بهترین نقطه است. جدول 3 محاسبه بار هر نقطه و تعیینx^best  و x^p در جمعیت فعلی را نشان می­دهد.

جدول 3- محاسبه بار هر نقطه و تعیینx^best  و x^p در جمعیت فعلی

نیروی کل وارد بر هر نقطه، ، از جمع برداری نیروهای وارد بر آن از طرف سایر نقاط حاصل می‌گردد. شایان ذکر است بارها علامت نداشته و برای نیروی بین هر دو نقطه بعد از مقایسه مقدار تابع هدف آنها تعیین می‌گردد؛ یعنی همان گونه که قبلاً توضیح داده شد، بین هر دو نقطه،  نقطه ای که مقدار تابع هدف بهتری دارد، جذب می‌کند، نقطه‌ای که تابع هدف بدتری دارد، دفع می‌کند. برای محاسبه نیروهای وارد بر نقطه x^p متغیرهای

تصادفی l و  υبه ترتیب برابر با 93/0 و 83/0 در نظر گرفته شده است. جدول 4 برآیند نیروی وارد بر هر نقطه را نشان می‌دهد. ضمناً همان گونه که گفته شد x^best حرکت داده نشده و بدون تغییر به تکرار بعد منتقل می‌شود. بنابراین، می‌توان از محاسبه نیروی وارد بر این نقطه صرف نظر کرد.

جدول 4- نیروی کل وارد بر هر نقطه

3-6- حرکت نقاط در راستای بردار نیرو

پس از تعیین نیروی کل وارد بر هر نقطه، آن نقطه در راستای نیروی محاسبه شده به اندازه‌ای که به صورت تصادفی تعیین می‌شود، حرکت می‌کند. جدول 5 بردار حرکت هر یک از نقاط را نشان می­دهد. به منظور سهولت در محاسبات مقدار متغیر تصادفی a برای همه نقاط برابر با 9/0 در نظر گرفته شده است. دقت کنید که برای محاسبه بردار RNG، حد پایین و بالا برای بُعد اول و آخر که مربوط به نخستین و آخرین فعالیت مجازی هستند، 1 و برای سایر ابعاد به ترتیب برابر 1 و 3 در نظر گرفته شده است. پس از محاسبه بردارهای حرکت، هر نقطه با استفاده از بردار متناظرش به نقطه ای جدید منتقل می‌شود. مختصات جدید هر نقطه بعد از حرکت با بردار حرکت متناظرش در جدول 6 آورده شده است.

جدول 5- بردار حرکت هر یک از نقاط

جدول 6- مختصات جدید نقاط بعد از حرکت

 پایین (1) و بالا (3) برای هر بعد جواب به سه زیر بازه مساوی تقسیم، مقادیر کوچکتر از  6665/1 تبدیل به 1، مقادیر بین 6665/1 و 3335/2 تبدیل به 2 و مقادیر بزرگتر از 3335/2 تبدیل به 3 و بدین ترتیب مقادیر غیر صحیح به مقادیر صحیح 1، 2 و یا 3 تبدیل می‌شود.

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

نقاط نهایی حاصل شده از الگوریتم جدول 7-

4- بحث

در این قسمت، عملکرد الگوریتم پیشنهادی در ارتباط با حل مسأله MRCPSP با بهترین روش‌‌های فرا ابتکاری ارایه شده برای حل این مسأله تاکنون با استفاده از مثال‌های موجود در کتابخانه مسایل برنامه‌ریزی پروژه (PSPLIB) (کولیش و اسپرچر[69]، 1996) مقایسه می‌گردد. مجموعه مثال‌های PSPLIB توسط نرم افزار ProGen (کولیش و همکاران[70]، 1995) تولید گردیده و در آدرس http://129.187.106.231/psplib/ در دسترس است. تعداد مسائل هر مجموعه مسأله در PSPLIB در جدول 8 آمده است. این مجموعه شامل مسایلی با 10، 12، 14، 16، 18، 20 و30 فعالیت غیر مجازی است که در آنها برای هر فعالیت 3 روش اجرایی در نظر گرفته شده است. انجام هر فعالیت به هر یک از روش‌‌های اجرایی به مقادیری از 2 منبع تجدید پذیر و 2 منبع تجدید ناپذیر نیاز دارد. زمان هر فعالیت در هر روش اجرایی عددی بین 1 تا 10 است. جواب بهینه مسایل با اندازه 10 تا 20 در بیشتر موارد با استفاده از روش­های دقیق تعیین گردیده و در کتابخانه معرفی شده موجود است، ولی برای مسایل با 30 فعالیت تنها بهترین جواب­های به دست آمده با روش­های ابتکاری در دسترس است، لذا این دسته مسایل استفاده نشده است.

.جدول 8- تعداد مسائل هر مجموعه مسأله در PSPLIB

با مرور مقالات مرتبط، به این نکته می رسیم که الگوریتم های ارایه شده برای حل MRCPSP بر اساس دو شرط توقف اصلی تعداد جواب‌های تولید شده و زمان حل با یکدیگر مقایسه می‌گردند. به منظور مقایسه الگوریتم پیشنهاد شده با سایر روش ها، ابتدا تعداد جواب‌های تولید شده مورد نظر قرار گرفت؛ لذا برنامه نویسی با نرم افزار MATLAB انجام شد. پس از آن با مقایسه زمان حل برنامه نوشته شده با زمان‌های حل ارایه شده در برخی مقالات برای حل مسأله با نرم افزار C++ به این نتیجه رسیدیم که نرم افزارMATLAB  با معیار زمان، قابلیت رقابتی خود را از دست می‌دهد، لذا به منظور مقایسه زمانی، کد برنامه به زبان C++ برگردانده شد.

مقایسه عملکرد الگوریتم پیشنهادی با سایر الگوریتم‌ها، برای مسایل PSPLIB با جواب‌های بهینه معلوم، بر مبنای تعداد جواب‌های تولید شده و زمان حل به ترتیب در جداول 9 و 10 آورده شده است. در این جداول میانگین انحراف از جواب بهینه به درصد (ADO) و درصد جواب‌های بهینه پیدا شده (POF) در هر مجموعه مثال برای هر روش گزارش گردیده است. در جدول 9 عملکرد الگوریتم پیشنهادی با الگوریتم‌های ژنتیکی ون پتقم و ونهوک[71] (2010)، لووا و همکاران[72] (2009) و الکاراز و همکاران[73] (2003)، جستجوی پراکنده رنجبرو همکاران[74] (2009) و شبیه‌سازی تبرید جوزفوسکا و همکاران[75] (2001) بر اساس 5000 جواب تولید شده مقایسه گردیده است؛ یعنی برای هر دسته مسأله عملیات پس از تولید 5000 جواب متوقف گردیده و بهترین جواب به دست آمده تا آن لحظه به عنوان جواب مسأله گزارش می‌گردد. همان گونه که نتایج نشان می‌دهد، در مسائل با 10، 12و 16 فعالیت، الگوریتم پیشنهادی با اختلافی ناچیز در رتبه دوم قرارگرفته، ولی برای مسائل با 14، 18 و 20 فعالیت، بهترین عملکرد را داراست.

در جدول 10، عملکرد روش حل پیشنهادی با الگوریتم‌های پیشنهادی جاربوی و همکاران[76] (2008)، داماک و همکاران[77] (2009) و بولیمن و لکوک[78] (2003) بر اساس زمان حل 0.15 ثانیه به ازای هر فعالیت مقایسه گردیده است، یعنی برای هردسته مسأله با اندازه n، عملیات پس از n×15/0 ثانیه متوقف گردیده و بهترین جواب به دست آمده تا آن لحظه به عنوان جواب مسأله گزارش می­گردد. نکته قابل ذکر اینکه دو الگوریتم اول (جاربوی و همکاران[79]، 2008 و داماک و همکاران[80]،2009) بر روی رایانه‌هایی با مشخصاتی مشابه آنچه در این مقاله استفاده شده: ((Pentium 4, 3.2 GHz processor, 1GB RAM و با قید زمانی 0.15 ثانیه برای هر فعالیت راه‌اندازی گردیده، ولی بولیمن و لکوک[81] (2003) الگوریتم شبیه‌سازی تبرید خود را بر روی یک رایانه با پردازنده 100 مگا هرتز با 5 ثانیه به ازای هر فعالیت راه اندازی نمودند. همان گونه که نتایج نشان می‌دهد، در مسائل با 10 فعالیت، الگوریتم پیشنهادی از نظر میانگین انحراف نسبت به جواب بهینه در رتبه دوم و از نظر درصد جواب‌های بهینه به دست آمده رتبه سوم را کسب می‌کند و برای مسائل با 12 فعالیت، الگوریتم پیشنهادی از نظر میانگین انحراف از جواب بهینه رتبه اول و از نظر تعداد جواب‌های بهینه حاصل شده رتبه دوم را به دست می‌آورد. الگوریتم پیشنهادی برای دسته مسائل دیگر بهترین عملکرد را داراست

.جدول9- مقایسه نتایج الگوریتم پیشنهادی با سایر روش ها بر مبنای 5000 جواب تولید شده

جدول 10- مقایسه نتایج الگوریتم پیشنهادی با سایر روش ها بر مبنای 0.15 ثانیه به ازای هر فعالیت