چکیده:
در سی تا چهل سال اخیر، تلاش های زیادی برای توسعه روش های فرموله سازی جدول زمانبندی موثر انجام شده است. هدف از مسئله فرموله سازی جدول زمانبندی امتحانات این است که مجموعه ای از امتحانات در مجموعه ای از پریود های زمانی، طوری زمانبندی شوند که تعدادی از محدودیت ها را ارضاء کنند. این محدودیت ها معمولا به دو نوع تقسیم بندی می شوند. یکی محدودیت های سخت می باشند، که نباید نقض شوند و دیگری محدودیت های نرم می باشند که به ازای هر نقض یک جریمه در نظر گرفته می شود .
به خاطر تعداد و تنوع زیاد این محدودیت ها، این قبیل مسائل زمانبندی از جمله مسائل np – hardمحسوب می شوند که حل دستی آنها خیلی سخت است. در این تحقیق می خواهیم به صورت خلاصه به بررسی روش های فرموله سازی زمانبندی و ارزیابی مسئله جدول زمانبندی امتحانات بپردازیم.
بیان مساله فرموله سازی جدول زمانبندی:
Carter مسئله جدول زمانبندی امتحانات را اینطور تعریف میکند:
فرموله سازی جدول زمانبندی که همه محدودیت های سخت را برآورده می کند، اغلب جدول زمانبندی امکان پذیر نامیده می شود . مجموعه ای از محدودیت هایی که باید برآورده شوند، معمولا از یک سازمان به سازمان دیگر، خیلی متفاوت است نمونه هایی از محدودیت های سخت مشترک توسط پی سی اسکریپت در زیر لیست شده است که عبارتند از:
– امتحانات باید طوری زمانبندی شوند که هیچ دانشجویی دو امتحان متفاوت در یک زمان مشترک نداشته باشد.
– در پایان فرآیند زمانبندی، نباید امتحان های زمانبندی نشده باقی بماند.
و…
در عمل معمولا هر سازمانی یک روش متفاوتی برای ارزیابی کیفیت جدول زمانبندی امکان پذیر دارد . در بسیاری از حالت ها، میزان کیفیت براساس تابع جریمه 4محاسبه می شود که نشان می دهد چه میزانی از محدودیت های نرم برآورده می شود.
کلمات کلیدی :
جدول زمانبندی امتحانات، فرموله سازی، ارزیابی
