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

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

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

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

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

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

خرید متن کامل این پایان نامه در سایت nefo.ir

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

1. در هر دوره زمانی باید منابع در دسترس برای مواردی که زمانبندی شده­اند کافی باشد.

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

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

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

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

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

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

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

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

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

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

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