ارایه مدلی ترکیبی برای تسطیح منابع چندگانه با استفاده از الگوریتم چند معیاره تکاملی تفاضلی در شرایط عدم قطعیت

1- مقدمه

پروژه یک تلاش موقتی و منحصر به فرد است که برای اجرا، به چندین فعالیت مختلف که نیازمند زمان و منابع تجدید پذیر از قبیل ماشین آلات، تجهیزات و یا نیروی انسانی است، تقسیم بندی می­شود. پروژه­ها، معمولاً دارای محدودیت­های زمانی هستند که این محدودیت­ها، از محدودیت­های تکنولوژیکی و یا سازمانی ناشی می­شوند (جزفو واسکا[1] و وگلارز[2]، 2006).

برای زمانبندی پروژه­ها عمدتاً از روش مسیر بحرانی استفاده می­شود. این روش به مجریان پروژه در مدیریت زمان اجرا و میزان بودجه­ی مورد نیاز برای پروژه­ها کمک می­کند. روش مسیر بحرانی، اطلاعات مفیدی از قبیل تعیین مسیر(های) بحرانی، زمان شناوری برای فعالیت­های غیر بحرانی و کل جریان را که برای برنامه­ریزی در پروژه­ها ضروری هستند، آماده می­کند (باورز[3]، 1995). اگر چه در این روش فرض بر این است که برای انجام فعالیت­ها، منابع نامحدود در دسترس است، اما در پروژه­های واقعی، منابع نامحدود نیستند، بنابراین زمانبندی پروژه بدون درنظر گرفتن محدودیت منابع، یک زمانبندی غیر قابل اعتماد و غیر کاربردی خواهد بود (کاستور[4] و سیراکولیس[5]، 2009).

نیاز به تسطیح منابع، زمانی به وجود می­آید که هدف، کاهش نوسانات در الگوی استفاده از منابع در طول زمان باشد. علاوه بر این، مطلوبیت در این مسایل، ثابت نگه داشتن زمان از پیش تعیین شده برای تکمیل پروژه است. مخصوصاً در مواردی که حتی تغییرات اندکی در نیازهای منابع، منجر به بار مالی و یا ریسک بالایی از حوادث هستند، یک رویکرد تسطیح منابع از طریق تلطیف منابع استفاده شده تا حد ممکن، به مجریان در زمانبندی فعالیت­های پروژه در کل افق برنامه ریزی کمک می­کند (پنز- تیندا[6] و دیگران، 2013).

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

هدف این پژوهش ارایه مدل مناسبی برای کاهش نوسان سطح مصرف منابع در یک پروژه و یافتن روش حل مناسب برای مدل پیشنهادی است. در ادبیات موضوع، مطالعات گسترده‌ای توسط پژوهشگران متعدد در این حوزه صورت گرفته است. مطالعات انجام شده در زمینه­ی تسطیح منابع، را می‌توان در سه دسته گروه­بندی نمود: روش­های تحلیلی، الگوریتم­های ابتکاری و الگوریتم­های فراابتکاری. استفاده از الگوریتم­های فرا ابتکاری در سال­های اخیر بسیار مورد توجه قرار گرفته است. از میان الگوریتم­های فراابتکاری، الگوریتم ژنتیک[9] و الگوریتم بهینه سازی ازدحام ذرات[10] بیش از سایر الگوریتم­ها مورد استفاده قرار گرفته است (هاشمی دولابی و دیگران، 2011).

