نشریه تخصصی مهندسی صنایع، دوره 47، شماره 1، فروردین ماه 1392، از صفحه 1 تا 13
کمینه کردن جریمه دیرکرد و بیشینه کردن پاداش زودکرد انجام فعالیت ها در مسئله MRCPSP/max با استفاده از الگوریتم ژنتیک دو مرحله اي

جعفر باقري نژاد*1 ، فریبرز جولاي2 و زهرا رفیعی مجد3
استادیار دانشکده مهندسی صنایع – دانشگاه الزهرا (س)
استاد دانشکده مهندسی صنایع -پردیس دانشکده هاي فنی-دانشگاه تهران
کارشناس ارشد مهندسی صنایع – دانشگاه الزهرا (س)
(تاریخ دریافت 9/2/91، تاریخ دریافت روایت اصلاحشده 6/8/91، تاریخ تصویب 24/1/92 )

چکیده
در این مقاله، براي اولین بار مسئله زمانبندي پروژه در شرایط محدود بودن منابع ،امکان اجراي فعالیت هـا در چنـدین مـد و بـا در نظـر
گرفتن تأخیرات زمانی بیشینه و کمینه میان زمان هاي شروع فعالیت ها، MRCPSP/max ، با هـدف کمینـه کـردن جریمـه دیرکـرد وبیشینه کردن پاداش زودکرد اتمام فعالیت ها، مطرح شده و مورد بررسی قرار گرفته است. پس از بررسی تاریخچه و روند استفاده از روش هـايمختلف در حل مسائل مشابه در سال هاي گذشته، الگوریتم ژنتیک به عنوان الگوریتم مورد استفاده در این تحقیق برگزیده شده است. در این مقاله، شیوه پیداکردن جواب براي مسئله مورد نظر به این ترتیب است که با استفاده از یک الگوریتم ژنتیک، مسئله اصلی را به مسئله اي که در آن هر فعالیت فقط یک حالت اجرایی دارد، ساده کرده و سپس در فاز دوم حل، با استفاده از یک الگوریتم ژنتیک مستقل دیگر، بهترین جواب مسئله حاصله از فاز اول الگوریتم را می یابیم. عناصر اصلی و عملگرهاي هر دو الگوریتم، از هم مستقل هستند. در انتها نیز نتایج عددي حاصل از الگوریتم هاي پیشنهادي که به وسیله زبان برنامه نویسی MATLAB نوشته شده است، با نتـایج موجـود در کتابخانـه مسـائل زمانبنـديمقایسه شده اند و مشاهده می شود که الگوریتم ارائه شده در این تحقیق در چندین مورد جواب هاي موجود را بهبود داده است.

واژه هاي کلیدي: زمانبندي پروژه ،تأخیرات زمانی بیشینه و کمینه ، الگوریتم ژنتیک، فعالیت ها با چندین مد اجرایی

