عنوان پایان‌نامه
ارائه یک الگوریتم جدید در حل مسئله : زمانبندی پروژه با محدودیت منابع و رسیدن به جوابهای بهتر
- رشته تحصیلی
- مدیریت پروژه و ساخت
- مقطع تحصیلی
- کارشناسی ارشد
- محل دفاع
- کتابخانه پردیس هنرهای زیبا شماره ثبت: 11193;کتابخانه مرکزی -تالار اطلاع رسانی شماره ثبت: 74368;کتابخانه پردیس هنرهای زیبا شماره ثبت: 11193;کتابخانه مرکزی -تالار اطلاع رسانی شماره ثبت: 74368
- تاریخ دفاع
- ۰۳ اسفند ۱۳۹۴
- دانشجو
- مجلله همتی
- استاد راهنما
- محمود محمدحسین زاده گلابچی
- چکیده
- چکیده در این پژوهش، ابتدا مسئله "زمان بندی پروژه با محدویت منابع" (RCPS) تشریح شده، و کاربردها و انواع این مسئله مورد ارزیابی قرار می گیرند. سپس، مرور ادبیات کاملی برای این مسئله ارائه شده که در آن، روش های کران پائین، دقیق، ابتکاری و فراابتکاری، به همراه منابع معتبر و به روز وجود دارند. در ادامه، توضیحاتی در مورد الگوریتم های تکاملی، روش های جستجوی محلی و الگوریتم ژنتیک داده می شود. از آنجا که مسئله زمان بندی پروژه با محدویت منابع NP-hard است، یک روش ترکیبی شامل الگوریتم ژنتیک و جستجوی محلی برای حل آن پیشنهاد می شود. در الگوریتم ژنتیک پیشنهادی، برنامه جدیدی برای کدگذاری کروموزوم ها معرفی شده و جمعیت ابتدایی به صورت غیرتصادفی تولید می شود. روش انتخاب چرخ رولت برپایه رتبه اصلاح شده و عملگرهای جابجایی دو نقطه ای، جابجایی چند نقطه ای و جهش مورد استفاده قرار می گیرند. در الگوریتم پیشنهادی، یک روش جستجوی محلی ترکیبی، شامل جستجوی محلی برپایه جایگشت و بهبود روبه جلو و روبه عقب بکار گرفته می شوند. در انتها، روش تاگوچی برای تعیین مقدار پارامترهای الگوریتم ژنتیک استفاده می شود. کارایی الگوریتم پیشنهادی توسط حل یک مثال عددی با تابع هدف کمتر از 3 الگوریتم ابتکاری و 6 الگوریتم فراابتکاری به اثبات رسید. در حل 50 مثالJ30 و مقایسه نتایج 35 الگوریتم فراابتکاری، نتایج خوبی برای الگوریتم ژنتیک پیشنهادی بدست آمده است
- Abstract
- Abstract In this research, "resource-constrained project scheduling" (RCPS) problem is first described, and applications and types have been evaluated. Then, a thorough literature review is presented to the problem in which there are methods of lower bounds, exact, heuristics and meta-heuristics, together with valid and updated resources. In the following, explanations are given about evolutionary algorithms, local search methods and genetic algorithm. Since RCPS problem is NP-hard, a hybrid method which combines genetic algorithm and local search is proposed to solve it. In the proposed genetic algorithm, a new scheme is introduced to encode chromosomes and the initial population is generated non-randomly. The rank-based roulette wheel selection mechanism is modified, and the operators of two-point crossover, multipoint crossover and mutation are used. In the proposed algorithm, a hybrid local search method which combines permutationbased local search and forward–backward improvement is applied. In the end, Taguchi method is used to determine the parameters of the genetic algorithm. The efficiency of the proposed algorithm is proved through solving a nemberical example with the objective function less than 3 heuristic algorithms and 6 meta-heuristic algorithms. In solving 50 examples from J30 and comparing results of 35 meta-heuristic algorithms, good results are obtained for the proposed genetic algorithm. Keywords: resource-constrained project scheduling; genetic algorithm; roulette wheel; permutation-based local search; forward–backward improvement.
