دانلود پایان نامه:زمانبندی دروس دانشگاهی تک هدفه و چند هدفه مبتنی بر ترجیحات اساتید، دانشجویان و دانشگاه

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

عنوان : زمانبندی دروس دانشگاهی تک هدفه و چند هدفه مبتنی بر ترجیحات اساتید، دانشجویان و دانشگاه

وزارت علوم، تحقیقات و فناوری

دانشگاه علوم و فنون مازندران

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

رشته: مهندسی سیستم­های اقتصادی و اجتماعی

عنوان: زمانبندی دروس دانشگاهی تک هدفه و چند هدفه مبتنی بر ترجیحات اساتید، دانشجویان و دانشگاه

استاد راهنما:  آقای دکتر مصطفی زندیه

استاد مشاور:  آقای دکتر ایرج مهدوی

(تابستان 1392 )

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

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

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

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

فهرست

 فصل اول: مقدمه وکلیات تحقیق… 1

1-1-مقدمه. 2

1-2- بیان مسأله. 2

1-3- ضرورت تحقیق.. 6

1-4- اهداف تحقیق.. 6

1-5- سئوالات تحقیق.. 7

1-6- جمع­بندی.. 7

فصل دوم :  ادبیات و پیشینه تحقیق.. 8

2-1-مقدمه. 9

2-2- طبقه­بندی مسائل جدول زمانی.. 10

2-3- جدول زمانی دروس دانشگاهی.. 11

2-3-1- محدودیت­های سخت  جدول زمانی دروس دانشگاهی.. 12

2-3-2- محدودیت­های نرم جدول زمانی دروس دانشگاهی.. 13

2-3-3- روش­های حل جدول زمانی دروس دانشگاهی.. 17

2-4- انواع روش­های حل مسائل بهینه­سازی.. 23

2-4-1- روش­های بهینه سازی ترکیبی.. 24

2-4-1-1- الگوریتم­های فراابتکاری.. 25

2-5-  الگوریتم جستجوی ممنوعه (TS). 28

2-5-1- همسایگی.. 29

2-5-2- لیست ممنوعه. 29

2-5-3- معیار آرمانی.. 30

2-5-4- استراتژی لیست کاندید.. 31

2-5-5- استراتژی تقویت… 32

2-5-6- استراتژی تنوع بخشی.. 32

2-5-7- معیار توقف…. 33

2-6- الگوریتم جستجوی متغیر همسایگی (VNS). 34

2-6- 1- فرآیند ارتعاش…. 35

2-6- 2- فرآیند جستجوی محلی.. 36

2-7- مدل­های بهینه سازی چند هدفه. 37

2-7-1- مفهوم غلبه در مسائل بهینه سازی چندهدفه. 38

2-8- الگوریتم چند هدفه ژنتیک (NSGA II). 38

2-9- فرآیند تحلیل سلسه مراتبی (AHP). 42

2-9-1- درخت سلسه مراتبی.. 42

2-9-2- انجام مقایسات زوجی.. 43

2-9-3- محاسبه ضرایب اهمیت… 44

2-9-4- تعیین امتیاز نهایی گزینه­ها 45

2-9-5- بررسی سازگاری سیستم.. 45

2-10- جمع­بندی.. 48

فصل سوم: روش تحقیق.. 49

3-1-  مقدمه. 50

3-2-  جدول زمانی دروس دانشگاهی مبتنی بر ترجیحات اساتید، دانشجویان و دانشگاه. 50

3-2-1- مفروضات مسأله ارائه شده. 51

3-2-2-  مهمترین تصمیمات اتخاذ شده در مدل ارائه شده. 52

3-3-  روش جمع آوری اطلاعات… 52

3-4-  الگوریتم­های تکاملی مورد استفاده. 52

3-5-  مدل ریاضی.. 53

3-5-1- محدودیت­های سخت… 53

3-5-2- محدودیت­های نرم. 54

3-5-3- پارامترها و مجموعه­های مدل.. 55

3-5-4- متغیر تصمیم.. 56

3-6-  مدل ریاضی تک هدفه. 56

3-7-  تشریح مدل ریاضی.. 57

3-8- الگوریتم جستجوی ممنوعه (TS). 57

3-8- 1- نحوه نمایش جواب… 58

3-8-2- تولید جواب اولیه. 59

3-8-3- همسایگی.. 59

3-8-4- لیست ممنوعه. 59

3-8-5- معیار آرمانی.. 60