بر اساس بیان دورنـدورف و همکـاران[1]، تـأخیرات زمانی کمینه 1 و تأخیرات زمانی بیشینه 2 امکان مدلسازي بس یاري از خصوص یات را ک ه ب ه ط ور کل ی در مس ائل زمانبندي کاربرد دارند ،امکانپذیر می کننـد [2]، از ایـن رومسئله به مسائل دنیـاي واقعـی نزدیـک تـر مـی شـود. اگـرمسئله زمانبندي پروژه را در شـ رایطی کـه منـابع محـدودهستند و تأخیرات زمانی بیشینه و کمینه میان فعالیت هـا نیز وجود دارد، در نظر بگیریم، به یـک مسـئله زمانبنـديپــروژه بــا منــابع محــدود بــا روابــط تقــدمی کلــی3 (محدودیت هاي زمانی 4، تـأخیرات زمـانی 5، پنجـره هـاي
مقدمه Email: [email protected] ،88035187 :نویسنده مسئول: تلفن: 88044040 ، فاکس *

زم انی6 ) ک ه ب ه ص ورت خلاص ه RCPSP/max7 (ی ا RCPSP/GPR ) نامیده می شود، خواهیم رسـید . بـراي حل مسئله RCPSP/max، پژوهشگرانی چـون بـارتوشو همک اران (1988) [3]، دي ری ک (1998) [4]، فس ت (1998) [5] و دورندورف (2000) [1] از رویکرد شـاخه وکران بهره برده اند. بعضی دیگـر از محققـان نیـز بـا کمـکروش هاي ابتکاري و فراابتکاري این نوع مسـئله را بررسـیکرده اند. از جمله این محققان می توان به فرانک و همکاران (2001) [6] و (1998) [7]، سستا (2002) [8]، اسمیت و پایل (2004) [9]، ایفینوا و همکاران (2013)[10]، فو و همکاران(2012)[11]، شـوت و همکـاران (2013) [12] و بیــانکو و کارامیــا (2011) [13] اشــاره کــرد. بالســتین و همکاران(2011)[14] نیز از یـک الگـوریتم تکـاملی بـرايبررسی این مسئله بهره برده اند.
حال اگر فعالیت ها امکان اجرا در بیش از یک مد را
داشته باشند، مسئله MRCPSP/ max8 (یا MRCPSP/GPR) پدید خواهد آمد.
مســئله MRCPSP/max، حالــت تعمــیم یافتــهبسیاري از مسائل زمانبندي پروژه اسـت کـه از میـان آنهـا
RCPSP و MRCPSP ،RCPSP/max م ی ت وان ب ه
اشاره کرد.
درباره مسئله MRCPSP/max مشاهده می شود که ادبیـــات MRCPSP/max بـــه گســـتردگی ادبیـــاتMRCPSP نیســت. در تحقیقــات انجــام شــده توســطمحققانی نظیر دي ریک (1998) [15] و ایباراکی و نونوبه (2003) [16] از رویکــرد فراابتکــاري جســتجوي ممنــوعبراي حل مسئله MRCPSP/max استفاده شـده اسـت.
هــیلمن [17] نیــز در ســال 2001 از قــانون اولویــتچند گذري کمـک گرفتـه اسـت و در سـال2003[18] بـااستفاده از روش حل دقیق (روش شاخه و کران) به بررسی مســئله مــورد نظــر پرداختــه اســت (در روش اولویــت چند گذري، که از جمله روش هاي ابتکاري است، با استفاده از طرح هاي تولیـد زمانبنـدي و قواعـد اولویـت، بـه تولیـدجواب پرداخته می شود[19]). سید حسـینی و سـبزه پـرورنی ز ب ا کم ک الگ وریتم ه اي فراابتک اري (2007)[20] و (2008) [21] اقدام به حل مسئله مذکور کرده اند. جیاویچ نیز در سال 2011 از روش هـا ي ابتکـاري بـراي حـل ایـنمسئله استفاده کرده است[22 و 23]. پژوهشگران دیگري نظیر باریوس و همکـاران (2011) [2] از الگـوریتم ژنتیـکدوبل9 براي حل مسئله MRCPSP/max بهره برده اند.
بدیهی است هنگامی که فعالیت هاي یک پروژه فقـط در یک حالت اجرا می شوند، حل مسئله زمانبندي مـرتبطبسیار ساده تر از زمـانی اسـت کـه هـر یـک از فعالیـت هـا چندین مد اجرایی دارند. اگر بتـوان بـا کمـک روش هـا یی، مسئله پیچیده اولی را به مسئله دوم تبدیل کرد، در زمـانحل صرفه جویی خواهد شد. یکی از شیوه هـاي انجـام ایـنکار، استفاده از الگوریتم هاي فراابتکاري اسـت کـه در ایـنمقاله مورد توجه قرار گرفته است.
از آنجایی که الگوریتم ژنتیک، یکی از پرکـاربرد تـرینروش فراابتکاري در حل مسائل زمانبندي بوده اسـت [24و 25]، در این مقاله نیز مورد استفاده قرار می گیرد. الگوریتم ژنتیک در حقیقت یک شیوه تکـاملی اسـت کـه روي یـکجمعیت اولیه، عملیاتی را انجـام مـی دهـد ،والـدین را بـرمی گزیند ،عملگر هاي تقاطع و جهش را اجرایی مـی کنـد وفرزندان به وجود آمـده را ارزشـیابی مـی کنـد . هـدف ایـنالگوریتم این اسـت کـه بـه طـور پـی در پـی بـا احتمـالبیشتري، بهترین پاسخ هاي موجود را براي ترکیب انتخـابکند تا در نهایت جواب هاي بهتري ایجاد شود.
ادامـه مقال ه بـدین ترتی ب اسـت : در بخ ش 2، م دل ریاضی مسئله مورد بحث در این مقاله ارائـه مـی شـود . در بخش3، راه حل پیشنهادي براي مدل ارائه شـده در بخـش2، شرح داده شده است. بخـش چهـارم بـه بررسـی نتـایجمحاسباتی الگوریتم هاي ارائه شده می پردازد و در نهایـت دربخش 5، نتیجه گیري و ارائه پیشنهاد براي تحقیقات آینـدهارائه شده است.

مدل
پیش از پرداختن به مدل ریاضی مسـئله مـورد بحـث دراین مقاله، ابتـدا جـدول علائـم اسـتاندارد مـورد اسـتفاده،معرفی می شود.

جدول 1: علائم استاندارد مورد استفاده در این مقاله

م دل ریاض ی مس ئله زمانبن دي پ روژه ب ا ه دف کمینه کردن هزینه هاي دیرکرد و بیشینه کردن پاداش زودکرد انجام فعالیت ها:
مدلی که در این مقاله معرفی می شـود ، بـه ایـن شـکل است که در آن به دنبال یافتن یک زمان شروع و یـک مـداجرایــی بــراي هــر فعالیــت هســتیم، بــه گونــه اي کــه محدودیت هاي مربوط به تأخیرات زمانی بیشـینه و کمینـهو نیز محدودیت هاي منـابع تجدیـد پـذیر و تجدیـ د ناپـذیربرقرار باشند و هزینـه دیرکـرد فعالیـت هـا کمینـه شـو د و پاداش تحویل دادن فعالیـت هـا پـیش از موعـد مقـرر نیـزبیشینه شود. پیش از ارائه مدل ریاضی مسئله مورد بحـث،لازم است درباره مفاهیم کلیدي این مدل توضیحاتی ارائـهشود.
در این مدل ℎ نمایانگر حداکثر زمان مطلـوب اتمـام فعالیت که در مد اجرا می شـود، اسـت و نیـززمان اتمام فعالیت مورد نظـر را نشـان مـی دهـد. بـدیهیاست که رابطه زیر همواره برقرار است:

=+

دیرکرد فعالیت که در مد اجرا مـی شـود، از معادلـهزیر به دست می آید:

= max (0,− ℎ)
نیز جریمه هر واحد دیرکرد فعالیت که در مد اجرا می شود ،است.
زودکرد فعالیت که در مد اجرا مـیشـود، از معادلـهزیر به دست می آید:

= max (0, ℎ−)

نیز پاداش هر واحد زودکرد فعالیت که در مد اجرا می شود، است.
حال با توجه به مفاهیم یـاد شـده، شـکل ریاضـی مـدلزمانبندي پروژه با هدف کمینه کردن هزینه هاي دیرکـرد و بیشینهکردن پاداش زودکرد انجام فعالیت ها را میتوان بـهصورت زیر نمایش داد :

min ∑∑ ∈ (− )

(4)

201168-629

:
(( , ))

≤ , ( ∈ ;≥ 0)
∈(, , )

∑ ∈ ≤ , ( ∈)

