پایان نامه با کلید واژگان
دروس دانشگاهی، هوش مصنوعی، مدل ریاضی، جستجوی محلی

پایان نامه با کلید واژگان دروس دانشگاهی، هوش مصنوعی، مدل ریاضی، جستجوی محلی

دی ۸, ۱۳۹۷ 0 By mitra1--javid

تعداد دورههای زمانی مورد نیاز، زمانبندی شوند.
(H2): هیچ کلاسی نمیتواند به طور همزمان به دو درس تخصیص داده شود (تداخل برنامه کلاسها).
(H3): تمام جلسات یک درس نباید به دورههای زمانی در یک روز، تخصیص داده شود.
(H4): هر درس باید به کلاسی متناسب با نیازش تخصیص داده شود.
(H5): دروس با توجه به روابط پیشنیازی، به دورههای زمانی تخصیص داده شوند.
(H6): باید همه دورههای زمانی ممنوع و از قبل تخصیص داده شده (دانشجویان، استاد و کلاس) در نظر گرفته شود.
(H7): دانشجو نباید درسهایش در چند روز متوالی باشد (برای مثال بیش از سه روز متوالی).
(H8): جلسات درسی یک گروه، دانشجوی مشابه نباید تداخل داشته باشد (تداخل برنامه دانشجویان).
(H9): باید تعداد دانشجویان با ظرفیت کلاس تخصیص داده شده همخوانی داشته باشد.
(H10): دانشجو نباید بیش از تعداد مشخص شده، درس متوالی در یک روز داشته باشد.
(H11): هیچ درسی نباید به بیش از یک استاد تخصیص داده شود.
(H12): هیچ استادی نمیتواند دو درس را بطور همزمان تدریس کند (تداخل برنامه اساتید).
(H13): هر درس باید به استادی تخصیص داده شود که توانایی تدریس آن را داشته باشد.
(H14): تعداد دروسی که یک استاد میتواند تدریس کند.
(H15): تعداد اساتیدی که میتوانند یک درس را تدریس کنند.
(H16): باید دروس به دورههای زمانی که استاد در آن زمان در دسترس است، تخصیص داده شوند.
(H17): نباید ساعات درسی اساتید از حد تعیین شده تجاوز کند.
(H18): میزان ساعت تدریس اساتید به طور یکنواخت در طول هفته تخصیص داده شود (فشار کاری اساتید).
(H19): استاد نباید بیش از تعداد مشخص شده، درس متوالی در یک روز داشته باشد.
(H20): استاد نباید درسهایش در چند روز متوالی باشد.

۲-۳-۲- محدودیتهای نرم جدول زمانی دروس دانشگاهی
محدودیتهای نرم (S)5 عمومی بکار رفته در مسائل زمانبندی دروس دانشگاهی در تحقیقات پیشین عبارت است از:
(S1): تمام جلسات یک درس باید در یک کلاس مشابه تشکیل شود.
(S2): به دورههای زمانی پایانی روز، درسی تخصیص داده نشود.
(S3): دروس با توجه به روابط پیشنیازی، به دورههای زمانی تخصیص داده شوند.
(S4): از فضای آموزشی (کلاس، آزمایشگاه و .. .) داخل دانشگاه استفاده شود (عدم استفاده از امکانات خارج دانشگاه).
(S5): جلسات یک درس باید در چند روز (حداقل تعداد تعیین شده) تدریس شود.
(S6): کلاسهای درسی دانشجویان تا جایی که امکان دارد باید فشرده و بیکاری آنها حذف شود.
(S7): نباید ساعات درسی دانشجویان بیش از حد تعیین شده باشد.
(S8): دانشجویان نباید در یک روز فقط یک درس داشته باشند.
(S9): تعداد روزهای آزاد (تعطیل) دانشجو حداکثر باشد.
(S10): باید تعداد دانشجویان با ظرفیت کلاس تخصیص داده شده، همخوانی داشته باشد.
(S11): دانشجو نباید بیش از دو درس متوالی در یک روز داشته باشد.
(S12): جلسات درسی یک گروه، دانشجوی مشابه نباید تداخل داشته باشد.
(S13): تعداد دانشجویان تخصیص داده شده به هر درس، با نوع آن درس تناسب داشته باشد.
(S14): دانشجو نباید درسهایش به چند روز متوالی (بیش از تعداد مشخص شده) تخصیص داده شود.
(S15): حدالامکان جلسات درسی اختیاری با اجباری یک گروه دانشجوی مشابه، نباید تداخل داشته باشد.
(S16): تعداد دانشجوی تخصیص داده شده به هر درس مطابق با حداکثر و حداقل دانشجو تعریف شده در هر درس باشد.
(S17): اساتید نباید به دورههای زمانی که برایشان نامطلوب است تخصیص داده شوند.
(S18): نحوه تعریف جلسات (سه جلسه در یک روز، در هر روز یک جلسه و . . .) هر درس توسط استاد رعایت شود.
(S19): اساتید نباید به دروسی که برایشان نامطلوب است تخصیص داده شوند.
(S20): نباید ساعات درسی اساتید از حد تعیین شده تجاوز کند.
(S21): استاد نباید درسهایش در بیش از تعداد مشخص شده، روز متوالی باشد.