3-8-6- استراتژی لیست کاندید.. 60

3-8-7- استراتژی تقویت… 61

3-8-8- استراتژی تنوع بخشی.. 61

3-8-9- معیار توقف…. 62

3-9-  الگوریتم جستجوی همسایگی متغیر در جستجوی ممنوعه (TS-VNS). 64

3-9-1- استراتژی­های ساختار همسایگی.. 64

3-10-  فرآیند تحلیل سلسه مراتبی (AHP). 67

3-10-1- درخت سلسه مراتبی.. 69

3-10-2-  انجام مقایسات زوجی.. 69

3-10-3- محاسبه ضرایب اهمیت… 70

3-10-4- تعیین امتیاز نهایی گزینه­ها 70

3-10-5- بررسی سازگاری سیستم.. 70

3-11-  مدل ریاضی چند هدفه. 71

3-12-  الگوریتم ژنتیک چند هدفه (NSGA II). 73

3-12-1-  نحوه نمایش جواب و جمعیت اولیه. 73

3-12-2-  انتخاب… 74

3-12-3- تقاطع. 74

3-12-4- جهش…. 77

3-12-5-  معیار توقف…. 78

3-13-  الگوریتم جستجوی ممنوعه چند هدفه (MOTS). 79

3-14-  جمع­بندی.. 81

فصل چهارم: محاسبات و یافته­های تحقیق.. 82

4-1-  مقدمه. 83

4-2-  تنظیم پارامترهای الگوریتم­های فراابتکاری.. 83

4-3-  اجرای الگوریتم­ها 86

4-4-  نتایج محاسباتی الگوریتم­های مدل تک هدفه و تجزیه و تحلیل آنها 86

4-4-1- تحلیل نتایج بهترین مقدار تابع هدف… 87

4-4-2- تحلیل نتایج اولین زمان رسیدن به بهترین مقدار تابع هدف… 89

4-5-  نتایج محاسباتی الگوریتم­های مدل چند هدفه و تجزیه و تحلیل آنها 91

4-5-1- تحلیل نتایج شاخص میانگین فاصله از نقطه ایده آل (MID). 92

4-5-2- تحلیل نتایج شاخص تعداد جوابهای آرشیو پاراتو. 95

4-5-3- تحلیل نتایج شاخص یکنواختی پاراتو. 98

4-5-4- تحلیل نتایج شاخص پوشش مجموعه. 100

4-5-5- تحلیل نتایج شاخص بیشترین گستردگی.. 102

4-5-6- تحلیل نتایج زمان اجرای الگوریتمها 104

4-6-  جمع­بندی.. 106

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

5-1-  نتیجه­گیری.. 109

5-2-  پیشنهادها برای تحقیقات آتی.. 110

5-2-1-  تحقیقات مربوط به گسترش مدل مسأله. 110

5-2-2-  تحقیقات مربوط به رویکرد حل مسأله. 111

مراجع.. 112

 

 

 

 

فهرست جداول

جدول 2-1. محدودیت­های نرم و سخت بکار رفته در تحقیقات گذشته. 16

جدول 2-2. فهرست الگوریتم­های مبتنی بر یک جواب و الگوریتم­های مبتنی بر جمعیت… 26

جدول 2-3. مقیاس نه کمیتی ساعتی برای مقایسات زوجی.. 43

جدول 2-4. شاخص تصادفی بودن R.I. 47

جدول3-1. پارامترها و مجموعه ها 55

جدول 3-2. مشخصات ماتریس های جواب… 58

جدول 3-3. عناصر الگوریتم جستجوی ممنوعه. 62

جدول 4-1. پارامترهای الگوریتم TS. 85

جدول 4-2. پارامترهای الگوریتم TS-VNS. 85

جدول 4-3. پارامترهای الگوریتم NSGA II. 85

جدول 4-4. پارامترهای الگوریتم MOTS. 85

جدول4-5. پارامترهای استفاده شده در فرمول (4-1). 87

جدول 4-6. داده­های نرمالایز شده بهترین مقدار تابع هدف در دو الگوریتم TS, TS-VNS. 88

جدول 4-7. داده­های نرمالایز شده اولین زمان رسیدن به بهترین مقدار تابع هدف در دو الگوریتم TS, TS-VNS. 90

جدول 4-8. نتایج محاسبه شاخص MID برای دو الگوریتم MOTS, NSGA II. 93

جدول 4-9. خروجی بدست آمده از آزمون­های فرض Tn-1  برای شاخص MID.. 95

