BAB 1 PENDAHULUAN
1.1 Latar Belakang Masalah
Seiring dengan pertumbuhannya, setiap organisasi baik organisasi bisnis (perusahaan), industri, jasa dan sebagainya, menghadapi kenyataan bahwa sumber daya yang terbatas harus dialokasikan pada semua unit dalam organisasi. Manajer, selaku orang mengelola organisasi, tidak boleh berdiam diri dalam menghadapi kenyataan di atas. Manajer harus menyelesaikan masalah pengalokasian tersebut dengan membuat keputusan yang sangat layak. Manajer harus dapat mengalokasikan sumber daya organisasi sedemikian sehingga tidak ada unit organisasi yang kelebihan sumber daya dan tidak ada unit organisasi yang kekurangan sumber daya. Singkatnya, manajer perlu memainkan peranannya sebagai pengalokasi sumber (resource allocator) dengan sebaik-baiknya. Masalah penugasan merupakan salah satu masalah yang dihadapi oleh manajer sebagai pengalokasi sumber. Di sini manajer harus menugaskan sejumlah tenaga kerja yang memiliki kemampuan berbeda pada sejumlah tugas yang berbeda pula. Karena keterbatasan jumlah tenaga kerja, maka setiap pekerja hanya dapat ditugaskan pada satu tugas dan setiap tugas hanya dikerjakan oleh satu orang. Manajer akan menghadapi berbagai kemungkinan penugasan sejumlah pekerja pada sejumlah tugas. Masing-masing kemungkinan penugasan tersebut mempunyai total keuntungan yang berbeda satu dengan yang lain. Tentunya manajer harus memilih kemungkinan penugasan yang memiliki total keuntungan maksimum. Dalam menyelesaikan suatu masalah, termasuk masalah penugasan, manajer tidak
boleh
mengandalkan
kemampuan
intuisinya
saja,
melainkan
harus
mempertimbangkan berbagai alat bantu untuk menyelesaikan masalah. Alat bantu tersebut dapat berupa metode kuantitatif maupun berbagai peralatan elektronik, khususnya komputer. Masalah penugasan nampaknya sangat sederhana, sehingga pada mulanya tidak dirasakan keperluan akan metode kuantitatif, apalagi komputer. Dalam penulisan ini, untuk menyelesaikan masalah penugasan akan diperlihatkan suatu pendekatan,
Universitas Sumatera Utara
yaitu dengan memanfaatkan teori graf. Teori graf merupakan alat bantu dalam berbagai bidang ilmu. Sehubungan dengan masalah penugasan, dalam teori graf dikenal adanya masalah matching bobot maksimum dalam graf bipartisi lengkap berlabel. Jadi, masalah penugasan dapat dimodelkan ke dalam graf bipartisi lengkap berlabel dan kemudian diselesaikan dengan menerapkan algoritma untuk mencari matching bobot maksimum dalam graf bipartisi lengkap berlabel.
1.2 Perumusan Masalah
Masalah dalam tugas akhir ini adalah bagaimana menyelesaikan masalah penugasan dengan menerapkan algoritma matching bobot maksimum dalam graf bipartisi lengkap berlabel.
1.3 Batasan Masalah
Masalah penugasan yang dibahas dalam tugas akhir ini dibatasi pada masalah maksimisasi. Penulis membatasi masalah penugasan dengan algoritma matching bobot maksimum dengan waktu tempuh sebagai contoh kasus dalam penelitian ini.
1.4 Tujuan Penelitian
Penulisan ini bertujuan untuk menunjukkan bahwa algoritma matching bobot maksimum dalam graf bipartisi lengkap berlabel dapat menyelesaikan masalah penugasan.
1.5 Manfaat Penelitian
Dapat merepresentasikan masalah graf bipartisi lengkap ke dalam model penugasan (assignment problem) dan sebagai penerapan ilmu yang dimiliki penulis.
Universitas Sumatera Utara
1.6 Metodologi Penelitian
Metodologi yang digunakan dalam rangka pembuatan dan penyusunan tugas akhir ini adalah penelitian literatur, guna memperoleh berbagai bahan referensi.
1.7 Tinjauan Pustaka
a. Pengenalan Terhadap Masalah Penugasan Defenisi 1: Masalah penugasan (assignment problem) merupakan masalah tentang menugaskan n elemen ke dalam n kategori dengan suatu cara yang optimal, sedemikian hingga tiap elemen yang ditugaskan pada satu dan hanya satu kategori dan tiap kategori memperoleh satu dan hanya satu elemen. Penugasan elemen pada kategori yang dimaksud dalam defenisi 1 dapat berupa penugasan pelamar atau jabatan, awak kapal pada kapal, perenang pada gaya renang, dan sebagainya. Selanjutnya, kita sebut elemen dengan pekerja dan kategori dengan tugas. Pada masalah penugasan, diasumsikan bahwa jumlah pekerja sama dengan jumlah tugas. Apabila terdapat suatu masalah penugasan yang tidak memenuhi asumsi ini, maka ditambahkan sejumlah pekerja khayal atau tugas khayal sedemikian hingga jumlah pekerja dan jumlah petugas sama. Masalah penugasan dapat dikelompokkan menjadi dua, yaitu : 1. masalah maksimasi, yaitu masalah penugasan yang mencari total keuntungan maksimum. 2. masalah minimisasi, yaitu masalah penugasan yang mencari total kerugian minimum. Data yang diperlukan oleh masalah penugasan dapat disajikan ke dalam matriks berordo n x n, yang disebut matriks penugasan. Setiap elemen cij menyatakan besar keuntungan/kerugian yang diperoleh pekerja ke-i ditugaskan ke tugas ke-j.
Universitas Sumatera Utara
tugas ke-n
Gambar 1.1 Matriks Penugasan
Matriks Penugasan
Penambahan pekerja/tugas khayal pada matriks penugasan dapat dilakukan dengan cara menambahkan baris yang semua elemennya nol, untuk penambahan pekerja khayal, atau menambahkan kolom yang semua elemennya nol, untuk penambahan tugas khayal. Contoh : a. Matriks penugasan dengan tambahan satu pekerja khayal menjadi b. Matriks penugasan dengan tambahan dua tugas khayal menjadi
Berdasarkan defenisi 1 dapat dilihat bahwa : 1. Tujuan yang akan dicapai dalam masalah penugasan adalah membentuk penugasan yang akan memberikan total keuntungan maksimum. 2. Batasan dalam masalah penugasan berupa terbatasnya sumber daya, yakni satu pekerja hanya ditempatkan pada tepat satu tugas, demikian pula setiap tugas hanya dapat memperoleh tepat satu pekerja. 3. Memutuskan apakah pekerja ke-i atau
tidak. Jadi masalah penugasan yang
memiliki n pekerja (dan n tugas), memiliki pula n variabel keputusan, yang masing-masing hanya dapat bernilai ya atau tidak.
Universitas Sumatera Utara
b. Penugasan Sebagai Masalah Matching Bobot Maksimum Dalam Graf Bipartisi Lengkap Berlabel
Defenisi 2 : Sebuah graf G adalah bipartisi jika V(G) dapat dipartisi ke dalam dua subset V1 dan V2 sedemikian sehingga semua sisi (edge) dalam G menghubungkan sebuah simpul (vertex) dalam V1 dan sebuah simpul dalam V2. Teori berikut menunjukkan karakteristik graf partisi : Teori : Sebuah (nontrival) graf (V,E) adalah bipartisi jika dan hanya jika graf tersebut tidak mengandung cycle dengan panjang ganjil. Dalam graf bipartisi, setiap simpul V1 tidak harus adjacent (berdampingan) ke semua simpul dalam V2. Namun jika hal ini dipenuhi, maka graf bipartisi disebut “graf bipartisi lengkap”. Contoh : Pada gambar (1.1) diperlihatkan contoh graf bipartisi dan graf bipartisi lengkap. V1
V4
V2
V5
V3
V6
V1
V7
V4
(a) Graf Bipartisi
V2
V3
V5
V6
V7
(b) Graf Bipartisi Lengkap
Gambar 1.2 Graf Bipartisi dan Bipartisi Lengkap
Graf bipartisi akan disebut graf bipartisi berlabel jika ruas-ruasnya diberi suatu bilangan non-negatif w, yang disebut label/bobot.
Universitas Sumatera Utara
Contoh : Sebuah contoh graf bipartisi berlabel dapat dilihat dalam gambar (1.2)
V1
V2
2
V1}
9 66
V4
V3
V5
4 5 V6
7 V7 V2
Gambar 1.3 Graf Bipartisi Berlabel
Universitas Sumatera Utara
