metode penugasan

Created by Wasis A. Latief - 2007


PENDAHULUANTujuan khusus lain dari algoritma yang digunakan dalam Linier Programming adalah metode penugasan (assigment method). Seperti halnya metode transportasi, metode penugasan adalah metode penghitungan yang lebih efisien dari pada metode simplek untuk suatu kasus khusus. Kita akan melihat juga bahwa problem penugasan adalah merupakan kasus khusus dari problem transportasi. Atau dengan kata lain kita bisa memecahkan persoalan penugasan tersebut dengan metode transportasi. Solosi model ini membuat pemecahan dengan model transportasi menjadi tidak efisien.


CONTOH, Sebuah Perusahaan Gaya Baru melakukan peker-jaan metalwork untuk sejumlah pabrik lokalnya. Pe-rusahaan mempunyai tiga pekerjaan /job (A,B,C) yang bisa dilakukan dan mempunyai tiga buah me-sin untuk melakukan pekerjaan tersebut (X, Y, Z). Tujuan Perusahaan Gaya Baru adalah menugaskan pekerjaan-pekerjaan tersebut ke mesin-mesin (satu pekerjaan per mesin) dengan biaya terendah. Data biaya seperti pada tabel berikut ini.

Pekerjaan MesinX Y Z

ABC

$ 25 15 22

$ 31 20 19

$ 35 24 17

Catatan :Jumlah kolom dan baris pada model ini adalah sama. Karakteristik semacam ini adalah khas bagi persoalan penugasan


Metode ini mempunyai keunggulan dari pada metode-metode yang lain. Terdapat tiga langkah yang perlu dilakukan dalam metode ini :

1. Menentukan Tabel Opportunity Cost 2. Menentukan Penugasan Optimal3. Merevisi Tabel Total Opportunity Cost.

SOLOSI (Hungarian Method)


Konsep Opportunity Cost :Adalah besarnya biaya pengorbanan jika kita memilih salah satu kesempatan yang ada. Misalnya kita menugaskan pekerjaan A ke mesin X dengan biaya $ 25. Karena Mesin X dapat juga memproses pekerjaan B dengan biaya $ 15, maka penugasan pekerjaan A ke mesin X bukan keputusan yang terbaik, karena kita akan mengorbankan biaya sebesar $ 10 (=$ 25 - $15). Pengorbanan inilah secara umum menjelaskan tentang opportunity cost. Konsep tersebut di sebut sebagai “Job Opportunity Cost Mesin X”, dan untuk mesin-mesin yang lainnya.Disamping itu ada juga konsep “Mesin Opportunity Cost Job A”, yang artinya menugaskan mesin X untuk mengerjakan pekerjaan A. Demikian seterusnya,

Langkah 1. Menentukan Tabel Opportunity Cost


ABC

$ 25 15 22

$ 31 20 19

$ 35 24 17


Langkah 1. Menentukan Tabel Opportunity Cost

Tabel Opportunity Cost :Biaya opportunity dari pekerjaan-pekerjaan tersebut disaji-kan dalam sebuah tabel yang dikenal sebagai “Tabel Job-Opportunity Cost” :

Job Mesin Penghitungan

X Y Z Kolom X Kolom Y Kolom Z

ABC

1007

1210

1870

25 – 15 = 1015 – 15 = 022 – 15 = 7

31 – 19 = 1220 – 19 = 119 – 19 = 0

35 – 17 = 1824 – 17 = 717 – 17 = 0

Job Mesin

X Y Z Penghitungan

ABC

007

210

870

Baris A:Baris B:Baris C:

10 – 10 = 0 0 – 0 = 0 7 - 0 = 7

12 – 10 = 2 1 – 0 = 1 0 – 0 = 0

18 – 10 = 8 7 – 0 = 7 0 – 0 = 0

Tabel bSelanjutnya tabel tersebut dikembangkan menjadi “Tabel Total Opportunity Cost”. Yaitu menghitung opportunity cost secara Horizon-tal, yaitu dari tabel a) , kita kurangkan entri terendah dari setiap baris terhadap entri-entri yang lain dalam baris yang bersangkutan, maka akan diperoleh Tabel Total Opportunity Cost seperti pada Tabel b.


Langkah 2 : Menentukan Penugasan Optimal

Tujuan dari metode penugasan adalah meminimumkan biaya. Dengan tabel total opportunity cost, tujuan tersebut akan dicapai bila kita dapat menugaskan pekerjaan-pekerjaan ke mesin-mesin hingga “total opportunity cost nol”. Dengan kata lain kita akan membuat tiga penugasan yang terbaik. Penugasan terbaik sebuah pekerjaan ke sebuah mesin akan meliputi opportunity cost yang bernilai nol. Dalam tabel b, terdapat 4 buah sel yang bernilai nol, yang masing-masing mengindikasikan sebuah opportunity cost nol untuk sel yang bersangkutan. Karenanya, kita dapat menugaskan pekerjaan A ke mesin X dan pekerjaan C ke mesin Y atau Z. Tapi tidak dapat menugaskan pekerjaan B ke setiap mesin yang nilai opportunity costnya nol (misalnya ke mesin X ). Alasannya, penugasan pekerjaan A ke mesin X menghalangi penugasan pekerjaanB ke mesin X. Kalau kita memiliki nilai nol pada sel B Y, maka kita telah membuat penugasan yang optimal. Dengan kata lain untuk membuat penugasan yang optimal dari tiga pekerjaan ke tiga buah mesin, kita harus menempatkan tiga sel nol tersebut dalam tabel sehingga sebuah penugasan yang lengkap ke sel-sel tersebut dapat dibuat melalui sebuah total opportunity cost yang bernilai nol.


ABC

007

210

870


Langkah 2 : Menentukan Penugasan Optimal