در جدول (۲-۱) محدودیتهای نرم و سخت، تحقیقات مورد بررسی و ارتباط آنها، نشان داده شده است.

۲-۳-۳- روشهای حل جدول زمانی دروس دانشگاهی
تحقیق و جستجو درباره زمانبندی ماشینی دروس به دهه ۶۰ میلادی برمیگردد. در سالهای ابتدایی زمانبندی ماشینی نیز به نوعی شبیهسازی نحوه زمانبندی توسط نیروی انسانی بود. پس از آن محققان به بررسی روشهای عمومیتر پرداختند، مانند روشهای برنامهریزی عدد صحیح، …. و در دو دهه اخیر، تلاشها بر استفاده از روشهای ابتکاری، فراابتکاری و هوش مصنوعی متمرکز شده است.
سعی شده در ادامه، تحقیقات انجام شده در سالهای اخیر، با روشهای حل متنوع مرور و مورد بررسی قرار گیرد:
سابر۶ و همکارانش در سال ۲۰۱۲، از الگوریتم فراابتکاری جفتگیری زنبور عسل برای حل مسأله زمانبندی امتحانات و زمانبندی دروس دانشگاهی استفاده کردند. الگوریتم جفتگیری زنبور عسل (HBMO)7 الگوریتمی الهام گرفته از طبیعت است که شبیه سازی فرایند واقعی جفت گیری زنبور عسل است. در این مقاله مدل ریاضی برای مسائل ارائه نشده است. محدودیتهای نرم مسأله تنها ترجیحات دانشجویان را در نظر گرفته است. یکی از ایرادهای این الگوریتم، تعداد پارامترهای زیاد آن است که نیاز به تنظیم دارند. یکی از تفاوتهای اصلی این الگوریتم با دیگر الگوریتمهای مبتنی بر جمعیت مانند ژنتیک و ممتیک، این است که بجای انتخاب دو والد در هر مرحله، تنها نیاز به انتخاب یک والد است و والد دوم همان ملکه است که در مرحله حضور دارد [۲۴].

مطلب مشابه :  پایان نامه با موضوعماکروسکوپی، اویداکتی، فولیکولها، نمیشود.

