A Multi-Objective Binary Integer Programming Model and Method for Online Course Timetable Problem: A Case Study of Mechanical Drawing Division
Abstract
งานวิจัยนี้นำเสนอตัวแบบกำหนดการเชิงจำนวนเต็มทวิภาคแบบหลายจุดประสงค์ (Multi-Objective Binary Integer Programming Model) สำหรับปัญหาการจัดตารางสอนออนไลน์กรณีศึกษาสาขาวิชาเขียนแบบเครื่องกล โดยมีจุดประสงค์เพื่อทำให้เหลืองบประมาณมากที่สุดและเพิ่มคะแนนความพึงพอใจรวมของอาจารย์มากที่สุด นอกจากนี้ผู้วิจัยได้นำเสนอวิธีการเพื่อแก้ปัญหาตัวแบบจำลองที่นำเสนอโดยมี 2 ขั้นตอนดังนี้ คือ (1) การเตรียมข้อมูลก่อนการประมวลผล (2) แก้ปัญหาตัวแบบกำหนดการเชิงจำนวนเต็มทวิภาคแบบหลายจุดประสงค์ด้วยวิธีการแตกกิ่งและตัด (Branch and Cut Algorithm) และสร้างพาเรโตฟร้อน (Pareto Front) ด้วยวิธีข้อจำกัดเอปซิลอน (ε-constraint method) จากนั้นจัดสนทนากลุ่มเพื่อรูปแบบที่ดีที่สุดจากพาเรโตฟร้อน ผลการวิจัยพบว่าตัวแบบกำหนดการเชิงจำนวนเต็มทวิภาคแบบหลายจุดประสงค์ที่นำเสนอสามารถทำให้เหลืองบประมาณมากขึ้นจาก 500,950 บาท เป็น 501,550 บาท หรือร้อยละ 0.12 และเพิ่มคะแนนความพึงพอใจของอาจารย์โดยรวมจาก 47.83 คะแนนเป็น 49.60 คะแนน หรือร้อยละ 3.70 ตามลำดับ นอกจากนี้ตัวแบบที่นำเสนอสามารถลดเวลาในการคำนวณให้น้อยลงจากเดิม 173,520 วินาที เป็น 55.80 วินาที หรือร้อยละ 99.97
This paper presents the multi-objective binary integer programming model for online course timetable problems of case studies in mechanical drawingdivision 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 solutionfrom 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%.
Keywords
[1] H. Babaei, J. Karimpour and A. Hadidi, A survey of approaches for university course timetabling problem, Computers and Industrial Engineering, 2015, 86, 43-59.
[2] 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.
[3] 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.
[4] 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.
[5] 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.
[6] 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.
[7] 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.
[8] 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.
[9] 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.
[10] 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.
[11] 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.
[12] 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.
[13] 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.
[14] 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.
[15] 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.
[16] 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.
[17] 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.
[18] R. Likert, A technique for the measurement of attitudes, Archives of Psychology, 1932, 22(140), 55.
[19] 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.
[20] S.B. Merriam, Qualitative research: A guide to design and implementation, 3rd Ed., Jossey-Bass, CA, USA, 2009.
[21] C. Puchta and J. Potter, Focus group practice, 1st Ed., SAGE Publications Ltd, CA, USA, 2004.
[22] 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.
[23] V. Chankong and Y.Y. Haimes, Multiobjective decision making: Theory and methodology. Elsevier Science Publishing Company, Inc., NY, USA, 1983.
[24] G. Mavrotas, Effective implementation of the ε-constraint method in Multi-Objective Mathematical Programming problems, Applied Mathematics and Computation, 2009, 213(2), 455-465.
[25] 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.
[26] 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.
DOI: 10.14416/j.ind.tech.2022.08.004
Refbacks
- There are currently no refbacks.
