Metaheuristic approach proposal for the solution of the bi-objective course scheduling problem

Document Type : Article

Authors

1 Department of Industrial Engineering, Kutahya Dumlupinar University, Kutahya, Turkey

2 Department of Informatics, Kutahya Dumlupinar University, Kutahya, Turkey

Abstract

Timetabling problems are among the commonly encountered problems in real life, from education institutions to airline companies. It is generally difficult to obtain optimal solutions for the timetabling problems that vary in terms of structures of constraints and objective functions, and these problems are considered being in NP-hard category, which cannot be solved in polynomial time in real life. In this study, a bi-objective mathematical model is proposed for a course scheduling problem in Kutahya Dumlupinar University Department of Industrial Engineering. While it is aimed in the first objective function to maximize the sum of the preferences of instructors determined by using the Analytic Hierarchy Process Method, it is aimed to minimize the students’ course overlap in the other. Conic scalarization method is used to combine the objective functions. Due to NP-hard nature of the problem, the Tabu Search Algorithm, one of metaheuristic approaches is used to solve it. Using the obtained data, the Tabu Search Algorithm by considering the proposed bi-objective mathematical model is designed for the problem and a software is developed in Excel Visual Basic program. The experimental results are evaluated with Analysis of Variance by using Minitab Program, comparing the results, satisfactory solutions are obtained.

Keywords

References

References:
1. Lewis, R. and Thompson, J. "Analysing the effects of solution space connectivity with an effective metaheuristic for the course timetabling problem", European Journal of Operational Research, 240, pp. 637- 648 (2015).
2. Song, T., Liu, S., Tang, X., et al. "An iterated local search algorithm for the university course timetabling problem", Applied Soft Computing, 68, pp. 597-608 (2018).
3. Yasari, P., Ranjbar, M., Jamili, N., et al. "A two-stage stochastic programming approach for a multi-objective course timetabling problem with courses cancelation risk", Computers & Industrial Engineering, 130, pp. 650-660 (2019).
4. Imran Hossain, S., Akhand, M.A.H., Shuvo, M.I.R., et al. "Optimization of university course scheduling problem using particle swarm optimization with selective search", Expert Systems With Applications, 127, pp. 9-24 (2019).
5. Ozturk, Z.K., Kasimbeyli, N., Ozdemir, M.S., et al. "University timetabling problem considering user preferences", Journal of Industrial Engineering, 27(1), pp. 2-16 (2015).
6. Badri, M.A. "A two-stage multiobjective scheduling model for faculty-course-time assignments", European Journal of Operational Research, 94, pp. 16-28 (1996).
7. Ozdemir, M.S. and Gasimov, R.N. "The analytic hierarchy process and multiobjective 0-1 faculty course assignment", European Journal of Operational Research, 157, pp. 398-408 (2004).
8. Aladag, C.H., Hocaoglu, G., and Basaran, M.A. "The effect of neighborhood structures on tabu search algorithm in solving course timetabling problem", Expert Systems with Applications, 36(10), pp. 12349-12356 (2009).
9. Akkan, C. and Gulcu, A. "A bi-criteria hybrid genetic algorithm with robustness objective for the course timetabling problem", Computers & Operations Research, 90, pp. 22-32 (2018).
10. Jamili, A., Hamid, M., Gharoun, H., et al. "Developing a comprehensive and multi-objective mathematical model for university course timetabling problem: A real case study", The  2nd European Int. Conf. on Industrial Engineering and Operations Management, Paris, France ( 2018).
11. Al-Yakoob, S.M. and Sherali, H.D. "A column generation mathematical programming approach for a class-faculty assignment problem with preferences", Computational Management Science, 12, pp. 297-318 (2015).
12. AlHadid, I., Kaabneh, K., Tarawneh, H., et al.  Investigation of simulated annealing components to solve the university course timetabling problem", Italian Journal of Pure and Applied Mathematics, 44, pp. 291-301 (2020).
13. Al-Jarrah, M.A., Al-Sawalqah, A.A., and Al-Hamdan, S.F. "Developing a course timetable system for academic departments using genetic algorithm", Jordanian Journal of Computers and Information Technology, 3(1), pp. 25-36 (2017).
14. Altunay, H. and Eren, T. "A literature review for course scheduling problem", Pamukkale University Journal of Engineering Sciences, 23(1), pp. 55-70 (2017).
15. Saaty, T.L. "How to make a decision: The analytic hierarchy process", European Journal of Operational Research, 48(1), pp. 9-26 (1990).
16. Can, E. "Metaheuristic approach proposal for the solution of the multiobjective course scheduling problem", Master's Thesis. Institute of Science And Technology, Kutahya Dumlupinar University (2019).
17. Ustun, O. "Interactive reference point procedure based on the conic scalarizing function", The Scientific World Journal, 2014(5), 242803 (2014).
18. Montgomery, D.C., Design and Analysis of Experiments, 5th Edn., John Wiley Sons, New York, US (1991).
19. Kocacaliskan, I. and Bingol, N.A. Biyoistatistik [Biostatistics], 3th Edn., Nobel Academic Publications, Ankara, Turkey (2017).
20. Scheffe, H., The Analysis of Variance, 1st Edn., Wiley- Interscience, New York, US (1999).
Scientia Iranica
Volume 30, Issue 4 - Serial Number 4
Transactions on Industrial Engineering (E)
July and August 2023
Pages 1435-1449

Files

Share

How to cite

Statistics