دانلود متن کامل پایان نامه با فرمت ورد

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

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

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

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

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

عنوان:

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

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

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

برای رعایت حریم خصوصی نام نگارنده درج نمی شود

تکه هایی از متن به عنوان نمونه :

فهرست مطالب:

فصل 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 ………………………………………………………………………………

5-3 نتایج آزمایش اجرای الگوریتم با پیکربندی­های مختلف …………………………………. 69

5-3-1 تاثیر اندازه جمعیت با تعداد تکرار ثابت ………………………………………….70

5-3-2 تاثیر اندازه جمعیت با تعداد تکرار متغیر ………………………………………. 72

5-3-3 تاثیر اندازه نخبه …………………………………………………………………………….. 73

5-3-4 تاثیر تاثیر روش زمانبدی سریال و موازی بر الگوریتم TLBO ……..

5-4 مقایسه نتایج با دیگر الگوریتم­های فراابتکاری در حل مسئله RCPSP ………….

5-5 نتیجه ­گیری ………………………………………………………………………………………..82

فهرست منابع ……………………………………………………………………………………….. 83

چکیده:

مسئله زمانبندي پروژه با منابع محدود، در سال­هاي اخیر مورد تحقیق بسیاري از محققان در رشته­های مختلف بوده­است. در این مسئله هدف زمانبندي فعالیت­های پروژه با توجه به روابط پیشنیازی و محدودیت منابع در کمترین زمان می­باشد. در این مسئله فضای جستجوی بسیار بزرگی جهت دست­یابی به جواب بهینه وجود دارد و نیازمند انجام محاسبات طولانی بخصوص برای ابعاد بزرگ مسئله با محدودیت­های زیاد می­­شود و الگوریتم­های دقیق برای آن موثر نیستند. الگوریتم­هاي فراابتکاری بعنوان جایگزین روش­های دقیق برای حل آن، پیشنهاد شده­است. در این پایان نامه الگوریتم فراابتکاري مبتنی بر آموزش- یادگیری براي حل این مسئله استفاده شده­است. این الگوریتم مبتنی بر جمعیت است که اخیرا معرفی شده است و فرایند آموزش و یادگیری در کلاس درس را شبیه سازی می­کند. همچنین برای جلوگیری از محلی شدن پاسخ­ها از رویکرد نخبه­گرایی در این الگوریتم استفاده شده­است. از ویژگی­های این الگوریتم این است که نیازی به پارامترهای کنترلی اختصاصی الگوریتم، ندارد و فقط پارامترهای کنترلی عمومی مانند اندازه جمعیت و تعداد نسلها را شامل می­گردد. الگوریتم داری دو فاز، فاز معلم و فاز فراگیر است. ابتدا تعدادی زمانبندي را بطور تصادفی بر اساس جمعیت اولیه الگوریتم ها تولید می کنیم، سپس فازهای الگوریتم را روی زمانبندی ­ها اعمال می­کنیم بطوریکه جمعیت اولیه به طور تکراري بهبود می­یابد تا به شرط توقف برسیم. همچنین تاثیر عواملی مانند اندازه جمعیت و اندازه نخبه و تعداد زمانبندی­ها بر الگوریتم، بررسی شده است. کارایی الگوریتم ارائه شده با دیگر الگوریتم­هاي بکار گرفته شده در حل این مسئله، مقایسه شده است و نتایج موثر با قابلیت رقابت بالا با دیگر الگوریتم­ها حاصل شده ­است.

فصل نخست: مقدمه

1-1- مقدمه

امروزه، جهانی شدن تجارت، تغييرات سريع تكنولوژيك، بازارهاي شديد رقابتي و رايزني فشرده و قدرتمندانه شركتها سازمانها و بنگاههای اقتصادی را وادار به تغيير سيستم مديريتي خود می­نماید، برای تطبيق و سازگاري با این تغییرات، مديريت پروژه و پروژه محوری در مدیریت از اهمیت بالایی برای سازمانها برخوردار است. تولید کنندگان در بازار رقابتی امروز باید هزینه های تولید را تا حد امکان کاهش دهند تا بتوانند کالاهای خود را با قیمتی مناسب و قابل رقابت با دیگر رقبا به بازارها عرضه کنند. بنگاههاي اقتصادي چاره­اي جز بالا بردن بهره­وري و انجام کارهاي بیشتر و بهتر با صرف منابع و زمان کمتر ندارند. از همین جاست که مفاهیمی همچون پروژه، کنترل پروژه، زمانبندي پروژه و … مطرح شده­اند.