عبدالله۸ و همکارش در سال ۲۰۱۲، مسألههای زمانبندی دروس دانشگاهی و زمانبندی امتحانات دانشگاهی را ارائه کردند و با ا
ستفاده از الگوریتم پیشنهادی ممتیک ممنوعه با ساختار همسایگی چندگانه مسائل را حل نمودند. محدودیتهای نرم مسائل مبتنی بر ترجیحات دانشجویان طراحی شده است. و هدف مسائل حداقل کردن تعداد تخطی از محدودیتهای نرم است. در الگوریتم پیشنهادی از عملگر جهش، تقاطع و از ۹ ساختار همسایگی و لیست ممنوعه برای ساختار همسایگیها استفاده شده است. نتایج نشان میدهد، مطلوبیت جوابهای حاصل از الگوریتم پیشنهادی نسبت به الگوریتم ممتیک تنها بهتر است [۲۹].
قرونی و همکارش در سال ۲۰۱۳، به بررسی و توسعه یک الگوریتم تکاملی پیشنهادی برای حل مسأله جدول زمانی دروس دانشگاهی پرداختند. هدف اصلی در این مقاله بررسی تأثیر روشهای حل تکاملی بر روی مسائل جدول دروس دانشگاهی است. الگوریتم تکاملی پیشنهادی از توسعه الگوریتم ممتیک حاصل شده است. الگوریتم پیشنهادی برای حل چندین مسأله در سایزهای کوچک، متوسط و بزرگ مورد استفاده قرار گرفته است. بررسی و مقایسه نتایج حاصل از الگوریتم تکاملی پیشنهادی با دیگر الگوریتمهای تکاملی مانند ممتیک و ژنتیک گروهی، نشان دهنده برتری الگوریتم تکاملی پیشنهادی برای مسألههای سایز کوچک و متوسط نسبت به دیگر الگوریتمها است [۳۸].

