![Open Access](https://i-scholar.in/lib/pkp/templates/images/icons/fulltextgreen.png)
![Restricted Access](https://i-scholar.in/lib/pkp/templates/images/icons/fulltextred.png)
Highly Constrained University Class Scheduling using Ant Colony Optimization
Solving University Class Scheduling Problem (UCSP) is a complex real-world combinatorial optimization task that has been extensively studied over the last several decades. Many meta-heuristic based techniques, including prominent swarm intelligence (SI) methods have been investigated to solve it in different ways. In this study, Ant Colony Optimization (ACO) based two methods are investigated to solve UCSP: ACO based method and ACO with Selective Probability (ACOSP). ACO is the well-known SI method that differs from other SI based methods in the way of interaction among individuals (i.e., ants); and an ant interacts with others indirectly through pheromone to solve a given problem. ACO based method considers probabilistically all the unassigned time slots to select next solution point for a particular course assignment. In contrast, ACOSP probabilistically selects next solution point for a particular course assignment from the selective probabilities. Such selective probability employment with ACO improves performance but reduces computational cost. The performances of the proposed methods have been evaluated comparing with Genetic Algorithm (GA) in solving real-world simple UCSPs. In addition, proposed methods are compared with each other for solving highly constrained UCSPs. Both the proposed methods outperformed GA and ACOSP was the best to solve the given problems.
Keywords
University Class Scheduling Problem (UCSP), Ant Colony Optimization (ACO), and Selective Probability (SP).
User
Font Size
Information
- Tomáš Müller, “Constraint-based Timetabling”, (2005), Ph.D. Thesis, Charles University, Prague.
- Tassopoulos Ioannis X., Beligiannis Grigorios N., “Solving effectively the school timetabling problem using particle swarm optimization”, (2012), Expert Systems with Applications, 39 (5), p.6029-6040.
- TassopoulosIoannis X., Beligiannis Grigorios N.,“A hybrid particle swarm optimization based algorithm for high school timetabling problems”, (2012), Applied Soft Computing, vol. 12 no. 11, pp. 3472-3489.
- D. F. Shiau, “A hybrid particle swarm optimization for a university course scheduling problem with flexible preferences”, (2011), Expert Systems with Applications, vol. 38, pp. 235-248.
- R. A. Valdes, E. Crespo, J. M. Tamarit, “Design and implementation of a course scheduling system using tabu search”, (2002), European Journal of Operational Research,vol.137, no.3, pp.512–523.
- Ernesto Ferrer, Queiros Nunez, “A Hybrid Genetic Algorithm for the Student-Aware University Course Timetabling Problem”, (2010), Bachelor Thesis, Macalester College.
- Mohammad-Reza Feizi-Derakhshi, Hamed Babaei, Javad Heidarzadeh, “A Survey of Approaches for University Course Timetabling Problem”, (2012), International Symposium on Intelligent and Manufacturing Systems (IMS), 307-321.
- Chohan, Ossam, “University scheduling using Genetic Algorithm”, (2009), Master’s Thesis, Dlarna University.
- Cagdas Hakan Aladag, Gulsum Hocaoglu, Murat Alper Basaran, “The effect of neighborhood structures on tabu search algorithm in solving course timetabling problem”, (2009), Expert Systems with Applications, 36 (10), p.12349-12356.
- ZhipengLü, Jin-Kao Hao, “Adaptive Tabu Search for course timetabling”, (2010), European Journal of Operational Research, 200 (1), p.235-244.
- Nasser R. Sabar, MasriAyob, Graham Kendall, Rong Qu, “A honey-bee mating optimization algorithm for educational timetabling problems”, (2012), European Journal of Operational Research, 216 (3), p.533-543.
- S Daskalaki, T Birbas, E Housos, “An integer programming formulation for a case study in university timetabling”, (2004), European Journal of Operational Research, 153 (1), p.117-135.
- Jin-Kao Hao, Una Benlic, “Lower bounds for the ITC-2007 curriculum-based course timetabling problem”, (2011), European Journal of Operational Research, 212 (3), p.464-472.
- Ruey-Maw Chen, Hsiao-Fang Shih, “Solving University Course Timetabling Problems Using Constriction Particle Swarm Optimization with Local Search”, (2013), Algorithms 2013, 6, 227-244.
![](https://i-scholar.in/public/site/images/abstractview.png)
Abstract Views: 347
![](https://i-scholar.in/public/site/images/pdfview.png)
PDF Views: 159