عنوان پایان‌نامه
ارایه یک الگوریتم فراابتکاری برای مساله زمانبندی پروزه بامحدودیت منابع در حالت چند مد
- رشته تحصیلی
- مهندسی صنایع
- مقطع تحصیلی
- کارشناسی ارشد
- محل دفاع
- کتابخانه پردیس 2 فنی شماره ثبت: 1877;کتابخانه مرکزی -تالار اطلاع رسانی شماره ثبت: 47252
- تاریخ دفاع
- ۲۷ شهریور ۱۳۸۹
- دانشجو
- محمدحسین صادقی
- استاد راهنما
- رضا توکلی مقدم
- چکیده
- مسأله برنامه ریزی پروژه با محدودیت منابع را می توان زمانبندی مجموعه ای از فعالیت ها {V={0,1,…,n,n+1 در نظر گرفت که باید به انجام برسند. فعالیت های . و 1+n فعالیت های مجازی ابتدا و انتهای پروژه هستند. دو دسته محدودیت کلی برای اجرای فعالیت ها وجود دارد، 1- روابط پیشنیازی که اجبار می کنند که هیچ فعالیتی قبل از اتمام تمام پیش نیاز هایش شروع نشود 2- مقدار در دسترس از هر یک منابع مورد نیاز فعالیت ها محدود می باشد. در مسأله برنامه ریزی پروژه با محدودیت منابع تک مد (RCPSP) فرض بر این است که هر یک از فعالیت ها دارای زمان اجرای مشخص و مصرف منابع معلوم بوده و تنها به یک روش قابل انجام هستند. یک روش اجرایی با یک طول زمانی و میزان مصرف منابع برای فعالیت مشخص می گردد. موارد عملی بسیاری وجود دارد که در آنها می توان با فراهم نمودن منابع بیشتر زمان فعالیت را کاهش داد. در این شرایط هر فعالیت می تواند به یکی از روش های اجرایی ممکن انجام شود. هر روش اجرایی یا مد ترکیبی از زمان اجرا و مصرف منابع می باشد. در این حالت مسأله حاصل مسأله زمانبندی پروژه با محدودیت منابع چند مد (MRCPSP) نامیده می شود. در این پایان نامه مسأله زمانبندی پروژه با محدودیت منابع چند مد، برای حل به دو زیر مسأله تقسیم شده است: تخصیص مدهای اجرایی به فعالیتها و سپس زمانبندی فعالیتها به منظور کمینه نمودن زمان اتمام پروژه. روش فراابتکاری الکترومگنتیزم با مسأله اول در ارتباط بوده و مد لیست اجرایی فعالیتها را تولید می کند. پس از تعیین مد اجرایی هر فعالیت زمان و مصرف منابع فعالیت بر اساس مد انتخاب شده برای آن تعیین و یک برنامه زمانبندی تصادفی به روش سری برای آن ایجاد می گردد. سپس یک روش جستجوی محلی نسبت به بهبود برنامه اقدام می کند. ضمناً در این پایان نامه یک تابع جریمه جدید برای مد لیست های نشدنی از نظر منابع تجدید ناپذیر پیشنهاد شده است. عملکرد روش حل پیشنهادی با بهترین روش های حل پیشنهاد شده تا کنون برای این مسأله بر اساس معیارهای توقف زمان حل و تعداد برنامه های زمانبندی تولید شده مقایسه گردیده است که نتایج گزارش شده از عملکرد عالی این روش حکایت دارد.
- Abstract
- A resource constrained project scheduling problem (RCPSP) can be stated as follows. A single project consists of a set V={0,1,…,n,n+1} of activities which have to be processed. Dummy activities 0 and n+1 correspond to the "project start" and to the "project end" respectively. The activities are interrelated with two kinds of constraints. First, precedence constraints force each activity not to be started before all its immediate predecessors have been finished. Second, performing the activities requires resources with limited capacities. ،he classical RCPSP assumes that each activity can only be executed in a single way which is determined by a fixed duration and fixed resource requests. But there are many practical situations in which the duration of an activity can be decreased at the expense of providing additional resources. In such a situation, an activity may be executed in one of several modes. A mode represents alternative ways of execution of an activity, and is a combination of the activity duration and its resource requests. In such a case, the resulting problem is called the multi-mode resource-constrained project scheduling problem We consider the MRCPSP as two different sub-problems: the assignment of modes to tasks and then the scheduling of these tasks in order to minimize the makespan of the project. The modified Electromagnetism-Like algorithm will deal with the first problem to create an assignment of modes to activities. This list is used to generate a project schedule. When a new assignment is made, it is necessary to fix all mode dependent requirements of the project activities and generate a random schedule with the serial SGS method. A local search will optimize the sequence of the activities. A new penalty function is proposed for solutions which are infeasible with respect to non-renewable resources. We compared performance of our algorithm and that of the best algorithms published so far on the basis of CPU time and number of generated schedules stopping criteria. Reported results show excellent performance of our algorithm.