به دلیل عدم انعطاف و ناکارآمدی روش­­های تحلیلی و ابتکاری در مسایل تسطیح منابع، لئو[11] و همکاران (2000)، یک سیستم پشتیبان تصمیم‌گیری برای ساختار تسطیح منابع مبنی بر الگوریتم ژنتیک ارایه کرده­اند. الگوریتم ارایه شده توسط آن­ها می­تواند ترکیب بهینه و یا نزدیک به بهینه را در ساختار هموار سازی منابع به دست آورد. الرایس[12] و دیگران (2009) برای حداقل کردن نوسان مصرف منابع، دو معیار جدید معرفی کردند. آن­ها برای بهینه­سازی روشی ارایه کردند که در آن الگوریتم ژنتیک به عنوان یک ماژول جستجو به­کار گرفته شده است و هدف آن حداقل کردن تاثیرات منفی نوسانات منابع روی هزینه و بهره­وری ساخت و ساز است. کولیناس[13] و آناگنوستپلوس[14] (2013)، یک الگوریتم جستجوی ممنوعه[15] مبتنی بر الگوریتم فوق فراابتکاری[16] برای مساله تسطیح منابع ارایه نموده‌اند. الگوریتم ارایه شده توسط آن‌ها، در سه پروژه به کار گرفته شده است و نتایج حاصله نشان‌دهنده‌ی توانایی بالای الگوریتم در بهینه‌سازی تسطیح منابع است.

در مقاله­ی ارایه شده توسط کیریکلیدیس[17] و دیگران (2014)، از یک روش ترکیبی مبتنی بر الگوریتم ژنتیک و بهینه‌سازی کلونی مورچه‌ها[18] برای تسطیح منابع چندگانه استفاده گردیده است. سپس روش پیشنهادی براساس سری داده‌های استاندارد با برخی از روش­های سنتی تسطیح منابع مقاسیه شده است. مسعودی[19] و هیت[20] (2013)، یک مدل فازی و یک روش حل دقیق برای مساله زمانبندی و تسطیح منابع ارایه داده‌اند. حل دقیق ارایه شده توسط آن­ها به طور قابل ملاحظه‌ای زمان حل را کاهش داده است.

ژئوفو و جییانگ (2011) بر اساس یک مدل پایه، مدلی برای تسطیح منابع ارایه کردند و با ترکیب اصول پایه­ای الگوریتم بهینه­سازی کلونی مورچه و مدل ارایه شده، یک الگوریتم برای هموارسازی منابع طراحی کردند. عسگری[21] و همکاران (2013) یک رویکرد مبتنی بر نظریه بازی‌ها برای حل مساله تسطیح منابع در صنعت ساخت و ساز توسعه داده‌اند. نتایج حاصل از مدل آن‌ها، نشان‌دهنده‌ی کارآیی و اثربخشی روش ارایه شده است. یک مدل تسطیح منابع چندگانه و بهینه‌سازی آن با استفاده از الگوریتم ژنتیک توسط قدوسی[22] و دیگران(2013) توسعه داده شده است. آن‌ها از روش وزن‌دهی و نرمال‌سازی برای یکپارچه‌سازی تابع هدف استفاده نموده‌اند. در مقاله‌ای که توسط تانگ[23] و دیگران (2013) ارایه شده است، به کاربرد تسطیح منابع در زمانبندی پروژه‌های ساخت راه‌آهن پرداخته شده است. آن‌ها از یک روش زمانبندی خطی برای حل مساله تسطیح منابع استفاده نموده‌اند. یک الگوریتم ژنتیک تطبیقی برای تسطیح منابع چندگانه توسط پنز تیندا و دیگران (2013) ارایه گردیده است. الگوریتم آن‌ها با استفاده از زبان برنامه‌نویسی ویژوال بیسیک در نرم‌افزار اکسل 2010 پیاده‌سازی گردیده و به عنوان یک سیستم پشتیبان تصمیم منعطف ارایه شده است.

 هو[24] و فلود[25] (2013) نیز از جمله افرادی هستند که به بهینه‌سازی در زمینه تسطیح منابع چندگانه پرداخته‌اند. آن‌ها از رویکرد تکاملی پارتو برای دست‌یابی به جواب بهینه استفاده کرده‌اند. ریک[26] و دیگران (2012)، یک مدل برنامه‌ریزی عدد صحیح مختلط برای تسطیح منابع توسعه داده‌اند. مدل ارایه شده توسط آن‌ها تک‌هدفه و با استفاده از سری داده‌های استاندارد ارزیابی گردیده است. در مقاله‌ای که توسط سبفالبی[27] و زندروی[28] (2012) ارایه شده است، یک روش ترکیبی مبتنی بر الگوریتم ابتکاری و فراابتکاری توسعه داده شده است. نقطه قوت الگوریتم آن‌ها، یافتن جواب بهینه در کمترین زمان نسبت به سایر الگوریتم‌های مورد مقایسه بوده است. همچنین جیو[29] و دیگران (2012) نیز یک الگوریتم بهینه‌سازی ازدحام ذرات برای تسطیح منابع چندگانه توسعه داده‌اند.

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

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

