Optimisasi Penyusunan Jadwal Menggunakan Pendekatan Pembangkit Kolom (Column Generation)

Penyusunan jadwal memiliki proses pembuatan yang cukup rumit, khususnya penjadwalan yang memiliki kombinasi yang sangat besar. Hal ini dapat diselesaikan dengan menggunakan program linear. Permasalahan penjadwalan
dimodelkan dengan menggunakan pemograman linier integer dan diselesaikan menggunakan metode pendekatan pembangkit kolom (Column Generation). Metode pembangkit kolom mengambil sub himpunan dari himpunan kolom yang besar. Kolom baru ini dibangkitkan hanya saat diperlukan, yaitu ketika variabel
yang bersesuaian dengan kolom tersebut berpotensi mengoptimalkan fungsi tujuan. Adapun rumusan masalah dari penelitian ini adalah “Bagaimana optimasi penyusunan jadwal dengan pendekatan column generation?”. Sedangkan tujuan
dari penelitian ini adalah memodelkan program integer untuk penyusunan jadwal,membentuk proses program integer dengan pendekatan column generation, dan mendapatkan hasil optimasi dari penyusunan jadwal. Penelitian ini adalah penelitian teoritis. Selanjutnya pendekatan masalah yang dilakukan merupakan studi kepustakaan yang berpedoman pada berbagai sumber yang relevan terhadap permasalahan program bilangan bulat (integer programming) untuk penyusunan jadwal menggunakan pendekatan column generation. Berdasarkan hasil pembahasan, diperoleh model program linier integer
masalah penjadwalan. Selanjutnya, model tersebut diproses melalui beberapa tahap yaitu menentukan master problem, membuat RMP, mengujikan apakah solusi RMP juga merupakan solusi optimal master problem dengan menggunakan
dual dan pricing problem. Tahapan tersebut diaplikasikan ke dalam penjadwalan mata pelajaran sehingga didapat hasil yang optimal.