{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,2]],"date-time":"2026-04-02T22:09:12Z","timestamp":1775167752497,"version":"3.50.1"},"reference-count":27,"publisher":"MDPI AG","issue":"2","license":[{"start":{"date-parts":[[2013,4,19]],"date-time":"2013-04-19T00:00:00Z","timestamp":1366329600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/3.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>Course timetabling is a combinatorial optimization problem and has been confirmed to be an NP-complete problem. Course timetabling problems are different for different universities. The studied university course timetabling problem involves hard constraints such as classroom, class curriculum, and other variables. Concurrently, some soft constraints need also to be considered, including teacher\u2019s preferred time, favorite class time etc. These preferences correspond to satisfaction values obtained via questionnaires. Particle swarm optimization (PSO) is a promising scheme for solving  NP-complete problems due to its fast convergence, fewer parameter settings and ability to fit dynamic environmental characteristics. Therefore, PSO was applied towards solving course timetabling problems in this work. To reduce the computational complexity, a timeslot was designated in a particle\u2019s encoding as the scheduling unit. Two types of PSO, the inertia weight version and constriction version, were evaluated. Moreover, an interchange heuristic was utilized to explore the neighboring solution space to improve solution quality. Additionally, schedule conflicts are handled after a solution has been generated. Experimental results demonstrate that the proposed scheme of constriction PSO with interchange heuristic is able to generate satisfactory course timetables that meet the requirements of teachers and classes according to the various applied constraints.<\/jats:p>","DOI":"10.3390\/a6020227","type":"journal-article","created":{"date-parts":[[2013,4,19]],"date-time":"2013-04-19T11:00:47Z","timestamp":1366369247000},"page":"227-244","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":42,"title":["Solving University Course Timetabling Problems Using Constriction Particle Swarm Optimization with Local Search"],"prefix":"10.3390","volume":"6","author":[{"given":"Ruey-Maw","family":"Chen","sequence":"first","affiliation":[{"name":"Department of Computer Science and Information Engineering, National Chinyi University of Technology, Taichung, Taiwan"}]},{"given":"Hsiao-Fang","family":"Shih","sequence":"additional","affiliation":[{"name":"Department of Computer Science and Information Engineering, National Chinyi University of Technology, Taichung, Taiwan"}]}],"member":"1968","published-online":{"date-parts":[[2013,4,19]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"369","DOI":"10.1080\/07408179608966284","article-title":"Large scale classroom scheduling","volume":"28","author":"Mooney","year":"1995","journal-title":"IIE Trans."},{"key":"ref_2","doi-asserted-by":"crossref","unstructured":"Even, S., Itai, A., and Shamir, A. (1975, January 13\u201315). On the Complexity of Timetable and Multi-Commodity Flow Problems. Proceedings of the 16th IEEE Annual Symposium on Foundations of Computer Science, California, CA, USA.","DOI":"10.1109\/SFCS.1975.21"},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"39","DOI":"10.1016\/0377-2217(91)90321-L","article-title":"Tabu search for large scale timetabling problems","volume":"54","author":"Herz","year":"1991","journal-title":"Eur. J. Oper. Res."},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"16","DOI":"10.1016\/0377-2217(95)00204-9","article-title":"A two-stage multiobjective scheduling model for faculty-course-time assignment","volume":"94","author":"Masood","year":"1996","journal-title":"Eur. J. Oper. Res."},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"161","DOI":"10.1016\/S0012-365X(96)00208-7","article-title":"Restricted coloring models for timetabling","volume":"165\u2013166","author":"Werra","year":"1997","journal-title":"Discret. Math."},{"key":"ref_6","doi-asserted-by":"crossref","unstructured":"Abdullah, S., and Turabieh, H. (2008, January 11\u201313). Generating university course timetable using genetic algorithm and local search. Proceedings of the 3rd International Conference on Convergence and Hybrid Information Technology, Busan, Korea.","DOI":"10.1109\/ICCIT.2008.379"},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"111","DOI":"10.1007\/s10479-010-0737-7","article-title":"Local search and constraint programming for the post enrolment-based course timetabling problem","volume":"194","author":"Cambazard","year":"2012","journal-title":"Ann. Oper. Res."},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"3074","DOI":"10.1016\/j.cor.2012.03.011","article-title":"A hybridized Lagrangian relaxation and simulated annealing method for the course timetabling problem","volume":"39","author":"Gunawan","year":"2012","journal-title":"Comput. Oper. Res."},{"key":"ref_9","unstructured":"Burke, E.K., Elliman, D.G., and Weare, R.F. (2007, January 15\u201317). Application of genetic algorithm for solving university timetabling problems: A case study of Thai universities. Proceedings of the 7th WSEAS International Conference on Simulation, Modelling and Optimization, Beijing, China."},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"325","DOI":"10.1007\/s10479-012-1078-5","article-title":"Solving the post enrolment course timetabling problem by ant colony optimisation","volume":"194","author":"Nothegger","year":"2012","journal-title":"Ann. Oper. Res."},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"235","DOI":"10.1016\/j.eswa.2010.06.051","article-title":"A hybrid particle swarm optimization for a university course scheduling problem with flexible preferences","volume":"38","author":"Shiau","year":"2011","journal-title":"Expert Syst. Appl."},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"3472","DOI":"10.1016\/j.asoc.2012.05.029","article-title":"A hybrid particle swarm optimization based algorithm for high school timetabling problems","volume":"12","author":"Tassopoulos","year":"2012","journal-title":"Appl. Soft Comput."},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"664","DOI":"10.1109\/TSMCC.2011.2174356","article-title":"University course timetabling using a hybrid harmony search metaheuristic algorithm","volume":"42","author":"Khader","year":"2012","journal-title":"IEEE Trans. Syst. Man Cybern. Rev."},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"617","DOI":"10.1007\/s10951-010-0202-0","article-title":"A hybrid genetic algorithm and tabu search approach for post enrolment course timetabling","volume":"14","author":"Jat","year":"2010","journal-title":"J. Sched."},{"key":"ref_15","unstructured":"Kennedy, J., and Eberhart, R. (December, January 27). Particle Swarm Optimization. Proceedings of the Fourth IEEE International Conference on Neural Networks, Perth, WA, USA."},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"432","DOI":"10.1016\/j.cor.2009.03.004","article-title":"A hybrid multi-swarm particle swarm optimization algorithm for the probabilistic traveling salesman problem","volume":"37","author":"Marinakis","year":"2010","journal-title":"Comput. Oper. Res."},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"18","DOI":"10.1109\/TSMCB.2006.883272","article-title":"An Effective PSO-Based Memetic Algorithm for Flow Shop Scheduling","volume":"37","author":"Liu","year":"2007","journal-title":"IEEE Trans. Syst. Man Cybern. Rev."},{"key":"ref_18","doi-asserted-by":"crossref","unstructured":"Shen, H., Zhu, Y., Liu, T., and Jin, L. (2009, January 10\u201311). Particle Swarm Optimization in Solving Vehicle Routing Problem. ICICTA 09\u2019 Second International Conference on Intelligent Computation Technology and Automation, Hunan, China.","DOI":"10.1109\/ICICTA.2009.77"},{"key":"ref_19","doi-asserted-by":"crossref","unstructured":"Chen, R.M., and Wang, C.M. (2011). Project scheduling heuristics based standard PSO for task-resource assignment in heterogeneous grid. Abstr. Appl. Anal., 2011.","DOI":"10.1155\/2011\/589862"},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"1899","DOI":"10.1016\/j.eswa.2009.07.024","article-title":"Using a novel particle swarm optimization scheme to solve resource-constrained scheduling problem in PSPLIB","volume":"37","author":"Chen","year":"2010","journal-title":"Expert Syst. Appl."},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"7102","DOI":"10.1016\/j.eswa.2010.12.059","article-title":"Particle swarm optimization with justification and designed mechanisms for resource-constrained project scheduling problem","volume":"38","author":"Chen","year":"2011","journal-title":"Expert Syst. Appl."},{"key":"ref_22","unstructured":"Shi, Y., and Eberhart, R. (1998, January 4\u20139). A Modified Particle Swarm Optimizer. Proceedings of the IEEE International Conference on Evolutionary Computation, Anchorage, Piscataway, NJ, USA."},{"key":"ref_23","unstructured":"Clerc, M. (1999, January 6\u20139). The Swarm and the Queen: Towards a Deterministic and Adaptive Particle Swarm Optimization. Proceedings of the Congress on Evolutionary Computation, Washington, DC, USA."},{"key":"ref_24","unstructured":"Eberhart, R., and Shi, Y. (2000, January 16\u201319). Comparing Inertia Weights and Constriction Factors in Particle Swarm Optimization. Proceedings of the 2000 IEEE Congress on Evolutionary Computation, La Jolla, CA, USA."},{"key":"ref_25","doi-asserted-by":"crossref","unstructured":"Bratton, D., and Kennedy, J. (2007, January 1\u20135). Defining a Standard for Particle Swarm Optimization. Proceedings of the 2007 IEEE Swarm Intelligence Symposium, Honolulu, HI, USA.","DOI":"10.1109\/SIS.2007.368035"},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"58","DOI":"10.1109\/4235.985692","article-title":"The particle swarm\u2014Explosion, stability, and convergence in a multidimensional complex space","volume":"6","author":"Clerc","year":"2002","journal-title":"IEEE Trans. Evol. Comput."},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"5872","DOI":"10.1016\/j.eswa.2010.02.018","article-title":"An improved multi-objective particle swarm optimizer for multi-objective problems","volume":"37","author":"Tsai","year":"2010","journal-title":"Expert Syst. Appl."}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/6\/2\/227\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T21:46:16Z","timestamp":1760219176000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/6\/2\/227"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,4,19]]},"references-count":27,"journal-issue":{"issue":"2","published-online":{"date-parts":[[2013,6]]}},"alternative-id":["a6020227"],"URL":"https:\/\/doi.org\/10.3390\/a6020227","relation":{},"ISSN":["1999-4893"],"issn-type":[{"value":"1999-4893","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,4,19]]}}}