Abstract
Timetabling presents an NP-hard combinatorial optimization problem which requires an efficient search algorithm. This research aims at designing a genetic algorithm for timetabling real-world school resources to fulfil a given set of constraints and preferences. It further aims at proposing a parallel algorithm that is envisaged to speed up convergence to an optimal solution, given its existence. The timetable problem is modeled as a constraint satisfaction problem (CSP) and a theoretical framework is proposed, which guides the approach used to formulate the algorithm. The constraints are expressed mathematically and a conventional algorithm is designed that evaluates solution fitness based on these constraints. Test results based on a subset of real-world, working data indicate that convergence on a feasible (and optimal/Pareto) solution is possible within the search space presented by the given resources and constraints. The algorithm also degrades gracefully to a workable timetable if an optimal one is not located. Further, a SIMD-based parallel algorithm is proposed that has the potential to speed up convergence on multi-processor or distributed platforms.
Gondwe, W (2021). Genetic Algorithms For Timetable Generation. Afribary. Retrieved from https://afribary.com/works/genetic-algorithms-for-timetable-generation
Gondwe, Walusungu "Genetic Algorithms For Timetable Generation" Afribary. Afribary, 16 Apr. 2021, https://afribary.com/works/genetic-algorithms-for-timetable-generation. Accessed 16 Nov. 2024.
Gondwe, Walusungu . "Genetic Algorithms For Timetable Generation". Afribary, Afribary, 16 Apr. 2021. Web. 16 Nov. 2024. < https://afribary.com/works/genetic-algorithms-for-timetable-generation >.
Gondwe, Walusungu . "Genetic Algorithms For Timetable Generation" Afribary (2021). Accessed November 16, 2024. https://afribary.com/works/genetic-algorithms-for-timetable-generation