∈ ( ),
≥ 0 ( ),
= 0 (9)

تــابع هــدف در مــدل بــالا( رابطــه 4 )، در پـ ی کمینه کردن هزینه دیرکرد و بیشینه کردن پاداش زودکرد تحویــل فعالیــت اســت. رابطــه (5) محــدودیت روابــطتقدمی کلی میان فعالیت ها را نشان می دهـد و رابطـه هـاي(6) و(7) نیز به ترتیب بیانگر محدودیت منابع تجدید پذیر و منابع تجدید ناپذیر هستند. زمان هاي شـروع فعالیـت هـا غیر منفی در نظر گرفته شـده اسـت. پـروژه نیـز در زمـانصفر آغاز می شود ( روابط 8 و 9).

روش حل مدل با کمـک الگـوریتم ژنتیـک دومرحله اي
هیلمن در پژوهشی در سال 2001 [17]، یک مسـئله MRCPSP/max را بـ ه دو زیـ ر مسـ ئله :1- مسـ ئله تخصیص بهترین مد 2- مسـئله RCPSP/max تقسـیمک رده اس ت. ب ه عب ارت دیگ ر ب راي ح ل ی ک مس ئله
MRCPSP/max باید ابتدا در مورد هر فعالیـت تعیـینکرد که بهترین حالت انجام آن فعالیت، کدام حالت است؟ پاسخ به این سؤال، مدهاي انجام هـر فعالیـت را بـه 1 مـدتقلیــل داده و مسـ ئله را بــه یـ ک مســئله زمانبنـ دي RCPSP/max تبـــدیل مـــی کنـــد. حـــل مســـئله RCPSP/max حاصل، در حقیقت به حل مسـئله اصـلی
MRCPSP/max منجر خواهد شد.
در این پـژوهش نیـز از ایـده هـیلمن بهـره مـی بـریم ومسئله مورد بحث را که می توان آن را از مشـتقات مسـئله MRCPSP/max به حساب آورد بـه دو زیـر مسـئله 1- تخص یص بهت رین م د و 2- مس ئله حاص ل از تخص یص بهترین مد به فعالیت ها، تفکیک می کنیم و هر یک از این زیر مسائل را به کمک یک الگوریتم ژنتیک مستقل کـه درمحیط نرم افزار MATLAB نسخه 2005 با کمـک یـک
کـامپیوترCore(TM)2 Duo P7350 2.00GHz بـا سیستم عامل ویستا کدنویسی کرده ایم ،حل می کنیم. هـرالگ وریتم ژنتی ک در ی ک الگ وریتم ژنتی ک دومرحل ه اي، ساختار کرومـوزوم 10، تـابع بـرازش11، عملگـر تقـاطع12 و عملگر جهش13 مربوط به خود را دارد.

مسئله یافتن بهترین حالت هاي انجام فعالیت ها
در تعیین بهترین مـد انجـام هـر فعالیـت، از برخـی ازنکات مطرح شده در پژوهش باریوس و همکـاران در سـال2011 [2]، بهره گرفته ایم. طرح کلی فـاز اول الگـوریتم رامی توان به این شرح بیان کرد:

تولید جمعیت اولیه
تا زمانی که شرط پایان الگوریتم (تکرار به تعداد از پیش تعیین شده / معیار همگرایی الگوریتم ) محقق نشده است:
27432-714499

کروموزوم هایی را به عنوان والدین از میان جمعیـتانتخاب کنید ( بدیهی است که هر چـه کرومـوزومی بهتـرباشد، با احتمال بیشتري به عنـوان پـدر یـا مـادر انتخـابمی شود).
به وسیله عملگر تقـاطع فرزنـدان والـدین انتخـابشده را تولید کنیـد .( شـدنی بـودن فرزنـدان از نظـر منبـعبررسی شود).
عملگر جهش را روي فرزند اعمال کنید.
ارزیابی کنید که آیا فرزنـدان از نظـر منبـع شـدنیهستند یا خیر؟
اگر فرزندان بهتر از والدین بودند، جایگزین والـدینشوند.
بهترین بردار مد، بردار باقیمانده متناظر با این بـردار مـدو نیز مقدار برازش این بردار مد را گزارش کنید.

ساختار کروموزوم و جمعیت اولیه در فاز اول
در الگوریتم ژنتیک فاز اول، هر کروموزوم به وسیله یک بردار مد14 M نشان داده می شود. برازش هر کروموزوم نیز برابر با طول مسـیر بحرانـی (یـا بـه عبـارتی دیگـر، جمـعتأخیرات زمانی در مسـیر بحرانـی) پـروژه متنـاظر بـا آنکروم وزوم خواه د ب ود و ب ا نم اد CP(M) نش ان داده می شود.
براي هر بردار مد، یک بردار بـه نـام بـردار باقیمانـده 15 تعریف می شود که تعداد آرایه هاي این بردار، به تعداد انواع منـابع تجدی د نش دنی اس ت. ه ر آرای ه، نمای انگر تع داد واحدهاي آن نوع منبع تجدید نشدنی اسـت کـه بـا فـرضاجراي فعالیت ها طبق بردار مد متناظر، هنـوز در دسـترسهستند. بدیهی است که اگر آرایه هاي یک بـردار باقیمانـده نامنفی باشند، این موضوع به معنی این است که بردار مـدمتناظر با این بردار باقیمانده، از نظر منبع، شـدنی خوا هـدبود و چنانچه مقدار این آرایه ها، عددي منفی بـود بـه ایـنمعنا است که اجرا شدن فعالیت هاي پروژه طبـق مـدهاییکه در آن کروموزوم براي فعالیـت هـا تعریـف شـده اسـتمنجر به مصرف بیش از مقدار موجود منبع تجدید نشـدنیخواهــد شــد و در نتیجــه، آن کرومــوزم از نظــر منبــعتجدید نشدنی، ناموجه و نشدنی خواهد بـود و بایـد حـذفشود.
براي ساخت جمعیـت اولیـه، ابتـدا بـه تعـداد از پـیشتعیین شده (که “اندازه جمعیت “16 و در اصـطلاح -popsize نامی ده م ی ش ود)، ب ه ش یوه اي ک ه بی ان ش د،کروموزوم هاي از نظر منبع موجـه، تولیـد مـی کنـیم . گـامبعدي این است که کروموزم هـا ي جمعیـت اولیـه، از نظـرزمان نیز شدنی باشند. بـراي ایـن منظـور کـافی اسـت درپروژه انجام شده طبق بردار مد هر کروموزوم ،”سیکل هایی با طول مثبت”17 ایجاد نشود. یعنی جمع تـأخیرات زمـانیروي آن سیکل، مثبت نباشد. پس از اعمـال شـرط شـدنیبودن از نظر زمان ،بار دیگر باید کروموزم ها را بررسی کـرد تا در طول فرآیند شدنی شدن از نظر زمان، از منظر منبـع ، ناموجه نشده باشـند؛ حـال، جمعیـت اولیـه سـاخته شـدهاست. به عبارت دیگر تعداد مورد نظر کروموزوم وجود دارد که از نظر منبع تجدید نشدنی و زمان، موجه هستند.

عملگر تقاطع فاز اول
با توجه به ماهیت مسئله تخصیص بهترین مـد بـه هـرفعالیت ،”عملگر تقاطع مبتنـی بـر سـاختار حلقـه”18 [2] (تقاطع مبتنی بر ساختار حلقه، تضمین می کند که مدهاي ساخته شده به وسیله آن از نظر زمان موجه هستند) را بـاعملگر تقاطع دونقطه اي19 (در این روش دو نقطه بـه طـور تصادفی به عنوان نقاط برش انتخاب شده و کروموزوم هـا ي والد از آن دو نقطه به سه قسمت تقسیم مـی شـوند ، آنگـاهقســمت وســط ثابــت مانــده و دو قســمت کنــاري از دوکروموزوم با یکدیگر تعویض می شوند.) ترکیب کرده ایم. بـامشــخص بــودن احتمــال تقــاطع ،pc، مــاکزیمم درصــد کروموزوم هایی که مشمول اجراي عملگر تقاطع مـی شـوندمشخص خواهد شد. اگر این تعداد زوج نبـود ، از آنجـا کـهامکان جفت کردن کروموزوم ها میسر نمـی شـود، مـی تـوانی ک کروم وزوم اضــافه یـا ک م کــرد. ح ال ب ه تعــدادمش خص ش ده، کروم وزمه ایی را ک ه می زان آرای ه ب ردار باقیمانده بیشتري از سایرین دارند را دو به دو براي اعمـالعملگر تقاطع انتخاب می کنـیم . سـپس از آنجـایی کـه درمورد همه کروموزوم ها ژن آخر، مربوط به میزان باقیمانـدهاز منبع تجدید ناپذیر است و نمایانگر مد نیست. بنابراین در محاسبات مربـوط بـه عملگـر تقـاطع، ایـن ژن را در نظـرنمی گیریم. حال با ترکیب دو عملگـر یـاد شـده، بـه ایـنصورت عمل می کنیم که فرزنـد دختـر، ژن هـا ي واقـع بـرس یکله ا (حلق ه ه ا) را از م ادر و ب اقی ژن ه ا را از پ در می گیرد و فرزند پسر، ژن هاي واقع بر سیکل ها را از پـدر وباقی ژن ها را از مادر می گیرد. به این شیوه ،فرزندان دختـرو پسـ ر را ایجـ اد کـ رده و مقـ دار باقیمانـ ده از منبـ ع تجدید نشدنی را براي هر یک از کروموزوم هاي دختر و پسر محاسبه می کنیم. اگر کروموزم هاي فرزند، مقدار باقیمانـدهبیشتري از والدین داشته باشند، جـایگزین والدینشـان درجمعیت می شوند و درغیر این صورت والـدین کماکـان درجمعی ت ب اقی خواهن د مان د. ب ا اس تفاده از ای ن ش یوه جایگزینی، شرط شدنی بـودن از نظـر منبـع نیـز در مـوردکروموزوم هاي جمعیت همچنـان برقـرار خواهـد مانـد. بـااعمال عملگر تقاطع، جمعیت حاصـله ، حـداقل بـه خـوبیجمعیت قبل از اعمال این عملگر خواهد بود.

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

ارزیابی مقدار برازش هر کروموزم در فاز اول براي محاسبه مطلوبیت هر کروموزوم، مقدار برازش هـرکروموزوم را برابر با طول مسیر بحرانـی پـروژه، در حـالتی که فعالیت ها از مـدهاي موجـود در آن کرومـوزوم پیـروي کنند، قرار می دهیم. طول مسـیر بحرانـی را مـی تـوان بـهصورت حاصل جمع تأخیرات زمانی در مسیر انجـام پـروژهمتناظر تعریف کرد.
پس از محاسبه مقدار برازش براي همه کرومـوزوم هـا ي موجود در جمعیت ،کرومـوزم هـا را بـه ترتیـب از بهتـرینبرازش به بدترین ،مرتب می کنیم. بهترین کرومـوزوم (کـهبهترین بـرازش/ کمتـرین طـول مسـیر بحرانـی را دارد )، انتخاب می شود. در اینجا یک نسل از الگوریتم ژنتیـک بـهپایان می رسد.
زمانی که نسل ها به تعداد از پیش تعیین شده ( معیـارهمگرایی الگوریتم ) تکرار شدند، بهتـرین کرومـوزوم همـه نسل ها(کروموزومی که بهترین برازش را در میـان بهتـرینکروموزوم هاي همه نسل ها دارد)، به عنوان جـواب نهـاییمسئله معرفی مـی شـود و مـی تـوان از کرومـوزوم حاصـلهاستفاده کرد و فعالیت ها را طبـق مـدهاي موجـود در ایـنکروموزوم اجرا کرد.
حال با مشخص شدن بهترین حالت اجـراي فعالیـت هـا ، در حقیقـــت مســـئله MRCPSP/max بـــه مســـئله RCPSP/max تبدیل شده اسـت و از پیچیـدگی آن تـاحد زیادي کاسته شده است. لازم به ذکر است که به دلیل جامعیـت مس ئله MRCPSP/max نسـبت ب ه مس ئله MRCPSP، از ای ن ش یوه م ی ت وان ب راي کاس تن از پیچیدگی هاي مسئله MRCPSP و تبدیل آن به مسئله RCPSP نیز بهره برد.

