A deep-belief network approach for course scheduling

Document Type : Research Paper

Authors

1 Department of Computer Science, Faculty of Statistics, Mathematics and Computer Science, Allameh Tabataba’i University, Tehran, Iran.

2 Department of Computer Engineering, Islamic Qazvin Azad University, Qazvin, Iran.

10.22105/jarie.2020.243184.1185

Abstract

The scheduling of academic courses is a problem in which a weekly schedule is produced for educational purposes. Many different types of scheduling problems exist at various universities in accordance with their laws, needs, and constraints. These problems fall into the category of NP-hard problems and are incredibly complex. In this paper, an intelligent system for scheduling courses using the deep-belief network is proposed. The reason why the proposed system is intelligent is that it can learn the constraints, inputs, and other necessary parameters in one step by receiving the inputs as well as the training needed by the deep-belief network. The deep-belief network used has one output layer, four hidden layers, and four input layers. The experimental results of this research show that the deep-belief network proposed for the scheduling of academic courses provides a better score, less error, and execution time compared with Sequence-Based Selection Hyper-Heuristic (SSHH) approach.

Keywords

Main Subjects


[1]         Kazarlis, S., Petridis, V., & Fragkou, P. (2005). Solving university timetabling problems using advanced genetic algorithms. GAs2(7), 8-12.
[2]         McCollum, B. (2006, August). A perspective on bridging the gap between theory and practice in university timetabling. International conference on the practice and theory of automated timetabling (pp. 3-23). Springer, Berlin, Heidelberg.‏
[3]          Aladag, C. H., & Hocaoglu, G. (2007). A tabu search algorithm to solve a course timetabling problem. Hacettepe journal of mathematics and statistics36(1), 53-64.
[4]         Carter, M. W. (2000, August). A comprehensive course timetabling and student scheduling system at the University of Waterloo. International conference on the practice and theory of automated timetabling (pp. 64-82). Springer, Berlin, Heidelberg.
[5]         Kheiri, A., & Keedwell, E. (2017). A hidden markov model approach to the problem of heuristic selection in hyper-heuristics with a case study in high school timetabling problems. Evolutionary computation25(3), 473-501.
[6]         Liu, Y., Zhou, S., Chen, Q. (2011). Discriminatory deep faith networks for visual data       classification. Pattern recognition, 44(10-11), 2287-2296. 
[7]         Burke, E. K., & Petrovic, S. (2002). Recent research directions in automated timetabling. European journal of operational research140(2), 266-280.
[8]         Burke, E., Jackson, K., Kingston, J. H., & Weare, R. (1997). Automated university timetabling: The state of the art. The computer journal40(9), 565-571.
[9]         Carter, M. W., & Laporte, G. (1995, August). Recent developments in practical examination timetabling. International conference on the practice and theory of automated timetabling (pp. 1-21). Springer, Berlin, Heidelberg.
[10]     Corr, P. H., McCollum, B., McGreevy, M. A. J., & McMullan, P. (2006). A new neural network based construction heuristic for the examination timetabling problem. In Parallel problem solving from nature-PPSN IX (pp. 392-401). Springer, Berlin, Heidelberg.
[11]     Glover, F. (1987). Tabu search methods in artificial intelligence and operations research. ORSA artificial intelligence, 1(2).‏ ci.nii.ac.jp/naid/10026173744
[12]     Hinton, G. E., & Salakhutdinov, R. R. (2006). Reducing the dimensionality of data with neural networks. Science, 313(5786), 504-507.‏
[13]     Kheiri, A., Özcan, E., Lewis, R., & Thompson, J. (2016). A sequence-based selection hyper-heuristic: A case study in nurse rostering. Proceedings of the 11th international conference on practice and theory of automated timetabling (pp. 503-505). Udine, Italy.
[14]     Lee, M., Pham, H. & Zhang, X. (1999). Methodology for priority with application to software development process. European journal of operational research, 118(2), 375-389.    
[15]     Lee, H., Ekanadham, C., & Ng, A. (2007). Sparse deep belief net model for visual area V2. Advances in neural information processing systems20, 873-880.
[16]     Lai, X., Hao, J. K., Glover, F., & Lü, Z. (2018). A two-phase tabu-evolutionary algorithm for the 0–1 multidimensional knapsack problem. Information sciences, 436, 282-301.‏
[17]     Keyvanrad, M. A., & Homayounpour, M. M. (2014). A brief survey on deep belief networks and introducing a new object oriented toolbox (DeeBNet). https://arxiv.org/abs/1408.3264
[18]    Salakhutdinov, R., & Hinton, G. (2009, April). Deep boltzmann machines. Artificial intelligence and statistics (pp. 448-455). http://proceedings.mlr.press/v5/salakhutdinov09a/salakhutdinov09a.pdf
[19]    Dener, M., & Calp, M. H. (2018). Solving the exam scheduling problems in central exams with genetic algorithms. https://arxiv.org/abs/1902.01360
[20]     Zhang, H., Huang, T., Liu, S., Yin, H., Li, J., Yang, H., & Xia, Y. (2020). A learning style classification approach based on deep belief network for large-scale online education. Journal of cloud computing, 9(1), 9-26.
[21]     Sanchis-Font, R., Castro-Bleda, M. J., Gonzalez, J. A., Pla, F., & Hurtado, L. F. (2020). Cross-Domain Polarity Models to Evaluate User eXperience in E-learning. Neural processing letters. https://doi.org/10.1007/s11063-020-10260-5
[22]    AlHadid, I., Kaabneh, K., Tarawneh, H., & Alhroob, A. (2020). Investigation of simulated annealing components to solve the university course timetabling problem. Italian journal of pure and applied mathematics, 44, 282-290. https://www.researchgate.net/profile/Huan_Nan_Shi/publication/343609279_Schur_convexity_of_the_dual_form_of_complete_symmetric_function_involving_exponent_parameter/links/5f33e6d192851cd302ef63fa/Schur-convexity-of-the-dual-form-of-complete-symmetric-function-involving-exponent-parameter.pdf#page=306
[23]     Hossain, S. I., Akhand, M. A. H., Shuvo, M. I. R., Siddique, N., & Adeli, H. (2019). Optimization of university course scheduling problem using particle swarm optimization with selective search. Expert systems with applications127, 9-24.
[24]    Chen, T., & Xu, C. (2015). Solving a timetabling problem with an artificial bee colony algorithm. World transactions on engineering and technology education, 13(3), 438-442. http://www.wiete.com.au/journals/WTE&TE/Pages/Vol.13,%20No.3%20(2015)/41-Chen-T.pdf
[25]     Nugroho, M. A., & Hermawan, G. (2018). Solving University course timetabling problem using memetic algorithms and rule-based approaches. MS&E407(1), 012012.
[26]     Bolaji, A.L., Khader, A.T., Al-Betar, M.A., & Awadallah, M.A. (2014). University course timetabling using hybridized artificial bee colony with hill climbing optimizer. Journal of computational science, 5(5), 809-818.
[27]     Rizk Y., Hajj, N., Mitri, N., & Awad, M. (2019). Deep belief networks and cortical algorithms: A comparative study for supervised classification. Applied computing and informatics, 15(2), 81-93.
[28]     MathWorks:Deep Neural Network, Program Code in MATLAB. Retrieved April 12, 2020, from https://ww2.mathworks.cn/matlabcentral/fileexchange/42853-deep-neural-network
[30]     Fukushima, K. (1988). A hierarchical neural network capable of visual pattern recognition. Neural newt. 1(2) 119–130.
[31]     Felder, R. M., Soloman, B. A. (1996). Index of learning styles questionnaire. Retrieved 18 September, 2020 from http://www.engr.ncsu.edu/learningstyles/ilsweb.html