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

 

بنابراین، لزوم در نظر گرفتن متغیر­های متناظر با دروس، اساتید، کلاس­ها، روزهای هفته و ساعات قابل برنامه ­ریزی در روز سبب می­شود که با یک مسئله­ برنامه ­ریزی ریاضی از نوع برنامه ­ریزی غیر­خطی با اعداد صحیح و با ابعاد بزرگ مواجه باشیم­که­حتی نرم­افزار­های قوی نیز نمی­توانند آن را در زمان کم حل کنند، بنابراین الگوریتم­های فرا­ابتکاری مورد توجه قرار گرفته­اند که بتوانند مسائل بهینه­سازی با ابعاد بزرگ را با زمان اجرای مناسب تا حدودی حل کنند. مبنای اجرای تحقیق حاضر، حل مسئله زمان­بندی با بهره گرفتن از تکنیک الگوریتم ژنتیک و استفاده از نرم­افزار 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- اهمیت و ضرورت تحقیق

 

مسئله زمان­بندی کلاس­های دانشگاه، چالشی جدی برای مدیران دانشگاهی در هر نیم­سال تحصیلی است، زیرا در این­گونه مسائل با محدودیت­های فراوانی مواجه خواهیم