جدول 4-10. نتایج محاسبه شاخص تعداد جواب های آرشیو پاراتو برای دو الگوریتم MOTS, NSGA II. 96

جدول 4-11. خروجی بدست آمده از آزمون­های فرض tn-1  برای شاخص تعداد جواب­های پاراتو. 97

جدول 4-12. نتایج محاسبه شاخص یکنواختی پاراتو برای دو الگوریتم MOTS, NSGA II. 99

جدول 4-13. خروجی بدست آمده از آزمون­های فرض tN-1  برای شاخص بیشترین گستردگی.. 100

جدول 4-14. نتایج محاسبه شاخص پوشش مجموعه  برای دو الگوریتم MOTS, NSGA II. 101

جدول 4-15. نتایج محاسبه شاخص بیشترین گستردگی برای دو الگوریتم MOTS, NSGA II. 103

جدول 4-16. خروجی بدست آمده از آزمون­های فرض tn-1  برای شاخص بیشترین گستردگی.. 104

جدول 4-17. نتایج زمان اجرای دو الگوریتم  MOTS, NSGA II. 105

جدول 4-18. خروجی بدست آمده از آزمون­های فرض tn-1  برای زمان اجرای دو الگوریتم MOTS, NSGA II. 105

 

فهرست اشکال

شکل 2-1. انواع روش­های حل برای مسائل بهینه سازی.. 24

شکل 2-2. نمودار درختی الگوریتم­های فراابتکاری.. 27

شکل 2-3. شبه کد الگوریتم فراابتکاری جستجوی ممنوعه (TS) 33

شکل 2-4. نمای شماتیک جستجوی همسایگی در الگوریتم VNS. 35

شکل 2-5. شبه کد الگوریتم فراابتکاری جستجوی همسایگی متغیر(VNS) 36

شکل 2-6. شبه کد الگوریتم فراابتکاری NSGA II. 41

شکل 3-1. فلوچارت جستجوی ممنوعه پیشنهادی.. 63

شکل 3-2. چهار استراتژی بکار رفته در الگوریتم های TS, TS-VNS. 65

شکل 3-3. فلوچارت الگوریتم TS-VNS. 66

شکل 3-4. فلوچارت الگوریتم فرایند تصمیم گیری AHP. 68

شکل 3-5. فلوچارت درخت سلسله مراتبی.. 69

شکل 3-6. فرایند تقاطع در الگوریتم NSGA II. 76

شکل 3-7. فرایند جهش در الگوریتم NSGA II. 77

شکل 3-8. فلوچارت الگوریتم NSGA II. 78

شکل 3-9 فلوچارت الگوریتم MOTS. 80

شکل 4-1. نمودار میانگین و فاصله اطمینان 95% بهترین مقدار تابع هدف TS, TS-VNS. 89

شکل 4-2. نمودار میانگین و فاصله اطمینان 95% اولین زمان رسیدن به بهترین مقدار تابع هدف TS, TS-VNS. 91

شکل 4-3. نمودارهای همگرایی دو الگوریتم  برای مسائل در سه سایز کوچک، متوسط و بزرگ…. 94

 

فصل اول

 مقدمه وکلیات تحقیق

 

1-1-مقدمه

امروزه زمانبندی جزء ضروریات اجتناب ناپذیر زندگی بشری است. در برنامه­های کلان کشورهای توسعه یافته، یکی از بخش­هایی که در نیل به تحقق برنامه­ها و اهدافشان نقش به سزا و مؤثری ایفا کرده، نظام آموزشی است. بنابراین با توجه به نقش کلیدی نظام آموزشی در هر جامعه، می­توان به اهمیت برنامه­ریزی درست و مناسب در این سیستم پی برد. به طوری که یک زمانبندی مناسب سبب ارتقای کیفیت آموزشی و رضایتمندی کارکنان می­باشد. جدول زمانی[1] نوع خاصی از مسأله زمانبندی است. مسأله زمانبندی در دانشگاه­ها به دو دسته جدول زمانی برای امتحانات و زمانبندی دروس تقسیم می­شود. مقصود از زمانبندی در این تحقیق، دسته دوم است. در این تحقیق تلاش شده است که تا حد امکان از مقالات اخیر در حوزه جدول زمانی، بویژه جدول زمانی دروس دانشگاهی و همچنین مقالات مربوط به روش­های حل فراابتکاری استفاده شود تا بیان نوین و کارا با اثربخشی مناسب ایجاد گردد.

 

