Masalah Penugasan Untuk Kasus Minimasi Tidak Normal

Langkah Langkah

1. Menambahkan baris dummy bila karyawan lebih sedikit daripada pekerjaannya atau menambahkan kolom dummy bila pekerjaan lebih sedikit jumlahnya daripada karyawan. Lalu mengubah matriks biaya menjadi matrik reduce cost matriks dengan cara memilih biaya terkecil setiap barisnya, kemudian mengurangi seluruh elemen biaya dalam baris itu dengan elemen biaya terkecil.

2. Setelah diperoleh tabel Reduce-Cost Matriks, kita cek apakah setiap kolom memiliki sedikitnya satu elemen bernilai nol (selain dummy E). Bila masih ada kolom yang belum mengandung nilai nol, maka kita cari elemen terkecil pada kolom yang belum mengandung nilai nol. Kemudian kurangi seluruh elemen pada kolom tersebut dengan elemen terkecil yang sudah ditentukan. Lakukan langkah tersebut, sampai diperoleh sedikitnya satu elemen bernilai nol pada setiap kolom.

3. Langkah selanjutnya adalah mencari skedul penugasan dengan suatu Total-Opportunity-Cost nol, yaitu dengan menarik sejumlah minimum garis horisontal dan/atau vertikal untuk meliputi seluruh elemen bernilai nol dalam total-opportunity cost sehingga diperoleh tabel test for optimality.

4. Jika pada tabel test for optimality jumlah garis belum mencapai jumlah baris atau kolom, maka dilakukan revisi. Caranya adalah dengan mengurangi seluruh elemen yang belum terliput oleh garis dengan elemen terkecil yang belum terliput oleh garis. Kemudian tambahkan seluruh elemen yang dialui oleh dua garis dengan elemen terkecil yang belum terliput oleh garis (kecuali elemen pada dummy). Ulangi langkah 3 dan 4 sehingga diperoleh jumlah garis yang sama dengan jumlah kolom atau baris.

5. Setelah diperoleh jumlah garis yang sama dengan jumlah kolom atau baris, maka matriks penugasan optimal telah tercapai. Kemudian pilih baris yang memiliki elemen bernilai nol paling sedikit. Kemudian pasangkan karyawan dengan pekerjaan yang elemennya bernilai nol pada baris yang telah dipilih, lalu diikuti dengan pasangan karyawan dengan pekerjaan yang lainnya. Sehingga diperoleh skedul penugasan optimal dengan biaya minimum.