.

جدول 1- مقایسه پژوهش‌های اخیر

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

2- روش پژوهش

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

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

3- الگوریتم تفاضلی تکاملی^[31]

در سال­های اخیر، توسعه­ی الگوریتم­های تکاملی، پیشرفت قابل ملاحضه­ای داشته است. الگوریتم تفاضلی تکاملی نمونه­ای از این الگوریتم­هاست. در ابتدا، چنین تصور می­شد که الگوریتم تفاضلی تکاملی برای مسایل بهینه سازی پیوسته و بدون محدودیت کاربرد دارد. اما با توسعه­ این الگوریتم می­توان از آن برای مسایلی با متغیرهای مختلط و محدودیت­های غیر‏خطی نیز بهره جست. این الگوریتم به عنوان یک روش فرا ابتکاری، کاربرد گسترده­ای در حل مسایل نظری و عملی دارد. عملیات ثبت نام، بهینه سازی فرآیندهای شیمیایی، تصمیم‌گیری چند معیاره، آموزش شبکه­های عصبی، برازش توابع فازی و غیره از جمله زمینه­های کاربردی این الگوریتم در سالیان اخیر بوده است.الگوریتم تفاضلی تکاملی از ترکیب الگوریتم ژنتیک و استراتژی­های تکاملی با تکنیک‏های جستجوی هندسی حاصل شده است. در الگوریتم ژنتیک تغییر ساختار بردار جواب با استفاده از عملگر ترکیب و عملگر جهش انجام می­شود، در حالی که در استراتژی تکاملی، انطباق از طریق دستکاری هندسی بردار جواب حاصل می­گردد. الگوریتم تفاضلی تکاملی بر اساس ایده­­ی ساده اما قدرتمند: «جهش برداری»، که در سال ۱۹۹۵ توسط استورن[32] و پرایس[33] ارایه شد، بنا گردید و به سرعت مورد توجه پژوهشگران قرار گرفت. ایده­ی اصلی در شکل گیری این الگوریتم، تولید بردارهای پارامتری آزمایشی است. جهش و جابجایی برای تولید بردارهای جدید استفاده می‌شوند و در مرحله­ی انتخاب، بردارهای ایجاد کننده­ی نسل بعد تعیین می­گردند. در الگوریتم تفاضلی تکاملی مجموعه­ای از پارامترهای بهینه سازی D یک بردار جواب نامیده شده و به وسیله­ی بردارهای پارامتری D بُعدی نمایش داده می­شوند (فابریس[34] و کرهلینگ[35]، 2012؛ گوش[36] و دیگران، 2012؛ سان[37] و دیگران، 2012).

4- روش الکتر

الکتر، یک روش تصمیم گیری چند معیاره است که تعدادی متغیر را با توجه به چند معیار که مبین میزان ترجیح تصمیم گیرنده­ هستند رتبه بندی می­کند (آیلو[38] و دیگران، 2006). ارتباط میان متغیرها و معیارها به وسیله­ی توابع هدف توصیف می­شود. مهم­ترین تفاوت الکتر با سایر روش­ها، جبران کننده نبودن آن است، به این معنی که در این روش امتیاز بسیار بد در یک تابع هدف با امتیاز بسیار خوب در تابع هدف دیگر جبران نمی­شود. به بیان دیگر، تصمیم‏گیرنده متغیری که در یکی از معیارها بسیار بدتر از متغیرهای دیگر باشد را انتخاب نمی­کند. ویژگی دیگر این روش استفاده از شبه معیار است. این روش با به‏کار‏گیری شبه‏معیارها، امکان درنظر گرفتن ابهام­ها و عدم قطعیت در معیارها (توابع هدف) را فراهم می­نماید. (نصرالهی، 1387)

