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

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

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

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

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

عنوان:

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

استاد راهنما:

آقاي دكتر مصطفی زندیه

استاد مشاور:

آقاي دكتر ایرج مهدوی

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

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

فهرست مطالب:

فصل اول: مقدمه وکلیات پژوهش…………………….. 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)…………………….

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)…………………….

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

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

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

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

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

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

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)…………………….

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)…………………….

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

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

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)…………………….

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

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

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

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

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

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

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)………………….

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

چکیده:

در این پایان­نامه، یک مدل برای مسأله زمانبندی دروس دانشگاهی به دو صورت تک هدفه و دو هدفه ارائه شده می باشد. هدف این مسأله تهیه جدول زمانی دروس دانشگاهی مناسب و قابل قبول، با در نظر گرفتن مجموعه­ای از محدودیت­ها و ترجیحات اساتید، دانشجویان و دانشگاه با در نظر داشتن فضای آموزشی در ایران می باشد. در مسائل جدول زمانی محدودیت­ها به دو دسته سخت و نرم تقسیم می­شوند. محدودیت­های سخت بایستی برآورده شوند و شدنی بودن جواب را تضمین می­کنند و محدودیت­های نرم که اظهار کننده مطلوبیت و ترجیحات مسأله هستند که برای کیفیت بهتر جدول زمانی در نظر گرفته    می­شوند. برای بدست آوردن یک جدول زمانی با کیفیت، بایستی مسأله شدنی و کمترین تعداد تجاوز را در محدودیت نرم داشته باشیم. با در نظر داشتن NP-Hard بودن مسأله، برای حل مدل­ها از الگوریتم­های فرا ابتکاری بهره گیری شده می باشد. در مدل تک هدفه از الگوریتم جستجوی ممنوعه (TS) و الگوریتم جستجوی همسایگی متغیر در جستجوی ممنوعه (TS-VNS) برای حل مدل بهره گیری شده می باشد. با بهره گیری از فرآیند تصمیم­گیری AHP، جدول­های زمانی بدست آمده از الگوریتم­های فراابتکاری، رتبه­بندی و گزینه برتر انتخاب می­گردد. در مدل دو هدفه از الگوریتم ژنتیک چند هدفه (NSGA II) و الگوریتم جستجوی ممنوعه چند هدفه (MOTS) بهره گیری شده می باشد. همچنین در هر بخش با مقایسه عملکرد الگوریتم­ها، کارایی آنها ارزیابی شده می باشد.

فصل اول: مقدمه و کلیات پژوهش

1-1- مقدمه

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

2-1- اظهار مسأله

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1-3-­ ضرورت پژوهش

شما می توانید مطالب مشابه این مطلب را با جستجو در همین سایت بخوانید                     

از آنجایی که زمانبندی دستی وقتگیر بوده و لزوماً تمام خواسته­ها و ترجیحات اساتید، دانشجویان و دانشگاه را پوشش نمی­دهد و همچنین با افزايش روز افزون رشته­ها، گرایشات، تنوع دروس، افزایش تعداد دانشجویان و محدود بودن منابع در يك دانشگاه، كار زمانبندي دروس را دشوار می­نماید. همه این عوامل ضرورت بهره گیری از روش­های مدل­سازی و حل کامپیوتری که در زمان بسیار کمتری جواب خوبی فراهم می­آورند، را دو چندان می­کند. با در نظر داشتن این که در دنیای واقعی، مشخصات و ابعاد مسأله فوق گوناگونی و محدودیت­های زیادی دارد، در نظر گرفتن تمام این خصوصیات منجربه فضای حل بسیار بزرگی می­گردد که این مسأله را تبدیل به یک مسأله NP-Hard کرده [6]، و در بعضی منابع نیز این مسأله به عنوان یک مسأله NP-Complete معرفی شده می باشد [7].

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

[1]. Wren

[2]. University Course Timetabling

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

متن کامل را می توانید دانلود نمائید

زیرا فقط تکه هایی از متن پایان نامه در این صفحه درج شده (به گونه نمونه)

اما در فایل دانلودی متن کامل پایان نامه

 با فرمت ورد word که قابل ویرایش و کپی کردن می باشند

موجود می باشد

تعداد صفحه : 129

قیمت : چهارده هزار و هفتصد تومان