دانشکده آموزشهاي الکترونيکي
پايان‌نامه كارشناسي ارشد در رشته مهندسي فناوري اطلاعات
(تجارت الکترونيک)
استفاده از الگوريتم بهينه سازي مبتني بر آموزش- يادگيري براي حل مسئله زمانبندي پروژه ها با منابع محدود
به کوشش
محسن قاسمي
استاد راهنما:
دکتر رضا اکبري
12/11/92
به نام خدا
اظهارنامه
اينجانب محسن قاسمي(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: دستهبنديهاي مختلف مسئله زمانبندي با محدوديت منابع …………………………….. 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 معروفند. زمانبندي پروژه با در نظر گرفتن محدوديت منابع از جمله مسايل با ادبيات غني در حوزه مسائل تحقيق در عمليات و مديريت پروژه است. اين مسئله با توجه به شرايط متفاوت کاربردي و صنعتي از نظر تابع هدف، خصوصيات فعاليت ها، منابع و روابط پيش نيازي بسيار متنوع اند و محققين همواره به دنبال ارائه راه حل هاي کاراتري براي حل اين مسئله بودهاند. با توجه به اينکه در تمام سطوح پروژه با محدوديت منابع مواجه هستيم، لذا لزوم ايجاد و بکارگيري روشهايي که انواع محدوديتهاي منابع را در نظر بگيرند، مشخص است.
1-2 اهداف پژوهش
معمولا در مسئله زمانبندي پروژه با محدوديت منابع، هدف زمانبندي فعاليتها با توجه به روابط پيشنيازي و محدوديت منابع در کمترين زمان ميباشد. در اين تحقيق نيز، راهحلي جديد براي مسئله زمانبندي پروژه با منابع محدود ارايه ميشود که از الگوريتم بهينهسازي مبتني بر آموزش- يادگيري TLBO استفاده ميشود. به علت کاربردهاي عملي فراوان و همچنين پيچيدگيهاي خاص، اين مسئله بسيار مورد توجه محققين بوده است و در سالهاي اخير تحقيقات بسياري بر روي آن صورت گرفته است. در اين تحقيقات معيارهايي براي تشخيص و تعيين مطلوبيت يک زمانبندي براي پروژههاي تحت بررسي بکار گرفته شده است. از جمله اين معيارها نرخ موفقيت و ميانگين زمان پردازش و ميزان انحراف از پاسخ بهينه يا ميزان انحراف از مسير بحراني پروژه است. در اين پايان نامه معيارهاي نرخ موفقيت و ميزان انحراف از پاسخ بهينه يا ميزان انحراف از مسير بحراني پروژه براي بررسي و مقايسه در نظر گرفته شده است. به علت اهميت اين مسئله محققين کتابخانههايي از مسايل نمونه را ايجاد کردهاند و در اختيار کاوشگران قرار دادهاند. براي حل اين مسئله بصورت دقيق با استفاده از مدلهاي رياضي تلاشهاي زيادي انجام گرفته است که با بزرگ شدن اندازه مسئله يعني افزايش تعداد فعاليتها و منابع اين الگوريتمها موثر نيستند. در حالتهاي با پيچيدگي زياد از پاسخهاي مسئله زمانبندي پروژه بدون محدوديت منابع کمک گرفته ميشود و اين پاسخها به عنوان حدپايين براي الگوريتمها در حل مسئله زمانبندي پروژه با محدوديت منابع در نظر گرفته ميشوند و مانند پاسخ بهينه نگريسته ميشوند. همچنين طول مسير بحراني پروژه در حالت بدون محدوديت منابع نيز عامل ديگري است که ميزان انحراف پاسخهاي يافته شده در حالت محدوديت منابع از اين مسير بحراني از فاکتورهاي مطلوب بودن الگوريتم بکار گرفته شده است. در زمانبندي پروژه بدون در نظر گرفتن محدوديت منابع از روشهايي مانند CPM , PERT استفاده ميشود. اين روشها شبيه به هم هستند و تفاوتشان در زمان اجراي فعاليتهاست. هيچکدام از روشهاي مذکور محدوديت منابع را در نظر نميگيرند و به همين دليل در حل مسئله زمانبندي پروژه با محدوديت منابع، قابل استفاده نيستند.
در سالهاي اخير الگوريتمهاي فراابتکاري زيادي براي حل اين مسئله پيشنهاد شده است. به علت پيچيدگي بالا، به دست آوردن جواب بهينه اين مسئله با استفاده از روشهاي سنتي بهينهسازي، بسيار دشوار و يا حتي غير ممکن است. بهينهسازي رياضي و محاسباتي در مسايل مهندسي با مقياس بزرگ، سختيهاي زيادي را با همراه دارد و زمان حل آنها در اين مسائل به صورت نمايي افزايش مي‌يابد. بهمين دليل راه حلهاي جايگزين و متناوب را بصورت مشارکتي ايجاد کردهاند. روشهاي سنتي مانند برنامهنويسي خطي، برنامهنويسي پويا و … هستند که غالبا در اين مسايل با شکست روبرو مي شوند يا داراي پاسخهاي بهينه محلي هستند. اين مسايل داراي متغيرهاي خيلي زيادي هستند و توابع هدف غير خطي دارند. براي حل و پوشش اين مسايل الگوريتم هاي فراابتکاري جديدي ارايه شده اند که پاسخهايي نزديک به جواب بهينه را جستجو مي کنند. اين الگوريتمها در دسته هاي مختلفي دسته بندي ميشوند که بستگي به معيار مورد نظر مانند مبتني بر جمعيت، مبتني بر تکرار و… دارند. در اين پايان نامه الگوريتم فرا ابتکاري مبتني بر آموزش- يادگيري يعني 3TLBO براي حل اين مسئله استفاده شده است. TLBO يکي از الگوريتمهاي مبتني بر جمعيت است که اخيرا معرفي شده است و فرايند آموزش و يادگيري در کلاس درس را شبيهسازي ميکند. همچنين براي جلوگيري از محلي شدن پاسخها از رويکرد نخبهگرايي در اين الگوريتم استفاده شدهاست.
الگوريتم مورد استفاده با بکارگيري عمليات فازهاي خود به حل مسئله زمانبندي پروژه با محدوديت منابع ميپردازد. به منظور بررسي کارايي الگوريتم و مقايسه آن با الگوريتمهاي ديگري که به حل اين مسئله پرداختهاند، مسائل نمونه مختلف و شناخته شدهاي که در اين حوزه تعريف شدهاند، با الگوريتم پيشنهادي حل شدهاست. نتايج به دست آمده با بهترين الگوريتم هاي موجود در ادبيات موضوع مقايسه شدهاست. نتايج بدست آمده دلالت بر اين دارد که الگوريتم مورد استفاده از کارايي مطلوب و قابل رقابتي در مقايسه با الگوريتمهاي ديگر برخوردار است و نتيجه بهتري از بيشتر آنها دارد.
1-3 ساختار پژوهش
در اين پژوهش در ادامه يعني در فصل دوم، به معرفي مسئله زمانبندي پروژه با منابع محدود ميپردازيم و با فرمول هاي رياضي آن را مدل ميکنيم. سپس در فصل سوم الگوريتم TLBO را بررسي ميکنيم. در فصل چهارم، رويکردهاي سري و موازي و روشهاي پسرو و پيشرو را براي زمانبندي اوليه با مثال تشريح ميکنيم. سپس الگوريتم TLBO با رويکرد نخبهگرايانه را با مسئله زمانبندي پروژه با منابع محدود تطبيق ميدهيم و بوسيله برنامهنويسي، مسئله را حل ميکنيم. در فصل پنجم، مسايل نمونهاي که با اين الگوريتم حل شدهاند توضيح داده شدهاند. نتايج عددي بدست آمده را با توجه به پارامترهايي مانند اندازه جمعيت و حداکثر تعداد زمانبنديها بررسي مينماييم. در پايان نيز نتايج بدست آمده با الگوريتم TLBO در حل مسئله زمانبندي پروژه با منابع محدود با ديگر الگوريتمها مقايسه ميگردد.
فصل دوم:
مروري بر ادبيات تحقيق و حل مسئله
2-1 مقدمه
دراين فصل از پايان نامه ادبيات موضوع را مشخص ميکنيم و به تعريف مسئله زمانبندي پروژه با محدوديت منابع (RCPSP) ميپردازيم. ابتدا زمانبندي پروژه را بررسي ميکنيم و سپس مسئله زمانبندي پروژه با محدوديت منابع را به تفصيل تعريف ميکنيم.
2- 2 زمانبندي پروژه
زمانبندي، يکي از مسائل مهم در مرحله برنامهريزي پروژه است. زمانبندي پروژه عبارت است از تعيين زمان شروع هر يک از فعاليت هاي پروژه با توجه به محدوديتها و به منظور رسيدن به يک يا چند هدف مشخص ميباشد[1]. گاهي برنامه ريزي پروژه با برنامه زمانبندي پروژه معادل گرفته ميشوند که اين همارزي دقيق نيست. زمانبندي پروژه با توالي فعاليتها، طول عمليات و روابط آنها سروکار دارد، در صورتيکه برنامهريزي بستر بزرگتري بوده که برنامه زمانبندي جزيي از آن است. برنامه ريزي عبارت از تجهيز منابع و کليه سيستمهاي پروژه در جهت اجراي بموقع و طبق طرح و بودجه تعيين شده آن است. در اين تحقيق زمانبندي پروژه بررسي ميگردد. مهمترين اهداف زمانبندي پروژه عبارتند از[2]:
تعيين زمان شروع و پايان فعاليتها و مشخص کردن زمان پايان پروژه
تعيين ميزان منابع در دسترس و منابع استفاده شده در هر لحظه از اجراي پروژه
ارزيابي تاثير تغيير در ترتيب اجراي فعاليتها بر زمان تکميل پروژه
تصميم گيري و واکنش صحيح در مواردي که زمانبندي نشان ميدهد، زمان پايان پروژه دير است.
ارزيابي زيان ناشي از ديرکرد تکميل پروژه
تعيين جريان نقدينگي پروژه
فرض بر اين است که پروژه در حدي بزرگ است که ميتوان آن را به چند فعاليت تقسيم کرد و روابط پيشنيازي بين فعاليتها برقرار است يعني يک فعاليت زماني شروع به اجرا ميکند که فعاليتهاي پيشنياز آن اجرا شدهباشند. در دنياي واقعي پروژهها شامل صدها فعاليت هستند[2]. با استفاده از گراف (شبکه) ميتوان فعاليتهاي پروژه و روابط پيشنيازي آنها را نمايش داد. وزن هر يال زمان اجراي فعاليت انتهاي يال را مشخص ميکند. همچنين ممکن است هر فعاليت، محدوديتي به شکل زودترين زمان شروع يا ديرترين زمان پايان داشته باشد، يعني اين فعاليت بايد در يک بازه زماني مشخص انجام پذيرد. در مسائل زمانبندي در نظر گرفتن تمام محدوديتهايي که براي اجراي فعاليتها وجود دارند الزامي است. تابع هدف نيز در زمانبندي مهم است. کمترين زمان اتمام پروژه، کمترين زمان تاخير، کمترين تعداد فعاليتهايي که بعد از زمان تعيين شده به پايان ميرسند يا ترکيبي از اين موارد، نمونههايي از تابع هدف هستند.
از مهمترين تکنيکهاي زمانبندي که بطور گسترده استفاده شده است روش مسير بحراني (CPM)4 است. برنامههاي کامپيوتري و الگوريتمهاي زيادي براي زمانبندي به روش مسير بحراني موجود است. در اين روش کمترين زمان تکميل پروژه همراه با زمانهاي ممکن شروع و پايان فعاليتهاي پروژه محاسبه ميگردد. مسير بحراني، مجموعه يا ترتيبي از فعاليتهاست که بيشترين زمان اجرا را خواهند داشت. طول زمان مسير بحراني، مجموع مدت زمانهاي اجراي فعاليتهاي اين مسير است. مسير بحراني را ميتوان بعنوان طولانيترين مسير ممکن در شبکه فعاليتهاي پروژه تعريف کرد. مدت زمان اجراي فعاليتهاي مسير بحراني، حداقل زمان لازم براي تکميل پروژه را مشخص ميکند. هر تاخيري در مسير بحراني منجر به افزايش زمان تکميل پروژه ميشود[2]. پروژه ممکن است چند مسير بحراني داشته باشد. در روش مسير بحراني محدوديت منابع را در نظر نميگيريم. اين روش را در مسائل زمانبندي پروژه بدون محدوديت منابع ميتوان بکار برد. در روش مسير بحراني طول زمان اجراي هر فعاليت از قبل مشخص و بصورت ثابت در نظر گرفته ميشود، در حاليکه در بيشتر پروژهها، اينگونه نيست. روش PERT 5روش ديگري است که مانند روش مسير بحراني است، با اين تفاوت که طول زمان اجراي فعاليتها از قبل مشخص و ثابت نيست. در اين روش کمترين مدت زمان و بيشترين مدت زمان انجام هر فعاليت تخمين زده ميشود و زمان مورد انتظار محاسبه ميشود. روش PERT يک روش احتمالي است. در اين روش نيز محدوديت منابع در نظر گرفته نميشود و مناسب مسائل زمانبندي پروژه بدون محدوديت منابع است. روشهاي مذکور هر چند محدوديت منابع را رعايت نميکنند ولي به معني بدون استفاده بودن آنها در حالت محدوديت منابع نيز نيستند. مشکل تخصيص منابع وقتي بوجود ميآيد که منابع مورد نياز براي انجام هم‌زمان فعاليت‌هاي غير وابسته را نتوان تامين کرد. در اين وضعيت ناچاريم برخي فعاليتها را با تاخير اجرا کنيم. بهتر است تاخير را به فعاليتهايي دهيم که در مسير بحراني نيستند. همچنين ميزان انحراف از مسير بحراني از معيارهاي سنجش الگوريتمهاي زمانبندي است.
2-3 زمان بندي پروژه با منابع محدود
مسئله زمان بندي پروژه با منابع محدود، يك مسئله کاملا سخت6 است و براي نخستين بار در سال 1963 مطرح شد. اين مسئله يكي از پيچيده‌ترين مسائل تحقيق در عمليات است كه در دهه‌هاي اخير پيشرفتهاي قابل توجهي در تدوين روشهاي حل دقيق و ابتكاري آن به وجود آمده و اخيرا روشهاي جديد بهينه‌سازي در حل آن به كار گرفته شدهاند. در اين مسئله، پروژه به تعدادي فعاليت تجزيه مي‌شود. اين فعاليتها به لحاظ روابط منطقي متفاوتي كه حاكم بر آنهاست با يكديگر ارتباط پيدا مي‌كنند و همچنين باعث ايجاد محدوديتهايي مي گردند. يک نوع از اين روابط، رابطه تقدم- تاخر است؛ يعني اجراي برخي فعاليت ها، وابسته به اجراي چند فعاليت ديگر در پروژه است. يعني برخي فعاليتها پيش نياز برخي ديگر هستند. در اين صورت ميگوييم پروژه داراي محدوديتهاي تقدمي است. اما علاوه بر اين محدوديتها، ممکن است محدوديتهايي تحت عنوان محدوديتهاي منابع نيز در پروژه وجود داشته باشند. منظور از منابع مواردي مانند ماشين آلات و مواد اوليه و نيروي انساني و پول و سرمايه و …است. اين منابع غالباً به دو دسته تجديدشدني7 و تجديدنشدني8 تقسيم مي‌شوند. منابع تجديد نشدني مانند سرمايه را پس از استفاده ديگر نميتوان مجددا بکار برد ولي منابع تجديد شدني مانند نيروي انساني و ماشينآلات قابل استفاده مجدد هستند. در اين پاياننامه منابع تجديدشدني در نظر گرفتهشدهاند. هر فعاليت پروژه ميتواند در چندين حالت مختلف اجرا شود که اجراي هر حالت به منابع معيني نياز دارد. بنابراين در برنامهريزي پروژه علاوه بر اينکه بايد به محدوديتهاي تقدمي توجه داشت، برنامه ريزي بايد بهگونهاي انجام گيرد که با محدوديت منابع نيز سازگار باشد. در چنين مسائلي برنامه ريزي عمدتا اجراي فعاليتها به صورت پيوسته در نظر گرفته ميشود. آن دسته از مسائل برنامهريزي پروژه که محدوديتهاي منابع در آنها وجود ندارد يا در نظر گرفته نميشود به مسائل برنامه ريزي پروژه بدون محدوديت منابع و آن دسته که داراي محدوديت منابع ميباشند و اين محدوديتها در برنامهريزي پروژه در نظر گرفته ميشوند به مسائل برنامه ريزي پروژه با محدوديت منابع معروفند. اين مسئله بصورتهاي مختلف و با فرضيات متفاوت بيان شده است. در برخي مسايل، فعاليتها براي اجرا يک حالت بيشتر ندارند که به آنها تک حالته9 ميگويند و در برخي ديگر هر فعاليت چند سناريو براي اجرا دارد که به آن چندحالته10 ميگويند. در برخي مسائل امکان قبضه کردن11 وجود دارد يعني ميتوان اجراي يک فعاليت را متوقف کرد و فعاليت ديگر با اولويت بالاتر را اجرا کرد. در برخي مسائل حتي روابط پيشنيازي نيز از ابتدا مشخص نيستند و در حين اجرا مشخص ميشوند، همچنين مدت زمان اجراي فعاليتها نيز در برخي مسائل قطعي و ثابت نيستند و درحين اجراي پروژه يا بصورت تصادفي تعيين ميشوند. در اين پايان نامه مسئله زمانبندي با توجه به محدوديت منابع و تک حالته، بدون قبضه کردن، با روابط پيشنيازي و مدت اجراي معين فعاليتها بررسي ميگردد.
مسئله زمانبندي پروژه با منابع محدود، با توجه به شرايط متفاوت، به صورتهاي مختلف مدلسازي مي‌شود. در اينجا فرض مي‌كنيم پروژه به صورت يك شبكه فعاليت است و مانند گراف G=(V, E) كه در آنV مجموعه گره ها و بيانگر فعاليتهاي پروژه و E مجموعه يالها و بيانگر روابط منطقي بين فعاليتهاست، تعريف شده باشد. مجموعه فعاليتهاي پروژه را با N={0,1,2,…,n} نشان ميدهيم. فعاليتها از 0 تا n شماره‌گذاري شده‌اند. فعاليتهاي 0 وn مجازي هستند و شروع و پايان پروژه را نشان مي‌دهند. زوج مرتب (i,j) نشان دهنده اين خاصيت است که فعاليت i پيشنياز فعاليت j ميباشد، يعني فعاليت i قبل از اجراي فعاليت j بايد حتما اجرا شده باشد. مجموعه اين زوج مرتبها را با A نشان ميدهيم. مدت زمان اجراي فعاليت i را با di نشان ميدهيم. مجموعه همه منابع تجديد شدني را با R نمايش مي دهيم. در اين مجموعه K منبع متفاوت وجود دارد. ظرفيت منبع i را با Ri مشخص مي کنيم.
Ri ? R+ ? {?} ، اين ظرفيت را در طول اجراي پروژه در هر واحد زمان مي توان استفاده کرد. Ri=? يعني منبع، ظرفيت نامحدود دارد و به هرميزان قابل استفاده است. از آنجا که استفاده از هرواحد ظرفيت منبع داراي هزينه است، جهت کاهش هزينه بايد استفاده از منابع را کمينه کنيم. ميزان نياز فعاليت i به منبع k ام را با rik مشخص ميکنيم. rik ? R+، در زمان اجراي فعاليت i، ميزان rik واحد از ظرفيت منبع k ام درگير انجام فعاليت است که ديگر فعاليتها در زمان اجراي فعاليت i نميتوانند از آن استفاده کنند. rik = 0 يعني فعاليت i براي اجرا به منبع k ام نياز ندارد. پس از اجراي کامل فعاليتi ، اين ميزان ظرفيت از منبع k ام آزاد ميگردد. زمان شروع فعاليت i را Si در نظر ميگيريم. از آنجا که هر فعاليت بطور پيوسته اجرا ميگردد، زمان پايان فعاليت i، برابر با Si+ di ميباشد. بنابراين ميتوان گفت، فعاليت i در بازه[Si , Si+ di] اجرا ميشود. ميزان نياز هر فعاليت به هر منبع از کل ظرفيت آن نبايد تجاوز کند. يعني براي همه فعاليتها و منابع رابطه زير برقرار است:
rik ? Rk i ? N , k=1,2,…,K (2-1)
از آنجا که فعاليتهاي 0 , n مجازي هستند و فقط شروع و پايان پروژه را مشخص مي کنند، براي آنها روابط زير را داريم:
هيچ فعاليتي قبل از فعاليت 0 اجرا نميگردد. يعني هيچ فعاليتي پيش نياز فعاليت 0 نيست.
( i,0) ? A i=1,2,…,n (2-2)
فعاليت 0 زودتر از همه فعاليتها اجرا ميگردد يعني پيشنياز همه فعاليتهاست.
( 0,i) ? A i=1,2,…,n (2-3)
فعاليت n پيشنياز هيچ فعاليتي نيست.
( n ,i) ? A i=0,1,2,…,n-1 (2-4)
همه فعاليتها پيشنياز فعاليت n هستند و قبل از فعاليت n انجام ميگيرند.
( i,n) ? A i=0,1,2,…,n -1 (2-5)
زمان اجراي فعاليتهاي 0 و n ،صفراست.
d0=dn=0



قیمت: تومان


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