الکتر بر اساس اصل برتری عمل می­نماید؛ متغیر  از متغیر  برتر است اگر دلیل موجهی وجود داشته باشد که  به همان خوبی  است و دلیلی بر رد این مدعا وجود نداشته باشد. بنابراین، برتری بر اساس خصوصیات ترجیح و عدم ترجیح مشخص می­شود.

برای هر معیار ، سه حد زیر در نظر گرفته می‏شود:

: حد بی تفاوتی

: حد ترجیح

: حد رد

که در آن:

با استفاده از این حدود، شش نوع ارتباط میان متغیر  و متغیر  با توجه به  مقادیر معیار ام ـ  و ـ تعریف می­شود:

:متغیر با توجه به معیار  نسبت به متغیر  بی­تفاوت است اگر:

: متغیر با توجه به معیار  از متغیر  کمی برتر است اگر:

:متغیر  با توجه به معیار  از متغیر  خیلی برتر است اگر: 

: ادعای «متغیر برتر از متغیر  است» با توجه به معیار  رد نمی­شود اگر:

 : ادعای «متغیر  برتر از متغیر  است» با توجه به معیار  به صورت ضعیف رد می‏شود اگر:

: ادعای «متغیر  برتر از متغیر است» با توجه معیار  به شدت رد می­شود اگر:

حدود ،  و ، می­توانند برای هر معیار مقادیری ثابت یا تابعی از عملکرد به صورت رابطه­ی (1) باشند.

ارتباطات نوع اول تا سوم، ارتباطات ترجیح نامیده می­شوند و برای ارزیابی دلایلی که اثبات می‌کنند «متغیر  با توجه به معیار  برتر از متغیر  است» به کار می­روند؛ ارتباطات نوع چهارم تا ششم، ارتباطات عدم ترجیح نامیده می­شوند و برای اندازه‏گیری قدرت دلایلی که باعث رد ادعای این‏که «متغیر  با توجه به معیار  برتر از متغیر  است» استفاده می­شوند. (عابدی[39] و دیگران، 2012)

5- تعریف مساله

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

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

5-1- مدل پیشنهادی

با توجه به توضیحات ارایه شده مدل پیشنهادی به صورت زیر تعریف می­شود:

مفروضات:

فعالیت پس از شروع تا زمان پایان امکان توقف نداشته و امکان شکستن فعالیت­ها وجود ندارد.

امکان افزایش زمان پروژه طی فرآیند تسطیح منابع وجود ندارد.

پارامتر‌ها:

: میزان مصرف منبع نوع ام در امین روز از فعالیت ام

: مدت زمان اجرای فعالیت ام

: تعداد فعالیت­ها

: تعداد منابع

: تعداد دوره­های زمانی در افق انجام پروژه

: زودترین زمان آغاز فعالیت ام

: دیرترین زمان آغاز فعالیت ام

: حداکثر میزان در دسترس از منبع نوع  ام در دوره­ی ام

متغیرهای تصمیم:

: زمان شروع فعالیت ام

رابطه (2) نشان دهنده تابع هدف است. در این مدل هدف کمینه سازی مجموع مربعات سطح مصرف روزانه هر منبع درنظر گرفته شده است. بدیهی است با کمینه سازی این مجموع مربعات، میزان نوسان کلی مصرف منبع در طی دوره زمانی اجرای پروژه کمینه خواهد شد.

رابطه (3) تضمین کننده شروع فعالیت در بازه شناوری آن است که باعث می­شود فرآیند تسطیح سبب افزایش زمان کل اجرای پروژه نگردد. رابطه­ی (4) ضامن عدم تجاوز میزان مصرف یک منبع در هر روز از سطح در دسترس منبع در آن روز است. روابط (5) و (6) برای عدم شکست فعالیت­ها تعریف شده­اند. روابط (8) و (9) نیز به ترتیب مبین محدودیت صفر و یک و عدد صحیح هستند.

