Multi-objective fuzzy-based adaptive memetic algorithm with hyper-heuristics to solve university course timetabling problem

EAI Endorsed Transactions on Scalable Information Systems

article

Abdul Ghaffar¹  Mian Usman Sattar²  Mubbasher Munir¹  Zarmeen Qureshi² 

[1] University of Management and Technology;Beaconhouse National University

关键词: Timetabling;    Memetic Algorithm;    Hybrid Genetic Algorithm;    Hyper Heuristics;    Tabu Search;    Fuzzy Logic;   

DOI  :  10.4108/eai.16-12-2021.172435

学科分类：社会科学、人文和艺术（综合）

来源: Bern Open Publishing

【 摘 要 】

The university course timetabling is an NP-hard (non-deterministic polynomial-time hard) optimization problem to create a course timetable without conflict. It must assign a set of subject classes to a fixed number of timeslots with physical resources, including rooms and teachers. Avoiding hard constraints creates an executable timetable, whereas the removal of different soft constraints creates a satisfactory timetable. The most common way to resolve this problem is through the use of a hybrid genetic algorithm. The multi-objective fuzzy-based adaptive memetic algorithm, a population-based hybrid genetic approach, is proposed by combining genetic algorithm with local search with tabu search and various artificial intelligence techniques. It starts with generating a random population by using the hyper-heuristics and initial repairing method. By using the hill-climbing algorithm, it iteratively generates new offspring from the population by applying fuzzy- based adaptive crossover and mutation operations. If the solution still contains some conflicts, then the tabu search improves it by applying the most appropriate candidate repeatedly. While getting the workable solution, the algorithm tries to maximize multiple objective functions to get manageable solutions with different perspectives. It efficiently allocates all the required resources to subject classes and generates optimal solutions for the datasets provided by the University of Management & Technology, Lahore. It shows 96.29% accuracy in resolving conflicts compare with that of the simple and hybrid genetic algorithms. A web-based dynamic timetable manager visually represents a timetable and also provides options to adjust conflicts manually.

【 授权许可】

CC BY