An integer program and a hybrid genetic algorithm for the university timetabling problem. (4th May 2017)

• Record Type: Journal Article
• Authors: Feng, Xuehao; Lee, Yuna; Moon, Ilkyeong
• Is Part Of: Optimization methods and software. Volume 32:Number 3(2017)
• Page Start: 625
• Page End: 649
• Publication Date: 2017-05-04
• Subjects: university timetabling problem -- mixed integer linear program -- periodicity constraint -- consecutiveness constraint -- hybrid genetic algorithm; Mathematical optimization -- Periodicals; Algorithms -- Periodicals; 519.7
• DOI: 10.1080/10556788.2016.1233970
• Languages: English
• ISSNs: 1055-6788

Abstract

Abstract : The university timetabling problem (UTP) has been studied by numerous research groups for decades. In addition to addressing hard and soft constraints, we extend the UTP by considering consecutiveness and periodicity constraints of multi-session lectures, which are common in many eastern Asian universities. Because schedulers can decide the consecutiveness and periodicity constraints for the multi-session lectures within a limited ratio, we consider these novel decision variables in our model. We develop a mixed integer linear program for the UTP. For the analysis, we convert the UTP into the three-dimensional container packing problem (3DCPP) and create a hybrid genetic algorithm (HGA), which has been shown to be efficient in solving the 3DCPP. We also develop a tabu search algorithm based on the existing UTP literature and compare the findings with that of our HGA. The results show that our HGA obtains a better solution than the tabu search algorithm in a reasonable amount of time.