1-2- بیان مسأله

جدول زمانی نوع خاصی از مسأله زمانبندی است، در سال 1996، آقای رن[2] تهیه جدول زمانی را بعنوان مسئله قرار دادن منابع خاص، با توجه به محدودیت­ها، در تعداد محدودی بازه زمانی و مکان، با هدف ارضاء مجموعه­ای از اهداف تا حد ممکن توصیف کرد. این تعریف عمومی توصیفی از مسائل تهیه جدول زمانی است که به طور کلی پذیرفته شده است.

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

جدول زمانی دروس دانشگاهی[3] عبارت از تخصیص تعداد معینی از منابع مانند اساتید و دروس، به تعداد محدودی از دوره­های زمانی و کلاس در یک دوره مشخص با توجه به مجموعه­ای از محدودیت­ها، جهت رسیدن به یکسری از اهداف مشخص است. معمولاً در این نوع مسائل محدودیت­ها به دو دسته سخت و نرم تقسیم می­شوند. محدودیت­های سخت، محدودیت­هایی هستند که حتماً باید برآورده شوند و شدنی بودن جواب را تضمین می­کنند و محدودیت­های نرم بیان کننده مطلوبیت و ترجیحات مسأله هستند که برای کیفیت بهتر جدول زمانی در نظر گرفته می­شوند و حتماً لزومی ندارد که همانند محدودیت­های سخت به طور کامل برآورده شوند. برای بدست آوردن یک جدول زمانی باکیفیت، باید مسأله شدنی و کمترین تعداد تجاوز را در محدودیت­های نرم داشته باشیم [4].

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

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

  1. یک منبع (درس، استاد، دانشجو) نمی­تواند در آن واحد در چند جا (کلاس، پریود زمانی) استفاده شود.
  2. در هر دوره زمانی باید منابع در دسترس برای مواردی که زمانبندی شده­اند کافی باشد.

اما محدودیت­های نرم با توجه به نوع و ترجیحات، برای هر مسأله متفاوت است. ما در این تحقیق ترجیحات اساتید، دانشجویان و دانشگاه را مد نظر قرار داده­ایم.

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

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

تحقیق و جستجو درباره زمانبندی ماشینی دروس به دهه 60 میلادی برمی­گردد. بیشتر این روش­ها، به نوعی شبیه­­سازی نحوه زمانبندی توسط نیروی انسانی است. در این روش­ها، ابتدا مفیدترین دروس زمانبندی می­شوند. سپس دروس با اولویت کمتر، به طور متناوب به جدول زمانی ناتمام اضافه شده تا اینکه تمام دروس زمانبندی شوند. پس از آن محققان به بررسی روش­های عمومی­تر پرداختند مانند روشهای برنامه­ریزی عدد صحیح، جریان شبکه، رنگ آمیزی گراف و …. در دو دهه آخر، تلاش­ها بر روی روش­ها ابتکاری و فراابتکاری متمرکز شده است [5].

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

مفاهیم استفاده شده در جدول زمانی دروس دانشگاهی به شرح ذیل است:

رویداد: فعالیتی که باید زمانبندی شود، مانند: جلسات درسی.

برش زمانی: یک تعداد بازه زمانی، که هر یک از رویدادها در آن بازه­های زمانی، زمانبندی می­شوند.

منبع: منابعی که توسط رویدادها مورد نیاز است، مانند: کلاس­ها.

قید: یک محدودیت برای زمانبندی رویدادها، مانند: ظرفیت کلاس درسی.

افراد: کسی یا کسانی که همراه با رویدادها وجود دارند، مانند: اساتید، دانشجویان.

برخورد: اگر دو رویداد با یکدیگر برخورد داشته باشند، مانند: زمانبندی بیش از یک درس در یک کلاس در یک زمان یکسان.

[1]. Timetabling

[2]. Wren

[3]. University Course Timetabling

تعداد صفحه :129

قیمت : 14000تومان

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

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

پشتیبانی سایت :        09361998026        info@arshadha.ir

در صورتی که مشکلی با پرداخت آنلاین دارید می توانید مبلغ مورد نظر برای هر فایل را کارت به کارت کرده و فایل درخواستی و اطلاعات واریز را به ایمیل ما ارسال کنید تا فایل را از طریق ایمیل دریافت کنید.

شماره کارت :  6037997263131360 بانک ملی به نام محمد علی رودسرابی

11

مطالب مشابه را هم ببینید

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