مسئله زمانبنديپروژهبامنابعمحدود، درسالهاياخیرمورد تحقیق بسیاريازمحققان در رشتههای مختلف بودهاست. دراینمسئلههدفزمانبندي فعالیتهای پروژه باتوجهبهروابط پیشنیازی و محدودیتمنابعدرکمترین زمانمیباشد. در این مسئله فضای جستجوی بسیار بزرگی جهت دستیابی به جواب بهینه وجود دارد و نیازمند انجام محاسبات طولانی بخصوص برای ابعاد بزرگ مسئله با محدودیتهای زیاد میشود و الگوریتمهای دقیق برای آن موثرنیستند. الگوریتمهايفراابتکاریبعنوان جایگزین روشهای دقیق برای حل آن،پیشنهادشدهاست. در این پایان نامهالگوریتمفراابتکاري مبتنی بر آموزش- یادگیری برايحلاینمسئلهاستفاده شدهاست. این الگوریتم مبتنی بر جمعیت است که اخیرا معرفی شده است و فرایند آموزش و یادگیری در کلاس درس را شبیه سازی میکند.همچنین برای جلوگیری از محلی شدن پاسخها از رویکرد نخبهگرایی در این الگوریتم استفاده شدهاست. از ویژگیهای این الگوریتم این است که نیازی به پارامترهای کنترلی اختصاصی الگوریتم، ندارد و فقط پارامترهای کنترلی عمومی مانند اندازه جمعیت و تعداد نسلها را شامل میگردد. الگوریتم داری دو فاز، فاز معلم و فاز فراگیر است. ابتداتعدادیزمانبنديرابطورتصادفیبراساسجمعیتاولیهالگوریتمهاتولیدمیکنیم،سپس فازهای الگوریتم را روی زمانبندیها اعمال میکنیم بطوریکه جمعیتاولیهبهطورتکراريبهبودمییابدتابهشرطتوقفبرسیم. همچنین تاثیر عواملی مانند اندازه جمعیت و اندازه نخبه و تعداد زمانبندیها بر الگوریتم، بررسی شده است. کاراییالگوریتمارائهشدهبادیگرالگوریتمهاي بکار گرفته شده در حل این مسئله،مقایسهشدهاست ونتایج موثر با قابلیت رقابت بالا با دیگر الگوریتمها حاصل شدهاست.واژگان کلیدی:مسئله زمانبندي پروژه ها بامنابع محدود، روشهای فراابتکاری، الگوريتم بهینه سازی مبتنی بر آموزش-یادگیری.فهرست مطالبعنوان صفحهفصل 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 مدل کلین ........................................................................................................... 252-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 فصل نخست: مقدمه1-1 مقدمهامروزه، جهانی شدن تجارت، تغييرات سريع تكنولوژيك، بازارهاي شديد رقابتي و رايزني فشرده و قدرتمندانه شركتها سازمانها و بنگاههای اقتصادی را وادار به تغيير سيستم مديريتي خود مینماید، برای تطبيق و سازگاري با این تغییرات، مديريت پروژه و پروژه محوری در مدیریت از اهمیت بالایی برای سازمانها برخوردار است. تولید کنندگان در بازار رقابتی امروز باید هزینه های تولید را تا حد امکان کاهش دهند تا بتوانند کالاهای خود را با قیمتی مناسب و قابل رقابت با دیگر رقبا به بازارها عرضه کنند. بنگاههاي اقتصادي چارهاي جز بالا بردن بهرهوري و انجام کارهاي بیشتر و بهتر با صرف منابع و زمان کمتر ندارند. از همین جاست که مفاهیمی همچون پروژه، کنترل پروژه، زمانبندي پروژه و ... مطرح شدهاند.دنیای ارتباطی امروز به کمک فناوری اطلاعات و اینترنت امکان مشارکت بیشتر بنگاههای اقتصادی را فراهم آورده است و این خود امکان تعریف پروژه هایی بزرگتر را تسهیل کردهاست. تاخیر در ساخت یا توزیع، گاهی به از دست رفتن یک بازار میانجامد و از این روست که حداقل کردن زمان انجام پروژهها در کنار کیفیت و قیمت اهمیت بیشتری مییابد.تاريخچه مديريت پروژه در دنياي جديد به سالهاي ابتدايي دهه 1900 ميلادي باز ميگردد؛ هنري گانت با توسعه نمودار ميلهاي ابداعي خود آغازگر حركت پرشتاب بعدي طي سالهاي دهه 1950 و 1960 ميلادي در پروژه‌هاي نظامي و هوافضاي آمريكا و سپس انگلستان گرديد. هرچند نام پرآوازه هنري گانت به عنوان پدر تكنيكهاي برنامه‌ريزي و كنترل پروژه در تاريخ ثبت گرديده است ليكن سالهاي دهه 1950 و 1960 به عنوان سالهاي آغازين رشد و توسعه مديريت پروژه در دنياي معاصر شناخته مي‌شود. اين سالها سرآغاز تكوين و توسعه بسياري از روشها و دانشهاي مربوط به مديريت پروژه است كه سالها بعد توسط نرم‌افزارهاي مختلف عملياتي و در پروژهها بكار گرفته شدند.با توجه به همین مفاهیم، به دنبال طرح و زمانبندي براي انجام یک پروژه خواهیم بود که مسلما تاثیر بهسزایی در موفقیت پروژه و رسیدن به اهداف آن بازي خواهد کرد. این زمانبندي از طرفی باید با توجه به محدودیتهاي منابع باشد و از طرف دیگر ممکن است به دلایل مختلف به دنبال حداقل کردن مدت زمان انجام پروژه باشیم و یا به دلایل اقتصادي به دنبال بیشینه کردن ارزش خالص فعلی پروژه باشیم.يك پروژه مجموعه‌اي از فعاليتهاست كه براي دستيابي به منظور يا هدف خاصي انجام مي‌گيرد. پروژهها شامل فعاليتهايي هستند كه بايد در تاريخهاي معين، با هزينه‌هايي معين و كيفيت تعيين‌شده‌اي به انجام رسند. بین این فعالیتها روابط پیشنیازی برقرار است و روابط تقدم- تاخر بین آنها وجود دارد، به این معنی که برخی فعالیتها وابسته به برخی دیگر هستند و برای اجرای یک فعالیت باید فعالیتهای پیشنیاز آن پایان یافته باشند یا حداقل تا مرحله لازم پیش رفته باشند. برنامه ریزي پروژه عبارت است از تعیین ترتیب زمانی یا برنامه زمانبندي جهت انجام فعالیتهاي وابسته که تشکیل دهنده پروژه هستند. لازمه موفقيت هر پروژه، دستيابي توام به هر سه عامل زمان، هزينه و كيفيت معين است و خارج شدن هر يك از سه عامل مذكور از حدود تعيين شده، مي‌تواند به انجام پروژه‌اي ناموفق و غيراقتصادي منجر شود. از فاکتورهای مهم موثر در زمان و هزینه پروژه منابع مورد استفاده در پروژه از قبیل پول و مواد اولیه و تجهیزات و نیروی انسانی است. برخی منابع تجدیدپذیر هستند یعنی مصرفی نیستند و بارها میتوان از آنها استفاده کرد مانند نیروی انسانی و برخی دیگر مانند مواد خام مصرفی هستند و تجدیدناپذیر میباشند. معمولا این منابع محدود هستند و بین فعالیتها بصورت مشترک استفاده میشوند که این خود باعث ایجاد محدودیتی دیگر در اجرای فعالیتها و زمانبندی پروژه میشود. یک فعالیت برای اجرای خود باید تمام منابعش مهیا باشد تا به فعالیت اختصاص یابد. گاهی میتوان یک فعالیت را میتوان با تخصیص بخشی از منابع مورد نیازش، شروع کرد ولی برای خاتمه آن باید همه منابع مورد نیازش تامین شود. در اینجا فرض براین است که در ابتدای شروع هر فعالیت از پروژه همه منابع مورد نیازش به آن فعالیت تخصیص داده شود و پس از اجرای فعالیت، منابع باقیمانده آزاد گردند. منابع مورد نظر نیز تجدیدشدنی هستند.بطورکلی انجام پروژه به پنج فاز تقسيم مي‌شود. فاز اول، تعربف پروژه است که بر چگونگي پيدايش ديد نسبت به پروژه و تعيين اهداف تاكيد دارد. در اين فاز، برخي عناصر كليدي مجزا گردهم آمده و به تخمين اينكه پروژه چه‌چيز را بايد ارائه‌دهد، میپردازد، فعالیتهای پروژه مشخص میگردد و اهداف كلي پروژه تعريف میشوند. فاز دوم، برنامه‌ريزي پروژه است که شامل تعيين منابع لازم براي انجام پروژه، برنامه‌ريزي، زمانبندي و تهيه بودجه پروژه است. در این مرحله اهداف به فعاليت‌هاي ملموس تبديل میگردند و گروه‌هاي كاري براي انجام اين فعاليتها تشکیل میشود. در این مرحله است که محدوده پروژه واقعی میشود و توالی فعالیتها تعیین میشوند و زمانبندی موقت انجام میگیرد و برنامه تخصیص منابع به فعالیتها تهیه میشود. این تحقیق نیز در این فاز انجام میگیرد و به زمانبندی پروژه با توجه به محدودیت منابع میپردازد و در تلاش است تا با استفاده از روشهای بهینه سازی و الگوریتمهای فراابتکاری[1] بهترین توالی انجام فعالیتها را که کمترین زمان اجرا دارند را تعیین کند. فاز سوم، اجرای پروژه است که فعاليت‌هاي هماهنگ‌سازي و راهبري تيم پروژه به‌سوي انجام موثر فعاليت‌هاي پروژه را شامل میشود. نامین منابع مورد نیاز مانند پول، نيروي‌انساني، تجهيزات در این مرحله انجام میگیرد. فاز چهارم، هدايت و كنترل پروژه است که در آن بر چگونگي انجام پروژه نظارت مي‌شود. مرحله سوم و چهارم همزمان انجام میگیرند. تاكيد اين فاز بر روي چگونگي برخورد موثر مدير با تاخيرات ناخواسته، تخطي از سقف بودجه يا تغيير محدوده پروژه است. ممکن است در این فاز پروژه دوباره برنامه ریزی و زمانبندی شود. آخرين فاز پروژه، بستن پروژه است؛ زماني كه بازتاب همه فعاليتها و تلاش‌هاي انجام‌شده را مي‌توان ديد بي‌شك مهم‌ترين فاز پروژه ، بستن و اتمام آن است. فازهاي دو تا چهار يعني برنامه‌ريزي، اجرا و كنترل در يك چرخه قرار دارند؛ اين به دليل ماهيت وابستگي دروني اين فازها به يكديگر است. مثلا گاهي لازم است تا برنامه پروژه با توجه به تجربيات بدست‌آمده در حين اجرا، يا بواسطه تغييرات پديدآمده در طول پروژه، اصلاح شود و نتايج اصلاح مجددا براي اجرا ارسال گردد.زمانبندی پروژه در صنعت و کارخانجات و حمل و نقل و فروش و پرداخت و ... استفاده میگردد و کمتر سازمانی است که اهمیت آن را درک نکرده باشد. دستهای از مسائل برنامهریزي پروژه که محدودیتهاي منابع در آنها وجود ندارد یا در نظر گرفته نمیشود به مسائل برنامه ریزي پروژه بدون محدودیت منابع و آن دسته که داراي محدودیت منابع میباشند و این محدودیتها در برنامهریزي پروژه در نظر گرفتهمیشوند به مسائل برنامهریزي پروژه با محدودیت منابع[2] معروفند. زمانبندي پروژه با در نظر گرفتن محدودیت منابع از جمله مسایل با ادبیات غنی در حوزه مسائل تحقیق در عملیات و مدیریت پروژه است. این مسئله با توجه به شرایط متفاوت کاربردي و صنعتی از نظر تابع هدف، خصوصیات فعالیت ها، منابع و روابط پیش نیازي بسیار متنوع اند و محققین همواره به دنبال ارائه راه حل هاي کاراتري براي حل این مسئله بودهاند. با توجه به اینکه در تمام سطوح پروژه با محدودیت منابع مواجه هستیم، لذا لزوم ایجاد و بکارگیري روشهایی که انواع محدودیتهاي منابع را در نظر بگیرند، مشخص است.