بخشی از مقاله
چکیده
زمانبندی پروژه با محدودیت منابع از جمله مسائل بسیار مشهور در زمینه زمانبندی و کنترل پروژه است که از جمله مسائل NP-Hard می باشد. در این مقاله مساله زمانبندی پروژه با محدودیت منابع - RCPSP - مورد بررسی قرار گرفته است و سپس با یک الگوریتم فراابتکاری قدرتمند جدید به نام الگوریتم رقابت استعماری - 1 - ICA که تاکنون برای حل این سری از مسائل مورد استفاده قرار نگرفته است، حل شده است که نتایج حاکی از عملکرد موفقیت آمیز این الگوریتم فرا ابتکاری بوده است.
مقدمه
تاریخچه مدیریت پروژه در جهان را معمولا به مدیریت پروژههای عظیمی همچون ساخت اهرام مصر ، دیوار چین و یا بنا نهادن تخت جمشید به دستور داریوش مربوط میدانند اما تاریخچه مدیریت پروژه در دنیای جدید به سالهای ابتدایی دهه 1900 میلادی باز میگردد ؛ جایی که هنری گانت با توسعه نمودار میلهای ابداعی خود آغازگر حرکت پرشتاب بعدی طی سالهای دهه 1950 و 1960 میلادی در پروژه های نظامی و هوافضای آمریکا و سپس انگلستان گردید.
هرچند نام پرآوازه هنری گانت به عنوان پدر تکنیکهای برنامهریزی و کنترل پروژه در تاریخ ثبت گردیده است لیکن سالهای دهه 1950 و 1960 به عنوان سالهای آغازین رشد و توسعه مدیریت پروژه در دنیای معاصر شناخته میشود یکی از مسائل مشهور در زمینه کنترل پروژه، زمانبندی پروژه با محدودیت منابع و سایر محدودیتها می باشد. زمانبندی پروژه با در نظر گرفتن محدودیت منابع از جمله مسائل با ادبیات غنی در حوزه مسائل تحقیق در عملیات است. در این مساله اهدافی از قبیل بیشینه کردن نرخ ارزش فعلی و اهداف کیفی و مینیمم کردن هزینه و... در مدلسازی این مساله در نظر گرفته شده است. روشهای بهینه یابی موجود برای حل این مساله با ابعاد پروژه های واقعی کارآیی ندارد.
از این رو استفاده از روشهای ابتکاری و فراابتکاری در حل این مسائل به جا میباشد. روشهای ابتکاری برای حل این مسائل را می توان به دو دسته تقسیم کرد: دسته اول روشهایی هستند که فعالیتها را طبق یک قاعده اولویت دهی مرتب میکنند و سپس در هر مقطع زمانی از بین فعالیتهای باقیمانده با رعایت محدودیتهای پیشنیازی و ظرفیت منابع، فعالیتها را طبق فهرست مرتب شده برای تخصیص منابع در آن مقطع زمانی انتخاب میکنند.
عیب اصلی این روش ها در این است که نمیتوان یک قاعده کلی برای مرتب کردن فعالیت ها ارائه نمود و مطلوبیت جواب حاصل از قواعد اولویت دهی مختلف به شبکه فعالیتهای پروژه بستگی دارد و بدین معنی که چنانچه قاعدهای که برای یک مساله خاص جواب بهینه را به دست دهد لزوما همیشه موفق نخواهد بود. دسته دوم روش های فراابتکاری از یک یا چند جواب اولیه شروع میکند و بر اساس جوابهای موجود در هر روش به بهبود آن جوابها و نزدیک شدن به جواب بهینه اقدام می کند. از جمله این روشها میتوان روشهای جستجوی ممنوع، آنیلینگ شبیه سازی شده ، الگوریتم ژنتیک، الگوریتم مورچگان و ... نام برد.[1]
مساله زمانبندی پروژه با محدودیت منابع
مساله زمانبندی پروژه با منابع محدود در واقع کلیترین مساله زمان بندی است. مسائل زمانبندی کارگاهی ، جریان کارگاهی ، زمان بندی و سایر مسائل زمانبندی همگی زیر مجموعه ای از این مساله به حساب می آیند 2]و.[3 زمانبندی پروژه یکی از وظایف اصلی و فعالیت های اصلی در مدیریت پروژه است. وجود محدودیت منابع و همچنین روابط پیش نیازی بین فعالیتها مساله زمانبندی پروژه را امری دشوار میسازد. در عمل نرم افزارهای خاصی برای فرآیند زمان بندی به کار برده میشود. اساس این نرم افزارها یک مدل رسمی است که اجازه میدهد که پروژه واقعی تنها با یک مجموعه از محدودیتهای زمانبندی و یک تابع هدف توصیف شود.[4]
برای زمانبندی پروژهها به طور کلی از دو حالت استفاده میشود : در روش اول ابتدا برنامه زمانبندی فقط با در نظر گرفتن روابط پیش نیازی تعیین شده - با روش - CPM/PERT ایجاد شده، سپس با وارد کردن منابع، میزان مصرف منابع در دورههای زمانی و نحوه توزیع آنها در طول برنامه بدست میآید. با توجه به این اطلاعات اقدام به تامین منابع یا برون سپاری کارها با هدف تحقق برنامه صورت میگیرد. در صورت وجود محدودیت در سطوح منابع اقدام به تسطیح منابع میگردد. تسطیح منابع ممکن است منجر به طولانی شدن زمان پروژه گردد. در این روش زمانبندی بهینه نیست اما قابل قبول است ولی به علت سهولت محاسباتی این روش بیشتر مورد استفاده قرار میگیرد و نرم افزارهای تجاری، این روش را پوشش میدهند.
در روش دوم زمانبندی، در واقع تعیین برنامه با توجه همزمان به پیش نیازها و سطح منابع صورت میگیرد. در واقع محاسبات شبکه بر ارضاء محدودیتهای منابع اولویت ندارد بلکه به صورت همزمان در نظر گرفته میشوند. در این روش هدف در اغلب اوقات حداقل کردن زمان اتمام پروژه است. تک هدفه بودن از کاستیهای مطالعات انجام گرفته درباره این مدل ها میباشد. مدلهایی که برای تهیه زمانبندی به روش دوم توسعه داده شدهاند در ادبیات بهRCPSP مشهور هستند.
زمان انجام هر فعالیت j با نمایش داده میشود. هر فعالیت فقط یکبار میتواند شروع شود، و فعالیت می تواند قابل انقطاع باشد یا نباشد. به علت نیازهای فنی، یک سری روابط پیش نیازی بین فعالیتها وجود دارد که به این صورت مجموعه ای از روابط به صورت نمایش داده میشود که نشان میدهد که یک فعالیت j امکان شروع شدن ندارد مگر در حالتی که تمامی روابط پیش نیازی و پیش نیازهایش - - i Pj کامل شده باشد. روابط پیش نیازی میتواند با استفاده از شبکههای فعالیت روی گره - AON - نمایش داده شود که این با فرض غیر مدور بودن شبکه نمایش داده میشود. هر فعالیت یک مقدار مشخص از منابع را برای انجام و اجرا نیاز دارد.
منابعی "منابع تجدیدپذیر" نامیده میشوند که تمامی ظرفیت نها در تمامی دورههای زمانی موجود باشد. اگرK منبع تجدیدپذیر در پروژه موجود باشد، این منابع به صورت K 1,..., k نمایش داده میشود. برای هر منبع k در هر دوره سطح دسترسی وجود دارد که در تمامی زمان ها ثابت است که این سطح دسترسی منابع تجدیدپذیر با Rk تعریف میشود. فعالیت j به rjk واحد از منبع k در هر دورهای که آن فعالیت در حال اجراست نیاز دارد. دو فعالیت مجازی J 0 و J J 1 که زمان شروع و پایان پروژه را نشان میدهند نیز در نظر گرفته می شود که زمان انجام این دو فعالیت صفر و بدون نیاز به منبع میباشند.
مدل استاندارد RCPSP به صورت Cmax prec ps نمایش داده میشود که به ترتیب نمایانگر مساله زمانبندی پروژه با روابط پیش نیازی بین فعالیت ها و هدف کمینه کردن زمان اتمام پروژه است. با آنکه مدل RCPSP بیان شده در بالا یک مدل بسیار توانا است. اما نمیتواند تمامی موقعیت ها را در واقعیت و عمل پوشش دهد، بنابراین خیلی از محققین مدل های کلی بسیاری را برای مساله زمان بندی پروژه توسعه دادهاند که غالبا با یک RCPSP استاندارد به عنوان نقطه شروع کار میکند.
