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

---

شرح پروژه

تعاریف

قبل از شروع الگوریتم باید به تعریف المان های موجود بپردازیم . یک برنامه دروس دانشگاهی توسط المان های زیر مشخص میشود.

مجموعه رویداد ها :  E={ e1,e2,…  ,em  }

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

مجموعه بازه های زمانی : T={ t1,t2,…  ,tn }

 بازه زمانی یک محدوده زمانی است که کلاس درس در آن محدوده زمانی برگزار می شود . هر بازه زمانی یک شروع و یک پایان دارد . نحوه بیان هر بازه زمانی به صورت روز هفته تشکیل آن و سپس عددی است که مربوط به بازه زمانی چندم آن روز هفته است. به عنوان مثال  دوشنبه2  بیانگر این است که کلاس مورد نظر در بازه زمانی دوم روز دوشنبه برگزار می شود.

مجموعه مکان ها : P={ p1,p2,…  ,pi }

رویداد ها در مکان های خاصی انجام میشوند.هرکدام ازین مکان ها ، نام ،اندازه و سایر مشخصات مخصوص به خود را دارند. به عنوان مثال مکان pi  ممکن است به عنوان یک کلاس سخنرانی با اندازه متوسط و با ظرفیت حداکثر 60 نفر باشد. در این مثال pi   نام ، کلاس سخنرانی نوع کلاس و 60 ظرفیت را نشان می دهد.

مجموعه اساتید : L={ l1,l2,…  ,lj  }

در واقعیت معمولا یک درس خاص توسط یک استاد منحصر به فرد ارائه میشود. این مجموعه اساتیدی را که قرار است دروس را ارائه کنند نشان می دهد. رابطه منحصر به فردی بین اعضای این مجموعه و مجموعه رویدادها برقرار است به این صورت که هرکدام از رویدادها توسط یکی از اساتید مجموعه L  ارائه می شوند.

مجموعه گروه ها : C={ c1,c2,…  ,ck  }

دانش آموزان در این گروه ها ، درس های ارائه شده را با توجه به رشته و ترم تحصیلی خود انتخاب می کنند . در نمایش کروموزومی هرگروه اطلاعاتی از نام و اندازه را نشان می دهد.

علاوه بر موارد بالا ، هر برنامه درسی دانشگاهی با یک سری از محدودیت ها نیز مشخص میشود. این محدودیت ها به دو دسته محدودیت های سخت و نرم تقسیم بندی می شوند. محدودیت های سخت آن هایی هستند که به هر شکل ممکن باید در برنامه نهایی رعایت شوند . در طرف دیگر محدودیت های نرم آن هایی هستند که سعی میکنیم تا بیشترین تعداد آنها را رعایت کنیم ولی عدم رعایت آنها ، یک برنامه را به طور کامل مردود نمیکند .

محدودیت های سخت عمومی به شرح زیر هستند :

·        هر رویداد باید در یک زمان خاص به وقوع بپیوندد.

·        یک گروه ، یک استاد و یک مکان نمیتوانند در یک بازه زمانی خاص به بیشتر از یک درس مربوط شوند.

·        برای هر رویداد باید یک زمان و مکان خاص پیدا شود و نمیتوان رویدادی را حذف کرد.

·        هر کدام از مکان های اختصاص داده شده حداقل ظرفیت مورد نظر را برای رویداد ، دارا باشند.

·   ملزومات مورد نظر رویدادها باید توسط مکان های ارائه شده در دسترسی باشند. به عنوان مثال برای برخی از رویدادها ، ویدئوپروژکتور نیاز است و برخی دیگرباید در آزمایشگاه برگزار شوند.

محدودیت های نرم نیز به صورت زیرند :

·        اساتید و دانشجویان برنامه های درسی با تعداد زیاد زمان های خالی بین کلاس ها را نمی پسندند.

·   انواع مختلف رویدادها ترجیحاً باید دربازه های زمانی گسترده باشند. به عنوان مثال چند کلاس آزمایشگاهی یا عملی بهتر است پشت سر هم قرار نگیرند و در روزهای مختلف هفته تشکیل شوند.

·        ترجیحات اساتید.

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

·        اندازه مکان ها به اندازه کافی بزرگ باشد.

·        کلاس های اساتید و دانشجویان به صورت فشرده و پشت سر هم نباشند.

مهارت ها و تخصص های مورد نیاز

---

---