دنیای ارتباطی امروز به کمک فناوری اطلاعات و اینترنت امکان مشارکت بیشتر بنگاههای اقتصادی را فراهم آورده است و این خود امکان تعریف پروژه هایی بزرگتر را تسهیل کرده­است. تاخیر در ساخت یا توزیع، گاهی به از دست رفتن یک بازار می­انجامد و از این روست که حداقل کردن زمان انجام پروژه­ها در کنار کیفیت و قیمت اهمیت بیشتری می­یابد.

تاريخچه مديريت پروژه در دنياي جديد به سالهاي ابتدايي دهه 1900 ميلادي باز مي­گردد؛ هنري گانت با توسعه نمودار ميله‏اي ابداعي خود آغازگر حركت پرشتاب بعدي طي سالهاي دهه 1950 و 1960 ميلادي در پروژه‌هاي نظامي و هوافضاي آمريكا و سپس انگلستان گرديد. هرچند نام پرآوازه هنري گانت به عنوان پدر تكنيك‏هاي برنامه‌ريزي و كنترل پروژه در تاريخ ثبت گرديده است ليكن سالهاي دهه 1950 و 1960 به عنوان سالهاي آغازين رشد و توسعه مديريت پروژه در دنياي معاصر شناخته مي‌شود. اين سال­ها سرآغاز تكوين و توسعه بسياري از روش­ها و دانش­هاي مربوط به مديريت پروژه است كه سال­ها بعد توسط نرم‌افزارهاي مختلف عملياتي و در پروژه‌ها بكار گرفته شدند.

با توجه به همین مفاهیم، به دنبال طرح و زمانبندي براي انجام یک پروژه خواهیم بود که مسلما تاثیر به­سزایی در موفقیت پروژه و رسیدن به اهداف آن بازي خواهد کرد. این زمانبندي از طرفی باید با توجه به محدودیت­هاي منابع باشد و از طرف دیگر ممکن است به دلایل مختلف به دنبال حداقل کردن مدت زمان انجام پروژه باشیم و یا به دلایل اقتصادي به دنبال بیشینه کردن ارزش خالص فعلی پروژه باشیم.

يك پروژه مجموعه‌اي از فعاليت­هاست كه براي دستيابي به منظور يا هدف خاصي انجام مي‌گيرد. پروژه‌ها شامل فعاليت­هايي هستند كه بايد در تاريخ­هاي معين، با هزينه‌هايي معين و كيفيت تعيين‌شده‌اي به انجام رسند. بین این فعالیت­ها روابط پیش­نیازی برقرار است و روابط تقدم- تاخر بین آنها وجود دارد، به این معنی که برخی فعالیت­ها وابسته به برخی دیگر هستند و برای اجرای یک فعالیت باید فعالیت­های پیش­نیاز آن پایان یافته باشند یا حداقل تا مرحله لازم پیش رفته باشند. برنامه ریزي پروژه عبارت است از تعیین ترتیب زمانی یا برنامه زمانبندي جهت انجام فعالیت­هاي وابسته که تشکیل دهنده پروژه هستند. لازمه موفقيت هر پروژه، دستيابي توام به هر سه عامل زمان، هزينه و كيفيت معين است و خارج شدن هر يك از سه عامل مذكور از حدود تعيين شده، مي‌تواند به انجام پروژه‌اي ناموفق و غيراقتصادي منجر شود. از فاکتورهای مهم موثر در زمان و هزینه پروژه منابع مورد استفاده در پروژه از قبیل پول و مواد اولیه و تجهیزات و نیروی انسانی است. برخی منابع تجدیدپذیر هستند یعنی مصرفی نیستند و بارها می­توان از آنها استفاده کرد مانند نیروی انسانی و برخی دیگر مانند مواد خام مصرفی هستند و تجدیدناپذیر می­باشند. معمولا این منابع محدود هستند و بین فعالیتها بصورت مشترک استفاده می­شوند که این خود باعث ایجاد محدودیتی دیگر در اجرای فعالیتها و زمانبندی پروژه می­شود. یک فعالیت برای­ اجرای خود باید تمام منابعش مهیا باشد تا به فعالیت اختصاص یابد. گاهی می­توان یک فعالیت را می­توان با تخصیص بخشی از منابع مورد نیازش، شروع کرد ولی برای خاتمه آن باید همه منابع مورد نیازش تامین شود. در اینجا فرض براین است که در ابتدای شروع هر فعالیت از پروژه همه منابع مورد نیازش به آن فعالیت تخصیص داده شود و پس از اجرای فعالیت، منابع باقیمانده آزاد گردند. منابع مورد نظر نیز تجدیدشدنی هستند.

