×

Solving a real constraint satisfaction model for the university course timetabling problem: a case study. (English) Zbl 1400.90216

Summary: This paper proposes a real mathematical constraint satisfaction model which defines the timetabling problem in the Faculty of Chemical Sciences and Engineering (FCSE) at the Autonomous University of Morelos State, Mexico. A Constructive Approach Algorithm (CAA) is used to obtain solutions in the proposed model. A comparison is made between the CAA’s results and the schedule generated by the FCSE administration. Using the constraint satisfaction model, it is possible to improve the allocation of class hours in the FCSE so that classroom use is more efficient.

MSC:

90B90 Case-oriented studies in operations research
90B35 Deterministic scheduling theory in operations research
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Papadimitriou, C. H.; Steiglitz, K., Combinatorial Optimization: Algorithms and Complexity, (1998), New York, NY, USA: Dover, New York, NY, USA · Zbl 0944.90066
[2] Cook, S. A., The complexity of theorem-proving procedures, Proceedings of the 3rd Annual ACM Symposium on Theory of Computing (STOC ’71), Association for Computing Machinery · doi:10.1145/800157.805047
[3] Garey, M. G.; Johnson, D. S., Computers and Intractability: A Guide to the Theory of NP-Completeness, (1990), New York, NY, USA: W. H. Freeman & Co., New York, NY, USA
[4] Even, S.; Itai, A.; Shamir, A., On the complexity of timetable and multicommodity flow problems, SIAM Journal on Computing, 5, 4, 691-703, (1976) · Zbl 0358.90021 · doi:10.1137/0205048
[5] Ben-Ayed, O.; Hamzaoui, S., Multiobjective multiproduct parcel distribution timetabling: a real-world application, International Transactions in Operational Research, 19, 4, 613-629, (2012) · Zbl 1277.90047 · doi:10.1111/j.1475-3995.2012.00852.x
[6] Ribeiro, C. C., Sports scheduling: problems and applications, International Transactions in Operational Research, 19, 1-2, 201-226, (2012) · Zbl 1267.90056 · doi:10.1111/j.1475-3995.2011.00819.x
[7] Shen, Y.; Xu, J.; Zeng, Z., Public transit planning and scheduling based on AVL data in China, International Transactions in Operational Research, (2015) · Zbl 1348.90310 · doi:10.1111/itor.12164
[8] Kırış, S., AHP and multichoice goal programming integration for course planning, International Transactions in Operational Research, 21, 5, 819-833, (2014) · Zbl 1307.90162 · doi:10.1111/itor.12081
[9] Saldaña-Crovo, A.; Oliva-SanMartín, C.; Pradenas-Rojas, L., Integer programming models for scheduling problem on universities, Chilen Engineering Magazine, 15, 3, 245-259, (2007)
[10] Banczyk, K.; Boinski, T.; Krawczyk, H., Parallelization of genetic algorithms for solving university timetabling problems, Proceedings of the International Symposium on IEEE Xplore Conference: Parallel Computing in Electrical Engineering · doi:10.1109/PARELEC.2006.64
[11] Rossi-Doria, O.; Sampels, M.; Birattari, M.; Chiarandini, M.; Dorigo, M.; Gambardella, L. M., A comparison of the performance of different metaheuristics on the timetabling problem, Practice and Theory of Automated Timetabling IV, 2740, 329-351, (2003), Berlin, Germany: Springer, Berlin, Germany
[12] Thepphakorn, T.; Pongcharoen, P.; Hicks, C., Modifying regeneration mutation and hybridising clonal selection for evolutionary algorithms based timetabling tool, Mathematical Problems in Engineering, 2015, (2015) · doi:10.1155/2015/841748
[13] Di Stefano, C.; Tettamanzi, A. G. B., An evolutionary algorithm for solving the school time-tabling problem, Applications of Evolutionary Computing. Applications of Evolutionary Computing, Lecture Notes in Computer Science, 2037, 452-462, (2001), New York, NY, USA: Springer, New York, NY, USA · Zbl 0986.68886 · doi:10.1007/3-540-45365-2_47
[14] Yu, E.; Sung, K.-S., A genetic algorithm for a university weekly courses timetabling problem, International Transactions in Operational Research, 9, 6, 703-717, (2002) · Zbl 1044.90066 · doi:10.1111/1475-3995.00383
[15] Kahar, M. N. M.; Kendall, G., The examination timetabling problem at Universiti Malaysia Pahang: comparison of a constructive heuristic with an existing software solution, European Journal of Operational Research, 207, 2, 557-565, (2010) · Zbl 1205.90186 · doi:10.1016/j.ejor.2010.04.011
[16] Basir, N.; Ismail, W.; Norwawi, N., A simulated annealing for Tahmidi course timetabling, Procedia Technology, 11, 437-445, (2013) · doi:10.1016/j.protcy.2013.12.213
[17] Gunawan, A.; Ming Ng, K.; Leng Poh, K., A hybridized Lagrangian relaxation and simulated annealing method for the course timetabling problem, Computers & Operations Research, 39, 12, 3074-3088, (2012) · Zbl 1349.90349 · doi:10.1016/j.cor.2012.03.011
[18] Chacha, S.; Allen, R. M., Optimal solution strategy for university course timetabling problem, International Journal of Advanced Research in Computer Science, 4, 1, 35, (2013)
[19] Zhang, D.; Guo, S.; Zhang, W.; Yan, S., A novel greedy heuristic algorithm for university course timetabling problem, Proceedings of the 11th World Congress on Intelligent Control and Automation (WCICA ’14), IEEE · doi:10.1109/wcica.2014.7053619
[20] Shimazaki, S.; Sakakibara, K.; Matsumoto, T., Iterative optimization techniques using man-machine interaction for university timetabling problems, SpringerPlus, 4, 1, article 251, (2015) · doi:10.1186/s40064-015-1018-3
[21] Pereira, V.; Gomes Costa, H., Linear integer model for the course timetabling problem of a faculty in Rio de Janeiro, Advances in Operations Research, 2016, (2016) · Zbl 1387.90094 · doi:10.1155/2016/7597062
[22] Cruz-Rosales, M. H., The scheduling-courses problem at a university and a proposed solution [Thesis], CIICAp-UAEM
[23] Martínez-Bahena, B.; Calderón-Segura, Y. Y., Development of a management system for FCQeI hours, using a three-layer model client, web service and database [Engineering Thesis], Jiutepec, Mexico: Upemor, Jiutepec, Mexico
[24] Cruz-Chávez, M. A.; Martínez-Oropeza, A., B-Tree algorithm complexity analysis to evaluate the feasibility of its application in the university course timetabling problem, Journal of Artificial Intelligence and Soft Computing Research, 3, 4, 251-263, (2014)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.