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

Abstract

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.