طراحی جدول زمانبندی خودکار برای دروس دانشگاهی با استفاده از الگوریتم های ژنتیک

منجمی, امیر حسن; مسعودیان, سولماز; استکی, افسانه; نعمت بخش, ناصر

doi:10.22061/tej.2009.1340

نوع مقاله : مقاله پژوهشی

نویسندگان

گروه مهندسی کامپیوتر، دانشکده فنی و مهندسی، دانشگاه اصفهان،اصفهان،ایران

https://doi.org/10.22061/tej.2009.1340

چکیده

طراحی جدول زمانبندی، اساساً از وظایف پیچیده و وقت گیر برای پرسنل مسئول میباشد که از طرفی انجام خودکار آن گامی در جهت کاهش بار کاری پرسنل و از سوی دیگر یک نمونه مطلوب برای امتحان روشهای برنامهریزی و ارضای محدودیتها در هوش مصنوعی است. در این پژوهش، ابتدا الگوریتمهای ژنتیک مطالعه و بررسی شده، سپس در مسأله بهینه سازی جدول زمانی دروس برای یک دانشکده فرضی مورد استفاده قرار گرفته است. در این رویکرد روند تکاملی پاسخها طی تکرار نسلها در یک الگوریتم ژنتیک، نهایتاً منجر به تولید یک جدول زمانبندی دروس خوش کیفیت خواهد گردید. در مرحله پیاده سازی، به کمک تغییراتی که در روند معمول الگوریتمهای ژنتیک صورت داده شد، نتایج بسیار خوبی در زمینه طراحی جداول زمانبندی دروس دانشگاهی حاصل گردیده است. اساس کار الگوریتم طراحی شده، حفظ کروموزومهای بهتر جمعیت و اعمال عملگرهای ژنتیکی بر روی بقیه کروموزومها به منظور بهبود آنها میباشد. در آزمونها، مقایسه بین الگوریتم ژنتیک عادی و الگوریتم پیشنهادی، طی چند مرحله، نقاط قوت الگوریتم پیشنهادی را مشخص کرد. ایدههای مطرح شده در این تحقیق قابل تسری به کاربردهای مشابه نیز خواهد بود.

کلیدواژه‌ها

20.1001.1.20080441.1388.4.1.3.7

موضوعات

فناوری آموزش- آموزش عالی

عنوان مقاله [English]

Designing an Automated Timetable for University Courses Using Genetic Algorithms

نویسندگان [English]

A.H. Monajemi
S. Masoudian
A. Estaki
N. Nematbakhsh

Computer Engineering Department, Faculty of Engineering, University of Isfahan, Isfahan, Iran

چکیده [English]

Designing timetables, for example course timetables in an institute, is one of the most complicated and time-consuming challenges for personnel. Automating it, not only can help the personnel to manage their work better, but also can be considered as a desired sample to assess the ways of planning and to tackle the constraint satisfaction in artificial intelligence. In this paper, genetic algorithms are primarily studied and then it is applied for optimization of an imaginary faculty course timetable. The new designed algorithm is based on keeping the better chromosomes of the population and employing genetic operators on the others in order to improve the overall quality of genes. Some other amendments are also carried out to develop a more capable genetic algorithm for TT applications, compared to the standard one. According to the tests, the new GA algorithm will be more successful in generating high fidelity TTs which do not break any hard constraint. The proposed ideas, in this approach are applicable in other similar situations.

کلیدواژه‌ها [English]

Scheduling tables
planning
genetic algorithms
optimization
satisfaction constraints

مراجع

