امروزه زمانبندی جزء ضروریات اجتناب ناپذیر زندگی بشری است. در برنامه های کلان کشورهای توسعه یافته، یکی از بخشهایی که در نیل به تحقق برنامهها و اهدافشان نقش به سزا و مؤثری ایفا کرده، نظام آموزشی است. بنابراین با توجه به نقش کلیدی نظام آموزشی در هر جامعه، میتوان به اهمیت برنامه ریزی درست و مناسب در این سیستم پی برد. به طوری که یک زمانبندی مناسب سبب ارتقای کیفیت آموزشی و رضایتمندی کارکنان میباشد. جدول زمانی نوع خاصی از مسأله زمانبندی است. مسأله زمانبندی در دانشگاهها به دو دسته جدول زمانی برای امتحانات و زمانبندی دروس تقسیم می شود. مقصود از زمانبندی در این تحقیق، دسته دوم است. در این تحقیق تلاش شده است که تا حد امکان از مقالات اخیر در حوزه جدول زمانی، بویژه جدول زمانی دروس دانشگاهی و همچنین مقالات مربوط به روشهای حل فراابتکاری استفاده شود تا بیان نوین و کارا با اثربخشی مناسب ایجاد گردد.
2-1- بیان مسأله
جدول زمانی نوع خاصی از مسأله زمانبندی است، در سال 1996، آقای رن[1] تهیه جدول زمانی را بعنوان مسئله قرار دادن منابع خاص، با توجه به محدودیتها، در تعداد محدودی بازه زمانی و مکان، با هدف ارضاء مجموعه ای از اهداف تا حد ممکن توصیف کرد. این تعریف عمومی توصیفی از مسائل تهیه جدول زمانی است که به طور کلی پذیرفته شده است.
جدول زمانی در مسائلی با دامنههای وسیع و متنوع کاربرد دارد که از آن جمله میتوان مسائل آموزشی، مسابقات ورزشی، مسائل حملونقل، برنامهی کاری کارکنان، زمانبندی جلسات و زمانبندی فرایندهای تولیدی نام برد.
جدول زمانی دروس دانشگاهی عبارت از تخصیص تعداد معینی از منابع مانند اساتید و دروس، به تعداد محدودی از دوره های زمانی و کلاس در یک دوره مشخص با توجه به مجموعه ای از محدودیتها، جهت رسیدن به یکسری از اهداف مشخص است. معمولاً در این نوع مسائل محدودیتها به دو دسته سخت و نرم تقسیم میشوند. محدودیتهای سخت، محدودیتهایی هستند که حتماً باید برآورده شوند و شدنی بودن جواب را تضمین می کنند و محدودیتهای نرم بیان کننده مطلوبیت و ترجیحات مسأله هستند که برای کیفیت بهتر جدول زمانی در نظر گرفته میشوند و حتماً لزومی ندارد که همانند محدودیتهای سخت به طور کامل برآورده شوند. برای بدست آوردن یک جدول زمانی باکیفیت، باید مسأله شدنی و کمترین تعداد تجاوز را در محدودیتهای نرم داشته باشیم [4].
محدودیتهای نرم از طریق تابع پنالتی ارزیابی میشوند و تابع هدف این مسائل از مجموع وزن دهی شده توابع پنالتی محدودیتهای نرم تشکیل می شود.
محدودیتهای سخت عمومی به کار گرفته شده در این مسائل به صورت زیر هستند:
- یک منبع (درس، استاد، دانشجو) نمی تواند در آن واحد در چند جا (کلاس، پریود زمانی) استفاده شود.
- در هر دوره زمانی باید منابع در دسترس برای مواردی که زمانبندی شده اند کافی باشد.
اما محدودیتهای نرم با توجه به نوع و ترجیحات، برای هر مسأله متفاوت است. ما در این تحقیق ترجیحات اساتید، دانشجویان و دانشگاه را مد نظر قرار دادهایم.
در حال حاضر در اغلب دانشگاهها زمانبندی دروس به صورت دستی و توسط افراد مجرب انجام میگیرد. در برنامه ریزی دستی، با روشی تکراری دروس زمانبندی میشوند بدین صورت که در هر تکرار، یک درس انتخاب می شود و زمانبندی از دو درسی شروع می شود که تعداد دانشجوی بیشتری همزمان برای آن دو درس ثبت نام کرده باشند و بنابراین این دو درس نباید در یک زمان ارائه شوند و باید انتخاب استاد و بازه زمانی به گونه ای صورت گیرد که محدودیتهای دیگر را نیز نقض نکند. این روند همچنان ادامه پیدا می کند تا تمامی دروس به استاد و زمانی تخصیص داده شوند.
از آنجا که زمانبندی دستی وقتگیر است و لزوماً تمام خواسته های اساتید و دانشجویان را به بهترین نحو برآورده نمی کند، استفاده از روش کامپیوتری که در زمانی بسیار کمتر، جواب خوبی را فراهم میآورد، مناسب به نظر میرسد.
تحقیق و جستجو درباره زمانبندی ماشینی دروس به دهه 60 میلادی برمیگردد. بیشتر این روشها، به نوعی شبیهسازی نحوه زمانبندی توسط نیروی انسانی است. در این روشها، ابتدا مفیدترین دروس زمانبندی میشوند. سپس دروس با اولویت کمتر، به طور متناوب به جدول زمانی ناتمام اضافه شده تا اینکه تمام دروس زمانبندی شوند. پس از آن محققان به بررسی روشهای عمومیتر پرداختند مانند روش های برنامه ریزی عدد صحیح، جریان شبکه، رنگ آمیزی گراف و …. در دو دهه آخر، تلاشها بر روی روشها ابتکاری و فراابتکاری متمرکز شده است [5].
البته این گونه مسائل زمانبندی نمی تواند به صورت کاملاً نرمافزاری انجام شود. زیرا معیارهای بهتر بودن نسبی زمانبندیها، لزوماً به آسانی به زبان نرم افزارهای کامپیوتری بیان نمیشوند. از طرفی، از آنجا که فضای جواب در این گونه مسائل بسیار بزرگ است، دخالت نیروی انسانی می تواند مسأله را در راستای جوابهای مناسبتر هدایت کند، در حالی که روشهای کامپیوتری به صورت کامل، قادر به یافتن این جوابهای مناسب نیستند. به همین دلیل، بیشتر سیستمهای حل، امکان تغییر و دستکاری در جواب را برای کاربر فراهم میسازند. که در این تحقیق از مدیر گروه دانشکده به عنوان تعدیل کننده نهایی خروجی برنامه (برای مدل تک هدفه) با کمک گرفتن از روش AHP استفاده شده است، که در فصل 3 به صورت کامل تشریح شده است.
مفاهیم استفاده شده در جدول زمانی دروس دانشگاهی به شرح ذیل است:
رویداد: فعالیتی که باید زمانبندی شود، مانند: جلسات درسی.
برش زمانی: یک تعداد بازه زمانی، که هر یک از رویدادها در آن بازههای زمانی، زمانبندی میشوند.
منبع: منابعی که توسط رویدادها مورد نیاز است، مانند: کلاسها.
قید: یک محدودیت برای زمانبندی رویدادها، مانند: ظرفیت کلاس درسی.
افراد: کسی یا کسانی که همراه با رویدادها وجود دارند، مانند: اساتید، دانشجویان.
برخورد: اگر دو رویداد با یکدیگر برخورد داشته باشند، مانند: زمانبندی بیش از یک درس در یک کلاس در یک زمان یکسان.
1-3- ضرورت تحقیق
از آنجایی که زمانبندی دستی وقتگیر بوده و لزوماً تمام خواسته ها و ترجیحات اساتید، دانشجویان و دانشگاه را پوشش نمیدهد و همچنین با افزایش روز افزون رشتهها، گرایشات، تنوع دروس، افزایش تعداد دانشجویان و محدود بودن منابع در یک دانشگاه، كار زمانبندی دروس را دشوار مینماید. همه این عوامل ضرورت استفاده از روشهای مدلسازی و حل کامپیوتری که در زمان بسیار کمتری جواب خوبی فراهم میآورند، را دو چندان می کند. با توجه به این که در دنیای واقعی، مشخصات و ابعاد مسأله فوق گوناگونی و محدودیتهای زیادی دارد، در نظر گرفتن تمام این خصوصیات منجربه فضای حل بسیار بزرگی می شود که این مسأله را تبدیل به یک مسأله NP-Hard کرده [6]، و در برخی منابع نیز این مسأله به عنوان یک مسأله NP-Complete معرفی شده است [7].
مسأله زمانبندی دروس دانشگاهی با توجه به ساختار و مقرارت آموزش عالی از یک کشور به کشور دیگر متفاوت میباشد و حتی با توجه به قوانین داخلی هر دانشگاه، محدودیتها و تابع هدف می تواند تغییر کند.
[1]. Wren
[2]. University Course Timetabling
ممکن است هنگام انتقال از فایل اصلی به داخل سایت بعضی متون به هم بریزد یا بعضی نمادها و اشکال درج نشود ولی در فایل دانلودی همه چیز مرتب و کامل و با فرمت ورد موجود است
متن کامل را می توانید دانلود نمائید
چون فقط تکه هایی از متن پایان نامه در این صفحه درج شده (به طور نمونه)
ولی در فایل دانلودی متن کامل پایان نامه
با فرمت ورد word که قابل ویرایش و کپی کردن می باشند
موجود است
