اینجانب محسن قاسمی(901519) دانشجوی رشتهی مهندسی فناوری اطلاعات گرایش تجارت الکترونیک دانشکدهی آموزش های الکترونیکی دانشگاه شیراز اظهار میکنم که این پایاننامه حاصل پژوهش خودم بوده و در جاهایی که از منابع دیگران استفاده کردهام، نشانی دقیق و مشخصات کامل آن را نوشتهام. همچنین اظهار میکنم که تحقیق و موضوع پایان‌نامه‌ام تکراری نیست و تعهد مینمایم که بدون مجوز دانشگاه دستاوردهای آن را منتشر ننموده و یا در اختیار غیر قرار ندهم. کلیه حقوق این اثر مطابق با آیین نامه مالکیت فکری و معنوی متعلق به دانشگاه شیراز است.
نام و نام خانوادگی: محسن قاسمی
تاریخ و امضاء: 12/11/92
به نام خدا
استفاده از الگوريتم بهینه سازی مبتنی بر آموزش- یادگیری برای حل مسئله زمانبندي پروژه ها با منابع محدود
به وسیلهی :
محسن قاسمی
پایان نامه
ارائه شده به تحصیلات تکمیلی دانشگاه به عنوان بخشی
از فعالیتهای تحصیلی لازم برای اخذ درجه کارشناسی ارشد
در رشته‌ی:
مهندسی فناوری اطلاعات – تجارت الکترونیک
از دانشگاه شیراز
شیراز
جمهوری اسلامی ایران
ارزیابی شده توسط کمیته پایاننامه با درجه :
دکتر…………………………، استادیار بخش ……………….(رئیس کمیته) ………………………….
دکتر ……………………….، استادیار بخش…………………………………………………………………….
دکتر ……………………….، استادیار بخش ……………………………………………………………………
بهمن ماه 1392
تقدیم به آنان که به من آموختتند و تقدیم به همسرم که با شکیبایی و مهربانی در کنارم بود…
سپاسگزاری
اکنون که این پایان‌نامه به پایان رسیده است بر خود لازم می‌دانم تا از زحمات بی‌دریغ استاد بزرگوارم جناب آقای دکتر رضا اکبری، که از آغاز تا پایان کار با راهنمایی‌های ارزشمند خود زمینه ساز پیشرفت پایان‌نامه شدند و در این راه زحمات فراوانی را بر دوش گرفتند، نهایت سپاس و قدردانی را داشته باشم.
همچنین از استاد بزرگوار، جناب آقای دکتر حمزه که به عنوان استاد مشاور در این پژوهش بنده را همراهی کردند سپاسگزارم.
چکیده
استفاده از الگوريتم بهینه سازی مبتنی بر آموزش- یادگیری برای حل مسئله زمانبندي پروژه ها با منابع محدود
به کوشش:
محسن قاسمی
مسئله زمانبندي پروژه با منابع محدود، در سالهاي اخیر مورد تحقیق بسیاري از محققان در رشتههای مختلف بودهاست. در این مسئله هدف زمانبندي فعالیتهای پروژه با توجه به روابط پیشنیازی و محدودیت منابع در کمترین زمان میباشد. در این مسئله فضای جستجوی بسیار بزرگی جهت دستیابی به جواب بهینه وجود دارد و نیازمند انجام محاسبات طولانی بخصوص برای ابعاد بزرگ مسئله با محدودیتهای زیاد میشود و الگوریتمهای دقیق برای آن موثر نیستند. الگوریتمهاي فراابتکاری بعنوان جایگزین روشهای دقیق برای حل آن، پیشنهاد شدهاست. در این پایان نامه الگوریتم فراابتکاري مبتنی بر آموزش- یادگیری براي حل این مسئله استفاده شدهاست. این الگوریتم مبتنی بر جمعیت است که اخیرا معرفی شده است و فرایند آموزش و یادگیری در کلاس درس را شبیه سازی میکند. همچنین برای جلوگیری از محلی شدن پاسخها از رویکرد نخبهگرایی در این الگوریتم استفاده شدهاست. از ویژگیهای این الگوریتم این است که نیازی به پارامترهای کنترلی اختصاصی الگوریتم، ندارد و فقط پارامترهای کنترلی عمومی مانند اندازه جمعیت و تعداد نسلها را شامل میگردد. الگوریتم داری دو فاز، فاز معلم و فاز فراگیر است. ابتدا تعدادی زمانبندي را بطور تصادفی بر اساس جمعیت اولیه الگوریتم ها تولید میکنیم، سپس فازهای الگوریتم را روی زمانبندیها اعمال میکنیم بطوریکه جمعیت اولیه به طور تکراري بهبود مییابد تا به شرط توقف برسیم. همچنین تاثیر عواملی مانند اندازه جمعیت و اندازه نخبه و تعداد زمانبندیها بر الگوریتم، بررسی شده است. کارایی الگوریتم ارائه شده با دیگر الگوریتمهاي بکار گرفته شده در حل این مسئله، مقایسه شده است و نتایج موثر با قابلیت رقابت بالا با دیگر الگوریتمها حاصل شدهاست.
واژگان کلیدی: مسئله زمانبندي پروژه ها با منابع محدود، روشهای فراابتکاری، الگوريتم بهینه سازی مبتنی بر آموزش- یادگیری.
فهرست مطالب
عنوان صفحه
فصل 1: مقدمه
1-1 مقدمه …………………………………………………………………………………………………… 2
1-2 اهداف پژوهش ……………………………………………………………………………………….. 5
1-3 ساختار پژوهش ………………………………………………………………………………………. 7
فصل 2: مروری بر ادبیات تحقیق و تعریف مسئله
2-1 مقدمه …………………………………………………………………………………………………… 9
2- 2 زمانبندی پروژه ……………………………………………………………………………………… 9
2-3 زمان بندي پروژه با منابع محدود ………………………………………………………….. 11
2-4 معیارهای مدل کردن مسئله زمان بندي پروژه با منابع محدود ………………. 18
2-4-1 ماهيت فعاليتها ………………………………………………………………….. 18
2-4-2 نوع منبع ……………………………………………………………………………………. 19
2-4-3 نوع روابط پيش نيازي ……………………………………………………………….. 20
2-4-4 نوع تابع هدف ………………………………………………………………………. 21
2-4-5 تعداد تابع هدف ……………………………………………………………………………22
2-4-6 تعداد پروژهها ………………………………………………………………………. 22
2-5 مدل پریتسکر ……………………………………………………………………………………….. 24
2-6 مدل کلین …………………………………………………………………………………………….. 25
2-7 مدل آلوارز و تاماریت ……………………………………………………………………………… 26
عنوان صفحه
فصل سوم: الگوریتم بهینهسازی مبتنی بر آموزش یادگیری
3-1 مقدمه ……………………………………………………………………………………………………………….. 29
3-2 الگوریتمهای فراابتکاری …………………………………………………………………………………… 29
3-3 الگوریتم مبتنی بر آموزش- یادگیری ………………………………………………………………. 32
3-3-1 فاز معلم …………………………………………………………………………………………. 34
3-3-2 فاز فراگیر ……………………………………………………………………………………… 35
3-3-3 الگوریتم TLBO نخبه سالارانه ……………………………………………………… 36
فصل چهارم: حل مسئله
4-1 مقدمه ……………………………………………………………………………………………………………….. 41
4-2 سوابق اخیر حل مسئله زمانبندی پروژه با منابع محدود ………………………………… 42
4-3 حل مسئله زمانبندی با الگوریتمهای فراابتکاری سازنده ………………………………. 47
4-3-1 روش تولید زمانبندي سري …………………………………………………………… 50
4-3-2 روش تولید زمانبندي موازي …………………………………………………………. 52
4-3-3 روش زمانبندی پسرو و پیشرو …………………………………………………….. 54
4-4 حل مسأله زمانبندي پروژه با منابع محدود به وسیله الگوریتم فراابتکاری بهبود
دهنده مبتنی بر آموزش- یادگیری ………………………………………………………………. 56
4-4-1 ایجاد جمعیت اولیه ……………………………………………………………………….. 57
4-4-2 زمانبندی اولیه با الگوریتمهای سازنده ………………………………………….. 60
4-4-3 زمانبندی با الگوریتم TLBOنخبهگرایانه ……………………………………… 60
عنوان صفحه
فصل پنجم: نتایج عددی و نتیجه‌گیری
5-1 مقدمه …………………………………………………………………………………………………………………66
5-2 کتابخانه PSPLIB ……………………………………………………………………………………………. 66
5-3 نتایج آزمایش اجرای الگوریتم با پیکربندیهای مختلف …………………………………. 69
5-3-1 تاثیر اندازه جمعیت با تعداد تکرار ثابت ………………………………………….70
5-3-2 تاثیر اندازه جمعیت با تعداد تکرار متغیر ………………………………………. 72
5-3-3 تاثیر اندازه نخبه …………………………………………………………………………….. 73
5-3-4 تاثیر تاثیر روش زمانبدی سریال و موازی بر الگوریتم TLBO …….. 75
5-4 مقایسه نتایج با دیگر الگوریتمهای فراابتکاری در حل مسئله RCPSP …………. 77
5-5 نتیجهگیری …………………………………………………………………………………………………………82
فهرست منابع …………………………………………………………………………………………………………………… 83
فهرست شکل‌ها
عنوان صفحه
شکل2-1: مدت زمان و میزان منبع مورد نیاز فعالیتهای پروژه مثال 2-3-1 …………………… 17
شکل 2-2: گراف متناظر با پروژه مثال 2-3-1 …………………………………………………………………….. 17
شکل 2-3: یک زمانبندی شدنی برای پروژه مثال 2-3-1 …………………………………………………… 18
شکل 2-4: دستهبندیهای مختلف مسئله زمانبندی با محدودیت منابع

دسته بندی : No category

دیدگاهتان را بنویسید