Penerapan Algoritma Pewarnaan Graf Recursive Largest First dan Sequential Coloring Dalam Menentukan Jadwal Waktu Penerbangan Domestik Maskapai Garuda Indonesia

Abstract

Penjadwalan adalah bagian penting dari kegiatan penerbangan, sehingga sistem dan pembagian slotnya harus diperhatikan dengan cermat. Penelitian ini bertujuan menggunakan pewarnaan graf untuk menentukan jadwal penerbangan, dalam kasus ini diambil data penerbangan pesawat Garuda Indonesia. Untuk menghindari potensi kecelakaan atau kesibukan kru, masalah penjadwalan ini didekati dengan permasalahan pewarnaan dalam graf, dan algortima yang digunakan adalah menggunakan algoritma Recursive Largest First (RLF) dan Sequential Coloring. Simpul dalam graf mewakili bandara, sementara sisi menunjukkan ketersediaan slot penerbangan saat lepas landas pertama. Pewarnaan dengan algoritma Recursive Largest First (RLF) dan Sequential Coloring menghasilkan jumlah warna dan bilangan kromatik yang sama. Jumlah warna minimum yang dihasilkan memungkinkan pembentukan jadwal penerbangan optimal. Aplikasi kedua algoritma menghasilkan jumlah warna yang sama, sehingga hasil akhir penjadwalan penerbangan domestik Garuda Indonesia juga memiliki jadwal yang seragam, dengan membentuk sesi jadwal penerbangan berdasarkan jumlah warna minimum yang telah dihasilkan.

Scheduling is essential in flight operations, requiring careful consideration of the system and slot distribution. This study aims to determine the flight schedules, in which case Garuda Indonesia flight data is taken. To avoid potential accidents or crew rush, this scheduling problem is approached with a graph coloring problem, and the algorithms used are Recursive Largest First (RLF) and Sequential Coloring algorithms. Here, vertices represent airports, and edges indicate available flight slots at the first take-off. Both Recursive Largest First (RLF) dan Sequential Coloring algorithms produce the same number of colors and chromatic numbers. The minimum number of colors achieved facilitates the creation of optimal flight schedules. Consequently, Garuda Indonesia's domestic flight schedules are uniform, forming the sessions based on the minimum number of colors generated.