5-2 روش حل

روش­های ابتکاری و فرا ابتکاری زیادی برای حل مساله جابه­جایی فعالیت­ها ارایه شده­اند. در این پژوهش، راهکاری بر مبنای توسعه­ای از یک الگوریتم ترکیبی تفاضلی تکاملی ـ چند معیاره، برای تسطیح منابع چندگانه در شرایط واقعی طراحی شده است.

الگوریتم تفاضلی تکاملی، به عنوان یکی از قوی‌ترین الگوریتم‌های فراابتکاری شناخته می‌شود. کم بودن پارامترهای کنترلی این الگوریتم، باعث آسانی استفاده از آن شده است. این امر سبب شده است که این الگوریتم در مدت کوتاهی محبوبیت زیادی درمیان پژوهشگران بدست آورد. با توجه به کاربرد گسترده الگوریتم تفاضلی تکاملی در مسایل دنیای واقعی، پژوهشگران بسیاری توسعه‌هایی از این الگوریتم ارایه نموده‌اند (ژئوسانگ[40] و دیگران، 2008).

مساله مورد بررسی یک مدل در فضای بسته‌ی پیوسته است. بنابراین الگوریتمی برای حل باید انتخاب شود که با چنین فضایی متناسب باشد. الگوریتم تفاضلی تکاملی به صورت متداول برای مسایل بهینه سازی پیوسته استفاده می‏شود. فضای جستجو در چنین مسایلی یک فضای پیوسته‌ی بسته یا مجموعه‌ای متناهی از فضاهای پیوسته‌ی بسته است (ژانگ بو[41] و دیگران، 2014). بنابراین، این الگوریتم با مساله مورد بررسی سازگار است.

 روش پیشنهادی برای انتخاب جواب‌ها در هر نسل از توسعه‌ای از روش الکتر استفاده می‌کند. با توجه به پیچیدگی‌های محاسباتی این الگوریتم قدری زمان‌بر است. برای رفع این مشکل می‌بایست از یک الگوریتم فراابتکاری با پیچیدگی محاسباتی پایین و سرعت عمل بالا استفاده نمود. برخلاف بسیاری از الگوریتم­های فراابتکاری که با احتمال کمی ممکن است بهترین جواب‌ها را حذف کنند، عملگر انتخاب الگوریتم تفاضلی تکاملی همواره بهترین جواب‌ها را در جامعه‌ی جواب نگه می‌دارد. این امر سبب بالاتر بودن میانگین برازش جامعه‌ی جواب‌ها و همچنین سرعت بالاتر الگوریتم در دست‌یابی به جواب بهینه می‌شود. علاوه ‌بر این سادگی استفاده از این الگوریتم و همچنین محاسبات کم باعث سرعت دست‌یابی الگوریتم به جواب مناسب می‌شود (پیترووسکی[42]، 2014). در نتیجه این الگوریتم می‌تواند مشکل زمان‌بر بودن محاسبات روش الکتر را پوشش دهد و بهترین گزینه برای استفاده در روش پیشنهادی است.

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

در پژوهش حاضر با ارایه­ی روشی مبتنی بر فرآیند الکتر برای ارزیابی جواب­ها این مشکل حل شده­ است. برای مواجهه با ابهامات موجود در میزان مصرف منابع، بجای استفاده از اهداف تحلیلی از شبه معیار استفاده شده است. با استفاده از این روش می‌توان با توجه به نوع مصرف منابع، چندین شبه معیار (کمی، کیفی و فازی) متفاوت تعریف نمود.

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

مشکل نرمال سازی و محاسبه وزن­ها، باعث ضعف کاربردی این روش­ها شده است. در روش پیشنهادی با توسعه الگوریتم تفاضلی تکاملی، مشکل وزن دهی و نرمال سازی اهداف نیز رفع شده است.

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

برای اعمال محدودیت­ها، از استراتژی جستجوی محلی و جستجوی عمومی و تعمیر جواب­های غیر قابل قبول استفاده شده است. همچنین از یک مکانیزم جریمه درجه بندی شده برای سوق دادن جستجو به سمت فضاهای شدنی مساله استفاده شده است.

