فصلنامه علمی

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

نویسندگان

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

چکیده

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

کلیدواژه‌ها

موضوعات

عنوان مقاله [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