پایان نامه : استفاده از الگوریتم بهینه سازی مبتنی بر آموزش- یادگیری برای حل مسئله زمانبندی پروژه ها با منابع محدود

دانلود متن کامل پایان نامه مقطع کارشناسی ارشد رشته مهندسی فناوری اطلاعات

گرایش : تجارت الکترونیک

عنوان : استفاده از الگوریتم بهینه سازی مبتنی بر آموزش- یادگیری  برای حل مسئله زمانبندی پروژه ها با منابع محدود  

دانشگاه شیراز

دانشکده آموزش­های الکترونیکی

 

پایان‌نامه کارشناسی ارشد در رشته مهندسی فناوری اطلاعات

(تجارت الکترونیک)

استفاده از الگوریتم بهینه سازی مبتنی بر آموزش- یادگیری  برای حل مسئله زمانبندی پروژه ها با منابع محدود  

استاد راهنما:

دکتر رضا اکبری

 

 

12/11/92

برای رعایت حریم خصوصی نام نگارنده پایان نامه درج نمی شود(در فایل دانلودی نام نویسنده موجود است)تکه هایی از متن پایان نامه به عنوان نمونه :(ممکن است هنگام انتقال از فایل اصلی به داخل سایت بعضی متون به هم بریزد یا بعضی نمادها و اشکال درج نشود ولی در فایل دانلودی همه چیز مرتب و کامل است)چکیدهمسئله زمانبندی پروژه با منابع محدود، در سال­های اخیر مورد تحقیق بسیاری از محققان در رشته­های مختلف بوده­است. در این مسئله هدف زمانبندی فعالیت­های پروژه با توجه به روابط پیشنیازی و محدودیت منابع در کمترین زمان می­باشد. در این مسئله فضای جستجوی بسیار بزرگی جهت دست­یابی به جواب بهینه وجود دارد و نیازمند انجام محاسبات طولانی بخصوص برای ابعاد بزرگ مسئله با محدودیت­های زیاد می­­شود و الگوریتم­های دقیق برای آن موثر نیستند. الگوریتم­های فراابتکاری بعنوان جایگزین روش­های دقیق برای حل آن، پیشنهاد شده­است. در این پایان نامه الگوریتم فراابتکاری مبتنی بر آموزش- یادگیری برای حل این مسئله استفاده شده­است. این الگوریتم مبتنی بر جمعیت است که اخیرا معرفی شده است و فرایند آموزش و یادگیری در کلاس درس را شبیه سازی می­کند. همچنین برای جلوگیری از محلی شدن پاسخ­ها از رویکرد نخبه­گرایی در این الگوریتم استفاده شده­است. از ویژگی­های این الگوریتم این است که نیازی به پارامترهای کنترلی اختصاصی الگوریتم، ندارد و فقط پارامترهای کنترلی عمومی مانند اندازه جمعیت  و تعداد نسلها  را شامل می­گردد. الگوریتم داری دو فاز، فاز معلم و فاز فراگیر است. ابتدا تعدادی زمانبندی را بطور تصادفی بر اساس جمعیت اولیه الگوریتم ها تولید می­کنیم، سپس فازهای الگوریتم را روی زمانبندی­ها اعمال می­کنیم بطوریکه جمعیت اولیه به طور تکراری بهبود می­یابد تا به شرط توقف برسیم. همچنین تاثیر عواملی مانند اندازه جمعیت و اندازه نخبه و تعداد زمانبندی­ها بر الگوریتم، بررسی شده است. کارایی الگوریتم ارائه شده با دیگر الگوریتم­های بکار گرفته شده در حل  این مسئله، مقایسه شده است و نتایج موثر با قابلیت رقابت بالا با دیگر الگوریتم­ها حاصل شده­است.واژگان کلیدی: مسئله زمانبندی پروژه ها با منابع محدود، روشهای فراابتکاری، الگوریتم بهینه سازی مبتنی بر آموزش- یادگیری.فهرست مطالبعنوان                                                                                 صفحهفصل 1: مقدمه1-1 مقدمه  .................................................................................................................. 21-2 اهداف پژوهش ..................................................................................................... 51-3 ساختار پژوهش .................................................................................................... 7 فصل 2: مروری بر ادبیات تحقیق و تعریف مسئله 2-1 مقدمه .................................................................................................................. 92- 2 زمانبندی پروژه ................................................................................................... 92-3  زمان بندی پروژه با منابع محدود .................................................................... 112-4 معیارهای مدل کردن مسئله زمان بندی پروژه با منابع محدود ...................  182-4-1 ماهیت فعالیت­ها ............................................................................. 182-4-2  نوع منبع ................................................................................................. 192-4-3 نوع روابط پیش نیازی .......................................................................... 202-4-4 نوع تابع هدف .................................................................................. 212-4-5 تعداد تابع هدف .......................................................................................222-4-6 تعداد پروژه­ها .................................................................................. 222-5 مدل پریتسکر ..................................................................................................... 242-6 مدل کلین ........................................................................................................... 25            2-7 مدل آلوارز و تاماریت .......................................................................................... 26عنوان                                                                                 صفحهفصل سوم: الگوریتم بهینه­سازی مبتنی بر آموزش­ یادگیری            3-1 مقدمه ................................................................................................................................ 293-2 الگوریتم­های فراابتکاری ................................................................................................ 293-3 الگوریتم مبتنی بر آموزش- یادگیری ......................................................................... 323-3-1 فاز معلم ....................................................................................................... 343-3-2  فاز فراگیر ................................................................................................... 353-3-3 الگوریتم TLBO نخبه سالارانه ............................................................... 36فصل چهارم: حل مسئله4-1 مقدمه ................................................................................................................................ 414-2 سوابق اخیر حل مسئله زمانبندی پروژه با منابع محدود ....................................... 424-3  حل مسئله زمانبندی با الگوریتم­های فراابتکاری سازنده ..................................... 474-3-1 روش تولید زمانبندی سری ..................................................................... 504-3-2 روش تولید زمانبندی موازی ................................................................... 524-3-3 روش زمانبندی پسرو  و پیشرو .............................................................. 544-4 حل مسأله زمانبندی پروژه با منابع محدود به وسیله الگوریتم فراابتکاری بهبوددهنده مبتنی بر آموزش- یادگیری ......................................................................... 564-4-1 ایجاد جمعیت اولیه ................................................................................... 574-4-2 زمانبندی اولیه با الگوریتم­های سازنده .................................................. 604-4-3 زمانبندی با الگوریتم TLBOنخبه­گرایانه ............................................. 60عنوان                                                                                 صفحهفصل پنجم: نتایج عددی و نتیجه‌گیری5-1 مقدمه .................................................................................................................................665-2 کتابخانه PSPLIB .......................................................................................................... 665-3 نتایج آزمایش اجرای الگوریتم با پیکربندی­های مختلف ........................................ 695-3-1 تاثیر اندازه جمعیت با تعداد تکرار ثابت .................................................705-3-2 تاثیر اندازه جمعیت با تعداد تکرار متغیر .............................................. 725-3-3 تاثیر اندازه نخبه ......................................................................................... 735-3-4 تاثیر تاثیر روش زمانبدی سریال و موازی بر الگوریتم TLBO ........ 755-4 مقایسه نتایج با دیگر الگوریتم­های فراابتکاری در حل مسئله RCPSP ............. 775-5 نتیجه­گیری ........................................................................................................................82 فهرست منابع .................................................................................................................................... 83                                      فهرست شکل‌هاعنوان                                                                                  صفحهشکل2-1: مدت زمان و میزان منبع مورد نیاز فعالیت­های پروژه مثال 2-3-1 ........................ 17شکل 2-2: گراف متناظر با پروژه مثال 2-3-1 ................................................................................ 17شکل 2-3: یک زمانبندی شدنی برای پروژه مثال 2-3-1 ............................................................ 18شکل 2-4: دسته­بندی­های مختلف مسئله زمانبندی با محدودیت منابع ................................... 23شکل 3-1: فلوچارت TLBO ................................................................................................................ 38شکل 3-2: فلوچارت  Elitist TLBO  ............................................................................................... 39شکل 4-1: شبکه فعالیت­های متناظر با مثال 4-1 ......................................................................... 48شکل 4-2: شبکه فعالیت­های متناظر با مثال 4-2 ......................................................................... 50شکل 4-3: زمانبندی شدنی برای مثال 4-2 با روش زمانبندی سری ........................................ 51شکل 4-4: زمانبندی شدنی برای مثال 4-2 با روش زمانبندی سری ........................................ 52شکل 4-5: زمانبندی شدنی برای مثال 4-3 با روش زمانبندی موازی ....................................... 53شکل 4-6: نتیجه زمانبندی سری پسرو برای مثال4-4 ................................................................. 55شکل 4-7: نتیجه زمانبندی سری پیشرو برای مثال4-4 ............................................................... 55شکل 4-8: نتیجه زمانبندی موازی پسرو برای مثال4-4 ............................................................... 56شکل 4-9: نتیجه زمانبندی موازی پیشرو برای مثال4-4 ............................................................. 56شکل4- 10: گراف فعالیت یک پروژه ................................................................................................. 58شکل 4-11: مراحل تولید یک لیست فعالیت شدنی ....................................................................... 59شکل 4-12: سه لیست فعالیت شدنی برای گراف شکل 4-10 .................................................... 59شکل 4-13: بهبود زمان تکمیل فعالیت­ها با اجرای ETLBO ...................................................... 63شکل 4-14:  فلوچارت حل مسئله  RCPSPبا الگوریتم ETLBO .............................................. 64شکل 5-1: تاثیر اندازه جمعیت بر کارایی الگوریتم TLBO با تعداد تکرار 100 ...................... 71شکل 5-2: تاثیر اندازه جمعیت بر کارایی الگوریتم TLBO با تعداد تکرار 1000 .................... 72شکل 5-3: تاثیر اندازه نخبه  بر نرخ همگرایی در مسائل  J30...................................................... 74عنوان                                                                                  صفحه شکل 5-4: تاثیر اندازه نخبه  بر نرخ همگرایی در مسائل J60 ...................................................... 74شکل 5-5: تاثیر اندازه نخبه  بر نرخ همگرایی در مسائل  J90...................................................... 75شکل 5-6: تاثیر اندازه نخبه  بر نرخ همگرایی در مسائل  J120................................................... 75فهرست جدول‌هاعنوان                                                                                 صفحه جدول 4-1: سیرتکاملی حل مسئله زمانبندی پروژه با منابع محدود .................................... 42جدول 5-1: مقادیر پارامترهای مسائل نمونه در کتابخانه PSPLIB ....................................  68جدول 5-2: تاثیر اندازه جمعیت بر کارایی الگوریتم TLBO با تعداد تکرار 100 .............. 70جدول 5-3: تاثیر اندازه جمعیت بر کارایی الگوریتم TLBO با تعداد تکرار 1000 .............71جدول 5-4: تاثیر تعداد جمعیت و تعداد تکرار را بر کارایی الگوریتم TLBO ..................... 73جدول 5-5: تاثیر اندازه نخبه بر نرخ موفقیت الگوریتم TLBO ...............................................73جدول 5-6: تاثیر اندازه نخبه بر درصد انحراف میانگین الگوریتم  TLBO ......................... 74جدول 5-7: تاثیر روش زمانبندی بر الگوریتم TLBO برای مسائل J30 .............................. 76جدول 5-8: تاثیر روش زمانبندی بر الگوریتم TLBO برای مسائل J60 .............................. 76جدول 5-9: تاثیر روش زمانبندی بر الگوریتم TLBO برای مسائل J90 .............................. 76جدول 5-10: تاثیر روش زمانبندی بر الگوریتم TLBO برای مسائل J120 ........................ 76جدول 5-11: تاثیر روش زمانبندی بر الگوریتم TLBO .......................................................... 77جدول 5-12: مقایسه الگوریتم­ها برای مسائل J30 ................................................................... 79جدول 5-13: مقایسه الگوریتم­ها برای مسائل J60 ................................................................... 80جدول 5-14: مقایسه الگوریتم­ها برای مسائل J120 ................................................................. 81مقدمهامروزه، جهانی شدن تجارت، تغییرات سریع تکنولوژیک، بازارهای شدید رقابتی و رایزنی فشرده و قدرتمندانه شرکتها سازمانها و بنگاههای اقتصادی را وادار به تغییر سیستم مدیریتی خود می­نماید، برای تطبیق و سازگاری با این تغییرات، مدیریت پروژه و پروژه محوری در مدیریت از اهمیت بالایی برای سازمانها برخوردار است. تولید کنندگان در بازار رقابتی امروز باید هزینه های تولید را تا حد امکان کاهش دهند تا بتوانند کالاهای خود را با قیمتی مناسب و قابل رقابت با دیگر رقبا به بازارها عرضه کنند. بنگاههای اقتصادی چاره­ای جز بالا بردن بهره­وری و انجام کارهای بیشتر و بهتر با صرف منابع و زمان کمتر ندارند. از همین جاست که مفاهیمی همچون پروژه، کنترل پروژه، زمانبندی پروژه و ... مطرح شده­اند.دنیای ارتباطی امروز به کمک فناوری اطلاعات و اینترنت امکان مشارکت بیشتر بنگاههای اقتصادی را فراهم آورده است و این خود امکان تعریف پروژه هایی بزرگتر را تسهیل کرده­است. تاخیر در ساخت یا توزیع، گاهی به از دست رفتن یک بازار می­انجامد و از این روست که حداقل کردن زمان انجام پروژه­ها در کنار کیفیت و قیمت اهمیت بیشتری می­یابد.تاریخچه مدیریت پروژه در دنیای جدید به سالهای ابتدایی دهه 1900 میلادی باز می­گردد؛ هنری گانت با توسعه نمودار میله‏ای ابداعی خود آغازگر حرکت پرشتاب بعدی طی سالهای دهه 1950 و 1960 میلادی در پروژه‌های نظامی و هوافضای آمریکا و سپس انگلستان گردید. هرچند نام پرآوازه هنری گانت به عنوان پدر تکنیک‏های برنامه‌ریزی و کنترل پروژه در تاریخ ثبت گردیده است لیکن سالهای دهه 1950 و 1960 به عنوان سالهای آغازین رشد و توسعه مدیریت پروژه در دنیای معاصر شناخته می‌شود. این سال­ها سرآغاز تکوین و توسعه بسیاری از روش­ها و دانش­های مربوط به مدیریت پروژه است که سال­ها بعد توسط نرم‌افزارهای مختلف عملیاتی و در پروژه‌ها بکار گرفته شدند.با توجه به همین مفاهیم، به دنبال طرح و زمانبندی برای انجام یک پروژه خواهیم بود که مسلما تاثیر به­سزایی در موفقیت پروژه و رسیدن به اهداف آن بازی خواهد کرد. این زمانبندی از طرفی باید با توجه به محدودیت­های منابع باشد و از طرف دیگر ممکن است به دلایل مختلف به دنبال حداقل کردن مدت زمان انجام پروژه باشیم و یا به دلایل اقتصادی به دنبال بیشینه کردن ارزش خالص فعلی پروژه باشیم.یک پروژه مجموعه‌ای از فعالیت­هاست که برای دستیابی به منظور یا هدف خاصی انجام می‌گیرد. پروژه‌ها شامل فعالیت­هایی هستند که باید در تاریخ­های معین، با هزینه‌هایی معین و کیفیت تعیین‌شده‌ای به انجام رسند. بین این فعالیت­ها روابط پیش­نیازی برقرار است و روابط تقدم- تاخر بین آنها وجود دارد، به این معنی که برخی فعالیت­ها وابسته به برخی دیگر هستند و برای اجرای یک فعالیت باید فعالیت­های پیش­نیاز آن پایان یافته باشند یا حداقل تا مرحله لازم پیش رفته باشند. برنامه ریزی پروژه عبارت است از تعیین ترتیب زمانی یا برنامه زمانبندی جهت انجام فعالیت­های وابسته که تشکیل دهنده پروژه هستند. لازمه موفقیت هر پروژه، دستیابی توام به هر سه عامل زمان، هزینه و کیفیت معین است و خارج شدن هر یک از سه عامل مذکور از حدود تعیین شده، می‌تواند به انجام پروژه‌ای ناموفق و غیراقتصادی منجر شود. از فاکتورهای مهم موثر در زمان و هزینه پروژه منابع مورد استفاده در پروژه از قبیل پول و مواد اولیه و تجهیزات و نیروی انسانی است. برخی منابع تجدیدپذیر هستند یعنی مصرفی نیستند و بارها می­توان از آنها استفاده کرد مانند نیروی انسانی و برخی دیگر مانند مواد خام مصرفی هستند و تجدیدناپذیر می­باشند. معمولا این منابع محدود هستند و بین فعالیتها بصورت مشترک استفاده می­شوند که این خود باعث ایجاد محدودیتی دیگر در اجرای فعالیتها و زمانبندی پروژه می­شود. یک فعالیت برای­ اجرای خود باید تمام منابعش مهیا باشد تا به فعالیت اختصاص یابد. گاهی می­توان یک فعالیت را می­توان با تخصیص بخشی از منابع مورد نیازش، شروع کرد ولی برای خاتمه آن باید همه منابع مورد نیازش تامین شود. در اینجا فرض براین است که در ابتدای شروع هر فعالیت از پروژه همه منابع مورد نیازش به آن فعالیت تخصیص داده شود و پس از اجرای فعالیت، منابع باقیمانده آزاد گردند. منابع مورد نظر نیز تجدیدشدنی هستند.بطورکلی انجام پروژه به پنج فاز تقسیم می‌شود. فاز اول، تعربف پروژه است که بر چگونگی پیدایش دید نسبت به پروژه و تعیین اهداف تاکید دارد. در این فاز، برخی عناصر کلیدی مجزا گردهم ‌آمده و به تخمین اینکه پروژه چه‌چیز را باید ارائه‌دهد، می­پردازد، فعالیتهای پروژه مشخص می­گردد و اهداف ‌کلی پروژه تعریف می­شوند. فاز دوم، برنامه‌ریزی پروژه است که شامل تعیین منابع ‌لازم برای انجام پروژه، برنامه‌ریزی، زمانبندی و تهیه‌ بودجه‌ پروژه است. در این مرحله اهداف به فعالیت‌های ملموس تبدیل می­گردند و گروه‌های کاری برای انجام این فعالیت­ها تشکیل می­شود. در این مرحله است که محدوده پروژه واقعی می­شود و توالی فعالیت­ها تعیین می­شوند و زمانبندی موقت انجام می­گیرد و برنامه تخصیص منابع به فعالیت­ها تهیه می­شود. این تحقیق نیز در این فاز انجام می­گیرد و به زمانبندی پروژه با توجه به محدودیت منابع می­پردازد و در تلاش است تا با استفاده از روشهای بهینه سازی و الگوریتم­های فراابتکاری[1] بهترین توالی انجام فعالیتها را که کمترین زمان اجرا دارند را تعیین کند. فاز سوم، اجرای پروژه است که فعالیت‌های هماهنگ‌سازی و راهبری تیم ‌پروژه به‌سوی انجام موثر فعالیت‌های پروژه را شامل می­شود. نامین منابع مورد نیاز مانند پول، نیروی‌انسانی، تجهیزات در این مرحله انجام می­گیرد. فاز چهارم، هدایت و کنترل پروژه است که در آن بر چگونگی انجام پروژه نظارت ‌می‌شود. مرحله سوم و چهارم همزمان انجام می­گیرند. تاکید این فاز بر روی چگونگی برخورد موثر مدیر با تاخیرات ناخواسته،‌ تخطی از سقف بودجه یا تغییر محدوده‌ پروژه است. ممکن است در این فاز پروژه دوباره برنامه ریزی و زمانبندی شود. آخرین فاز پروژه، بستن پروژه است؛ زمانی که بازتاب همه‌ فعالیت‌ها و تلاش‌های انجام‌شده را می‌توان ‌دید  بی‌شک مهم‌ترین فاز پروژه ، بستن و اتمام آن است. فازهای دو تا چهار یعنی‌ برنامه‌ریزی، اجرا و کنترل در یک‌ چرخه قرار دارند؛ این به ‌دلیل ماهیت وابستگی درونی این فازها به‌ یکدیگر است. مثلا گاهی لازم ‌است تا برنامه‌ پروژه با توجه به تجربیات بدست‌آمده در حین اجرا، یا بواسطه‌ تغییرات پدیدآمده در طول پروژه، اصلاح شود و نتایج اصلاح مجددا برای اجرا ارسال‌ گردد.زمانبندی پروژه در صنعت و کارخانجات و حمل و نقل و فروش و پرداخت و ... استفاده می­گردد و کمتر سازمانی است که اهمیت آن را درک نکرده باشد. دسته­ای از مسائل برنامه­ریزی پروژه که محدودیت­های منابع در آنها وجود ندارد یا در نظر گرفته نمی­شود به مسائل برنامه ریزی پروژه بدون محدودیت منابع و آن دسته که دارای محدودیت منابع می­باشند و این محدودیت­ها در برنامه­ریزی پروژه در نظر گرفته­می­شوند به مسائل برنامه­ریزی پروژه با محدودیت منابع[2] معروفند. زمانبندی پروژه با در نظر گرفتن محدودیت منابع از جمله مسایل با ادبیات غنی در حوزه مسائل تحقیق در عملیات و مدیریت پروژه است. این مسئله با توجه به شرایط متفاوت کاربردی و صنعتی از نظر تابع هدف، خصوصیات فعالیت ها، منابع و روابط پیش نیازی بسیار متنوع اند و محققین همواره به دنبال ارائه راه حل های کاراتری برای حل این مسئله بوده­اند. با توجه به اینکه در تمام سطوح پروژه با محدودیت منابع مواجه هستیم، لذا لزوم ایجاد و بکارگیری روش­هایی که انواع محدودیت­های منابع را در نظر بگیرند، مشخص است.[1] meta-heuristic[2] Resource Constrained Project Scheduling Problem (RCPSP)تعداد صفحه : 110قیمت : 14000تومان

بلافاصله پس از پرداخت ، لینک دانلود پایان نامه به شما نشان داده می شود

و در ضمن فایل خریداری شده به ایمیل شما ارسال می شود.

پشتیبانی سایت :        09309714541 (فقط پیامک)        info@arshadha.ir

در صورتی که مشکلی با پرداخت آنلاین دارید می توانید مبلغ مورد نظر برای هر فایل را کارت به کارت کرده و فایل درخواستی و اطلاعات واریز را به ایمیل ما ارسال کنید تا فایل را از طریق ایمیل دریافت کنید.

--  -- --

مطالب مشابه را هم ببینید

فایل مورد نظر خودتان را پیدا نکردید ؟ نگران نباشید . این صفحه را نبندید ! سایت ما حاوی حجم عظیمی از پایان نامه های دانشگاهی است. مطالب مشابه را هم ببینید. برای یافتن فایل مورد نظر کافیست از قسمت جستجو استفاده کنید. یا از منوی بالای سایت رشته مورد نظر خود را انتخاب کنید و همه فایل های رشته خودتان را ببینید