The Influence of Population Size on the Computational Time of Genetic Algorithms in Course Scheduling
Abstract
Course scheduling is a complex problem in higher education because it must satisfy multiple constraints involving courses, instructors, rooms, and time slots. This study examines the impact of population size variation on the computational efficiency of a Genetic Algorithm (GA) applied to a medium-scale instance consisting of 35 courses, 15 instructors, 12 rooms, and 20 time slots. Simulations were conducted in MATLAB using population sizes ranging from 20 to 1000, while all other GA parameters were held constant to isolate the effect of population size. Solution quality was evaluated using a conflict-based fitness function, and all configurations yielded valid timetables with zero hard-constraint violations. Experimental results reveal a consistent non-linear relationship between population size and computation time. Statistical findings in Table 1—including mean values, standard deviations, and 95% confidence intervals—show that both very small and very large populations produce higher and more variable execution times. In contrast, population sizes of 300–400 achieve the lowest and most stable computation times, indicated by the smallest mean values and narrow confidence intervals. For the instance and configuration used in this study, this range serves as an effective starting point for population size tuning. Overall, the findings highlight the importance of empirical parameter selection to balance computational efficiency and solution quality in academic timetabling systems.
Keywords
Full Text:
PDFReferences
M. V. Rane, V. M. Apte, V. N. Nerkar, M. R. Edinburgh, and K. Y. Rajput, “Automated timetabling system for university course,” in Proc. 2021 Int. Conf. Emerging Smart Computing and Informatics (ESCI), Mar. 2021, pp. 328–334.
A. Rezaeipanah, S. S. Matoori, and G. Ahmadi, “A hybrid algorithm for the university course timetabling problem using the improved parallel genetic algorithm and local search,” Applied Intelligence, vol. 51, no. 1, pp. 467–492, Jan. 2021.
A. Bashab et al., “A systematic mapping study on solving university timetabling problems using meta-heuristic algorithms,” Neural Computing and Applications, vol. 32, no. 23, pp. 17397–17432, Dec. 2020.
L. Saviniec, M. O. Santos, A. M. Costa, and L. M. dos Santos, “Pattern-based models and a cooperative parallel metaheuristic for high school timetabling problems,” European Journal of Operational Research, vol. 280, no. 3, pp. 1064–1081, Feb. 2020.
G. Xiaoying, X. Shengjia, C. Guo, and Q. Meijiao, “Modal parameter identification by adaptive parameter domain with multiple genetic algorithms,” Journal of Mechanical Science and Technology, vol. 34, no. 12, pp. 4965–4980, Dec. 2020.
H. Alghamdi, T. Alsubait, H. Alhakami, and A. Baz, “A review of optimization algorithms for university timetable scheduling,” Engineering, Technology & Applied Science Research, vol. 10, no. 6, pp. 6410–6417, Dec. 2020.
N. M. Arratia-Martinez, C. Maya-Padron, and P. A. Avila-Torres, “University course timetabling problem with professor assignment,” Mathematical Problems in Engineering, vol. 2021, no. 1, pp. 1–11, 2021.
T. Benecke and S. Mostaghim, “The impact of population size on the convergence of multi-objective evolutionary algorithms,” in Proc. 2021 IEEE Symp. Series Computational Intelligence (SSCI), Dec. 2021, pp. 1–8.
A. Vié, “Population network structure impacts genetic algorithm optimisation performance,” in Proc. Genetic and Evolutionary Computation Conf. Companion, Jul. 2021, pp. 1994–1997.
M. Sulaiman, Z. Halim, M. Lebbah, M. Waqas, and S. Tu, “An evolutionary computing-based efficient hybrid task scheduling approach for heterogeneous computing environment,” Journal of Grid Computing, vol. 19, no. 1, p. 11, Mar. 2021.
Q. K. Pan, L. Gao, and L. Wang, “An effective cooperative co-evolutionary algorithm for distributed flowshop group scheduling problems,” IEEE Transactions on Cybernetics, vol. 52, no. 7, pp. 5999–6012, Dec. 2020.
Y. Zhou, Y. Xiang, and X. He, “Constrained multiobjective optimization: Test problem construction and performance evaluations,” IEEE Transactions on Evolutionary Computation, vol. 25, no. 1, pp. 172–186, Jul. 2020.
H. Ma, H. Wei, Y. Tian, R. Cheng, and X. Zhang, “A multi-stage evolutionary algorithm for multi-objective optimization with complex constraints,” Information Sciences, vol. 560, pp. 68–91, Jun. 2021.
R. Salman, S. Suprapto, I. Irfandi, and O. Y. Hutajulu, Optimization of Genetic Algorithm Computation Time with Mutation Probability Variations in Course Scheduling. Jambura Journal of Electrical and Electronics Engineering, vol. 7, no. 1, 2025.
G. Alnowaini and A. A. Aljomai, “Genetic algorithm for solving university course timetabling problem using dynamic chromosomes,” in Proc. 2021 Int. Conf. Technology, Science and Administration (ICTSA), Mar. 2021, pp. 1–6.
H. K. Mammi and L. Y. Ying, “Timetable scheduling system using genetic algorithm for school of computing (tsuGA),” International Journal of Innovative Computing, vol. 11, no. 2, pp. 67–72, Oct. 2021.
M. Elliot, F. S. Gbenga, and J. Mnisi Emmanuel, “Enhanced heuristic teaching timetabling algorithm using genetic algorithm,” International Journal of Scientific & Technology Research, vol. 9, no. 4, pp. 3804–3814, 2020.
B. Koohestani, “A crossover operator for improving the efficiency of permutation-based genetic algorithms,” Expert Systems with Applications, vol. 151, p. 113381, Aug. 2020.
M. Baioletti, G. Di Bari, A. Milani, and V. Santucci, “An experimental comparison of algebraic crossover operators for permutation problems,” Fundamenta Informaticae, vol. 174, no. 3–4, pp. 201–228, Sep. 2020.
A. N. Zaied, M. M. Ismail, and S. S. Mohamed, “Permutation flow shop scheduling problem with makespan criterion: literature review,” Journal of Theoretical and Applied Information Technology, vol. 99, no. 4, pp. 830–848, Feb. 2021.
A. Sharma, “A constraint driven solution model for discrete domains with a case study of exam timetabling problems,” arXiv preprint arXiv:2002.03102, Feb. 2020.
H. Algethami and W. Laesanklang, “A mathematical model for course timetabling problem with faculty-course assignment constraints,” IEEE Access, vol. 9, pp. 111666–111682, Aug. 2021.
B. Genc and B. O’Sullivan, “A two-phase constraint programming model for examination timetabling at university college cork,” in Proc. Int. Conf. Principles and Practice of Constraint Programming, Cham: Springer, Sep. 2020, pp. 724–742.
M. Mokhtari, M. Vaziri Sarashk, M. Asadpour, N. Saeidi, and O. Boyer, “Developing a model for the university course timetabling problem: a case study,” Complexity, vol. 2021, no. 1, p. 9940866, 2021.
F. de la Rosa-Rivera, J. I. Nunez-Varela, C. A. Puente-Montejano, and S. E. Nava-Muñoz, “Measuring the complexity of university timetabling instances,” Journal of Scheduling, vol. 24, no. 1, pp. 103–121, Feb. 2021.
E. Gashi, K. Sylejmani, and A. Ymeri, “Simulated annealing with penalization for university course timetabling,” in Proc. 13th Int. Conf. Practice and Theory of Automated Timetabling (PATAT), 2021, vol. 2, pp. 361–366.
B. Doerr and F. Neumann, “A survey on recent progress in the theory of evolutionary algorithms for discrete optimization,” ACM Transactions on Evolutionary Learning and Optimization, vol. 1, no. 4, pp. 1–43, Oct. 2021.
V. Buffalo and G. Coop, “Estimating the genome-wide contribution of selection to temporal allele frequency change,” Proceedings of the National Academy of Sciences, vol. 117, no. 34, pp. 20672–20680, Aug. 2020.
N. Shirmohammady, H. Izadkhah, and A. Isazadeh, “PPI-GA: A Novel Clustering Algorithm to Identify Protein Complexes within Protein-Protein Interaction Networks Using Genetic Algorithm,” Complexity, vol. 2021, no. 1, p. 2132516, 2021.
W. A. Algasm, “Hybrid algorithm to solve timetabling problem,” in IOP Conf. Ser.: Mater. Sci. Eng., vol. 928, no. 3, p. 032053, Nov. 2020.
A. P. Dimitriev, T. A. Lavina, and A. H. Aleksandrov, “Application of selection sequence optimization algorithm to university timetabling problem,” in Proc. Int. Sci. Conf. Digitalization of Education (DETP), May 2020, pp. 549–555.
X. D. Zhang, “Evolutionary computation,” in A Matrix Algebra Approach to Artificial Intelligence, Singapore: Springer, May 2020, pp. 681–803.
T. Benecke and S. Mostaghim, “The impact of population size on the convergence of multi-objective evolutionary algorithms,” in Proc. 2021 IEEE Symp. Series Computational Intelligence (SSCI), Dec. 2021, pp. 1–8.
A. Pourrajabian, M. Dehghan, and S. Rahgozar, “Genetic algorithms for the design and optimization of horizontal axis wind turbine (HAWT) blades: A continuous approach or a binary one?,” Sustainable Energy Technologies and Assessments, vol. 44, p. 101022, Apr. 2021.
A. J. Weiss and A. Z. Elsherbeni, “Performance of MATLAB and Python for computational electromagnetic problems,” Applied Computational Electromagnetics Society Journal (ACES), pp. 770–777, Jul. 2020.
T. Yaghoobi, “Parameter optimization of software reliability models using improved differential evolution algorithm,” Mathematics and Computers in Simulation, vol. 177, pp. 46–62, Nov. 2020.
A. H. Halim, I. Ismail, and S. Das, “Performance assessment of the metaheuristic optimization algorithms: an exhaustive review,” Artificial Intelligence Review, vol. 54, no. 3, pp. 2323–2409, Mar. 2021.
L. A. Odeniyi, A. O. Agbeyangi, G. A. Adeniran, and N. O. Lawal, “An Automatic Timetable Generator Using Meta-Heuristic Approach,” unpublished.
A. Slowik and H. Kwasnicka, “Evolutionary algorithms and their applications to engineering problems,” Neural Computing and Applications, vol. 32, no. 16, pp. 12363–12379, Aug. 2020.
M. A. Al-Furhud and Z. H. Ahmed, “Experimental study of a hybrid genetic algorithm for the multiple travelling salesman problem,” Mathematical Problems in Engineering, vol. 2020, no. 1, p. 3431420, 2020.
R. Hoshino and I. Fabris, “Optimizing student course preferences in school timetabling,” in Proc. Int. Conf. Integration of Constraint Programming, Artificial Intelligence, and Operations Research, Cham: Springer, Sep. 2020, pp. 283–299..
DOI: https://doi.org/10.37905/jjeee.v8i1.33508
Refbacks
- There are currently no refbacks.
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.
Published by:
Electrical Engineering Department
Faculty of Engineering
State University of Gorontalo
Jalan B.J.Habibie Desa Moutong Kecamatan Tilongkabila Kabupaten Bone Bolango
Telp. 0435-821175; 081340032063
Email: [email protected]/[email protected]
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.