Document Type : Original Article

Authors

1 Faculty of Industrial and Mechanical Engineering, Qazvin Branch, Islamic Azad University, Qazvin, Iran.

2 School of Mathematics and Statistics, University of Melbourne, Melbourne, Parkville, VIC 3010, Australia.

Abstract

Scheduling is a vital part of daily life that has been the focus of attention since the 1950s. Knowledge of scheduling is a very important and applicable category in industrial engineering and planning of human life. In the field of education, scheduling, and timetabling for best results in classroom teaching is one of the most challenging issues in university programming. As each university has its own rules, policies, resources, and restrictions a unique model of scheduling and timetabling cannot implement. This can cause more complexity and challenging point which needs to be considered scientifically. This study presents a sound scientific model of timetabling and classroom scheduling to improve faculties’ desirability based on days, times, and contents preferences. A sample in Parand branch of Islamic Azad university   chooses using the Bat metaheuristic algorithm. By considering the limitations, some unchangeable constraints regarding the specific rules and minimal linear delimitation of the soft constraints of the model, using the appropriate meta-heuristic algorithm to reduce the model run time to a minimum. The results show that the algorithm achieves better results in many test data compared to other algorithms due to meeting many limitations in the problem coding structure. The Bat algorithm is compared with four other algorithms while comparing the results of solving the proposed mathematical model with five metaheuristic algorithms to evaluate the performance. In this research, a multi-objective model is presented to maximize the desirability of professors and to solve the model using Bat, Cuckoo Search, Artificial bee colony, firefly, and Genetic algorithms. In this research 40 different runs of each algorithm were compared, and conclusions were drawn. Modeling has been solved with GAMS and MATLAB software and using the bat meta-heuristic algorithm. It is concluded that in this model, the bat algorithm is the most appropriate algorithm with the shortest time, which has caused the satisfaction of the professors of the educational departments of this academy.

Keywords

