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

پایان نامه کارشناسی ارشد دانشکده علوم انسانی  

گروه مدیریت

 عنوان:

مدل­سازی دومرحله­ای با الگوریتم ژنتیک برای حل مسئله برنامه­ریزی دروس دانشگاهی(مورد مطالعه: دانشکده علوم انسانی دانشگاه علم و هنر یزد)

استاد مشاور:

دکتر علیرضا ناصر صدرآبادی

مهرماه 1392

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

(در فایل دانلودی نام نویسنده و استاد راهنما موجود می باشد)

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

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

چکیده:

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

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

کلمات کلیدی: مدل زمان­بندی دروس دانشگاهی- ترجیحات اساتید- الگوریتم ژنتیک- محدودیت سخت- محدودیت نرم

فهرست مطالب

عنوان                                                                                                                                صفحه

 فصل اول: کلیات………………………………………………………………………………………………………………………………. 1

1-1- مقدمه ……………………………………………………………………………………………………………………………… 2

1-2- اظهار موضوع ……………………………………………………………………………………………………………………… 3

1-3- اهمیت و ضرورت پژوهش ……………………………………………………………………………………………………. 4

1-4- تعریف مسئله …………………………………………………………………………………………………………………… 5

1-5- اهداف پژوهش …………………………………………………………………………………………………………………… 6

1-6- سؤالات اساسی پژوهش ………………………………………………………………………………………………………. 6

1-7- قلمرو پژوهش ……………………………………………………………………………………………………………………. 6

1-8- روش انجام پژوهش …………………………………………………………………………………………………………….. 7

1-9- موردها کاربرد پژوهش …………………………………………………………………………………………………………… 9

1-10- تبیین اصطلاحات و واژه­های به کار­گرفته در پژوهش …………………………………………………………….. 9

1-11- محدودیت­های پژوهش …………………………………………………………………………………………………… 10

1-12- اختصار و جمع­بندی ……………………………………………………………………………………………………… 10

فصل دوم: ادبیات پژوهش………………………………………………………………………………………………………………. 11

2-1-  مقدمه…………………………………………………………………………………………………………………………… 12

2-2-  تعاریف و مبانی نظری ……………………………………………………………………………………………………. 13

      2-2-1- برنامه­ریزی دروس دانشگاهی ………………………………………………………………………………… 13

      2-2-2- مسائل NP-complete  ……………………………………………………………………………………… 15

       2-2-3- روش­های بهینه­سازی…………………………………………………………………………………………… 17

         2-2-3-1-روش­های ریاضی(دقیق) ………………………………………………………………………………… 17

         2-2-3-2- روش­های تقریبی …………………………………………………………………………………………. 18

      2-2-4- معرفی الگوریتم ژنتیک ………………………………………………………………………………………… 21

          2-2-4-1- انواع الگوریتم­های ژنتیکی…………………………………………………………………………….. 30

         2-2-4-2- مزایای الگوریتم­های ژنتیکی…………………………………………………………………………… 31

         2-2-4-3- محدودیت­های الگوریتم­های ژنتیکی ………………………………………………………………. 32

        2-2-4-4- استراتژی­های برخورد با محدودیت­های ژنتیکی ………………………………………………… 33

        2-2-4-5- بهبود الگوریتم­های ژنتیکی……………………………………………………………………………… 34

        2-2-4-6- چند نمونه از کاربردهای الگوریتم­های ژنتیکی …………………………………………………. 34

2-3- پیشینه پژوهش ……………………………………………………………………………………………………………….. 35

    2-3-1-مروری بر تاریخچه…………………………………………………………………………………………………… 35

    2-3-2- مطالعات داخلی …………………………………………………………………………………………………….. 37

    2-3-3- مطالعات خارجی …………………………………………………………………………………………………… 44

 2-4- اختصار و جمع­بندی ………………………………………………………………………………………………………. 55

فصل سوم: روش پژوهش ………………………………………………………………………………………………………………. 56

3-1- مقدمه …………………………………………………………………………………………………………………………… 57

3-2-روش پژوهش ……………………………………………………………………………………………………………………. 57

3-3- نوآوری­های پژوهش…………………………………………………………………………………………………………… 58

3-4- جامعه و نمونه آماری……………………………………………………………………………………………………….. 58

3-5- اطلاعات کلی مورد نیاز در مسائل برنامه­ریزی دروس دانشگاهی ………………………………………….. 59

3-6- معرفی محدودیت­های سخت و نرم در مسائل بهینه­سازی…………………………………………………….. 60

3-7- مفروضات کلی مسائل برنامه­ریزی دروس دانشگاهی …………………………………………………………… 61

3-8- تعریف کلی مسئله برنامه­ریزی دروس دانشگاهی ……………………………………………………………….. 63

3-9- تعریف مدل پیشنهادی مسئله برنامه­ریزی دروس دانشگاهی  ………………………………………………. 65

