دراین قسمت، با توجه به مطالعاتی پیرامون مسئله برنامه ریزی دروس دانشگاهی به بیان مبانی نظری و تعاریف مطرح شده در این زمینه پرداخته میشود.
۲-۲-۱- برنامه ریزی دروس دانشگاهی
زمانبندی دروس یکی از مسائل مهم و زمانبر در هر محیط آموزشی است. برنامه ریزی چیدمان دروس در جدول هفتگی، بر اساس معیارها و امکانات محیط، مشخصات دروس و ساعات حضور استادان صورت میگیرد (دهقانی و ذاکرتولائی، ۱۳۸۵). در ادامه به تعاریف مختلفی از برنامه ریزی دروس دانشگاهی اشاره خواهد شد.
یعقوبی،۱۳۸۴، در پایان نامه خود مسئله جداولزمانی را فرایند تخصیص منابع محدود مکانی- زمانی، به تعدادی رویداد، با شرط ارضا تعداد زیادی محدودیت، تعریف نموده است.
امیدوار،۱۳۸۴، یک مسئله برنامه ریزی هفتگی مدارس را برنامهای میداند که اولاً خالی از تداخل بوده و ثانیاً با استانداردهای آموزشی مطابقت داشته باشد.
خلیلی و منصورزاده، ۱۳۸۵، در مقاله خود، معتقدند که در مسائل زمانبندی دروس سعی بر این است که مجموعهای از منابع معین، متشکل از کلاسها، اساتید و دروس، تحت شرایط خاص به مجموعهای از ساعتهای درسی اختصاص یابد.
دهقانی و ذاکرتولائی، ۱۳۸۵، در مقاله خود زمانبندی دروس را ایجاد یک برنامهزمانی معتبر و قابل اجرا با حداقل تداخل تعریف میکنند.
جولا و خاتونناصری،۱۳۸۶، در مقاله خود، برنامه ریزی دروس دانشگاهی را تخصیص یک درس به دو منبع بازهزمانی و اتاق به گونهای که محدودیتهای مورد نظر در آن نقض نشوند، تعریف میکنند.
نعیمی و منجمی، ۱۳۸۸، در مقاله خود مسئله طراحی جداول زمانی درسی مراکز آموزشی را تخصیص دروس به تعدادی کلاس در بازههای زمانی مشخص با هدف ارضا نمودن حداکثر قیود موجود تعریف نمودهاند.
مسعودیان و استکی، ۱۳۸۸، مسئله جدولزمانی را تخصیص دروس هفتگی به بازههای زمانی و اتاقهای برگزاری کلاسها تعریف میکند که اگر شروطی مانند عدم تخصیص یک کلاس در یک ساعت به چند درس، یا عدم تلاقی زمانی در دروس یک استاد به مسئله اضافه گردد مشخص میشود که مسئله طراحی جدولزمانی دروس دانشگاهی، میتواند یک مسئله ارضای محدودیت^[۱] قلمداد شود.
در مقاله دیگری امینطوسی و صدوقییزدی، ۱۳۸۹، برنامه ریزی دروس دانشگاهی یک گروه یا دانشگاه را انتساب جلسات دروس، به یک سری بازههای زمانی و اتاقها به نحوی که مجموعهای از شرایط مختلف برآورده گردد، تعریف کردهاند.
باباییزاده، ۱۳۹۰، در مقاله خود مسئله جدولزمانی کلاسهای دانشگاه را مجموعهای از نشستهای همزمان استادان و دانشجویان در شماری از بازههای زمانی میداند که نیازمند برخی منابع است و باید شماری از محدودیتها را برآورده نماید.
راستگار امینی، ۱۳۹۱، زمانبندی دروس دانشگاهی را تخصیص دروس به اساتید در زمان های مناسب به طوری که اهداف سازمان را از یک سو و ترجیحات اساتید از سوی دیگر تامین شود، تعریف نموده است. این زمانبندی کلاسها نوعاً اختصاص کلاسها به استادها و اتاقها و همچنین زمان های ملاقات استاد و دانشجو در روز را در بر میگیرد.
در مقاله باشیزاده، ۱۳۹۱، برنامه ریزی دروس دانشگاهی یک مقدار چند بعدی تعریف شده است که در آن، دانشجویان و استادان به دروس، گروه دروس و یا کلاسها نسبت داده میشوند، در این میان محدودیتهایی به صورت طبیعی و یا با توجه به خواست کاربر وجود دارد که باید در هنگام حل مسئله در نظر گرفته شود.
مونتانا و همکاران^[۲]، ۲۰۰۰، در مقاله خود، مسئله زمانبندی دروس را شامل تخصیص تعدادی استاد به تعدادی از منابع زمانی و مکانی میدانند.
برانیمیر و همکاران۱، ۲۰۰۲، مسئله جدولزمانی دروس دانشگاهی را یک مسئله رایج در تمامی مراکز آموزشی میدانند که برای یافتن پاسخ بایستی تعداد زیادی محدودیت در نظر گرفته شود و تعداد تناقضات محدودیتها را تا حد امکان کم کرد.