حل مسئله RCPSP/MAX بـا هـدف کمینـه کـردنهزینه دیرکرد و بیشینه کردن پاداش زودکرد انجـامفعالیت ها
-10667959692

پس از اجراي فاز اول ،حال باید مسـئله حاصـل از فـازاول را در فاز دوم، مورد بررسی قرار داده و بهتـرین پاسـخآن را بی ابیم. بهتــرین پاســخ عبــارت اســت از تخصــیصزمـان ه اي پایـان (ی ا معـادل آن، زم ان هـا ي ش روع) ب ه فعالیت هاي پروژه ،به طـوري کـه محـدودیت هـا ي روابـطتقدمی میان فعالیت ها و نیز منابع تجدیـد شـدنی بـرآوردهشوند و بهترین میزان تابع هدف به دست آید.
طرح کلی فاز دوم الگوریتم را می تـوان بـه شـرح زیـربیان کرد:

تولید جمعیت اولیه
تا زمانی که شرط پایان الگوریتم (تکرار به تعداد از پیش تعیین شده / معیار همگرایی الگوریتم) محقق نشده است:
کروموزوم هایی را به عنوان والدین از میان جمعیـتانتخاب کنید ( بدیهی است که هر چـه کرومـوزومی بهتـرباشد، با احتمال بیشتري به عنـوان پـدر یـا مـادر انتخـابمی شود).
به وسیله عملگر تقاطع فرزندان والدین انتخاب شده را تولید کنید.( شدنی بودن فرزندان از نظـر روابـط تقـدمیمیان فعالیت ها بررسی شود).
عملگر جهش را روي فرزندان اعمال کنید.
ارزیابی کنید که آیا فرزندان از نظر روابـط تقـدمی، شدنی هستند یا خیر؟
بهترین ترتیب انجام فعالیت ها( بهترین لیست فعالیـت )، بردار زمان هاي شروع / پایان و نیز مقدار برازش متناظر بـابهترین لیست فعالیت را گزارش کنید.

ساختار کروموزوم و جمعیت اولیه فاز دوم
در یک دسته بندي کلی می توان بیان کرد کـه در یـکالگوریتم ژنتیک، کروموزوم ها را می توان به سه حالت کلـیبر مبناي جایگشت (لیست فعالیت)، بر مبناي روش “کلید تصــادفی”20 و بــر مبنــاي “قواعــد اولویــت”٢١ تعریــف کرد[26]. برخی محققان مانند کـولیش و هـارتمن [26 و 27]، نشــان داده انــد کــه در مســائلRCPSP نمــایش کروموزوم ها بـ ه صـورت لیسـت فعالیـت نسـبت بـه سـایرروش ه اي نمایش،باع ث ایج اد نت ایج بهت ري م ی ش ود.
بنابراین در این مقاله از این شیوه استفاده می کنیم.
از آنجا که در یک لیست فعالیـت، هـر فعالیـت بعـد ازتمام پیش نیازهایش قرار می گیرد، بنابراین لیسـت فعالیـتاز نظـر رواب ط تق دمی موج ه مـی ش ود و م ی ت وان آن را “لیست فعالیت موجه تقدمی”22 نامید. حال اگر به تعداد مشخصی، کروموزوم موجه تولیـد کنـی م ،مـی تـوانیم یـکجمعیت اولیه داشته باشیم.

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

عملگر جهش فاز دوم
در اینج ا از عملگ ر جه ش جاب ه ج ایی24 ، اس تفاده خواهیم کرد. در این روش، دو ژن به طور تصادفی انتخـابشده و با یکدیگر تعویض می شوند. پـس از اعمـال عملگـرجهش، شرط شـدنی بـودن کرومـوزوم هـا بـار دیگـر مـوردبازبینی قرار گرفته و در صـورت نقـض شـدن، بـه وسـیلهایجاد حداقل تغییرات در ترتیب ژن ها، نسبت به اصلاح آن اقدام می شود.
ارزیابی کروموزوم ها در فاز دوم
براي ارزیـابی هـر کرومـوزوم ابتـدا بایـد آن را بـه یـکزمانبندي موجه تبدیل کرد. می دانیم که براي یک لیسـتفعالیت ،یک طـرح تولیـد زمانبنـدي سـري(SGS سـري ) می تواند به طور مستقیم به عنوان شیوه کدشکنی بـ ه کـاررود و از این طریق زمانبندي به دست آید [28].
استفاده از طرح تولید زمانبندي سریال، بـدین صـورتاست که ابتدا فعالیتی که در لیسـت فعالیـت (کرومـوزوم ) مورد نظر در اولین مکان قرار گرفته و بیشـترین اولویـت رادارد، انتخاب و با در نظر گـرفتن بیشـترین تـأخیر زمـانیمی ان زم ان ه اي ش روع، کمت رین ت أخیر زم انی می ان زمان هاي شروع و میزان در دسترس منبع تجدید شدنی در هر واحد زمانی ،در زودتـرین زمـان شـروع آن، زمانبنـديمی کنیم و این کار را تا زمانبندي شـدن همـه فعالیـت هـا ادامه می دهیم. سپس هزینه کل ناشی از زودکرد و دیرکرد اتمام فعالیت ها نیز که نمایانگر تابع برازش الگوریتم خواهد بود، به راحتی و براي هر زمانبندي بـ ه دسـت آمـده، قابـلمحاسبه خواهد بود. بدیهی است هر زمانبندي که کمترین میزان تابع برازش (هزینه کل) را داشـته باشـد، زمانبنـديبهتري است.

