Sidang Tugas Akhir

Isdad Fuadi Sakbana
G54101017

Penyelesaian Masalah Penugasan yang Diperumum dengan Menggunakan Teknik Pembangkitan Kolom

Masalah penugasan yang diperumum (generalized assgnment problem/GAP) dapat dideskripsikan sebagai berikut: misalkan diberikan himpunan n buah pekerjaan yang harus dikerjakan oleh m buah pekerja/mesin. Akan dicari pasangan antara pekerjaan denagn pekerja/mesin, dengan setiap pekerjaan dikerjaan oleh satu pekerja/mesin dan adanya kendala batasan kemampuan kerja dari masing-masing pekerja/mesin. Model masalah penugasan yang diperumum bertujuan untuk mencari pasangan penugasan yang memaksimumkan keuntungan. Ide penyelesaian dari model masalah penugasan yang diperumum dengan menggunakan teknik pembangkitan kolom (column generation) adalah dengan hanya menggunakan beberapa variabel dari keseluruhan variabel masalah induk. Jika solusi pemrograman linear tersebut belum optimal, maka pada pemrograman linear tersebut harus ditambahkan variabel-variabel lain yang sesuai dengan kriteria tertentu. Pemrograman linear yang telah ditambahkan variabel lain, kemudian diselesaikan kembali sampai memenuhi suatu kriteria pemberhentian.