3-10- روش­های حل مدل پیشنهادی مسئله برنامه­ریزی دروس دانشگاهی …………………………………… 68

    3-10-1- الگوریتم­های ژنتیک …………………………………………………………………………………………….. 68

    3-10-2- شبه کد الگوریتم در مدل پیشنهادی …………………………………………………………………….. 69

    3 -10-3- تابع برازندگی و عملگرهای ژنتیکی ………………………………………………………………………. 71

3-11- معرفی نرم افزار ……………………………………………………………………………………………………………. 72

3-12-اختصار و جمع­بندی………………………………………………………………………………………………………… 72

فصل چهارم: تجزیه و تحلیل داده­ها …………………………………………………………………………………………….. 73

4-1- مقدمه…………………………………………………………………………………………………………………………….. 74

4-2- اظهار مسئله…………………………………………………………………………………………………………………….. 74

4-3- نمایش ریاضی مدل پیشنهادی مسئله برنامه­ریزی دروس دانشگاهی ……………………………………. 75

  4-3-1-تابع هدف مدل اول   …………………………………………………………………………………………………. 75

  4-3-2- محدودیت­های مدل اول ……………………………………………………………………………………………. 77

  4-3-3- مدل دوم …………………………………………………………………………………………………………………. 81

4-4- نتایج حل مدل پیشنهادی مسئله برنامه­ریزی دروس دانشگاهی …………………………………………… 83

4-5- اختصار و جمع­بندی ……………………………………………………………………………………………………… 102

فصل پنجم: نتیجه گیری و پیشنهاد­ها………………………………………………………………………………………… 103

5-1- مقدمه………………………………………………………………………………………………………………………….. 104

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

5-3- پیشنهاد­­ها…………………………………………………………………………………………………………………….. 107

  5 -3- 1- پیشنهاد­های کاربردی……………………………………………………………………………………………. 107

  5-3- 2- پیشنهاد­ها برای تحقیقات آتی…………………………………………………………………………………. 108

پیوست­ها ……………………………………………………………………………………………………………………………………. 109

پیوست (الف)- جدول ترجیحات اساتید……………………………………………………………………………………. 110

پیوست (ب)- کد نوشته شده در نرم­افزار، برای گروهی با همه محدودیت­ها………………………………….. 111

 فهرست مراجع ………………………………………………………………………………………………………………………….. 117

مقدمه

مسئله­های زمان­بندی و برنامه­ریزی، سازگارسازی و متناسب کردن مجموعه­ای از نهاد­ها مانند رخدادها، فعالیت­ها، افراد، ابزار و دستگاه­ها، خودروها، مکان­ها و مانند این­ها در یک الگوی مکان- زمان می باشد. در این دسته از مسئله­ها هدف این می باشد که منابع در دسترس به بهترین روش ممکن مورد بهره­برداری قرار گیرند و محدودیت­ها و شرایط موجود مورد توجه قرار گرفته و برآورده شوند (مسعودیان و استکی، 1388). مسائل زمان­بندی ماهیتاً مسائل پویایی بوده و لحاظ کردن انواع انعطاف پذیری­ها منجر به رفع معضلات گلوگاهی، بهبود عملکرد سیستم و ایجاد مزیت رقابتی می­شوند (نهاوندی و عباسیان، 1389). زمان­بندی کلاس­ها در سطح دانشگاه بسیار پیچیده می باشد، این به آن علت می باشد که در زمان­بندی کلاس­های دانشگاه، عامل­های زیادی اثرگذار هستند و شمار و انواع زیادی از محدودیت­ها نیز بایستی برآورده شوند (بابایی زاده، 1390).

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

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

1-2- اظهار موضوع

با در نظر داشتن تعداد روزافزون دانشجویان، رشته­های جدید، کمبود کلاس­ها، اتاق­های کنفرانس و آزمایشگاه­ها و تعداد رو به افزایش درس­های ارائه شده برای دانشجویان، برنامه­ریزی با محدودیت­های بسیاری برای ساخت یک جدول مناسب مواجه خواهد بود (مسعودیان و استکی، 1388).

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

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

این مطلب رو هم توصیه می کنم بخونین:   پایان نامه بررسی تاثیر تغییرات شاخص بازار سهام و نرخها ی ارز و سود  بانکی بر رفتار سپرده گذاران و عملکرد مالی در  صنعت بانکداری

مسئله برنامه­ریزی دروس دانشگاهی مانند مسائل NP-hard می باشد که به لحاظ تاثیر عوامل بسیار و وجود محدودیت­های مختلف از مشهورترین مسائل بهینه­سازی می باشد (راستگارامینی، 1391). یکی از دسته­های خاص مسائل زمان بندی را جدول­بندی زمانی می­نامند. جدول­بندی زمانی، در واقع زمان­بندی مجموعه­ای از رویدادهای هم­پیوند، در کم­ترین بازه­های زمانی می باشد به گونه­ای که منابع مورد نیاز، همزمان توسط بیش از یک رویداد بهره گیری نشوند (دتین و همکاران، 2009.م).

