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

چکیده

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