بطورکلی انجام پروژه به پنج فاز تقسيم مي‌شود. فاز اول، تعربف پروژه است که بر چگونگي پيدايش ديد نسبت به پروژه و تعيين اهداف تاكيد دارد. در اين فاز، برخي عناصر كليدي مجزا گردهم ‌آمده و به تخمين اينكه پروژه چه‌چيز را بايد ارائه‌دهد، می­پردازد، فعالیتهای پروژه مشخص می­گردد و اهداف ‌كلي پروژه تعريف می­شوند. فاز دوم، برنامه‌ريزي پروژه است که شامل تعيين منابع ‌لازم براي انجام پروژه، برنامه‌ريزي، زمانبندي و تهيه‌ بودجه‌ پروژه است. در این مرحله اهداف به فعاليت‌هاي ملموس تبديل می­گردند و گروه‌هاي كاري براي انجام اين فعاليت­ها تشکیل می­شود. در این مرحله است که محدوده پروژه واقعی می­شود و توالی فعالیت­ها تعیین می­شوند و زمانبندی موقت انجام می­گیرد و برنامه تخصیص منابع به فعالیت­ها تهیه می­شود. این تحقیق نیز در این فاز انجام می­گیرد و به زمانبندی پروژه با توجه به محدودیت منابع می­پردازد و در تلاش است تا با بهره گرفتن از روشهای بهینه سازی و الگوریتم­های فراابتکاری[1] بهترین توالی انجام فعالیتها را که کمترین زمان اجرا دارند را تعیین کند. فاز سوم، اجرای پروژه است که فعاليت‌هاي هماهنگ‌سازي و راهبري تيم ‌پروژه به‌سوي انجام موثر فعاليت‌هاي پروژه را شامل می­شود. نامین منابع مورد نیاز مانند پول، نيروي‌انساني، تجهيزات در این مرحله انجام می­گیرد. فاز چهارم، هدايت و كنترل پروژه است که در آن بر چگونگي انجام پروژه نظارت ‌مي‌شود. مرحله سوم و چهارم همزمان انجام می­گیرند. تاكيد اين فاز بر روي چگونگي برخورد موثر مدير با تاخيرات ناخواسته،‌ تخطي از سقف بودجه يا تغيير محدوده‌ پروژه است. ممکن است در این فاز پروژه دوباره برنامه ریزی و زمانبندی شود. آخرين فاز پروژه، بستن پروژه است؛ زماني كه بازتاب همه‌ فعاليت‌ها و تلاش‌هاي انجام‌شده را مي‌توان ‌ديد بي‌شك مهم‌ترين فاز پروژه ، بستن و اتمام آن است. فازهاي دو تا چهار يعني‌ برنامه‌ريزي، اجرا و كنترل در يك‌ چرخه قرار دارند؛ اين به ‌دليل ماهيت وابستگي دروني اين فازها به‌ يكديگر است. مثلا گاهي لازم ‌است تا برنامه‌ پروژه با توجه به تجربيات بدست‌آمده در حين اجرا، يا بواسطه‌ تغييرات پديدآمده در طول پروژه، اصلاح شود و نتايج اصلاح مجددا براي اجرا ارسال‌ گردد.