[1] Carter M., A Comprehensive Course Timetabling and Student Scheduling System at the University of Waterloo, Lecture Notes in Computer Science, Vol. 2079, 2001, pp. 64-82. [2] Burke E., Elliman D., Wearer R., A Genetic Algorithm based University Timetabling System, Proceedings of the 2nd East-West International Conference on Computer Technologies in Education, 1994, pp. 35-40. [3] Russell S., Norvig P., Artificial Intelligence: A Modern Approach, 3 rd Ed., Prentice Hall, 2009. ]1 ]علیرضا مهدی، مقدمهای بر الگوریتم های ژنتیک و کاربردهای آن، ناقوس اندیشه، 4۱8۵ . [5] Goldberg D., Genetic Algorithms in Search, Optimization and Machine Learning, AddisonWelsy, 1998. [6] Whitely D., A Genetic Algorithm Tutorial, Journal of Statistics and Computing Vol. 4, 1994, pp. 65-85. [7] Rossi-Doria O., Paechter B, A Memetic Algorithm for University Course Timetabling, Proceedings of the CO2004 Conference, Lancaster, UK, 2004, p. 65. [8] Erben W., Keppler J., A Genetic Algorithm Solving a Weekly Course-timetabling Problem, Proceedings of The First International Conference on The Practice and Theory of Automated Timetabling, Edinburgh, UK, 1995, pp. 198-211. [9] Abramson D., Abela J., A Parallel Genetic Algorithm for Solving the School Timetabling Problem, Proceedings of the 15th Australian Computer Science Conference, Hobart, Australia, 1992, pp.101. [10] Abdullah S., Burke E., McCollum B., An Investigation of Variable Neighbourhood Search for University Course Timetabling, Proceedings of the 2nd Multidisciplinary Conference on Scheduling: Theory and Applications, 2005, pp. 413-427. [11] Vorac J., Vondrak I., Vlcek K., School Timetabling Using Genetic Algorithm, Technical Report, VSB-Technical University of Ostrava, Czech Republic, 2002. [12] Cooper T., Kingston J., The Complexity of Timetable Construction Problems, Lecture Notes in Computer Science, Vol. 1153, 1996, pp. 281-295. [13] Beligiannisa G., Moschopoulosa C., Kaperonisa G., Likothanassisa D., Applying Evolutionary Computation To The School Timetabling Problem: The Greek Case, Journal of Computers & Operations Research, Vol. 35, 2008, pp. 1265–1280. [14] Pillay N., Banzhaf W., An Informed Genetic Algorithm For The Examination Timetabling Problem, Journal of Applied Soft Computing, Vol. 10, 2010, pp. 457–467. [15] Wilke P., Ostler J., Benchmarking CurriculumBased Course Timetabling: Formulations, Data Formats, Instances, Validation, and Results, Proceedings of the 7th International Conference for the Practice and Theory of Automated Timetabling (PATAT'2008), Montreal, Canada, 2008. ]41 ]نیپولیتان ریچارد و نعیمیپور کیومرث، طراحی الگوریتم ها با شبه کدهای ++C ،جهاد دانشگاهی مشهد، 4۱84 ،صفحه 868

نامه به سردبیر

سر دبیر نشریه فناوری آموزش، با تواضع انتشار نامه های واصله از نویسندگان و خوانندگان و بحث در سامانه نشریه را ظرف 3 ماه از تاریخ انتشار آنلاین مقاله در سامانه و یا قبل از انتشار چاپی نشریه، به منظور اصلاح و نظردهی امکان پذیر نموده است.، البته این شامل نقد در مورد تحقیقات اصلی مقاله نمی باشد.

توچه به موارد ذیل پیش از ارسال نامه به سردبیر لازم است در نظر گرفته شود:

[1]نامه هایی که شامل گزارش از آمار، واقعیت ها، تحقیقات یا نظریه ها هستند، لازم است همراه با منابع معتبر و مناسب باشند، اگرچه ارسال بیش از زمان 3 نامه توصیه نمی گردد

[2] نامه هایی که بجای انتقاد سازنده به ایده های تحقیق، مشتمل بر حملات شخصی به نویسنده باشند، توجه و چاپ نمی شود

[3] نامه ها نباید بیش از 300 کلمه باشد

[4] نویسندگان نامه لازم است در ابتدای نامه تمایل یا عدم تمایل خود را نسبت به چاپ نظریه ارسالی نسبت به یک مقاله خاص اعلام نمایند

[5] به نامه های ناشناس ترتیب اثر داده نمی شود

[6] شهر، کشور و محل سکونت نویسندگان نامه باید در نامه مشخص باشد.

[7] به منظور شفافیت بیشتر و محدودیت حجم نامه، ویرایش بر روی آن انجام می پذیرد.