بهینه‌سازی زمانبندی پروژه با محدودیت منابع با استفاده از الگوریتم ژنتیک

نوع مقاله : مقاله پژوهشی

نویسندگان

1 گروه عمران، واحد تبریز، دانشگاه آزاد اسلامی، تبریز، ایران

2 گروه مهندسی عمران، دانشگاه آزاد اسلامی، واحد تبریز، ایران

چکیده

مسئله زمان‌بندی پروژه با محدودیت منابع (RCPSP)، جز مسائل غیر چند جمله‌ای سخت (NP-Hard) است که برای حل آن، روش‌های ابتکاری و فرا ابتکاری در مقایسه با راه‌حل‌های دقیق، کارایی بیشتری دارند. در این مسئله هر پروژه از تعدادی فعالیت و تعدادی منبع با ظرفیت‌های محدود تعریف می‌شود. فعالیت‌ها علاوه بر اینکه نسبت به یکدیگر جهت اجرا دارای اولویت هستند، هر کدام می‌توانند به صورت گسسته و یا با همپوشانی زمانی اجرا شوند.
در این تحقیق از روش فراابتکاری الگوریتم ژنتیک برای حل مساله زمان‌بندی پروژه با محدودیت منابع در حالت تک حالته و از نظر نوع روابط تقدمی، پایان به آغاز، استفاده شده است. هدف اصلی،کاهش زمان انجام کار به حداقل زمان ممکن می باشد.
الگوریتم ارائه شده بر روی مجموعة مسائل استاندارد کتابخانه PSPLIB مورد آزمایش قرار گرفته است. الگوریتم پیشنهادی برای زمان‌بندی یک پروژة واقعی البته با تطبیق شرایط پروژه واقعی با شرایط مسئله استفاده گردید. پروژة مورد نظر شامل 29 فعالیت و روابط پیش‌نیازی از نوع پایان به آغاز ( (FSو با چهار نوع منبع تجدیدپذیر و محدود می‌باشد. زمان کمینه حاصله از الگوریتم پیشنهادی 245 روز که تقریباً برابر با زمان حاصله از نرم‌افزار مایکروسافت (5/244) می‌باشد، البته مزیت نسبی الگوریتم پیشنهادی، حصول به نتیجه در مدت زمان بسیار کوتاه می‌باشد که برای پروژه بزرگ با تعداد فعالیت‌های زیاد، کاملاً توصیه می‌گردد.

کلیدواژه‌ها


عنوان مقاله [English]

Resource-Constrained Project Scheduling Optimization by Genetic Algorithm

نویسندگان [English]

  • Sina Fard Moradi Nia 1
  • Alireza Khademi 2
1 Department of civil Engineering, Tabriz Branch, Islamic Azad University, Tabriz, Iran
2 Department of civil Engineering, Tabriz Branch, Islamic Azad University, Tabriz, Iran
چکیده [English]

The Resource-Constrained Project Scheduling Problem (RCPSP) is NP-hard problem that ingenious and metaheuristic solutions in comparison to the absolute solutions have better results. In 'RCPSP' every project has unique numbers of activities and resources. Activities have priority in relation with each other to be executed, but can be done discreetly or overlapped with each other.
In this research one metaheuristic solution, Genetic Algorithm, is proposed for solving Resource-Constrained Project Scheduling Problem (RCPSP) in single-mode and the priority rule is not general. Only Finish to Start relations are considered. The main goal is to minimize make span of the project.
The proposed algorithm is tested by the existing data available at PSPLIB . Furthermore, one real project with 29 activities is solved by recommended algorithm. The proposed algorithm for scheduling a real project was, of course, adapted to the conditions of the actual project. The project involves 29 types of end-to-start (FS) activities and relationships with four types of renewable and limited resources. The minimum time of the proposed algorithm is 245 days, which is roughly equivalent to the time taken by Microsoft's software (244.5). However, the relative advantage of the proposed algorithm is to achieve the result in a very short time, which is highly recommended for a large project with a large number of activities.

کلیدواژه‌ها [English]

  • Resource-Constrained Project Scheduling Problem(RCPSP)
  • Genetic Algorithm
  • Make span minimizing
  • MATLAB software