آلوارز-والدز۹ و همکارنش در سال ۲۰۰۲، یک مدل زمانبندی دروس دانشگاهی ارائه و برای اولین بار از الگوریتم جستجوی ممنوعه جهت حل مسأله زمانبندی دروس دانشگاهی استفاده کردند. آنها مسأله را در دو فاز حل کردند، فاز اول تخصیص دانشجویان به دروس و دورههای زمانی و در فاز دوم تخصیص دروس به کلاسها انجام شده است. برای فاز اول یک جواب اولیه شدنی برای تخصیص دانشجویان تولید و با الگوریتم جستجوی ممنوعه برنامه بهبود داده شده و در فاز دوم از الگوریتم جستجوی ممنوعه برای تخصیص کلاس و بهبود آن، البته بدون تغییر دادن تخصیص اولیه دروس به دورههای زمانی استفاده شده است. همچنین چندین استراتژی همسایگی و تأثیر ساختارها با هم مقایسه شده است [۲۷].
آلاداگ۱۰ و همکارانش در سال ۲۰۰۷، مدل جدول زمانی دروس دانشگاهی ارائه شده توسط آلوارز-والدز و همکارنش را توسعه و با الگوریتم جستجوی ممنوعه حل کردند [۲۳]. و همچنین آلاداگ و همکارانش در سال ۲۰۰۹، همان مدل را با الگوریتم جستجوی ممنوعه با چهار استراتژی همسایگی مختلف حل کردند. استراتژی اول: انتقال یک درس به یک کلاس خالی در یک دوره زمانی، استراتژی دوم: جابجایی دو درس با یکدیگر، استراتژی سوم: استفاده از دو استراتژی اول و دوم بصورت همزمان و موازی در هر تکرار و انتخاب بهترین جواب و استراتژی چهارم: الگوریتم با استراتژی اول شروع و در صورت دست نیافتن به یک جواب بهتر پس از تعداد تکرار مشخص، از استراتژی دوم یک بار استفاده میکند. در انتها نتایج حاصل از حل با تمام استراتژیها مقایسه و ارزیابی شده است. ارزیابی نتایج نشان دهنده برتری استراتژی چهارم نسبت به سه استراتژی دیگر است [۲۵].
گناون۱۱ و همکارانش در سال ۲۰۱۲، به توسعه مدل زمانی جدول دروس دانشگاهی که کارتر۱۲ در سال ۱۹۹۸ ارائه داده بود، پرداختند. مدل آنها یک مدل ریاضی عدد صحیح است. مسئله تنها مبتنی بر ترجیحات اساتید است و با فرض اینکه دانشجویان در هنگام ثبتنام حق انتخاب دارند، ترجیحات آنها در مدل، در نظر گرفته نشده است. هدف این مدل، تخصیص اساتید و زمانبندی دروس به نحوهی که ترجیحات اساتید بصورت حداکثر برآورد شود، میباشد. آنها از روش لاگرانژین برای بدست آوردن یک جواب اولیه مناسب و از الگوریتم شبیهسازی شده تبریدی برای بهبود جواب استفاده کردند. الگوریتم پیشنهادی در این تحقیق در یکی از دانشگاههای اندونزی پیادهسازی شده است، که نتایج حاصل از آن مطلوب بوده است [۱۵].
کاسمیکر۱۳ و همکارانش در سال ۲۰۰۹، با پیشنهاد یک الگوریتم جستجوی محلی به حل مسأله زمانبندی دروس دانشگاهی پرداختند. آنها مسأله مبتنی بر ترجیحات اساتید و دانشجویان طراحی کردهاند. هدف مسأله آنها تهیه یک جدول زمانی مطلوب با کمترین تخطی از ترجیحات مسأله است. مسأله با الگوریتم جستجوی محلی با چندین استراتژی ساختار همسایگی و لیست ممنوعه حل شده است. به گونهای که، اگر در چند تکرار الگوریتم به یک جواب بهتری نرسد، از یک ساختار همسایگی دیگر برای جستجو استفاده میشود، و ساختار همسایگی قبلی در لیست ممنوعه قرار می گیرد. سپس از این الگوریتم برای مسألهای با دادههای واقعی استفاده گردید، که جدول زمانی بدست آمده قابل قبول و با کیفیت بود [۳۹].
میرندا۱۴ و همکارانش در سال ۲۰۱۲، یک مدل برنامهریزی عدد صحیح برای مسأله زمانبندی دروس دانشگاهی ارائه دادند. مدل این مسئله مبتنی بر ترجیحات اساتید و دانشجویان و دانشگاه است. در این مقاله به ارائه یک سیستم پشتیبانی تصمیم DSS))15 و به برنامه نویسی آن در محیط وب پرداخته شده است. زمانبندی دروس با نرمافزار تهیه شده، زمان حل را به طور قابل توجهی کاهش میدهد، به طوری که زمان حل از چند هفته، به چند ساعت کاهش مییابد [۲۸].
چاو چین۱۶ در سال ۲۰۱۱، با روش خوشهبندی۱۷ به حل مسأله زمانبندی دروس پرداخته است. مدل جدول زمانی ارائه شده مبتنی بر ترجیحات دانشجویان است. در این تحقیق برای دستیابی به یک سیستم منعطف در برابر تغییرات محدودیتها با استفاده از ادغام سیستم خبره۱۸ و برنامهریزی محدودیتها۱۹، از رویکرد هوش مصنوعی استفاده شده است. نتایج نشان میدهد، حل مسأله با روش پیشنهادی بسیار سریع و دارای زمان اجرای کم است [۳۵].
مهرگان و همکارانش در سال ۲۰۱۲، از روش متدولوژی سیستم نرم (SSM)20 برا
ی حل مسأله زمانبندی دروس دانشگاه تهران استفاده کردند. در این مسأله ترجیحات اساتید، دانشجویان و دانشگاه در نظر گرفته شده است. هدف مسأله تهیه جدول زمانی با کیفیت با حداقل نمودن تخطی از ترجیحات مذکور است. با توجه به پیچیدگی و بزرگی سایز نمونههای این مسائل در دنیای واقعی، یک راهحل بهینه کارآمد را نمیتوان به راحتی یافت. در این مقاله با استفاده از روش SSM، مفاهیم یادگیری، فهم و رابطه معنادار ذینفعان مربوطه در مسأله، قابل تحلیل بوده و بررسی میشود [۵].
امینتوسی۲۱ و همکارانش در سال ۲۰۰۵، با روش فازی به ارائه جدول زمانی دروس دانشگاهی پرداختند. آنها با کلاسبندی فازی بهینه دانشجویان، و استفاده از یک تابع فازی مسأله برنامهریزی جدول زمانی دروس دانشگاهی را حل نمودند. تفکیک دانشجویان کلاسهای پرجمعیت (کلاسهبندی) یکی از مسائل مهم برنامهریزی هفتگی دروس دانشگاهی میباشد. در این رویکرد اجرای یک الگوریتم جدید در تفکیک باعث کاهش میزان تداخل دروس دانشجویان در برنامه هفتگی میشود. ابتدا با استفاده از خوشهبندی فازی، دانشجویان به چند دسته تقسیم میشوند. سپس با توجه به معیارهای میزان دور بودن مراکز خوشهها، میزان متراکم بودن هر خوشه، میزان هم ورودی بودن دانشجویان هر خوشه و نسبت ابعاد خوشهها و با استفاده از یک تابع فازی، ارزش خوشهبندی تعیین میشود. با انتخاب ویژگیهای (دروس) مناسب، بهترین تفکیک دانشجویان صورت و زمانبندی دروس دانشگاهی انجام میشود [۳۹].
ایسمیولوا۲۲ و و همکارانش در سال ۲۰۰۷، یک مدل چند هدفه جدول زمانی دروس دانشگاهی ارائه دادند. مسأله بر مبنای ترجیحات اساتید و دانشگاه و بصورت تخصیص استاد به درس و درس به دورههای زمانی بصورت همزمان، طراحی شده است. توابع اهداف در دو گروه ترجیحات اساتید و دانشگاه که متضاد هستند و در چهار سطح بصورت مینممسازی ارائه شده است. تابع هدف گروه اول برای مینممسازی تخطی از ترجیحات استاد برای تدریس درس- دوره زمانی و همچنین فشار کاری اساتید است. توابع گروه دوم جهت مینممسازی تخطی از ترجیحات دانشگاه جهت تخصیص استاد- درس و درس- زمان است. برای حل مدل از روش استاندارد GAMS/CPLEX استفاده شده است. در این تحقیق از روشهای AHP23 و ۲۴ANP برای وزندهی ترجیحات استفاده و نتایج حاصل مقایسه شدهاند [۴۱].

