Seminar Tugas Akhir

Agus Tri Antoro
G54102026

Penyelesaian Masalah Crew Pairing dengan Menggunakan Teknik Pembangkitan Kolom: Tinjauan Aspek Pemrograman

Setiap perusahaan penerbangan dituntut untuk dapat memenuhi permintaan masyarakat. Di pihak lain, perusahaan juga harus bisa meminimumkan biaya demi kelangsungan perusahaan. Untuk itu perusahaan harus bisa menentukan jadwal penerbangan yang dapat memenuhi keduanya. Penjadwalan penerbangan tersebut dilaksanakan oleh sejumlah crew (pekerja). Masalah penjadwalan penugasan crew pada penerbangan disebut masalah crew pairing atau sering juga disebut sebagai masalah crew scheduling yang berkaitan dengan penjadwalan dalam skala besar. Suatu perusahaan penerbangan harus memenuhi sejumlah penerbangan dalam periode waktu tertentu. Jadwal penerbangan berupa sejumlah flight segment, yaitu penerbangan nonstop dari suatu tempat ke tempat lain. Beberapa flight segment membentuk suatu flight service. Flight service adalah penerbangan yang terdiri atas beberapa flight segment yang berurutan dari suatu tempat ke tempat lain dengan waktu istirahat (rest time) di antara flight segment-flight segment penyusunnya. Untuk melaksanakan suatu jadwal penerbangan, perusahaan tersebut memerlukan sejumlah crew dan menugaskannya pada suatu crew pairing. Crew pairing adalah sebuah rangkaian dari beberapa flight service yang berurutan yang dimulai dari suatu pangkalan (base) dan kembali ke pangkalan semula. Pemilihan rangkaian penerbangan yang dilakukan oleh sejumlah pekerja tersebut dapat dimodelkan sebagai set covering problem. Pada umumnya banyaknya variabel pada masalah penjadwalan sangat besar. Penyelesaian masalah set covering dalam skala besar dapat dilakukan diantaranya dengan menggunakan teknik pembangkitan kolom (column generation). Teknik Pembangkitan Kolom merupakan suatu teknik untuk menyelesaikan masalah dengan hanya menggunakan sebagian variabel dari keseluruhan variabel yang ada untuk menghasilkan solusi optimal dari masalah utama. Dari teknik pembangkitan kolom akan dihasilkan suatu himpunan crew pairing dengan biaya minimum yang dapat menjalankan seluruh penerbangan yang telah dijadwalkan.