A Multi-Objective Binary Integer Programming Model and Method for Online Course Timetable Problem: A Case Study of Mechanical Drawing Division

DOI: 10.14416/j.ind.tech.2022.08.004

Authors

  • Rati Maneengam Department of Humanities, Faculty of Applied Arts, King Mongkut’s University of Technology North Bangkok
  • Apichit Maneengam Department of Mechanical Engineering Technology, College of Industrial Technology, King Mongkut’s University of Technology North Bangkok
  • Manop Chunin Department of Humanities, Faculty of Applied Arts, King Mongkut’s University of Technology North Bangkok

Keywords:

Multi-Objective Binary Integer Programming, Online Course Timetable Problem, Multi-Objective Optimization Method, ε-constraint Method

Abstract

This paper presents the multi-objective binary integer programming model for online course timetable problems of case studies in mechanical drawing division to maximize to the remaining budget and maximize the overall lecturer satisfaction score. In addition, we propose a method to solve the proposed model with two steps: (1) Data pre-processing (2) Solve the multi-objective binary integer programming model using the branch and cut algorithm, generate a Pareto Front using the ε constraint method, and then organize focus group discussions to choose the optimal solution from a Pareto Front. The results showed that the proposed method increased the remaining budget from 500,950 baht to 501,550 baht or 0.12% and increased the total satisfaction score of lecturers from 47.83 to 49.60 or 3.70%, respectively. In addition, the proposed model reduced the computational time from 173,520 seconds to 55.80 seconds or 99.97%.

References

H. Babaei, J. Karimpour and A. Hadidi, A survey of approaches for university course timetabling problem, Computers and Industrial Engineering, 2015, 86, 43-59.

S. Imran Hossain, M.A.H. Akhand, M.I.R. Shuvo, N. Siddique and H. Adeli, Optimization of university course scheduling problem using particle swarm optimization with selective search, Expert Systems with Applications, 2019, 127, 9-24.

P. Yasari, M. Ranjbar, N. Jamili and

M.H. Shaelaie, A two-stage stochastic programming approach for a multi-objective course timetabling problem with courses cancelation risk, Computers and Industrial Engineering, 2019, 130, 650-660.

S. Daskalaki and T. Birbas, Efficient solutions for a university timetabling problem through integer programming, European Journal of Operational Research, 2005, 160(1), 106-120.

M.A. Al-Betar and A.T. Khader, A harmony search algorithm for university course timetabling, Annals of Operations Research, 2012, 194(1), 3-31.

A.A. Mahiba and C.A.D. Durai, Genetic algorithm with search bank strategies for university course timetabling problem, Procedia Engineering, 2012, 38, 253-263.

R.P. Badoni, D.K. Gupta, and P. Mishra, A new hybrid algorithm for university course timetabling problem using events based on groupings of students, Computers and Industrial Engineering, 2014, 78, 12-25.

V.I. Skoullis, I.X. Tassopoulos, and G.N. Beligiannis, Solving the high school timetabling problem using a hybrid cat swarm optimization based algorithm, Applied Soft Computing Journal, 2017, 52, 277-289.

C. Akkan and A. Gülcü, A bi-criteria hybrid Genetic Algorithm with robustness objective for the course timetabling problem, Computers and Operations Research, 2018, 90, 22-32.

N.C.F. Bagger, M. Sørensen, and T.R. Stidsen, Benders’ decomposition for curriculum-based course timetabling, Computers and Operations Research, 2018, 91, 178-189.

M.A. Nugroho and G. Hermawan, Solving university course timetabling problem using memetic algorithms and rule-based approaches, IOP Conference Series: Materials Science and Engineering, 2018, 407, 012012.

L. Saviniec, M.O. Santos, A.M. Costa, and L.M.R. dos Santos, Pattern-based models and a cooperative parallel metaheuristic for high school timetabling problems, European Journal of Operational Research, 2020, 280(3), 1064-1081.

A. Gülcü and C. Akkan, Robust university course timetabling problem subject to single and multiple disruptions, European Journal of Operational Research, 2020, 283(2), 630- 646.

A. Rezaeipanah, S.S. Matoori, and G. Ahmadi, A hybrid algorithm for the university course timetabling problem using the improved parallel genetic algorithm and local search, Applied Intelligence, 2021, 51(1), 467-492.

N.M. Arratia-Martinez, C. Maya-Padron, and P.A. Avila-Torres, University course timetabling problem with professor assignment, Mathematical Problems in Engineering, 2021, 2021, 6617177.

M.C. Chen, S.N. Sze, S.L. Goh, N.R. Sabar, and G. Kendall, A Survey of University course timetabling problem: perspectives, Trends and Opportunities, IEEE Access, 2021, 9, 106515-106529.

A. Maneengam and A. Udomsakdigool, Solving the collaborative bidirectional multi-period vehicle routing problems under a profit-sharing agreement using a covering model, International Journal of Industrial Engineering Computations, 2020, 11(2), 185-200.

R. Likert, A technique for the measurement of attitudes, Archives of Psychology, 1932, 22(140), 55.

R.J. Rovinelli and R.K. Hambleton, On the use of content specialists in the assessment of criterion-referenced test item validity, Tijdschrift voor Onderwijsresearch, 1977, 2(2), 49-60.

S.B. Merriam, Qualitative research: A guide to design and implementation, 3rd Ed., Jossey-Bass, CA, USA, 2009.

C. Puchta and J. Potter, Focus group practice, 1st Ed., SAGE Publications Ltd, CA, USA, 2004.

T.O. Nyumba, K. Wilson, C.J. Derrick, and N. Mukherjee, The use of focus group discussion methodology: Insights from two decades of application in conservation, Methods in Ecology and Evolution, 2018, 9, 20-32.

V. Chankong and Y.Y. Haimes, Multiobjective decision making: Theory and methodology. Elsevier Science Publishing Company, Inc., NY, USA, 1983.

G. Mavrotas, Effective implementation of the ε-constraint method in Multi-Objective Mathematical Programming problems, Applied Mathematics and Computation, 2009, 213(2), 455-465.

G. Chiandussi, M. Codegone, S. Ferrero, and F.E. Varesio, Comparison of multi-objective optimization methodologies for engineering applications, Computers and Mathematics with Applications, 2012, 63(5), 912-942.

T. Friedrich, C. Horoba, and F. Neumann, Multiplicative approximations and the hypervolume indicator, The 11th Annual Genetic and Evolutionary Computation Conference (GECCO 2009), Proceeding, 2009, 571-578.

Downloads

Published

2022-08-16

Issue

Vol. 18 No. 2 (2022): May-August

Section

บทความวิจัย (Research article)

License

Creative Commons License

This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

ผลงานวิจัยและบทความวิชาการที่ปรากฏในวารสารนี้ เป็นความคิดเห็นอิสระของผู้เขียน ผู้เขียนจะต้องเป็นผู้รับผิดชอบต่อผลทางกฎหมายใด ๆ ที่อาจจะเกิดขึ้นจากบทความนั้น กองบรรณาธิการและคณะจัดทำวารสารฯไม่จำเป็นต้องเห็นด้วยเสมอไป