Masalah max-min matching dengan penugasan terbatas

Abstract

Dalam masalah matching kadang-kadang memerlukan penetapan beberapa pekerjaan untuk satu prosesor atau beberapa prosesor untuk satu pekerjaan dengan beberapa batas pada sejumlah penugasan yang diperbolehkan. Salah satu contoh yang termasuk penugasan yaitu penugasan konsultan ke proyek. Sehingga tujuan perusahaan adalah memaksimumkan keuntungan atau meminimumkan biaya, atau memaksimumkan nilai minimum tingkat kemampuan prosesor-prosesor melakukan suatu pekerjaan dalam suatu matching yang maksimal. Masalah ini merupakan bentuk variasi dari masalah matching berbobot dengan penugasan terbatas. Pada tulisan ini akan dibahas suatu metode untuk menyelesaikan masalah tersebut yaitu metode node splitting yang digambarkan dalam suatu algoritma yang menyelesaikan masalah matching yang berfokus pada memaksimumkan tingkat prosesor yang minimum dalam melakukan pekerjaan.