ینزنوانگ۲، ۲۰۰۳، در مقاله خود، خلق یک برنامه ریزی دروس دانشگاهی را یکی از مهمترین وظایف مسئولان برنامه ریزی در دانشگاهها میداند و این مسئله را یک مسئله پیچیده معرفی میکند که تحت محدودیتهای چندگانه قرار دارد.
نات و مانوئل۳ ،۲۰۰۳، مسئله زمانبندی دروس دانشگاهی را جزء مسائل بهینه سازی میدانند که برای یافتن جواب بهینه در کنار دیگر جوابهای موجه، زمان طولانی باید صرف شود.
عباس و تی سانگ۴، ۲۰۰۴، مسئله زمان بندی کلاسهای درس به صورت فرایند تخصیص دروس دانشگاهی به زمان های مشخص از برنامه هفتگی با در نظر گرفتن کلاس مناسب و امکانات مورد نیاز ارائه دروس تعریف میگردد.
کوینسول۵، ۲۰۰۶، در طرح تحقیقی خود، طراحی یک جدولزمانی برای بخش یا دانشکده کوچک را متفاوت از جدولزمانی برای یک دانشگاه بزرگتر میداند که شامل تداخلهای زمانی، مکانی و نیز ترجیحات اساتید میباشد، که بایستی در طراحی این جدولها در نظر گرفته و پاسخ داده شوند.
راجان و سانجای۶ ،۲۰۱۲، مسئله جدول زمانی را یک مسئله NP-hard معرفی میکنند که حل آن بسیار پیچیده و بستگی زیادی به محدودیتهای مختلف دارد.
۲-۲-۲- مسائل NP-complete
پیچیدگی رده NP، مجموعه تمامی مسائل تصمیمگیری را نشان میدهد که توسط یک الگوریتم غیر قطعی۷ در زمان چندجملهای قابل حل باشند. نکتهای که باید به آن توجه کرد این است که واژه NP از ” non-polynomial time ” گرفته نشده است. بلکه NP، از ” nondeterministic polynomial-time ” گرفته شده است. رده NP، اکثر مسائل بهینه سازی ترکیبی و همچنین تمامی مسائل موجود در رده P را در بر میگیرد. بنابراین، P زیرمجموعه NP می باشد. رده NP طبقهای از مسائل تصمیم را در بر میگیرد که پاسخ مثبت به مسئله تصمیم آن در زمان کوتاهی محدود به زمان چندجملهای قابل بررسی میباشد. نشان داده شده است که اغلب مسائل زمانبندی که به عنوان یک مسئله تصمیم بررسی میشوند، متعلق به طبقه NP میباشد ( بارکر، ۲۰۰۷).
در داخل رده NP، مسائلی از رده NP-complete وجود دارد. یک مسئله تصمیم که عضوی از NP است زمانی NP-complete محسوب میگردد که تمامی مسائل دیگر رده NP، در زمان چندجملهای قابل کاهش به آن مسئله باشد.
مسائل NP-hard، مسائل بهینه سازی می باشند که مسائل تصمیم مرتبط با آنها از نوع NP-hard می باشند و الگوریتم موثر اثبات شدهای برای حل آنها وجود ندارد. زمان حل بهینه آنها، در رده زمان نمایی میباشد که متاهیورستیکها گزینه مناسب و با اهمیتی برای حل این دسته از مسائل میباشند. در زیر دستهای از مسائل NP-hard آورده شده است:
مسائل زمانبندی و تعیین توالی مانند زمانبندی جریان کارگاهی، زمانبندی تولید کارگاهی و مسائل زمانبندی کارگاهی باز.
مسائل تخصیص و جانمایی از قبیل مسئله تخصیص درجه دو^[۳]، مسئله تخصیص تعمیمیافته^[۴]، جانمایی تسهیلات، مسئله P-median.
مسائل گروهبندی مانند خوشهبندی داده ها، افراز گراف و رنگآمیزی گراف.
مسائل مسیریابی و پوششدهی از قبیل مسئله مسیریابی وسایل حملونقل^[۵]، مسائل پوششدهی مجموعه^[۶] و مسائل تور پوشاننده.
مسائل برش، بستهبندی، کولهپشتی و غیره (فتاحی، ۱۳۹۰).
۲-۲-۳- روش های بهینه سازی
دو دسته کلی از روش های حل مسائل بهینه سازی شامل روش های دقیق^[۷] و روش های تقریبی^[۸] وجود دارد. روش های دقیق راه حلهای بهینه را به دست آورده و شرایط بهینگی را تضمین مینمایند. روش های تقریبی (هیوریستیکی)، راهحلهای با کیفیت بالا در زمان معقولی، تولید مینمایند، اما تضمینی برای یافتن راه حل بهینه مطلق ندارند.
۲-۲-۳-۱- روش های دقیق
روش های دقیق، الگوریتمهایی میباشند که جوابهای بهینه را پیدا نموده و شرط بهینگی را تضمین مینمایند. بعضی از این الگوریتمها عبارتند از برنامه ریزی پویا و الگوریتمهای خانواده شاخه و کران. روش های دقیق برای ابعاد کوچک بعضی از مسائل بهینه سازی دشوار نیز قابل به کارگیری میباشند. ابعاد مسئله، شاخص واحدی برای تشریح سختی یک مسئله نمیباشد. یک مسئله، ممکن است قابل حل با روش های دقیق نباشد در حالی که ابعاد بزرگتر آن توسط روش های دقیق حل شده باشد.
روشهایی که در این قالب دسته بندی می شود به شرح زیرند:
برنامه ریزی خطی عدد صحیح
روش تولید (ایجاد) ستون
در این روش همه مسیرهای ممکن به عنوان جوابهای اولیه تولید میشوند و سپس به کمک یکی از روش های بهبود مسیرهای پرهزینه حذف و مسیرهای کمهزینه باقی میمانند.
برنامه ریزی پویا (دینامیک)
در این روش مسئله به مسائل فرعی تجزیه میشود و تصمیمات طی چند مرحله انجام میشود. در این تکنیک ابتدا پارامترهایی چون مرحله، اقدام، حالت، نقطه آغازین و معادله برگشتی را تعریف نموده و مسئله را به صورت روبه جلو یا برگشت به عقب میتوان حل کرد.
روش انشعاب و تحدید
ابتدا مسئله در حالت پیوسته حل میشود و در صورتیکه جواب شرط صحیح بودن را برآورده نکند، شروط یا محدودیتهایی که تأمینکننده صحیح شدن متغیرها میشود به مسئله اضافه میشود.
این الگوریتم اولین بار در سال ۱۹۸۱ توسط لاپورته و نوبرت با یک انبار و تعداد ثابت وسایل نقلیه بکار گرفته شد (کارگری، ۱۳۹۰).
الگوریتم شاخه و برش
در این روش ایده کلی به این صورت است که ابتدا باید مسئله برنامه ریزی خطی آزاد شده و سپس مسئله برنامه ریزی عدد صحیح را حل کرد (طه،۱۳۸۸).
مدلهای آزادسازی ضرایب لاگرانژ
برای حل مشکل برنامه ریزی با اعداد صحیح از یک سری محدودیتهای جانبی برای سادهسازی استفاده میشود. که با نوشتن مزدوج این محدودیتها یک مسئله لاگرانژ که حل سادهتری دارد به دست میآید.
۲-۲-۳-۲- روش های تقریبی
در طبقه روش های تقریبی، دو طبقه از الگوریتمها شامل الگوریتمهای تقریبزنی و الگوریتمهای هیوریستیکی، وجود دارد. برخلاف هیوریستیکها، که معمولا به دنبال راهحلهای خوب در زمان معقولی میباشند، الگوریتمهای تقریب زنی حدود قابل اثباتی برای زمان اجرا و کیفیت جواب، ارائه مینمایند.
هیوریستیکها راهحلهای خوب را برای مسائل با اندازه های بزرگ جستجو مینمایند. آنها عملکرد قابل قبولی را، همراه با هزینه قابل قبولی برای حوزه وسیعی از مسائل به همراه دارند. متاهیوریستیکها زیر مجموعهای از هیوریستیکها هستند که برای مسائلی با اندازه های بزرگ کاربرد داشته و راه حلهای راضی کنندهای در زمان معقولی ارائه مینمایند. در این الگوریتمها، هیچ گونه ضمانتی برای یافتن جواب بهینه مطلق یا حدودی از آن وجود ندارد. متاهیوریستیکها در طول بیست سال گذشته شهرت رو به افزونی داشتهاند. کاربرد و استفاده از آنها در خیلی از مسائل، کارایی و اثربخشی آنها را برای حل مسائل پیچیده و بزرگ نشان میدهد.
این روشها به صورت غیرقطعی در فضای جواب به دنبال جواب بهینه میگردد. این روشها با الهام از طبیعت به وجود آمدهاند و در مسائل پیچیده و بزرگ کارایی و عملکرد مناسبی دارند.
برخی از این روشها به شرح زیر است: