Optimasi Penjadwalan Mata Pelajaran di SMA Negeri 3 Tondano Menggunakan Integer Linear Programming

Abstract

The preparation of school timetables is a complex problem because it involves various components, such as teachers, classes, time slots, and numerous constraints that must be satisfied. Manual timetable construction often leads to scheduling conflicts, including teacher and classroom clashes. Therefore, an optimization method is required to generate an efficient and optimal timetable. This study aims to develop a timetable optimization model using the Integer Linear Programming (ILP) method and to obtain an optimal scheduling solution at SMA Negeri 3 Tondano. The proposed model consists of 7,245 decision variables and 14,394 constraints that reflect the actual conditions of the school, including instructional time allocation, teacher availability, and scheduling regulations. The model was solved using LINGO 22.0 software. The results show that the developed Integer Linear Programming model successfully generated feasible timetables without teacher or classroom scheduling conflicts in all 30 program runs. In addition, Global Optimum status was achieved in several runs, while the objective function values ranged from 17 to 19, with computation times varying from 18 seconds to 8 minutes and 59 seconds. These results indicate that the proposed model is capable of satisfying all scheduling constraints and producing effective and efficient solutions. Therefore, the Integer Linear Programming method can serve as an alternative approach to assist schools in developing more structured, optimal, and error-free timetables.