文章基本信息

标题：A Hybrid Exam Scheduling Technique based on Graph Coloring and Genetic Algorithms Targeted towards Student Comfort
本地全文：下载
作者：Osama Al-Haj Hassan ; Osama Qtaish ; Maher Abuhamdeh 等
期刊名称：International Journal of Advanced Computer Science and Applications(IJACSA)
印刷版ISSN：2158-107X
电子版ISSN：2156-5570
出版年度：2019
卷号：10
期号：3
页码：503-512
DOI：10.14569/IJACSA.2019.0100365
出版社：Science and Information Society (SAI)
摘要：Scheduling is one of the vital activities needed in various aspects of life. It is also a key factor in generating exam schedules for academic institutions. In this paper we propose an exam scheduling technique that combines graph coloring and genetic algorithms. On one hand, graph coloring is used to order sections such that sections that are difficult to schedule comes first and accordingly scheduled first which helps in increasing the probability of generating valid schedules. On the other hand, we use genetic algorithms to search more effectively for more optimized schedules within the large search space. We propose a two-stage fitness function that is targeted toward increasing student comfort. We also investigate the effect and potency of the crossover operator and the mutation operator. Our experiments are conducted on a realistic dataset and the results show that a mutation only hybrid approach has a low cost and converges faster toward more optimized schedules.
关键词：Exam scheduling; optimization; graph coloring; genetic algorithms; time tabling; fitness value