نتایج محاسباتی
پس از طراحی یک الگوریتم، نوبت به آزمـودن کـارآیی آن در حیطه مـورد نظـر مـی رسـد . از آنجـا کـه محققـان مسائل زمانبنـدي بـا محـدودیت منـابع، اغلـب بـراي ایـنمنظور از مسائل نمونه کتابخانه مسائل زمانبندي پروژه که به اختصار PSPlib 25 نامیده می شود اسـتفاده مـی کننـد،بنابراین در این مقاله نیز از همین شیوه استفاده مـی شـود .
به این صورت که نتایج حاصل از الگوریتم با نتایج موجـوددر کتابخانه مسائل زمانبندي با منابع محدود، مقایسه شده است.

نتایج محاسباتی مربوط به الگوریتم فاز اول
از آنجا که الگوریتم پیشنهادي فاز اول ،مسئله تخصیص بهترین مد به هر فعالیت را مـورد بررسـی قـرار مـی دهـد .
بنابراین آنچه براي ما مهم است، این است که بـدانیم ایـنالگوریتم در چه مدت زمانی مسئله دشوار اولیه را بـه یـکمسئله بسیار ساده تر که در آن هر فعالیت فقط یک حالـتاجرا دارد تبدیل می کند؟ بنابراین مدت زمان سـ پري شـدهبراي حل مسئله تخصیص بهترین مد، پارامتري اسـت کـهب ا اس تفاده از آن، کارآم دي الگ وریتم ژنتی ک ف از اول را می سنجیم.
براي بررسی کارایی الگوریتم ژنتیک ارائـه شـده در فـازاول، از مس ئله mm-j10-psp104 موج ود در کتابخان ه مسائل زمانبنـدي (از دسـته مسـائلMRCPSP/max ) اســتفاده مــی کنــیم. ایــن مســئله توســط نــرم افــزار ProGen/Max تولید شده است.
احتمال جهش در دو سطح 1,0 (پایین) و 5,0 (بـالا ) و احتمال تقاطع نیز در دو سـطح 1,0 (پـایین ) و 8,0 (بـالا ) مورد بررسی قرار گرفته اند.
با یک “طراحی عاملی کامل” 26 (22)، از پـ ارامتر هـا ي ذکر شده، تعداد 4 =2 ×2 حالـت( اجـرا) بـراي بررسـیتأثیر هر یک از عوامل احتمال جهش و احتمال تقـاطع بـرمدت زمان حصول نتیجه توسـط الگـوریتم وجـود خواهـدداشت. هر یک از حالت هـا ي آزمـایش، 5 بـار تکـرار شـدهاست و نتایج حاصله که زمان دستیابی نتیجـه را برحسـبثانیه نشان می دهند، در جدول (2) آورده شـده انـد . معیـارتوقف الگوریتم، تکرار تـا 500 نسـل در نظـر گرفتـه شـدهاست.

جدول 2: آزمایشات انجام شده در 4 سطح جدول (2)

نرخ تقاطع1,0 (- ) نرخ تقاطع 8,0
( +)

نرخ جهش
( -) 0,1

5,2416
5,3040
5,2728
5,1948
5,0388
5,3664
5,2260
5,2104
5,1324
5,2416

نرخ جهش
( +) 0,5
5,5536
5,6160
5,6160
5,5380
5,7876
5,8032
5,5848
5,6160
5,5224
5,7720

میانگین و واریانس آزمایشات انجام شده در هـر یـک ازحالات، در جدول (3) محاسبه شده است. اثـرات( تفـاوتمیانگین آزمایشات در سطح بالا و میـانگین آزمایشـات درسطح پایین) هر یک از عوامل نرخ جهش، نرخ تقاطع و نیز تأثیر متقابل نرخ هاي جهش و تقاطع شده اند.
همان گونه که مشاهده می شود، تأثیر نرخ جهـش (42,0) بر زمان حصول نتیجه در الگوریتم فاز اول بسیار بیشـتر ازتأثیر عامل نرخ تقـاطع (02,0) و نیـز تـأثیر متقابـل نـرخجهش و نرخ تقـاطع (0,007) اسـت . نمـودار پـارتو اثـرات، شکل (1)، تفاوت این اثـرات را بـا وضـوح بیشـتري نشـانمی دهد:

زمان پاسخ دهی الگوریتم، از آماره اي با توزیع t و با درجه آزادي 16 (16 = (1- (تعــداد مشــاهدات در هــر ترکیــبآزم ایش)) × ( تع داد ترکی ب ه اي آزم ایش) ) اس تفاده می کنـیم . سـطح معنـاداري ایـن آزمـون را 01,0 در نظـرمــی گیـ ریم. بـ راي تعیــین حـ دود تصـ میم گیـ ري از رابطه هاي(11) و (12) استفاده می کنیم:

.,= 2.583 (11)
= .= 2.583 × 0.04 = 0.103
54864189888

(12)

̅
̅
در آزمون تشخیص، معنادار بـودن تـأثیر عوامـل نـرخ تصمیمگیري جهش، نرخ تقاطع و اثر متقابل نرخ جهش و نرخ تقاطع بر

80264188195

جدول 3: محاسبات مربوط به اندازه گیري اثرات هر عامل
+

جدول 4: نتایج محاسباتی مربوط به مسئله هایی با اندازه j10
شماره مثال حد پایین جواب حاصل از الگوریتم پیشنهادي درصد انحراف از حد پایین زمان محاسبه
(ثانیه) نتایج مربوط به جریمه دیرکرد و پاداش زودکرد
تعداد تکرار 1000 تعداد تکرار 500 تعداد تکرار 1000 تعداد تکرار 500 تعداد تکرار 1000 تعداد تکرار 500 واحد
جریمه(تعداد تکرار 1000) زمان محاسبه
(ثانیه)
Psp13 *40 44 44 0,1000 0,1000 40,7305 21,3419 -542 46,2387
Psp107 *46 50 50 0,0869 0,0869 49,5459 25,0226 171 49,9671
Psp50 *68 71 71 0,0441 0,0441 54,0699 26,1770 380 52,3227
Psp64 *47 47 47 0,0000 0,0000 57,4396 28,6730 220 58,1260
Psp26 54 70 70 0,2269 0,2269 53,2275 26,2706 392 48,8127
Psp92 81 85 85 0,0493 0,0493 48,6099 24,5078 133 44,1246
Psp237 49 61 63 0,2448 0,2858 49,8735 25,1162 229 50,3571
Psp125 42 59 59 0,4047 0,4047 52,5567 26,4422 300 51,8391
Psp100 *44 61 61 0,3863 0,3863 49,8579 25,9118 495 49,7955
Psp17 36 52 53 0,4444 0,4722 51,7143 26,0054 417 51,3867
*- پاسخ بهینه

جدول 5: نتایج محاسباتی مربوط به مسئله هایی با اندازه j20
شماره مثال

حد پایین
حد بالا- درصد انحراف جواب حاصل از الگوریتم پیشنهادي درصد انحراف از حد پایین زمان محاسبه
(ثانیه) نتایج مربوط به جریمه دیرکرد و پاداش زودکرد
تعداد نسل 1000 تعداد نسل 500 تعداد نسل 1000 تعداد نسل 500 تعداد نسل 1000 تعداد نسل 500 واحد
جریمه(تعداد تکرار 500) زمان محاسبه
(ثانیه)
Psp65

(GA) 68
%35,29 -92
84
87
0,2352
0,2794
325,090
163,567
1472
165,7667
Psp70

(BB) 79
%48,10-117
124
124
0,5696
0,5696
333,202
162,3658
2259
164,8307
Psp224 *83 106 106 0,2771 0,2771 294,8419 148,5286 2556 151,2134
Psp154

(BB) 85
%40,00-119
131
131
0,5411
0,5411
318,975
157,935
2446
159,0742
Psp220

(BB) 74
%52,70-113
124
124
0,6756
0,6756
310,1612
157,3894
2348
156,0166
*- پاسخ بهینه

جدول 6: نتایج محاسباتی مربوط به مسئله هایی با اندازه j30
شماره مثال

حد پایین حد بالا- درصد انحراف جواب حاصل از الگوریتم پیشنهادي درصد انحراف از حد پایین زمان محاسبه
(ثانیه) نتایج مربوط به جریمه دیرکرد و پاداش زودکرد
تعداد نسل 1000 تعداد نسل 500 تعداد نسل 1000 تعداد نسل 500 تعداد نسل 1000 تعداد نسل 500 واحد جریمه(تعداد تکرار 250) زمان محاسبه
(ثانیه)
Psp129

(BB) 83
%74,70-145
165
165
0,9879
0,9879
993,8824
508,5789
5464
243,1744
Psp247

(GA) 106
%65,09-175
167
167
0,5754
0,5754
972,0266
502,4792
4554
241,0059
Psp261 *184 184 187 0,0000 0,0163 954,5545 490,7791 5343 238,1043
Psp157 110 170 172 0,5455 0,5636 996,0040 499,8428 7402 243,0340
Psp216 145 167 169 0,1517 0,1655 985,0059 486,5515 5054 476,0059
*- پاسخ بهینه
نشریه تخصصی مهندسی صنایع , دوره 47 ، شماره1، فروردین ماه 1392
نتایج محاسباتی مربوط به الگوریتم فاز دوم ب راي بررس ی الگ وریتم ژنتی ک پیش نهادي ف از دوم ،تعداد 10 مسئله نمونه با 12 فعالیت (که از این تعـداد 10 فعالیت، غیرمجازي هستند)، 5 مسئله نمونه با 20 فعالیـتغیر مجازي و 5 مسـئله نمونـه دیگـر بـا 30 فعالیـت غیـر مجازي به طور تصادفی از کتابخانه مسـائل زمانبنـدي و از دسته مسائل RCPSP/max انتخاب شـده انـد کـه ایـنمسـئله ه ا نی ز توس ط ن رم اف زار ProGen/Max تولی د شده اند( جداول 4، 5 و 6). همانگونه که مشاهده می شـود ، الگوریتم پیشنهادي در چندین مورد بهترین جواب موجود در کتابخانه مسـائل زمانبنـدي را بهبـود بخشـیده اسـت وجواب هاي به دست آمده قابلیت ارسال به سایت کتابخانـهمسائل زمانبندي را دارند.
در ستون هاي آخر از سمت چپ در هر یـک از جـداول4، 5 و 6، نتایج مربوط به جریمه دیرکرد و پاداش زودکرد تحویل فعالیت ها آورده شده است. از آنجا که حداکثر زمان مطلوب اتمام هر فعالیت، جریمه هر واحد دیرکرد و پاداش هر واحد زودکرد فعالیت ها در هر پروژه اي بر اساس شرایط آن پروژه و نظر کارفرما تعیین می شود، بنابراین براي اینکه مبناي مقایسه اي میان الگوریتم ارائه شـده در ایـن مقالـه وتحقیقات بعدي فراهم باشد، به این ترتیب عمل کـرده ایـمکه جریمه هاي دیرکرد و پـاداش هـاي زودکـرد را اعـداديتصادفی بین 1 تا 5 مقدار داده ایم و مقادیر ℎ را نیـز بـهطور تصادفی در حد فاصل میان 1 تا حد پایین متناظر بـامسئله( در مورد مسائل جدول 4) و حد بـالاي متنـاظر بـاهر مسئله ( درباره مسائل جداول 5 و 6) انتخاب کرده ایـم . سپس نتایج حاصله را در ستون ذکر شده در هر یک از سه جدول، آورده ایم.

نتیجـه گیــري و ارائــه پیشــنهادهایی بــراي تحقیقات بعدي
در حیطـــه مســـائل زمانبنـــدي پـــروژه، مســ ئله MRCPSP/max از جملــه کلــی تــرین و دشــوار ترین مســائل بــه شــمار مــی رود. مــی تــوان یــک مســئله MRCPSP/max را با کمک الگوریتم ژنتیک به مسـئله بسیار ساده تري که در آن، فعالیت ها فقط در یک مد اجـرامی شوند، تبدیل کرد. این کار سـرعت رسـیدن بـه جـواببهینه مسئله را بالا خواهـد بـرد و از پیچیـدگی هـاي حـلمستقیم MRCPSP/max خواهد کاست. در این مقالـه،مدلی که از مشتقات مسئله MRCPSP/max بـه شـمارمی آید، مورد بررسی قرار گرفت. براي حـل ایـن مسـئله از الگوریتم ژنتیکی با کروموزوم هاي نمایـانگر بـردار مـدهاي تخصیص یافته و بردار مقدار باقیمانده منابع تجدیدناپـذیرکمک گرفتیم و با اعمال عملگرهاي تقاطع و جهش، سـعیدر بهبود کروموزوم ها داشـتیم و در نهایـت، پـس از تکـرارنسل هاي کروموزوم به تعداد معین، بهترین بـردار مـد کـهکمترین طول مسیر بحرانی را ایجاد می کـرد را بـ ه دسـتآوردیــ م. پــ س از کســ ب ایــ ن نتیجــ ه ،مســ ئله MRCPSP/max بـــه یـــک مســـئله RCPSP/max تبدیل شده است و با استفاده از الگوریتم ژنتیـک دیگـري، اقدام به یافتن بهترین جواب براي این مسئله خواهیم کرد.
در تحقیقات آینده می توان با ایجاد تغییراتـی در مـدلمطرح شده در این مقاله، نزدیکی بیشتري با دنیاي واقعـیایجاد کرد. براي مثال می توان با توجه به خواست کارفرمـاو نیز شرایط پروژه، معیارهاي ارزیـابی عملکـرد دیگـري رانیز در نظر گرفت و توازنی بین آن معیارهـا و تـابع هـدفمطرح شده در این مقاله برقرار کرد. همچنین می توان براي حل مدل، از الگوریتم هاي ترکیبی استفاده و نتایج حاصـلهرا با نتایج الگوریتم پیشنهادي در این مقاله مقایسـه کـر د.
الگوریتم پیشنهادشده در این پژوهش را نیـز مـی تـوان بـااعمال تغییراتی در سـاخ تار کرومـوزوم هـا و بهبـود شـیوهنمایش جواب ها، همچنین ایجاد تغییراتـی در عملگرهـايتقاطع و جهش، ارتقاء بخشید. براي تسریع حصول جـوابنیز ،می توان الگوریتم را به گونه اي طراحی کرد که در ابتدا و براي ساده تر شدن مراحل انجـام الگـوریتم، منبـع/منـابعتجدیــد نشــدنی زائــد 27 را حــذف کنــد. (یــک منبــعتجدیدنشدنی را زائد گویند، اگر جمـع بیشـترین نیازهـايفعالیـت هـا بـه ای ن منبـع، در هـیچ صـورتی از می زان دردسترس و مجاز آن منبع تجاوز نکند.)

قدردانی
نویسندگان مقاله از آقاي شهرام شادرخ و خانم نیلوفر هدایت به دلیل الهامبخشی ایده این تحقیق سپاسگزارند.
مراجع
Dorndorf, U., Pesch, E. and Phan-Huy, T. (2000). “A time oriented branch and bound algorithm for resource constrained project scheduling with generalised precedence constraints.” Management Science Informs, Vol. 46, PP. 1365–84.
Barrios, A., Ballestín, F. and Valls, V. (2011).“A double genetic algorithm for the MRCPSP/max.” Computers & Operations Research, Vol. 38, PP. 33– 43.
Bartusch, M,. Möhring, R. H. and Radermacher, F.J. (1988) “Scheduling project networks with resource constraints and time windows.” Annals of Operations Research, Vol. 16, PP. 199 – 240.
De Reyck, B. and Herroelen,W. (1998). “A branch-and-bound procedure for the resource-constrained project scheduling problem with generalized precedence constraints.” European Operational Research, Vol. 111, PP. 152–174.
Fest, A., Möhring, R. H., Stork, F. and Uetz, M. (1998). “Resource constrained project scheduling with time windows: a branching scheme based on dynamic release dates.” Technical report 596, TU Berlin, Germany.
Franck, B., Neumann, K. and Schwindt, Ch. (2001). “Truncated branch and bound, schedule construction, and schedule improvement procedures for resource constrained project scheduling.” OR Specktrum-Berlin Springer, Vol. 23, PP. 297–324.
Franck, B. and Selle, T. (1998). “ Metaheuristics for the resource-constrained project scheduling problem with schedule-dependent time windows.” Technical Report WIOR-546, Universitat Karlsruhe, Germany.
Cesta, A., Oddi, A. and Smith, S.F. (2002). “A Constraint-Based Method for Project



قیمت: تومان


دیدگاهتان را بنویسید