ساختار روش ارایه شده متناسب با تنوع مقیاسی توابع هدف و محدودیت­های ویژه­ی این مساله طراحی شده است. مراحل الگوریتم روش ارایه شده به شرح زیر است:

گام یک: جمعیت جواب اولیه را تولید کنید.

برای ایجاد جمعیت اولیه، بردار  را به صورت تصادفی تولید می­شود. جمعیت هر نسل با نماد  نشان داده شده و از روابط (10) و (11) محاسبه می‌گردد.

در این روابط اندیس­های  و   به ترتیب نشان‌دهنده نسل و جمعیت هستند که به یک بردار تعلق دارند.  اندازه جمعیت را نشان می­دهد. همچنین  نشان دهنده­ی شمارنده­ی هر عنصر در بردار جوابی است که شامل  عنصر است.

گام دو: با استفاده از عملگر جابه­جایی جمعیت جواب آزمایشی را از جمعیت جواب اولیه تولید کنید.

 در عملگر جابه­جایی عناصری از یک بردار جهش یا چند بردار جواب اولیه با یک بردار از نسل فعلی مطابق رابطه­ی (12) جابه­جا می­شود و بردار جواب آزمایشی را به وجود می­آورد.

در رابطه (12)    فاکتور جابجایی است که با توجه به شرایط مساله مقداری بین صفر و یک به آن اختصاص داده می­شود. این فاکتور با خروجی یک عدد تصادفی از تابع توزیع یکنواخت ( ) مقایسه می­شود، اگر عدد تصادفی کوچکتر یا مساوی  باشد در این صورت عنصر جواب آزمایشی از بردار جهش ( ) انتخاب می­شود در غیر این‌صورت از بردار نسل فعلی انتخاب می­گردد.

گام سه: با استفاده از عملگر جهش جمعیت جواب فرزند را از جمعیت جواب اولیه و جمعیت جواب آزمایشی به صورت زیر تولید کنید:

در عملگر جهش از سه والد ،  و  برای ایجاد فرزند ( ) مطابق رابطه­ی (13) استفاده می‌شود.

در این رابطه    نشان دهنده­ی فاکتور جهش و عددی مثبت است که میزان نرخ تکامل جمعیت را کنترل می­کند. اگر چه برای فاکتور جهش حد بالا وجود ندارد اما اگر این فاکتور بزرگتر از یک انتخاب شود به ندرت موثر واقع خواهد شد.

گام چهار: با استفاده از عملگر انتخاب جواب­های بهتر را برای شرکت در نسل بعد گزینش کرده و سایر جواب­ها را حذف کنید.

در این گام، دو بردار  و  بر اساس توابع هدفشان با یکدیگر مقایسه می­شوند و جواب مناسب­تر مطابق رابطه (14) در نسل بعدی قرار می‏گیرد.

اگر برتری هیچ­یک از دو جواب قابل تایید نبود، یک جواب از ترکیب خطی دو جواب تولید می‏گردد. روش محاسبه برتری جواب  بر    به شرح زیر است:

• فرض کنید:

: مقدار تابع هدف ام به ازای جواب ام
 ( )

: ترجیح جواب  بر جواب  با توجه به تابع هدف ام 

: عدم ترجیح جواب  بر جواب  با توجه به تابع هدف ام

: ماتریس ترجیح جواب  بر جواب  با توجه به کلیه­ی توابع هدف

: اعتبار ترجیح جواب  بر جواب  با توجه به کلیه­ی توابع هدف

:  بزرگ­ترین اعتبار ترجیح جواب  بر جواب  به ازای کلیه­ی جواب­ها

: حد بی تفاوتی، : حد ترجیح و : حد رد

• اگر  است، را برابر با یک قرار دهید؛ اگر است،  را برابر صفر قرار دهید  و در صورتی که   باشد از رابطه­ی (15) برای محاسبه­ی  استفاده کنید.

