Tugas Metode Penugasan (Algoritma Hungarian)

Diketahui:

Tabel Penugasan sebagai berikut:

	Mesin
Operator	1	2	3	4
1	10	12	9	11
2	5	10	7	8
3	12	14	13	11
4	8	15	11	9

Ditanyakan:

Tentukan SOLUSI OPTIMAL dengan metode penugasan (Algoritma Hungarian) untuk kasus tersebut

Penyelesaian:

Langkah 1: Tentukan Baris minimum

	Mesin				Baris Minimum
Operator	1	2	3	4
1	10	12	9	11	9
2	5	10	7	8	5
3	12	14	13	11	11
4	8	15	11	9	8

Langkah 2: Kurangi setiap baris dengan nilai masing-masing pada Baris minimumnya. Kemudian tentukan kolom minimum.

	Mesin				Baris Minimum
Operator	1	2	3	4
1	10-9 = 1	12-9=3	9-9=0	11-9=2	9
2	5-5 = 0	10-5=5	7-5=2	8-5=3	5
3	12-11=1	14-11=3	13-11=2	11-11=0	11
4	8-8=0	15-8=7	11-8=3	9-8=1	8
Kolom Minimum	0	3	0	0

Langkah 3: Cek kolom yang masih belum ada nilai nolnya jika ada maka kurangi dengan nilai kolom minimum tersebut

	Mesin				Baris Minimum
Operator	1	2	3	4
1	1	3-3=0	0	2	9
2	0	5-3=2	2	3	5
3	1	3-3=0	2	0	11
4	0	7-3=4	3	1	8
Kolom Minimum	0	0	0	0

 

Langkah 4: Lakukan pengecekan BARIS 1 jika ada 1 nilai nol maka beri tanda kotak (warna) pada nol tersebut, jika baris tersebut ada 2 nilai nol maka abaikan pindah ke baris berikutnya. Tetapi jika hanya ada 1 nol maka kolom tersebut diberi garis vertikal. Lakukan ke baris berikutnya langkah tersebut.

Lakukan pengecekan KOLOM yang tersisa (yg tidak dicoret garis vertikal) apakah masih ada nilai yang nol jika ada berikan tanda kotak (warna) dan baris tersebut berikan tanda garis horizontal. Jika pada kolom tersebut ada 2 nilai nolnya maka abaikan dan pindah ke kolom berikutnya

	Mesin
Operator	1	2	3	4
1	1	0	0	2
2	0	2	2	3
3	1	0	2	0
4	0	4	3	1

 

Dari tabel tersebut hitunglah ada berapa kotak (warna) terlihat ada 4 angka nol yg diberi tanda kotak (warna). Sedangkan jumlah baris ada 4 baris. Sehingga jumlah nol yg diberi kotak (warna) tidak sama dengan jumlah baris  4 ≠ 4 maka hal ini dinyatakan BELUM tercapai solusi optimal.

 

Langkah 5: Karena belum tercapai solusi optimal dilakukan pengecekan nilai terkecil dari sel kolom dan baris yg tdk terkena garis. Diperolehnya nilai angka 1. Kemudian yg terkena perpotongan garis kolom dan baris TAMBAHKAN dengan angka 1 tersebut, sedangkan angka yg tdk terkena garis kolom dan baris KURANGI dengan angka 1 tersebut. Untuk sel baris dan sel kolom yg lain tetap. Jika masih blm optimal lakukan pengecekan baris dan kolom lagi untuk diberikan tanda kotak (warna).

	Mesin
Operator	1	2	3	4
1	1+1=2	0	0	2
2	0	2-1=1	2-1=1	3-1=2
3	1+1=2	0	2	0
4	0	4-1=3	3-1=2	1-1=0

Atau

	Mesin
Operator	1	2	3	4
1	2	0	0	2
2	0	1	1	2
3	2	0	2	0
4	0	3	2	0

 

Diketahui :

 

	Mesin
Operator	1	2	3	4
1	10	12	9	11
2	5	10	7	8
3	12	14	13	11
4	8	15	11	9

 

Dari tabel tersebut hitunglah ada berapa kotak (warna) terlihat ada 4 angka nol yg diberi tanda kotak (warna). Sedangkan jumlah baris ada 4 baris. Sehingga jumlah nol yg diberi kotak (warna) tidak sama dengan jumlah baris à 4 = 4 maka hal ini dinyatakan tercapai solusi optimal.

 

Operator	Mesin	Waktu (Jam)
1	3	9
2	1	5
3	2	14
4	4	9
Total Waktu Proses		37