مطلب مشابه :  پایان نامه با کلید واژگانمدیران مدارس، منابع مالی، محیط آموزشی، روابط انسانی

۲-۴- انواع روشهای حل مسائل بهینهسازی
مسائل بهینهسازی به دو دسته مسائل بهینهسازی ترکیبی و پیوسته تقسیم میشود. در زمینه مسائل پیوسته، روشهای کلاسیک بسیاری برای بهینهسازی سراسری ارائه شده است. اما این تکنیکها در صورتی که تابع هدف دارای ویژگیهای مشخصی نظیر محدب بودن نباشد، معمولاً کارایی ندارد. روشهای بهینهسازی پیوسته به دو دستهی روشهای بهینهسازی خطی و غیر خطی تقسیمبندی میشوند. روشهای حل مسائل بهینهسازی ترکیبی را نیز میتوان به دو قسمت الگوریتمهای دقیق و تقریبی تقسیم نمود. بهینهسازی غیرخطی پیوسته و روشهای تقریبی مسائل گسسته، جزء مسائل سخت محسوب میشود.

۲-۴-۱- روشهای بهینه سازی ترکیبی
همان طوری که بیان شد روشهای حل مسائل بهینهسازی ترکیبی را نیز میتوان به دو قسمت الگوریتمهای دقیق و تقریبی تقسیم نمود. الگوریتمهای دقیق معمولاً برای حل مسائل با اندازههای کوچک و متوسط بکار میرود، و رسیدن به جواب بهینه را در هر یک از این مسائ