Tabel Uji Penugasan Optimal


ABC

007

210

870

garis 2

garis 1

P ada tabel terdapat dua garis (baris C dan kolom X ) yang menutupi sel-sel nol. Padahal diperlukan tiga buah garis, sehingga tabel tersebut belum menggambarkan solosi optimal.

Ada metode yang paling baik untuk menentukan suatu penugasan optimal. Metode ini dilakukan dengan cara membuat garis lurus (vertikal atau horisontal) pada tabel opportunity cost. Jika jumlah garis tersebut sama dengan jumlah baris atau kolom dalam tabel, maka penugaasan optimal dapat di capai dan persoalan dapat terpecahkan. Sebaliknya, jika jumlah garis kurang dari jumlah baris atau kolom penugasan optimal belum tercapai. Untuk itu kita harus me-ngembangkan tabel total opportunity cost yang baru.

Pengujian penugasan yang optimal diaplikasikan pada tabel berikut ini.


Langkah 3 : Merevisi Tabel Total Opportunity Cost. Karena penugasan belum optimal,tabel total opportunity

cost harus dimodifikasi dengan memasukkan beberapa penugasan baru pada baris atau kolom yang belum tertutupi oleh garis. Penugasan itu dipilih sel yang mempunyai nilai opportu-nity cost terendah, yaitu menugaskan pekerjaan B ke mesin Y yang mempunyai opportunity cost = 1. Dengan kata lain kita akan merubah opportunity cost dari penu-gasan yang bernilai 1 menjadi nol. Prosedur penugasan ini secara rinci adalah sbb. : a) Pilih nilai terkecil pada tabel yang belum tertutupi oleh

garis dan kurangkan nilai tersebut terhadap semua nilai yang belum tertutupi oleh garis.

b) Tambahkan nilai terendah itu ke nilai pada perpotongan dua garis yang telah ada (7).

Dengan prosedur tersebut maka dapat diciptakan tabel baru lagi seperti berikut :


Langkah 3 : Merevisi Tabel Total Opportunity Cost.

Tabel Uji Penugasan Optimal Tabel Uji Penugasan Optimal garis 1

garis 1

8 – 1 = 7 7 – 1 = 6 garis 1

8 – 1 = 7 7 – 1 = 6 garis 1

8 – 1 = 7 7 – 1 = 6

JobMesin

PerhitunganX Y Z

A 0 1 7 0 2 - 1 = 1 8 – 1 = 7 a) Mengurangi nilai yang belum tertutup garis

dengan nilai terendahB 0 0 6 0 1 – 1 = 0 7 – 1 = 6

C 8 0 0 7+1 = 8 0

0 Garis 1

Garis 2b) Menambah nilai perpotongan garis dengan nilai terendah

Tabel Opportunity Cost yang direvisi

Tabel Uji Penugasan Optimal

Pekerjaan Mesin

X Y Z

ABC

008

100

760

Biaya Total (Minimum)

A ke X = $ 25B ke Y = $ 20C ke Z = $ 17

$ 62


8 – 1 = 7 7 – 1 = 6

8 – 1 = 7 7 – 1 = 6

8 – 1 = 7 7 – 1 = 6

LATIHAN1. Sebuah perusahan besi GTAW, mempunyai tiga

buah mesin dan tiga macam pekerjaan, dimana satu pekerjaan dikerjakan dalam satu mesin. Biaya setiap pekerjaan pada setiap mesin seperti disajikan pada tabel berikut. Tentukan penugasan pekerjaan tersebut sehingga biaya minimum !

Job MesinX Y Z

A Rp 4000 Rp 6000 Rp 8000BC

2000 4000

3000 8000

4000 5000


8 – 1 = 7 7 – 1 = 6

8 – 1 = 7 7 – 1 = 6

8 – 1 = 7 7 – 1 = 6

2. Sebuah perusahan yang bekerja dalam perdirganta-raan GTK Company, telah memutuskan sebuah kon-trak pengembangan mesin roket. Kontrak tersebut paling tidak membutuhkan lima industri kecil sebagai subkontrak dari sebagian pekerjaan. GTK Company, meminta penawaran biaya dari kelima indistri tersebut (A, B, C, D dan E) untuk melakukan pekerjaan di lima wilayah (V, W, X, Y dan Z). Penawaran biaya tersebut adalah sbb. :

IndustriBiaya Penawaran Dari Sub-Kontrak (Rupiah)V W X Y Z

A 45 juta 60 juta 75 Juta 100 juta 30 JutaB 50 Juta 55 Juta 40 Juta 100 Juta 45 JutaC 60 Juta 70 Juta 80 Juta 110 Juta 40 JutaD 30 Juta 20 Juta 60 Juta 55 Juta 25 JutaE 60 Juta 25 Juta 65 Juta 185 Juta 35 Juta


8 – 1 = 7 7 – 1 = 6

8 – 1 = 7 7 – 1 = 6

8 – 1 = 7 7 – 1 = 6

` V W X Y Z

A 45 60 75 100 30

B 50 55 40 100 45

C 60 70 80 110 40

D 30 20 60 55 25

E 60 25 65 185 35

A 15 40 35 45 5

B 20 35 0 45 20

C 30 50 40 55 15

D 0 0 20 0 0

E 30 5 25 130 10

A 10 35 30 40 0

B 20 35 0 45 20

C 15 35 25 40 0

D 0 0 20 0 0

E 25 0 20 125 5

A 0 35 30 30 0

B 10 35 0 35 20

C 5 35 25 30 0

D 0 10 30 0 10

E 15 0 20 115 5

A – ZB – XC - ?D – AE - W

A – V = 45B – X = 40C – Z = 40D – Y = 55E – W = 25Total = 205

metode penugasan

Documents