Seminar Tugas Akhir

Ratna Nirwana Sari
G54101002

Penyelesaian Crew Rostering Problem (CRP) dengan Menggunakan Algoritma Heuristik Caprara

Perusahaan transportasi semacam maskapai penerbangan atau perkeretaapian biasanya menawarkan sejumlah macam perjalanan kepada konsumen. Setiap perjalan ini membutuhkan pekerja. Bagi pekerja, perjalanan itu merupakan tugas. Oleh karena itu, perusahaan membutuhkan jadwal 'tugas apa dilaksanakan oleh siapa' dalam suatu periode tertentu. Agar biaya pengadaan perjalanan ini minimum, maka perusahaan akan meminimumkan banyaknya pekerja yang dibutuhkan terkait dengan sejumlah aturan/kendala. masalah penugasan pekerja atau Crew Restoring Problem (CRP) adalah meminimumkan banyaknya pekerja yang dibutuhkan dan menentukan rangkaian tugas atau roster yang harus dilaksanakan setiap pekerja dalam setiap periode tertentu. Secara matenatik CRP dimodelkan dahulu dalam bentuk graf kemudian diubah menjadi bentuk IntegerLinear Programming (ILP). Setelah itu, dicari solusinya berupa sekumpulan roster dengan menggunakan Algoritma Heuristik Caprara yang dibuat oelh Caprara dan kawan-kawan dengan terlebih dahulu mencari batas bawah panjang keseluruhan roster. Roster-roster 0ini kemudian akan menentukan banyaknya pekerja minimum dan rangkaian tugas yang harus dilaksanakan setiap pekerja.