بخشی از مقاله
خلاصه
مساله زمانبندی پروژه با شرایط محدود بودن منابع، در حوزه مسائل تحقیق در عملیات و مدیریت پروژه قرار دارد. با توجه به کاربرد وسیع این مساله و اینکه از لحاظ تابع هدف از نوع NP-HARD می باشد، خود می تواند علتی باشد که محققین را برای بدست آوردن جواب های کارآتر و بکارگیری الگوریتم های مختلف برای حل این مساله ترغیب کند.[1] در این مقاله با استفاده از الگوریتم های ژنتیک و نرم افزار لینگو به حل مدل پرداختیم و در انتها به ارزیابی و مقایسه جواب های مدل در روش ذکر شده خواهیم پرداخت.
1. مقدمه
در این مساله هر پروژه از تعدادی فعالیت تشکیل شده است، بعلاوه تعدادی منبع با ظرفیت های محدود در هر دوره زمانی وجود دارد. فعالیت ها علاوه بر اینکه نسبت به یکدیگر جهت اجرا دارای اولویت هستند، در استفاده از منابع نیز محدودیت دارند. هدف معمولا کمینه کردن زمان اتمام پروژه - Cmax - می باشد به نحوی که محدودیت های تقدمی و محدودیت منابع ارضاء شود. روش های بهینه یابی موجود برای حل این مساله عمدتا شامل تعداد زیادی متغیر و محدودیت می باشد که از کارآیی عملی آنها در حل مسائل با ابعاد واقعی می کاهد.
از این رو استفاده از روش های ابتکاری و فراابتکاری در حل این مسائل کاملا بجا می باشد. به عنوان مثال می توان به تحقیق [3] اشاره کرد که در آن از الگوریتم جستجوی ممنوع با جستجوی همسایگی متغییر برای حل این مسئله کمک گرفته شده است. در مقاله [4] و[5] نیز به ترتیب از الگوریتم آنیلینگ شبیه سازی شده و از الگوریتم جستجوی پراکندگی [2] کمک گرفته شده است. در این مقاله ابتدا به معرفی مدل و پارامترهای آن میپردازیم و سپس توسط الگوریتم ژنتیک و نرم افزار لینگو آن را حل می نماییم.
2. پیشینه
زمانبندی پروژه با در نظرگرفتن محدودیت منابع عبارت است از زمانبندی فعالیت های پروژه با توجه به روابط پیشنیازی و محدودیت منابع. این مساله دارای انواع گوناگونی است و در حالت های مختلفی مورد بررسی قرار گرفته است که می توان به دسته بندی های زیر اشاره کرد:[6]
-1 بر اساس ماهیت فعالیت ها
-2 بر اساس منابع مورد نیاز
-3 بر اساس روابط پیشنیازی
-4 بر اساس نوع تابع هدف
-5 بر اساس تعداد تابع هدف
-6 بر اساس تعداد پروژه ها
مسائل RCPSP مسائل از دسته NP-Hard هستند لذا از دو طریق قابل حل می باشند: -1 روش های دقیق -2 روش های ابتکاری در روش های دقیق در انتهای اجرای الگوریتم جواب بهینه مساله به دست می آید. از جمله این روش ها انواع برنامه ریزی خطی، برنامه ریزی صفر و یک، برنامه ریزی عدد صحیح، برنامه ریزی پویا، برنامه ریزی غیر خطی، روش های شاخه و کران و... می باشد. از آنجا که برای مسائل پیچیده معمولا این نوع الگوریتم ها در زمان معقول جواب بهینه را بدست نمی آورند، برای این گونه از مسائل به الگوریتم های دیگری متوسل می شویم که در زمان کم، جواب قابل قبولی به ما بدهند. این دسته از مسائل را روش های نادقیق یا ابتکاری می گویند که اخیرا توجه بیشتری را به خود جلب نموده اند.[1]
3. پارامترهای مدل
پارامترهای مورد استفاده در مدل در زیر خلاصه شدهاند: :n تعداد فعالیت ها
:G گراف غیر مدور نمایش دهنده پروژه :Mj مدهای اجرایی فعالیت j ام
:tjm زمان انجام فعالیت j ام در مد m ام
:Pj مجموعه فعالیت های پیشنیازی فعالیت j ام :R تعداد منابع تجدیدپذیر
:NR تعداد منابع تجدید ناپذیر
:NRK تعداد واحدهای در دسترس منبع تجدید ناپذیر K ام :RK تعداد واحدهای در دسترس منبع تجدید پذیر k ام
:rjkm تعداد واحدهای مورد نیاز منبع تجدید پذیر k ام برای فعالیت j ام در مد اجرایی m ام :nrjkm تعداد واحدهای مورد نیاز منبع تجدید ناپذیر k ام برای فعالیت j ام در مد اجرایی m ام.
:TT افق زمانبندی پروژه - حداکثر زمانی که پروژه می تواند به انجام برسد. در اینجا Cmax از TT کوچکتر است. - : Cmax حداکثر زمان تکمیل پروژه اگر فعالیت j ام در حالت m ام خود اجرا شده و در دوره t ام تمام شود.
5. متدولوژی
محدودیت - 1 - مقدار تابع هدف که حداقل سازی زمان تکمیل است را نشان میدهد. محدودیت - 2 - تضمین می کند که فعالیت j تنها در یکی از مدهای خود حتما اجرا خواهدشد. محدودیت - 3 - تضمین میکند که روابط پیشنیازی فعالیت ها رعایت میشود. محدودیت - 4 - زمان تکمیل فعالیت ها را محاسبه میکند. محدودیت - 5 - به محاسبه حداکثر زمان تکمیل پروژه میپردازد. محدودیت - 6 - با محاسبه افق برنامه ریزی پروژه مرتبط است. محدودیت - 7 - تضمین میکند که پروژه قبل از افق برنامهریزی پروژه به اتمام میرسد. محدودیت - 8 - برای اعمال محدودیتهای منابع تجدیدپذیرمی باشد.
