sis 18: e14

Research Article

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

Download857 downloads
  • @ARTICLE{10.4108/eai.16-12-2021.172435,
        author={Abdul Ghaffar and Mian Usman Sattar and Mubbasher Munir and Zarmeen Qureshi},
        title={Multi-objective fuzzy-based adaptive memetic algorithm with hyper-heuristics to solve university course timetabling problem},
        journal={EAI Endorsed Transactions on Scalable Information Systems: Online First},
        volume={},
        number={},
        publisher={EAI},
        journal_a={SIS},
        year={2021},
        month={12},
        keywords={Timetabling, Memetic Algorithm, Hybrid Genetic Algorithm, Hyper Heuristics, Tabu Search, Fuzzy Logic},
        doi={10.4108/eai.16-12-2021.172435}
    }
    
  • Abdul Ghaffar
    Mian Usman Sattar
    Mubbasher Munir
    Zarmeen Qureshi
    Year: 2021
    Multi-objective fuzzy-based adaptive memetic algorithm with hyper-heuristics to solve university course timetabling problem
    SIS
    EAI
    DOI: 10.4108/eai.16-12-2021.172435
Abdul Ghaffar1, Mian Usman Sattar2,*, Mubbasher Munir3, Zarmeen Qureshi4
  • 1: Department of Information Systems, University of Management and Technology, Lahore, Pakistan
  • 2: Assistant Professor, Department of Management Sciences, Beaconhouse National University, Lahore, Pakistan
  • 3: Department of Economics and Statistics, University of Management and Technology, Lahore, Pakistan
  • 4: Department of Management Sciences, School of Business, Beaconhouse National University, Lahore, Pakistan
*Contact email: usman.sattar@bnu.edu.pk

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.