زمانبندی پروژه در صنعت و کارخانجات و حمل و نقل و فروش و پرداخت و … استفاده می­گردد و کمتر سازمانی است که اهمیت آن را درک نکرده باشد. دسته­ای از مسائل برنامه­ریزي پروژه که محدودیت­هاي منابع در آنها وجود ندارد یا در نظر گرفته نمی­شود به مسائل برنامه ریزي پروژه بدون محدودیت منابع و آن دسته که داراي محدودیت منابع می­باشند و این محدودیت­ها در برنامه­ریزي پروژه در نظر گرفته­می­شوند به مسائل برنامه­ریزي پروژه با محدودیت منابع[2] معروفند. زمانبندي پروژه با در نظر گرفتن محدودیت منابع از جمله مسایل با ادبیات غنی در حوزه مسائل تحقیق در عملیات و مدیریت پروژه است. این مسئله با توجه به شرایط متفاوت کاربردي و صنعتی از نظر تابع هدف، خصوصیات فعالیت ها، منابع و روابط پیش نیازي بسیار متنوع اند و محققین همواره به دنبال ارائه راه حل هاي کاراتري براي حل این مسئله بوده­اند. با توجه به اینکه در تمام سطوح پروژه با محدودیت منابع مواجه هستیم، لذا لزوم ایجاد و بکارگیري روش­هایی که انواع محدودیت­هاي منابع را در نظر بگیرند، مشخص است.

1-2 اهداف پژوهش

معمولا در مسئله زمانبندي پروژه با محدودیت منابع، هدف زمانبندي فعالیت­ها با توجه به روابط پیش­نیازي و محدودیت منابع در کمترین زمان می­باشد. در این تحقیق نیز، راه­حلی جدید برای مسئله زمانبندی پروژه با منابع محدود ارایه می­شود که از الگوریتم بهینه­سازی مبتنی بر آموزش- یادگیری TLBO استفاده می­شود. به علت کاربردهاي عملی فراوان و همچنین پیچیدگیهاي خاص، این مسئله بسیار مورد توجه محققین بوده است و در سالهاي اخیر تحقیقات بسیاري بر روي آن صورت گرفته است. در این تحقیقات معیارهایی براي تشخیص و تعیین مطلوبیت یک زمانبندي براي پروژه­هاي تحت بررسی بکار گرفته شده است. از جمله این معیارها نرخ موفقیت و میانگین زمان پردازش و میزان انحراف از پاسخ بهینه یا میزان انحراف از مسیر بحرانی پروژه است. در این پایان نامه معیارهای نرخ موفقیت و میزان انحراف از پاسخ بهینه یا میزان انحراف از مسیر بحرانی پروژه برای بررسی و مقایسه در نظر گرفته شده است. به علت اهمیت این مسئله محققین کتابخانه­هایی از مسایل نمونه را ایجاد کرده­اند و در اختیار کاوشگران قرار داده­اند. براي حل این مسئله بصورت دقیق با بهره گرفتن از مدلهاي ریاضی تلاشهاي زیادي انجام گرفته است که با بزرگ شدن اندازه مسئله یعنی افزایش تعداد فعالیت­ها و منابع این الگوریتم­ها موثر نیستند. در حالت­های با پیچیدگی زیاد از پاسخهای مسئله زمانبندی پروژه بدون محدودیت منابع کمک گرفته می­شود و این پاسخها به عنوان حدپایین برای الگوریتم­ها در حل مسئله زمانبندي پروژه با محدودیت منابع در نظر گرفته می­شوند و مانند پاسخ بهینه نگریسته می­شوند. همچنین طول مسیر بحرانی پروژه در حالت بدون محدودیت منابع نیز عامل دیگری است که میزان انحراف پاسخ­های یافته شده در حالت محدودیت منابع از این مسیر بحرانی از فاکتورهای مطلوب بودن الگوریتم بکار گرفته شده است. در زمانبندي پروژه بدون در نظر گرفتن محدودیت منابع از روشهایی مانند CPM , PERT استفاده می­شود. این روشها شبیه به هم هستند و تفاوتشان در زمان اجرای فعالیتهاست. هیچکدام از روشهای مذکور محدودیت منابع را در نظر نمی­گیرند و به همین دلیل در حل مسئله زمانبندي پروژه با محدودیت منابع، قابل استفاده نیستند.

در سال­هاي اخیر الگوریتم­هاي فراابتکاری زیادي براي حل این مسئله پیشنهاد شده است. به علت پیچیدگی بالا، به دست آوردن جواب بهینه این مسئله با بهره گرفتن از روش­هاي سنتی بهینه­سازي، بسیار دشوار و یا حتی غیر ممکن است. بهینه­سازی ریاضی و محاسباتی در مسایل مهندسی با مقیاس بزرگ، سختی­های زیادی را با همراه دارد و زمان حل آنها در این مسائل به صورت نمایی افزایش می‌یابد. بهمین دلیل راه حل­های جایگزین و متناوب را بصورت مشارکتی ایجاد کرده­اند. روش­های سنتی مانند برنامه­نویسی خطی، برنامه­نویسی پویا و … هستند که غالبا در این مسایل با شکست روبرو می شوند یا دارای پاسخهای بهینه محلی هستند. این مسایل دارای متغیرهای خیلی زیادی هستند و توابع هدف غیر خطی دارند. برای حل و پوشش این مسایل الگوریتم های فراابتکاری جدیدی ارایه شده اند که پاسخ­هایی نزدیک به جواب بهینه را جستجو می کنند. این الگوریتم­ها در دسته های مختلفی دسته بندی می­شوند که بستگی به معیار مورد نظر مانند مبتنی بر جمعیت، مبتنی بر تکرار و… دارند. در این پایان نامه الگوریتم فرا ابتکاري مبتنی بر آموزش- یادگیری یعنی [3]TLBO براي حل این مسئله استفاده شده است. TLBO یکی از الگوریتم­های مبتنی بر جمعیت است که اخیرا معرفی شده است و فرایند آموزش و یادگیری در کلاس درس را شبیه­سازی می­کند. همچنین برای جلوگیری از محلی شدن پاسخ­ها از رویکرد نخبه­گرایی در این الگوریتم استفاده شده­است.

الگوریتم مورد استفاده با بکارگیري عملیات فازهای خود به حل مسئله زمانبندي پروژه با محدودیت منابع می­پردازد. به منظور بررسی کارایی الگوریتم و مقایسه آن با الگوریتم­هاي دیگري که به حل این مسئله پرداخته­اند، مسائل نمونه مختلف و شناخته شده­ای که در این حوزه تعریف شده­اند، با الگوریتم پیشنهادي حل شده­است. نتایج به دست آمده با بهترین الگوریتم هاي موجود در ادبیات موضوع مقایسه شده­است. نتایج بدست آمده دلالت بر این دارد که الگوریتم مورد استفاده از کارایی مطلوب و قابل رقابتی در مقایسه با الگوریتم­هاي دیگر برخوردار است و نتیجه بهتری از بیشتر آنها دارد.

1-3 ساختار پژوهش

در این پژوهش در ادامه یعنی در فصل دوم، به معرفی مسئله زمانبندی پروژه با منابع محدود می­پردازیم و با فرمول ­های ریاضی آن را مدل می­کنیم. سپس در فصل سوم الگوریتم TLBO را بررسی می­کنیم. در فصل چهارم، رویکردهای سری و موازی و روش­های پسرو و پیشرو را برای زمانبندی اولیه با مثال تشریح می­کنیم. سپس الگوریتم TLBO با رویکرد نخبه­گرایانه را با مسئله زمانبندی پروژه با منابع محدود تطبیق می­دهیم و بوسیله برنامه­نویسی، مسئله را حل می­کنیم. در فصل پنجم، مسایل نمونه­ای که با این الگوریتم حل شده­اند توضیح داده شده­اند. نتایج عددی بدست آمده را با توجه به پارامترهایی مانند اندازه جمعیت و حداکثر تعداد زمانبندی­ها بررسی می­نماییم. در پایان نیز نتایج بدست آمده با الگوریتم TLBO در حل مسئله زمانبندی پروژه با منابع محدود با دیگر الگوریتم­ها مقایسه می­گردد.

[1] meta-heuristic

[2] Resource Constrained Project Scheduling Problem (RCPSP)

[3] Teaching-Learning-Based Optimization(TLBO)

ممکن است هنگام انتقال از فایل اصلی به داخل سایت بعضی متون به هم بریزد یا بعضی نمادها و اشکال درج نشود ولی در فایل دانلودی همه چیز مرتب و کامل و با فرمت ورد موجود است

متن کامل را می توانید دانلود نمائید

چون فقط تکه هایی از متن پایان نامه در این صفحه درج شده (به طور نمونه)

ولی در فایل دانلودی متن کامل پایان نامه

 با فرمت ورد word که قابل ویرایش و کپی کردن می باشند

موجود است

تعداد صفحه : 104

قیمت : 14700 تومان

 

—-

پشتیبانی سایت :       

*         serderehi@gmail.com

جستجو در سایت : کلمه کلیدی خود را وارد نمایید :