بخشی از مقاله
چکیده
تهیه جدول زمانبندی دانشگاهی به عنوان نوعی خاص از مسائل زمانبندی است که یکسری رویداد یا منابع را در تعداد محدودی فاصله زمانی و مکانی با در نظر گرفتن شرایط و محدودیتهای مشخصی انتساب می دهد. باتوجه به افزایش تعداد دانشجویان، ایجاد رشتههای جدید و کمبود فضاهای آموزشی، با محدودیتهای بسیاری برای ساخت یک برنامه کلاسی مناسب مواجه هستیم. از آنجایی که مسئله جداول زمانی، از جمله مسائل NP-Complete به شمار میرود، نیاز به استفاده از الگوریتمهای هوشمند جهت حل آن قطعی است.در این مقاله با استفاده از الگوریتم های ژنتیک ، جدول زمانبندی دروس دانشگاه را بر اساس محدودیتهای قوی مانند در دسترس بودن اساتید و نوع اتاق و همچنین محدودیتهای ضعیف ایجاد می کنیم. جدول زمانبندی را ابتدا با در نظر گرفتن محدودیت قوی بدست آورده و در حین انجام آن محدودیت های ضعیف را اعمال می کنیم.
کلمات کلیدی : الگوریتم ژنتیک، جدول زمانبندی
.1 مقدمه
مسئله جداول زمانی، به فرایند تخصیص منابع محدود مکانی- زمانی، به تعدادی رویداد، با شرط ارضا تعداد زیادی محدودیت، اشاره مینماید.[1] گرچه تعریف فوق دامنه بسیار وسیعی از مسائل را در بر میگیرد اما عموما مسئله جداول زمانی به طراحی برنامه کلاسی یا امتحانات، در محیطهای آموزشی اشاره مینماید. در این تحقیق، بر روی تهیه برنامه کلاسی دانشگاه تمرکز شده است. باتوجه به افزایش تعداد دانشجویان، ایجاد رشتههای جدید و کمبود فضاهای آموزشی، با محدودیتهای بسیار برای ساخت یک برنامه کلاسی مناسب مواجه هستیم. پرزینا در - 2006 - [2] اینگونه عنوان می نمایدکه :"مسئله جداول زمانی به عنوان یک مسئله NP شناخته شده است، بنابراین هیچ الگوریتمی وجود ندارد که آن را با پیچیدگی زمانی چندجملهای حل نماید".
تمامی محققان در این زمینه اتفاق نظر دارند که: مسئله جداول زمانی دارای فضای پاسخ نمایی بوده و مانند تمامی مسائل NP-complete، نیاز به استفاده از الگوریتمهای هوشمند جهت حل آن اجتناب ناپذیر است. با توجه به توضیحات و پیچیدگی مساله، روشهای مختلفی برای حل این مساله در مقالات مختلف پیشنهاد شده است که می توان روش سردکردن شبیه سازی شده[3]، الگوریتم کلونی مورچه[4]، روش برنامه نویسی منطقی[5]، جستجوی تابو - ممنوعه - [6] را نام برد.مبنای حل مساله جدول زمانبندی در این مقاله ترکیبی از دو روش رنگ آمیزی گراف و الگوریتم ژنتیک است. از آنجا که محدودیتهای همزمانی غیر مجاز تدریسها در جداول زمانبندی را می توان بر اساس گراف پیاده سازی کرد و با در نظر گرفتن صورت مساله رنگ آمیزی گرافها، این محدودیتها را در جداول زمانبندی حل کرد، در این مقاله سعی شده است با معادل سازی قسمتهای مختلف جدول زمانبندی با سیستم گرافها و منطبق کردن آن دو به یکدیگر جدول زمانبندی بهینه ای برای دروس دانشگاهی تهیه کرد.
و با توجه به تفاوتهای رنگ آمیزی گراف نسبت به مساله جدول زمانبندی مانند در نظر گرفتن حداکثر رنگ برای یک سیستم گراف و همچنین حداکثر تعداد گره هایی که باید دارای یک رنگ یکسان باشند، در حین استفاده از رنگ آمیزی گراف از الگوریتم ژنتیک که یکی از روشهای پرکاربرد جهت حل مسئله جداول زمانی است استفاده می کنیم تا این تفاوتها را بصورت سریعتر حل کند.در این مقاله سعی شده است که با در نظر گرفتن محدودیتهای قوی بصورت کامل، محدودیتهای ضعیف نیز دیدهشود.در بخش دوم، مساله بطور کامل شرح داده شده است. در بخش سوم، تعریفی کامل از رنگ آمیزی گراف و ارتباط آن با جدول زمانبندی تشریح شده است. بخش چهارم به تشریح الگوریتم ژنتیک و نحوه استفاده از آن در حل مساله اختصاص - یافته است. در فصل پنجم نتیجهگیری و پیشنهاداتی برای کارهای آینده ارائه خواهد شد.
.2 تشریح مساله
در مساله جدول زمانبندی از مفاهیم زیر استفاده می شود.
روز و بازه زمانی : - Day, Timeslot - در این مساله حداکثر تعداد روز تدریس در هفته را مشخص می کنیم - که معمولا 5 یا 6 روز است - . هر روز به بازه های زمانی ثابتی تقسیم بندی می شود که معمولا بازه های 2 ساعتی است که به این ترتیب معمولا هر روز به 8 یا 9 بازه زمانی تقسیم بندی می شود. در بعضی تشریح مسائل به ترکیب روز و بازه زمانی یک دوره - Period - گفته می شود.
درس و تدریس: در هر بازه زمانی یک یا چند درس - در چندین اتاق - تدریس می شود. تدریس هر درس بر اساس این مقاله نیاز به یک یا دو بازه زمانی است - هر درس شامل 2 یا 4 ساعت تدریس است - .
استاد: هر درس توسط استادی تدریس می شود. هر استاد در یک بازه زمانی فقط می تواند در مکان تدریس کند.
اتاق: هر اتاق دارای ظرفیت و نوع خاصی است. در این مقاله فرض شده است که کلیه اتاقها به اندازه کافی ظرفیت دارند. هر اتاق به منظور نوع خاصی از تدریس در نظر گرفته شده است و اتاقهایی مجزا برای تدریسهای عملی و آزمایشگاهی و تئوری و غیره پیش بینی شده است.
ترم و رشته تحصیلی: هر رشته تحصیلی در هر ترم دارای دروس مشخصی است که باید تمامی آن دروس در جدول زمانبندی گنجانده شود بطوریکه در یک بازه زمانی در اتاقهای مختلف دروس یک ترم تدریس نشود.
از بین این مفاهیم، در این مقاله از سه مفهوم کلی دوره زمانی - روز و بازه زمانی - ، تدریس - استاد و رشته تحصیلی - و اتاق استفاده شده است.
کلیه محدودیتها بر روی تدریسها اعمال شده است:
هر تدریس مشخص شده است در کدامیک از اتاقها مجاز به تشکیل شدن است و در کدامیک غیر مجاز است مثلا تدریس با نوع درس آزمایشگاهی در یک اتاق خاصی با ارائه شود و یا اینکه تدریسی دارای تعداد دانشجوی زیاد است که فقط در اتاقهای با ظرفیت کافی قابل ارائه است.هر تدریس در کدام بازه های زمانی مجاز به تشکیل شدن است مثلا تدریسی توسط استادی با محدودیتهای زمانی مشخصی ارائه می شود و یا تدریسی باید در صبح یا عصر تشکیل شود.هر تدریس مشخص شده است که با کدامیک از دیگر تدریسها نباید در یک دوره زمانی قرار گیرد مثلا تدریسهایی که در مورد یک رشته تحصیلی در یک ترم هستند و یا تدریسهایی که در مورد یک درس هستند.
این سه محدودیت به عنوان محدودیتهای قوی اعمال شده بر روی جداول زمانبندی است.
همچنین می توان مشخص کرد که یک تدریس با فاصله تعداد دوره زمانی خاصی نسبت به دیگر تدریس قرار گیرد، مثلا اگر درسی نیاز به دو تدریس دو ساعته داشته باشد می توان مشخص کرد که این دو تدریس بصورت متوالی در یک روز قرار گیرد - فاصله دوره زمانی بین دو تدریس صفر باشد - و یا اینکه این دو تدریس در دو روز مختلف قرار گیرد.
محدودیتهای قوی در نظر گرفته شده شامل موارد زیر است:
1.هر استاد در هر دوره زمانی فقط می تواند یک تدریس داشته باشد.
2.کلیه تدریسهای در نظر گرفته شده باید در جدول زمانبندی گنجانده شود.
3.در دوره زمانی در نظر گرفته شده برای یک استاد، آن استاد در دسترس باشد.
4.اتاقهای در نظر گرفته شده از نظر موضوع با تدریس منطبق باشد.
5.دروسی که استاد مشترک دارند نمی توانند همزمان ارائه شوند.
6.دروس همنیاز که توسط گروه مشترکی از دانشجویان باید اخذ شوند نباید همزمان ارائه شوند.
7. ...
موارد زیر را به عنوان محدودیتهای ضعیف می توان شمرد:
1.دروس با موضوعات مشابه بطور یکنواخت بین ساعات هفته توزیع شود.
2.استادی می تواند ساعات یا روزهای خاصی را برای تدریس ترجیح بدهد - اجباری نیست - .
3.اتاق در نظر گرفته شده در نزدیکی محل سکونت یا دفتر استاد باشد.
4.بهتر است کلیه کلاسها در ساعات صبح یا عصر یا ... تشکیل شود.
5.تعداد اتاقهای استفاده شده حداقل باشد.