• اگر  باشد، را برابر با صفر قرار دهید، اگر  باشد، را برابر با یک قرار دهید و در صورتی که:

   باشد از رابطه­ی (16) برای محاسبه­ی  استفاده کنید.

• برای هر زوج جواب  و  مجموع مقدار ترجیح­های را با در نظر گرفتن وزن  برای هر تابع هدف  در ماتریس ترجیح بنویسید. درایه­های ماتریس ترجیح با استفاده از رابطه­ی (17) محاسبه می­شوند.

• اعتبار ترجیح جواب  بر جواب را با استفاده از رابطه (18) ارزیابی کنید.

(18)

و اعتبار ترجیح جواب  بر جواب را با استفاده از رابطه­ی (19) ارزیابی کنید.

(19)

• حد ترجیح  که کمتر ولی نزدیک به  است به گونه­ای در نظر بگیرید که  آنقدر ناچیز باشد که نتوان میان ترجیح­ها تفاوتی قایل شد. سپس یک ماتریس باینری با استفاده از رابطه (20) و (21) تعریف کنید.

شکل 1- نمودار روش پیشنهادی

گام پنج: در صورت برآورده شدن شرط خاتمه الگوریتم پایان یافته است، در غیر این صورت به گام دوم برگردید. شرط خاتمه می­تواند رسیدن به تعداد مشخصی تکرار، رسیدن به حد معینی از جواب، عدم تغییر جواب در چند تکرار و غیره باشد. مراحل این الگوریتم در شکل (1) نمایش داده شده است.

6- مثال عددی

برای بررسی کارآیی مدل ارایه شده از دو  سری داده از ادبیات موضوع (هریس[43]، 1990؛ کولیناس و آنجنستوپلوس 2013) استفاده شده است. سری داده اول شامل 11 فعالیت و یک نوع منبع است. شکل (2) نمودار تقدم و تأخر و زمان­ اجرای این فعالیت‌ها را نشان می­دهد.

کریستودولو^[44] و دیگران، (2010) سری داده اول را بررسی کرده و دو روش بهتر برای تسطیح منابع ارایه نموده­اند. در این پژوهش، با توجه به این‌که روش پیشنهادی قادر به تسطیح چند منبع است، علاوه بر سری  داده­ی اولیه، دو سری داده­ی دیگر نیز ارایه شده­اند (جدول 2).  شکل (3)- الف) نشان دهنده وضعیت مصرف منبع 1 قبل از تسطیح، شکل (3)- ب) وضعیت مصرف سری منبع 1 بعد از تسطیح به روش اول ارایه شده توسط کریستودولو و دیگران، شکل (3)- ج) روش دوم ارایه شده توسط کریستودولو و دیگران و شکل (3)- د) روش پیشنهادی است و به همین صورت، شکل­های (4) و (5) به ترتیب برای منابع (2) و (3) ارایه شده‏اند.مقدار تابع هدف برای منبع 1 در حالت قبل از تسطیح 1161، در حالت تسطیح به روش اول 856، در حالت تسطیح به روش دوم 841 و در حالت تسطیح به روش پیشنهادی 833 است.

مقدار تابع هدف برای منبع 2 در حالت قبل از تسطیح 4594، در حالت تسطیح به روش اول 3504، در حالت تسطیح به روش دوم 3486 و در حالت تسطیح به روش پیشنهادی 3282 است.

مقدار تابع هدف برای منبع 3 در حالت قبل از تسطیح 2620، در حالت تسطیح به روش اول 1990، در حالت تسطیح به روش دوم 1980 و در حالت تسطیح به روش پیشنهادی 1886 است.  

شکل (6) نشان دهنده­ی تسطیح هر سه منبع به صورت هم­زمان، با استفاده از روش پیشنهادی است. مقدار تابع هدف به ازای منبع 1 برابر با 851، به ازای منبع 2 برابر با 3312 و به ازای منبع 3 برابر با 1898 است.

برای بررسی بهتر مدل پیشنهادی و همچنین مقایسه روش ارایه شده با یک الگوریتم فر‏اابتکاری دیگر، از سری داده ارایه شده توسط کولیناس و آنجنستوپلوس (2013) استفاده شده است.

