بخشی از مقاله
چکیده
یکی از موضوعات جدید در زمینه مساله زمانبندی پروژه، استفاده از منابع تجدیدناپذیر است. در همین راستا، یک مساله زمانبندی پروژه با در نظر گرفتن منابع تجدیدناپذیر با هدف کمینهسازی زمان اتمام پروژه ارایه میشود. بطوریکه منابع در طول افق برنامهریزی تامین میشوند. در ادامه، یک الگوریتم فراابتکاری جستجوی انتشاری در محیط برنامهنویسی C# به عنوان روش حل مسالهی پیشنهادی توسعه داده شده است. از اطلاعات مربوط به مرجع دادههای زمانبندی - PSPLIB - 1 استفاده شده است. آزمایشهای عددی کارایی این الگوریتم را از نظر زمان حل و کیفیت جواب برای حل مساله در مقیاس بزرگ نشان میدهد.
-1 مقدمه
در سالهای اخیر، زمانبندی پروژه توجه بسیاری از محققان را به خود جلب نموده است. مساله زمانبندی پروژه با محدودیت منابع - RCPSP - 1 دارای تاریخچه بسیار قوی در مدیریت پروژه میباشد و شامل فعالیتهای است که باید با حداقل اولویت و محدودیت منابع برنامهریزی شود. منابع تجدیدپذیر و تجدید ناپذیر از پرکاربردترین انواع منابع مورد مطالعه در این حوزه میباشند. در برنامهریزی پروژه، اغلب فرض میشود که کل منابع تجدیدناپذیر در ابتدای پروژه در دسترس هستند حال آنکه در بسیاری از مواقع، این منابع در طول افق پروژه تهیه میشوند. این موضوع در مواردی که هزینه نگهداری یا سفارش منابع تجدید ناپذیر بالا باشد بیشتر نمود پیدا می کند. در مدل پیشنهادی این مقاله، این نوع منابع در نظر گرفته شده اند. مساله مورد بررسی این مقاله، این نوع از منابع را به صورت توام در مساله RCPSP در نظر گرفته است.
مساله مورد بررسی این مطالعه در کلاس مسائل با درجه پیچیدگی NP-Hard است، بنابراین استفاده از روشهای فراابتکاری می تواند کمک کننده باشد. از این رو، برای حل مساله پیشنهادی از الگوریتمهای فراابتکاری جستجوی انتشاری استفاده شده است. در ادامه در بخش بعدی به پیشینه تحقیق مسائله زمانبندی پروژه با منابع محدود پرداخته می شود. در بخش 3 به بیان مدلسازی مساله می پردازیم. در بخش 4 نتایج عددی آورده شده است. در انتها نیز نتیجه گیری و پیشنهادها برای مطالعات آتی آمده است.
-2 ادبیات موضوع
در مرحله طراحی پروژهها، یکی از وظایف مهم مدیریت پروژه، زمانبندی مناسب فعالیتها با توجه به محدودیت منابع است. در همین راستا، در این بخش به مرور مطالعات پیشین برای معرفی مساله RCPSP و انواع رویکردهای حل این دسته مسائل می پردازیم.
1؛-2 مساله زمانبندی پروژه با محدودیت منابع
به طور کلی برنامههای زمانبندی به دو دسته کلی تقسیم میشوند: . 1 برنامه زمانبندی که با در نظر گرفتن روابط پیش نیاز انجام شود و سپس منابع مصرفی در طول برنامه تامین می شوند. .2 برنامه زمانبندی که از همان ابتدا با روابط پیش نیاز فعالیتها و منابع مصرفی محاسبه میشود و مساله زمانبندی پروژه با منابع محدود نامیده می شود. بطوریکه در این حالت هدف کمینه سازی زمان اتمام پروژه است. مساله RCPSP به یک مساله استاندارد در زمینه برنامه ریزی تبدیل شده که بطور گسترده مورد توجه محققان قرار گرفته است. ادبیات موضوع مساله استاندارد RCPSP با منابع تجدیدپذیر به سال 1960 باز میگردد.
بطوریکه الگوریتمهای مختلفی همچون کمینه و بیشینه وقفه زمان، اهداف چندگانه و پروژههای غیر متمرکز چندگانه برای این مساله توسعه داده شده است است - برای مطالعه بیشتر: کولیش و پادمن [1]، کولیش و هارتمن [ 2]، هارتمن و بریسکون .[3] مساله زمانبندی پروژه با منابع محدود در واقع کلیترین مساله زمانبندی است .[4] این مساله تنها از منبع تجدیدپذیر استفاده می کند زیرا در هر دوره محدودیتی برای ظرفیت این نوع منبع وجود دارد.
2؛-2 دسته بندی منابع برای مساله RCPSP
در مسائل زمانبندی پروژه با محدودیت منابع چند حالته از سه نوع منبع از جمله منابع تجدیدپذیر، منابع تجدید ناپذیر و منابع دوگانه استفاده میشود .[ 5] منابع تجدیدپذیر از جمله نیروی انسانی و ماشین آلات هستند. در مقابل منابع تجدیدناپذیر مانند بودجه پروژه دارای ظرفیت محدود برای پروژه اند. همانطور که منابع تجدیدپذیر یک بخش اصلی از RCPSP تک حالته است منابع تجدید ناپذیر هم یک بخش اصلی از مدل RCPSP چند حالته است. منابع دوگانه ترکیبی از منابع ذکر شده در هر دوره پروژه هستند. بنابراین یک منبع دوگانه از بهم پیوستن یک منبع تجدیدپذیر و یک منبع تجدید ناپذیر حاصل میشود.
رنجبر و کیانفر [6] و رنجبر و همکاران [7] مسائل مدیریت پروژه با منابع تجدیدپذیر چند حالته با رویکرد تبادل را در نظر گرفتند. ژئو و همکاران[ 8] 2 منابع تجدیدپذیر را در مدل RCPSP چندحالته به کار گرفتند. نئومن و اسچویدنت [ 9] 3 منابع تجمعی4 را با ترکیب حداقل تاخیرها و حداکثر تاخیرها در داخل RCPSP معرفی شد. بارتلز و زیمرمن[ 10] 5 منابع تجمعی را با مدل RCPSP چند حالته و با حداقل و حداکثر تاخیرها استفاده کرده اند.
ظرفیت منابع تجدیدپذیر مانند ظرفیت تجهیزات مختلف در طول زمان متغیر است. در همین راستا، بمسدرف و دریگز[11] 6، کلین[12] 7 ، کلین و اسکول[13] 8 ، نانوب و ایبراکی[14] 9، اسچویدنت و تراتمن[15] 10 به بررسی این دسته مسائل پرداختند. همچنین اکان و همکاران[16] 11 مدلی با هدف مبتنی بر منابع تجدید ناپذیر12 معرفی کردند، بطوریکه در مساله تبادل زمان- هزینه گسسته13 معرفی شده آنها تنها منبع تجدید ناپذیر، پول است.
3؛-2 رویکردهای حل مساله RCPSP
بلازویچ و همکاران[17] 14 نشان دادند که مسائل RCPSP جز مسائل NP-hard قوی میباشد. از این رو استفاده از رویکردهای حل فراابتکاری بیشتر مورد توجه محققان قرار گرفته است. در همین راستا، ذگردی و همکاران [18] یک الگوریتم ژنتیک برای مساله زمانبندی پروژه با درنظرگرفتن محدودیت منابع تجدیدپذیر و تجدید ناپذیر ارایه دادند. بطوریکه با استفاده از روش بهبود هوشمند به جستجوی همسایگی می پردازد. باقری نژاد و همکاران [19] از یک الگوریتم فراابتکاری برای حل مساله زمانبندی پروژه با محدودیت منابع چندحالته استفاده کردند.
امیری و همکاران [20] مساله زمانبندی پروژه با محدودیت منابع دوگان را در حالت چند وضعیتی با استفاده از یک روش فراابتکاری حل کردند. شاه محمدی و همکاران [21] حل مسألهی زمانبندی پروژه با منابع محدود را با استفاده از ترکیب الگوریتم فراابتکاری مورچگان و روش ابتکاری ابداعی حذف و اضافه مورد بررسی قرار دادند. همچنین، حمزه نیا و همکاران [22] یک الگوریتم فراابتکاری تبرید برای حل مساله زمانبندی پروژه با محدودیت بودجه با وجود فعالیتهای چند حالته و منابع تجدیدپذیر و تجدید ناپذیر ارایه دادند. همچنین از الگوریتم-های ژنتیک و ژنتیک چندهدفه نیز برای مقایسه جوابها استفاده شد.
شادرخ [23] مساله زمانبندی را با مساله سرمایه گذاری منابع در پروژه مورد مطالعه قرار داد و از الگوریتم ژنتیک به عنوان روش حل مساله استفاده کرد. مهدی زاده و همکاران [24] مساله زمانبندی پروژه با منابع محدود را با هدف بیشینه سازی ارزش برنامه ریزی شده، تامین می گردند. مدل مساله ی پیشنهادی با اضافه کردن منابع تجدید ناپذیر همراه با تدارکات از پیش تعیین شده، به مساله ی کلاسیک RCPSP، توسعه داده شده است. در ادامه مساله مورد بررسی با در نظر گرفتن برخی مفروضات مدل سازی شده است که این مفروضات به شرح زیر میباشد:
-1 وجود وقفه در هنگام اجرای فعالیتها مجاز نیست.
-2 همه فعالیتها تک حالته هستند بطوریکه در ابتدای افق برنامه ریزی پروژه مشخص هستند.
-3 زمانبندی یک پروژه با n-2 فعالیت غیرموهومی17 در نظر گرفته میشود.
-4 مدت زمان اجرا و منبع مورد نیاز برای فعالیتهای موهومی متناظر با گرهها برابر صفر است.
-5 دیرترین و زودترین زمان شروع فعالیتها به روش مسیر بحرانی - رفت و برگشت - محاسبه میشود.
پیش از ارایه مدل، تعریف نشانههای بکار رفته در مدل بیان می شود. خالص فعلی مطرح نمودند بطوریکه پارامترهای زمانی فعالیتها به صورت اعداد فازی در نظر گرفته شدند. برای حل مدل از الگوریتم بهینه سازی میرایی ارتعاش15 استفاده شد. کیا و نیکدل [25] روش ابتکاری بهبود یافته مبتنی بر اولویت را برای مساله زمانبندی پروژه محدود با پارامترهای فازی ارایه دادند. گلاب و نجفی [26] مساله زمانبندی پروژه بر پایه حجم کار با منبع محدود برای کمینه کردن هزینههای زودکرد و دیرکرد را ارایه دادند. برای حل این مساله دو الگوریتم فراابتکاری ژنتیک و شبیه سازی تبرید طراحی شد.
-3 تعریف مساله
بسیاری از مسائل واقعی با محدودیت منابع تجدید ناپذیر مواجه هستند که این نوع منابع اغلب در مطالعات پیشین در نظر گرفته نشده اند. این تفاوت ناشی از عدم تامین منابع تجدیدناپذیر در ابتدای پروژه بوده، بطوریکه اغلب بتدریج در طول زمانبندی پروژه تامین میشوند. از این رو در این مقاله مساله زمانبندی پروژه با در نظر گرفتن این دسته از منابع مورد بررسی قرار گرفته است.
