A Micro-Genetic Algorithm Approach for Soft Constraint Satisfaction Problem in University Course Scheduling

• Main Author: Abd. Halim, Bohadean @ Bohari
• Format: Thesis
• Language: English; English
• Published: 2013
• Subjects: LB2300 Higher Education; QA Mathematics
• Online Access: https://etd.uum.edu.my/3856/1/s88485.pdf; https://etd.uum.edu.my/3856/7/s88485.pdf; https://etd.uum.edu.my/3856/

A university course timetabling problem is a combination of optimization problems. The problems are more challenging when a set of events need to be scheduled in the time slot, to be located to the suitable rooms, which is subjected to several sets of hard and soft constraints. All these constraints that exist as regulations within each resource for the event need to be fulfilled in order to achieve the optimum tasks. In addition, the design of course timetables for universities is a very difficult task because it is a non-deterministic polynomial, (NP) hard problem. This problem can be minimized by using a Micro Genetic Algorithm approach. This approach, encodes a chromosome representation as one of the key elements to ensure the infeasible individual chromosome produced is minimized. Thus, this study proposes an encoding chromosome representation using one-dimensional arrays to improve the Micro Genetic algorithm approach to soft constraint problems in the university course schedule. The research contribution of this study is in developing effective and feasible timetabling software using Micro Genetic Algorithm approach in order to minimize the production of an infeasible individual chromosome compared to the existing optimization algorithm for university course timetabling where UNITAR International University have been used as a data sample. The Micro Genetic Algorithm proposed has been tested in a test comparison with the Standard Genetic algorithm and the Guided Search Genetic algorithm as a benchmark. The results showed that the proposed algorithm is able to generate a minimum number of an infeasible individual chromosome. The result from the experiment also demonstrated that the Micro Genetic Algorithm is capable to produce the best course schedule to the UNITAR International University.