شکل (7)- الف) نشان دهنده­ی وضعیت مصرف منبع قبل از تسطیح، شکل (7)- ب) وضعیت مصرف منبع بعد از تسطیح به روش ارایه شده توسط کولیناس و آنجنستوپلوس و شکل (7)- ج) وضعیت مصرف منبع بعد از تسطیح به روش پیشنهادی را نشان می‌دهد. مقدار تابع هدف در حالت قبل از تسطیح 2386، در حالت تسطیح به روش کولیناس و آنجنستوپلوس 1654 و در حالت تسطیح به روش پیشنهادی 1652 است.

جدول 2- میزان منابع مورد نیاز هر فعالیت

7- بحث

در این پژوهش برای حل مدل ارایه شده از الگوریتم تفاضلی تکاملی استفاده شد. اما قبل از استفاده از الگوریتم‌های تکاملی، تحلیل نظری پارامترهای الگوریتم برای درک نحوه‌ی جستجوی فضای حل بسیار با اهمیت است (ژئوسانگ و دیگران، 2008). عدم تنظیم مناسب پارامترهای الگوریتم می‌تواند باعث ناکارآمدی الگوریتم برای یافتن جواب مناسب شود (یانگ[45]، 2014). با توجه تعداد کم پارامترهای قابل تنظیم در الگوریتم تفاضلی تکاملی، تنظیم پارامترها برای یافتن جواب مناسب چندان مشکل نیست.

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

شکل 3- تسطیح منبع یک سری داده اول

 شکل4- تسطیح منبع دو سری داده اول

 شکل 5- تسطیح منبع سه سری داده اول

این مهم با انتخاب هوشمند و مناسب اندازه­ جمعیت تضمین می­شود. اگر اندازه­ جمعیت کوچک انتخاب شود الگوریتم در زمان کمتری جواب
 زیر ـ بهینه (نزدیک به بهینه) را می­یابد ولی ممکن است جواب یافته شده، زیر ـ بهینه­ محلی باشد. اما اگر اندازه­ جمعیت بزرگ انتخاب شود، الگوریتم، به زمان بیشتری برای جستجو در فضای شدنی و یافتن جواب نیاز دارد. در این حالت امکان یافتن جواب بهینه­ مساله نسبت به حالتی اندازه­ی جمعیت کوچک انتخاب شده، بیشتر است. درنتیجه انتخاب جمعیت جواب باید براساس دو فاکتور زمان و دقت مورد نیاز تعیین گردد. در این پژوهش با توجه به حجم داده‌ها و نوع مدل پیشنهادی، اندازه جمعیت 100 تعیین گردید. با این اندازه جمعیت الگوریتم قادر است در زمان قابل قبولی جواب مناسب را ارایه نماید. زمان حل هر یک از مسایل مورد بررسی در جدول (3) آمده است.

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

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

 پارامتر بعدی فاکتور جهش است. فاکتور جهش عددی مثبت است که میزان نرخ تکامل جمعیت را کنترل می­کند. انتخاب فاکتور جهش بالاتر سبب واگرایی بیشتر الگوریتم می‌شود. اگر چه برای فاکتور جهش حد بالا وجود ندارد اما اگر این فاکتور بزرگتر از یک انتخاب شود به ندرت موثر واقع خواهد شد (ژئوسانگ و دیگران، 2008).

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

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

  با حل مثال عددی از سری داده ارایه شده توسط هریس (1990) می‌بینیم که در حالت تسطیح یک منبع، برای منابع یک، دو و سه به ترتیب 69/3، 36/6 و 23/5 درصد نسبت به روش اول  ارایه شده توسط کریستودولو و دیگران (2010) و 95/0، 85/5 و 75/4 درصد نسبت به روش دوم کریستودولو و دیگران (2010)، در تابع هدف بهبود ایجاد شده است. این امر مبین کارایی روش پیشنهادی در حل مسایل تسطیح دارای یک منبع است. خلاصه نتایج حاصله در جدول (3) نشان داده شده است.