Agarwal, A., Colak, S., & Erenguc, S. (2011). A neurogenetic approach for the resource-constrained project scheduling problem. Computers & operations research, 38(1), 44-50.
Ahmed, L.N., Özcan, E. and Kheiri, A. (2012). Solving high school timetabling problems worldwide using selection hyper-heuristics. Expert Systems with Applications. 42(13), 5463-5471.
Akkan, C. and Gulcu, A. (2018). A bi-criteria hybrid Genetic Algorithm with robustness objective for the course timetabling problem. Computers & Operations Research. 90(1), 22-32.
Alzaqebeh, M., & Abdullah, S. (2015). Hybrid bee colony optimization for examination timetabling problems. Computers & Operations Research, 54, 142-154.‏
Badoni, R. P., Gupta, D. K., & Mishra, P. (2014). A new hybrid algorithm for university course timetabling problem using events based on groupings of students. Computers & Industrial Engineering, 78, 12-25.
Bagger, N. C. F., Sørensen, M., & Stidsen, T. R. (2018). Benders’ decomposition for curriculum-based course timetabling. Computers & Operations Research, 91, 178-189.‏
Barrera, D., Velasco, N., & Amaya, C. A. (2012). A network-based approach to the multi-activity combined timetabling and crew scheduling problem: Workforce scheduling for public health policy implementation. Computers & Industrial Engineering, 63 (4), 802-812.
Basir, N., Ismail, W., & Norwawi, N. M. (2013). A simulated annealing for Tahmidi course timetabling. Procedia Technology, 11(1), 437-445.‏
Bolaji, A.L., Khader, A.T., Al-Betar, M.A. and Awadallah, M.A. (2014). University Course Timetabling using Hybridized Artificial Bee Colony with Hill Climbing Optimizer, Journal of Computational Science, 5(5), 809-818.
Daskalaki, S., Birbas, T., & Housos, E. (2004). An integer programming formulation for a case study in university timetabling. European Journal of Operational Research, 153(1), 117-135.‏
Di Gaspero, L., McCollum, B., & Schaerf, A. (2007). The second international timetabling competition (ITC-2007): Curriculum-based course timetabling (track 3). Technical Report QUB/IEEE/Tech/ITC2007/CurriculumCTT/v1. 0, Queen’s University, Belfast, United Kingdom.
Dimopoulou, M., & Miliotis, P. (2001). Implementation of a university course and examination timetabling system. European Journal of Operational Research, 130(1), 202-213.‏
Fonseca, George HG, et al. Integer programming techniques for educational timetabling. European Journal of Operational Research 262.1 (2017): 28-39.
Goh, S. L., Kendall, G., & Sabar, N. R. (2017). Improved local search approaches to solve the post enrolment course timetabling problem. European Journal of Operational Research, 261(1), 17-29.
Jafari H, Salmasi N. Maximizing the nurses’ preferences in nurse scheduling problem: mathematical modeling and a meta-heuristic algorithm. Journal of Industrial Engineering International. 2015 Sep 1;11(3):439-58.
Landir et. al. 2020 Saviniec, L., Santos, M. O., Costa, A. M., & dos Santos, L. M. (2020). Pattern-based models and a cooperative parallel metaheuristic for high school timetabling problems. European Journal of Operational Research, 280(3), 1064-1081.
Lewis R, Thompson J. On the application of graph colouring techniques in round-robin sports scheduling. Computers & Operations Research. 2011 Jan 31;38(1):190-204.
Lü, Z., & Hao, J.-K. (2010). "Adaptive tabu search for course timetabling". European Journal of Operational Research, 200(1), 235-244.
Nagata, Y. (2018). Random partial neighborhood search for the post-enrollment course timetabling problem. Computers & Operations Research, 90, 84-96.
Pereira, V., & Gomes Costa, H. (2016). Linear integer model for the course timetabling problem of a faculty in Rio de Janeiro. Advances in Operations Research, 2016.
Phillips, A. E., Waterer, H., Ehrgott, M., & Ryan, D. M. (2015). Integer programming methods for large-scale practical classroom assignment problems. Computers & Operations Research, 53, 42-53.‏
Pita, J. P., Barnhart, C., & Antunes, A. P. (2013). Integrated flight scheduling and fleet assignment under airport congestion. Transportation Science, 47(4), 477-492.
Post, G., Kingston, J. H., Ahmadi, S., Daskalaki, S., Gogos, C., Kyngas, J., ... & Schaerf, A. (2014). XHSTT: an XML archive for high school timetabling problems in different countries. Annals of Operations Research, 218 (1), 295-301.
Rangel-Valdez, N., Jasso-Luna, J. O., Rodriguez-Chavez, M. H., & Bujano-Guzman, G. (2014)., Practical relaxation of a special case of the Curriculum-Based Course Timetabling problem, Progress in Artificial Intelligence, 2(4), 237-248.
Ranjbar, M., Rostami, S., “Fortnightly Course Scheduling Problem: A Case Study”, 2nd International Industrial Engineering Conference, The 5th Int. Conference of The Iranian Society of Operations Research, 2012.
Reisman, A., Kumar, A., & Motwani, J. (1997). Flowshop scheduling/sequencing research: A statistical review of the literature, 1952-1994. IEEE transactions on Engineering Management, 44(3), 316-329.‏
Shafia, M. A., Aghaee, M. P., Sadjadi, S. J., & Jamili, A. (2012). Robust Train Timetabling problem: Mathematical model and Branch and bound algorithm. Intelligent Transportation Systems, IEEE Transactions on, 13 (1), 307-317.
Shahmoradi Hadi, Saeedeh's ketabi, Ismailian Majid (2018), timetabling problem of university courses using constraint planning, production management and operations.
Song, K., Kim, S., Park, M., & Lee, H. S. (2017). Energy efficiency-based course timetabling for university buildings. Energy, 139, 394-405.
Stafford Jr, E. F., & Tseng, F. T. (2002). Two models for a family of flowshop sequencing problems. European Journal of Operational Research, 142(2), 282-293.‏
Tavakoli,M. M.,SHIROUYEHZAD H.,HOSSEINZADEH LOTFI F.,NAJAFI E(20018), Proposing A New Mathematical Model For Planning Of University Course Timetabling Based On Quality Of Lesson Presentation, JOURNAL OF OPERATIONAL RESEARCH AND ITS APPLICATIONS,15(3),45-66.
Veenstra, M. and Vis, I.F.A. (2016). School timetabling problem under disturbances. Computers & Industrial Engineering, 95(1) 175-186.
Vermuyten, H., Lemmens, S., Marques, I., & Beliën, J. (2016). Developing compact course timetables with optimized student flows.European Journal of Operational Research, 251(2), 651-661.
Wood, J., & Whitaker, D. (1998). Student centred school timetabling. Journal of the Operational Research Society, 49(11), 1146-1152.
Yang, X. S. (2010). A new metaheuristic bat-inspired algorithm. In Nature inspired cooperative strategies for optimization (NICSO 2010) (pp. 65-74). Springer, Berlin, Heidelberg.