پایان نامه مدل سازی دومرحله ای با الگوریتم ژنتیک برای حل مسئله برنامه ریزی دروس دانشگاهی

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

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

گروه مدیریت

 عنوان:

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

استاد مشاور:

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

مهرماه 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 تومان

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

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

پشتیبانی سایت  [email protected]

background