بخشی از مقاله
چکیده
مسئلهی زمانبندی پروژه با محدودیت منابع کلاسیک یک مسئلهی بهینهسازی ترکیبی است که در دستهی مسائل Np-Hard از نظر پیچیدگی محاسباتی قرار دارد. این مسئله در واقع کلیترین مسئلهزمانبندی است که مسائل زمانبندی کار کارگاهی، زمانبندی جریان کارگاهی و سایر مسائل زمانبندی همگی زیرمجموعهای از این مسئله به حساب میآیند. پیچیدگی محاسباتی این مسئله و اهمیت آن در حوزهی مباحث مدیریت پروژه سبب شده است تا محققان همواره با بهکارگیری الگوریتم-های گوناگون، سعی در ارائهی روشی کارا و مؤثر جهت حل این مسئله داشته باشند.
هدف این مقاله ارائهی روشی نوین بر اساس الگوریتم بهینهسازی فاخته و نیز روش مرتبسازی توپولوژیکال برای حل مسئلهی زمانبندی پروژه با محدودیت منابع کلاسیک است. به منظور بررسی عملکرد روش پیشنهادی مثالهای استاندارد و شناختهشده این مسئله، با تعداد فعالیتهای متفاوت توسط روش پیشنهادی حل و نتایج آن مورد تحلیل و بررسی قرار گرفت. نتایج نشاندهندهی این موضوع است که الگوریتم پیشنهادی روشی مناسب برای حل مسئلهی زمانبندی پروژه با محدودیت منابع کلاسیک است.
مقدمه
یکی از وظایف مهم و پر چالش مدیریت پروژه در مراحل طراحی و اجرا، زمانبندی مناسب و کارای فعالیتها با توجه به محدودیت منابع در دست است. مسئلهی زمانبندی پروژه با منابع محدود، یک مسئلهی بهینهسازی ترکیبی است که علیرغم تعریف سادهی آن، مسائل مربوط به آن در کلاس مسائل Np-Hard دستهبندی میشوند. در این مسئله هر پروژه از تعدادی فعالیت تشکیل شده است، به علاوه تعدادی منبع با ظرفیتهای محدود در هر دوره زمانی وجود دارد.
فعالیتها علاوه بر این که نسبت به یکدیگر جهت اجرای دارای اولویت هستند، در استفاده از منابع نیز محدودیت دارند . به طور کلی هدف مسئلهی زمانبندی پروژه با منابع محدود، تخصیص منابع و یا مجموعهای از منابع با ظرفیت محدود به فعالیتها با رعایت روابط پیشنیازی برای نیل به اهدافی مشخص و متنوعی است؛ اما متداولترین آنها حداقل کردن زمان تکمیل پروژه است
توابع هدف گوناگونی که برای مسائل زمانبندی پروژه با منابع محدود1 در نظر گرفته میشود سبب تقسیمبندی این مسائل به چندین شاخه میشود که یکی از آنها مسئلهی زمانبندی پروژه با منابع محدود کلاسیک است. در این مسئله هدف کاهش زمان انجام یک پروژه با یافتن توالی مناسبی از فعالیتهای پروژه است، به نحوی که محدودیتهای تقدم و تأخر شبکهی پروژه و انواع مختلف محدودیتهای منبعی موجود به طور همزمان ارضا شوند
با توجه به اهمیت RCPSP تاکنون محققان بسیاری با به کارگیری روشهای مختلف برای حل این مسئله تلاش کردهاند، اما همواره محققان در پی یافتن روشی کارا جهت حل این مسئله هستند. به نحوی که در یک زمان معقول محاسباتی، جوابی بهتر و کاربردیتری را برای اینگونه مسائل بیابد. پژوهشگران تاکنون الگوریتمهای بسیاری را برای حل این مسئله توسعه دادهاند که در جدول 1 پارهای از این مطالعات نمایش دادهشدهاند. در این مقاله روشی نوین بر اساس الگوریتم بهینهسازی فاخته2 و نیز روش مرتبسازی توپولوژیکال برای حل مسئله زمانبندی پروژه با محدودیت منابع کلاسیک ارائه شده است.
جدول - 1 برخی از الگوریتمهای معرفی شده برای حل RCPSP
بیان مسئله
مسئلهی زمانبندی پروژه با منابع محدود کلاسیک را میتوان به صورت زیر تعریف کرد: فرض کنیم N تعداد فعالیتهای پروژه و J مجموعهی تمام فعالیتها به انضمام فعالیتهای موهومی 0 و n+1 که به ترتیب نشاندهندهی شروع و اتمام پروژه هستند باشد. همچنین K مجموعهی منابع تجدید پذیر مسئله شامل k نوع منبع تجدید پذیر به تعداد Rk واحد است. فعالیتهای مجموعهی J دو نوع محدودیت دارند: محدودیتهای پیشنیازی و محدودیتهای منابع. محدودیتهای پیشنیازی ترتیب اجراشدن فعالیتها را مشخص میکنند.
محدودیتهای منابع نیز مشخصکنندهی ظرفیت محدود منابع مورد نیاز فعالیتها هستند. مجموعهی پیشنیازهای فعالیت j با Pj و زمان انجام آن را با dj نمایش داده میشود. هر فعالیت در حال پردازش نظیر j در طول زمان اجرا به مقدار مشخصی از منبع k نیاز دارد که آن را با rjk نشان میدهیم. برای فعالیتهای ابتدا و انتهای پروژه d0=dn+1=0 و r0k= rn+1k=0 است. زمان شروع هر فعالیت مانند i را با Si و زمان خاتمهی آن را با Fi نمایش میدهیم. مجموعه A - t - فعالیتهای در حال اجرا در زمان t را نشان داده و متغیر T برابر بیشترین زمان اجرای پروژه است. با توجه به فرضیات فوق میتوان مدل ریاضی زیر را برای RCPSP در نظر گرفت
شکل 1 مثالی از فعالیتهای یک پروژه را با 8 فعالیت نشان میدهد که در آن فعالیتهای 0 و 9 به عنوان فعالیتهای موهومی در نظر گرفتهشدهاند. همچنین در این مثال دو منبع تجدید پذیر وجود دارد که از هر کدام 5 واحد در اختیارداریم. اطلاعات مربوط به این مثال نیز در جدول 2 مشاهده میشود.
شکل - 1 مثالی از RCPSP
الگوریتم بهینهسازی فاخته
الگوریتم بهینهسازی فاخته - COA - یک روش جدید جستجوی آگاهانه سراسری است که از زندگی پرندهای موسوم به فاخته الهام گرفتهشده و در سال 2011 توسط رجبیون ارائه شده است - . - Rajabioun, 2011 همانند سایر الگوریتم های تکاملی، COA هم با یک جمعیت اولیه کار خود را شروع میکند؛ جمعیتی که متشکل از فاخته ها است.