در این مسئله کوشش بر این می باشد که مجموعه­ای از منابع معین، متشکل از کلاس­ها، اساتید و دروس تحت شرایط خاص به مجموعه­ای از ساعت­های درسی اختصاص یابد (خلیلی و منصورزاده، 1385). با در نظر داشتن توضیحات و پیچیدگی مسئله، روش­های مختلفی برای حل این مسئله در مقالات مختلف پیشنهاد شده می باشد (غافری، 1387)، مانند برنامه­ریزی­های خودکار (باشی زاده، 1391) و در نظرگیری معیار­های ارزیابی نظیر ترجیحات اساتید ­(­اولویت زمانی و اولویت درسی­) و رعایت محدودیت­هایی مانند تعداد ظرفیت کلاس­ها می­باشد (راستگار­امینی، 1391).

در مسئله زمان­بندی کلاس­های دانشگاه، این محدودیت­ها به دو دسته محدودیت­های سخت و محدودیت­های نرم گروه بندی می­شوند. محدودیت­های سخت، محدودیت­هایی هستند که در هر زمان­بندی، بایستی رعایت شوند. اگر یک زمان­بندی، این دسته از محدودیت­ها را نقض کند، آن وقت­بندی پذیرفتنی نخواهد بود. هر چه این محدودیت­ها بیشتر برآورده شوند، زمان­بندی به دست آمده از مطلوبیت بیشتری برخوردار خواهد بود (بابایی زاده، 1390).

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

 1-3- اهمیت و ضرورت پژوهش

مسئله زمان­بندی کلاس­های دانشگاه، چالشی جدی برای مدیران دانشگاهی در هر نیم­سال تحصیلی می باشد، زیرا در این­گونه مسائل با محدودیت­های فراوانی مواجه خواهیم بود، تمامی محققان در این زمینه اتفاق نظر دارند که مسئله جدول­های زمانی دارای فضای پاسخ نمایی بوده و مانند تمامی مسائل NP-hard  نیاز به بهره گیری از الگوریتم­های هوشمند جهت حل آن اجتناب ناپذیر می باشد (غافری، 1387).

دستیابی به یک برنامه زمان­بندی پذیرفتنی که محدودیت­های سخت را برآورده نماید و بتواند محدودیت­های نرم را تا حد ممکن برآورده کند، کاری بس دشوار و بسیار زمان­بر می باشد (بابایی زاده، 1390). در مورد محدودیت­های سخت می­توان به قوانین و مقررات آموزشی تصریح نمود که این گونه محدودیت­ها حتماً بایستی در نظر

 

گرفته شوند زیرا  نشان­دهنده اهمیت چگونگی برنامه­ریزی درسی می­باشد (حاجی یخچالی، 1378)، و رعایت نکردن این قوانین و مقررات به عنوان محدودیت­های سخت نشان­دهنده نامعتبر بودن برنامه درسی می­باشد (دهقانی و ذاکر تولائی، 1385 ).

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

1-4-­تعریف مسئله

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

1-5-­اهداف پژوهش

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

  • دستیابی به مدلی با در نظرگرفتن ترجیحات اساتید
  • یافتن بازه­های زمانی مناسب با رعایت کردن حداقل فاصله بین بازه ها برای دروس هر گروه

1-6-سوالات پژوهشی

در این پژوهش به سوالات زیر پاسخ داده می­گردد:

  • با در نظر داشتن محدودیت­های مسئله زمان­بندی دروس دانشگاهی چه مدلی مناسب می باشد؟
  • کدام بازه­های زمانی به عنوان جواب نهایی مدل، به دست آمده و مطلوب می باشند؟

1-7-قلمرو پژوهش

قلمرو پژوهش در سه بعد موضوعی، مکانی و زمانی در این پژوهش به تبیین زیر می­باشد:

قلمرو موضوعی: قلمرو موضوعی این پژوهش  بر اساس مسئله زمان­بندی برای دروس دانشگاهی می­باشد که این دسته مسائل جزء مسائل بسیار سخت و پیچیده شناخته شده­اند و برای حل این­گونه مسائل نیاز به مدل­سازی­های ریاضی می­باشد که بتوان تمامی محدودیت­های نرم و سخت را در آن گنجاند و به دلیل زیاد بودن متغیرها نیاز به بهره گیری از الگوریتم­های هوشمند و فراابتکاری می­باشد. در این پژوهش پس از نوشتن مدل از الگوریتم ژنتیک برای حل مدل بهره گیری شده می باشد.

قلمرو مکانی: قلمرو مکانی این پژوهش دانشکده فنی- مهندسی دانشگاه علم و هنر یزد می باشد، که با در نظر داشتن وجود مقاطع کارشناسی و کارشناسی ارشد این دانشکده، 4 گروه­ از مقاطع کارشناسی ارشد سال 1391 انتخاب

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

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

1-8-روش انجام پژوهش

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

تعداد صفحه :139

قیمت :37500 تومان

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

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

پشتیبانی سایت  serderehi@gmail.com

دسته‌ها: رشته مدیریت