Abstrak —Permasalahan dalam penelitian ini adalah permasalahan  penugasan  bersyarat  dimana  terdapat  beberapa pekerjaan  dan  beberapa  orang  pekerja.  Setiap  pekerjaan  harus dilakukan oleh semua orang yang ada serta setiap orang memiliki waktu  yang  dibutuhkan  tersendiri  dalam  menyelesaikan pekerjaan  tersebut.  Setiap  orang  hanya  dapat  mengerjakan sebuah pekerjaan dan sebuah pekerjaan hanya dapat dikerjakan oleh satu orang dalam satu waktu. Pekerjaan yang dimaksud juga bersifat independen dalam artian dapat dilakukan kapanpun oleh setiap  orang.  Semua  orang  juga  dapat  berhenti  kapanpun  untuk melakukan sebuah pekerjaan tersebut.
Penelitian  ini  akan  mengimplementasikan  metode  pencarian maximum - size matching pada  sebuah bipartite graph yang mengacu  pada  permasalahan  penugasan  bersyarat.  Dalam penelitan ini dibahas algoritma Hopcroft-Karp untuk menyelesaikan  permasalahan  penugasan  bersyarat  tersebut dengan menggunakan bahasa pemrograman C++.
Dari  serangkaian  proses  penelitian  yang  telah  dilakukan, didapatkan  kesimpulan  bahwa  algoritma  yang  dirancang  sesuai dengan permasalahan ini dipengaruhi secara kuadratik baik oleh jumlah pekerjaan ataupun pekerjanya.
Kata  Kunci — Algoritma  Hopcroft-Karp,  Grafik  Bipartite, Masalah Penugasan Bersyarat, Perfect Matching, Teori Grafik

## I. PENDAHULUAN
Dalam  teori  grafik,  permasalahan  penugasan  bersyarat membahas  bagaimana  menemukan  susunan  pemberian  tugas atau  pekerjaan  pada  pekerja  agar  sebuah  pekerjaan  tersebut dapat  dilakukan  dengan  seoptimal  mingkin  dengan  beberapa konstrain  permasalahan  yang  ada.  Pemasalahan  penugasan bersyarat  yang  diangkat  dalam  penelitian  ini  diambil  dari persoalan  SPOJ  Klasik  6819  yang  berjudul Yet  Another Assignment Problem dengan kode soal ASSIGN5. Permasalahan  tersebut  akan  diselesakan  dengan  pendekatan pencarian Maximum-size  Matching pada  sebuah birpartite graph .
Pada  permasalahan Yet  Another  Assignment  Problem , terdapat beberapa pekerjaan dan beberapa orang pekerja yang akan  mengerjakan  pekerjaan  tersebut.  Setiap  pekerjaan  harus dilakukan  oleh  semua  orang  yang  ada  serta  setiap  orang memiliki waktu yang dibutuhkan tersendiri dalam menyelesaikan  pekerjaan  tersebut.  Setiap  orang  hanya  dapat mengerjakan  sebuah  pekerjaan  dan  sebuah  pekerjaan  hanya dapat dikerjakan oleh satu orang dalam satu waktu. Pekerjaan yang  dimaksud  juga  bersifat  independen  dalam  artian  dapat
dilakukan kapanpun oleh setiap orang. Semua orang juga dapat berhenti  kapanpun  untuk  melakukan  sebuah  pekerjaan tersebut.
Diberikan pekerjaan  dan pekerja,  serta baris kelompok  bilangan.  Setiap  baris    berisi buah  bilangan dimana  bilangan  ke  -nya  adalah yang  berarti  teman  ke- harus melakukan pekerjaan  selama menit. Diminta untuk mencari  waktu  minimal  yang  diperlukan  untuk  melakukan semua  pekerjaan  tersebut  beserta  susunan  penugasan  pada menit pertama yang mungkin terjadi.

## II. TINJAUAN PUSTAKA

## A. Bipartite Graph
Bipartite graph merupakan  grafik  spesial  yang vertex -nya dapat  dibagi  menjadi  dua  himpunan vertex dan    dimana pada setiap himpunan vertex -nya, tidak ada vertex yang saling bertetangga.  Dalam  kasus  khusus, bipartite graph dapat membentuk  sebuah complete  bipartite graph . Complete bipartite graph adalah  sebuah bipartite  graph dimana  tiap vertex pada  satu  himpunan,  bersinggungan  dengan  semua vertex pada himpunan yang lainnya.
B. Matching
Sebuah matching pada  grafik adalah  sebuah himpunan edge
dimana  tidak  ada edge yang  saling bersentuhan di dalam . Untuk setiap matching pada grafik
, kumpulan edge
dinamakan matched edge , sedangkan  kumpulan edge dinamakan unmatched edge .  Sebuah vertex dikatakan matched vertex apabila vertex tersebut besinggungan dengan matched edge pula. Sebaliknya unmatched  vertex adalah vertex yang  tidak  bersinggungan dengan matched edge . Tiap matched vertex memiliki sebuah mate atau pasangan yang terletak pada endpoint dari matched edge yang  bersinggungan  dengan  .  Sebuah matching dapat dikatakan  sebagai perfect  matching apabila  semua edge pada matching dalam  grafik mencakup  setiap vertex dalam  grafik  atau  tiap vertex dalam    bersinggungan  dengan tepat  satu edge pada . Kardinalitas dari matching adalah banyaknya edge pada dan  biasa  dinotasikan  dengan . Maximum-size  matching adalah  sebuah matching pada grafik
yang  kardinalitasnya  tidak  dapat  dinaikkan lagi atau memiliki terbesar.

## Desain dan Analisis Algoritma Penyelesaian Permasalahan Penugasan Bersyarat dengan Representasi Bipartite Graph
Muhammad Izzuddin, Arya Yudhi Wijaya, Rully Soelaiman Jurusan Teknik Informatika, Fakultas Teknologi Informasi, Institut Teknologi Sepuluh Nopember (ITS)
Jl. Arief Rahman Hakim, Surabaya 60111 Indonesia
e-mail : rully@is.its.ac.id
Bipartite matching merupakan  kasus matching khusus  yang melibatkan  struktur bipartite graph didalamnya. Bipartite graph
dapat  memiliki  sebuah complete matching dengan kardinalitas
.
C. Algoritma Hopcroft-Karp
Algoritma
Hopcroft-Karp adalah algoritma yang memerlukan bipartite graph sebagai  masukannya  dan menghasilkan maximum-size matching didalam grafik tersebut sebagai keluarannya. Algoritma ini ditemukan John Hopcroft and Richard Karp pada tahun 1973.
Sebagian  besar  ide  dasar  dari  algoritma  ini  hampir  sama dengan  teknik inverting  augmenting  path dalam  mencari maximum-size matching ,  hanya  saja  algoritma  ini  mencari beberapa augmenting  path sekaligus  dalam  sekali  iterasi dengan  meggunakan  himpunan  maksimal  dari augmenting path terpendek.
Secara  keseluruhan,  algoritma  ini  berjalan  pada  sebuah grafik ,  dimana
adalah jumlah vertex yang berada  pada dan adalah  jumlah edge pada  grafik, dengan kompleksitas . Dimisalkan  terdapat  sebuah  grafik
dan adalah matching yang  di  dapat  dari  grafik  tersebut.  Secara garis besar, algoritma ini berjalan sebagai berikut:
a. Sebuah breadth-first  search digunakan  untuk  membagi vertex - vertex menjadi  beberapa layer. Sebuah layer dalam  hal  ini  diartikan  sebagai  sebuah level dalam tree , dan  setiap level dalam tree menunjukkan  panjang augmented path yang dapat di bentuk. Unmatched vertex pada   digunakan sebagai vertex awal dari pencarian.
b. Pada  awal  pencarian,  hanya  terdapat unmatched  edge dikarenakan masih  merupakan  himpunan  kosong.
Setelah  itu,  pada  pencarian  selanjutnya,  melalui unmatched vertex pada ,  pencarian  path  dilakukan dengan men- treverse unmatched edge dan matched edge secara  bergantian.  Pencarian  akan  berhenti  pada  sebuah layer -   dimana  terdapat  satu  atau  beberapa unmatched vertex pada   tercapai.
c. Setelah layer pada  grafik  tersebut  terbentuk,  melalui depth-first  search, sebuah  himpunan  maksimal  dari augmenting  path terpendek  yang  memiliki  panjang dapat  dicari  dengan  awal unmatched  vertex pada    dan berakhir pada unmatched vertex .
d. Untuk  setiap augmenting path yang  ditemukan,  semua unmatched vertex pada tersebut diubah menjadi matched vertex begitu pula sebaliknya.
Algoritma  ini  berakhir  apabila  pada  proses  pencarian breadth-first  search tidak  menemukan augmented path yang dapat dibentuk.

## III. STRATEGI PENYELESAIAN
A. Menentukan waktu minimum penyelesaian semua pekerjaan (
Sesuai pada deskripsi masalah, dapat diketahui bahwa setiap orang  harus  mengerjakan  semua  pekerjaan  yang  ada  sesuai dengan waktu penyelesainnya masing-masing dan setiap
Gambar  2.  Proses expanding-matrix (a) Matrix awal  (b) Matrix selelah mengalami proses expanding-matrix
B. Mencari maximum-size matching pada bipartite graph Secara umum algoritma yang digunakan untuk menyelesaikan permasalahan ini berjalan sebagai berikut:
a. Membentuk bipartite grafik dengan
merupakan  representasi  dari  kolom  (pekerja)  dan merupakan representasi dari baris (pekerjaan) dari matrix yang  baru.  Sebuah edge pada    menghubungkan vertex pada   dan   apabila nilai pada matrix tersebut tidak 0.
b. Mencari  maximum matching yang  terdapat  pada  grafik tersebut.  Apabila  sebuah  kolom    memiliki  pasangan dengan  baris ,  artinya  pekerja  ke-   mengerjakan pekerjaan  ke-   dalam  suatu  waktu  tersebut.  Apabila maka  pekerja  tersebut tidak melakukan pekerjaan apapun di satuan waktu tertentu.
c. Setiap  baris    dan  kolom    yang  berpasangan,  kurangi nilai pada matrix tersebut sebanyak 1.
d. Ulangi setiap proses 1 – 3 hingga matrix tersebut menjadi matrix dengan semua isinya adalah 0.
Pada  setiap  proses  yang  terjadi,  sebuah perfect matching terbentuk  melalui  grafik  tersebut.  Dikarenakan matrix adalah sebuah matrix persegi  dengan  ukuran , maka semua baris memiliki pasangan pada kolom, begitu pula dengan kolom yang seluruhnya memiliki pasangan pada baris.
Seperti yang dijelaskan sebelumnya, diketahui bahwa jumlah dari  semua  elemen matrix tersebut  adalah dan setiap  kali  proses  jumlah  dari matrix tersebut  berkurang sebanyak ,  maka  total  proses  yang  diperlukan  untuk menjadikan matrix tersebut  menjadi matrix 0  adalah  tepat sebanyak  .

## IV. UJI COBA DAN ANALISIS

## A. Uji Coba Kebenaran
Uji  coba  kebenaran  dilakukan  dengan  mengirimkan  kode sumber  program  kedalam  situs  penilaian daring SPOJ  dan melakukan  perbandingan  hasil  keluaran  dari  sistem  dengan permasalahan.  Permasalahan  yang  diselesaikan  yaitu Yet Another Assignment Problem dengan kode soal ASSIGN5.
Gambar 3. Hasil Uji Coba pada Situs SPOJ
Kode sumber mendapat keluaran Accepted dari situs SPOJ . Hal  ini  berarti  keluaran  kode  sumber  telah  sesuai  dengan persoalan yang terdapat pada situs SPOJ. Waktu tercepat yang dibutuhkan  program  adalah  0.08  detik  dan  memori  yang dibutuhkan adalah 64 MB.
Dilakukan  pengujian  sebanyak  20  kali  pada  situs  penilaian daring SPOJ  untuk  melihat  variasi  waktu  dan  memori  yang dibutuhkan  program.  Dari  hasil  uji  coba  sebanyak  20  kali, seluruh  kode  sumber  program  mendapat  keluaran Accepted dengan  waktu  minimum  sebesar  0.08  detik,  waktu maksimum sebesar  0.12  detik  dan  waktu  rata-rata  sebesar  0.103  detik. Memori yang dibutuhkan program konstan sebesar 64 MB.
Tabel 1. Hasil pengujian pada situs SPOJ sebanyak 20 kali ID RESULT TIME MEM 17014913 accepted 0.08 64M 17014912 accepted 0.10 64M 17014910 accepted 0.10 64M 17014909 accepted 0.09 64M 17014906 accepted 0.11 64M 17014903 accepted 0.11 64M 17014901 accepted 0.09 64M 17014899 accepted 0.10 64M 17014898 accepted 0.11 64M 17014896 accepted 0.12 64M 17014895 accepted 0.11 64M 17014893 accepted 0.09 64M 17014891 accepted 0.11 64M 17014890 accepted 0.10 64M 17014889 accepted 0.11 64M 17014886 accepted 0.12 64M 17014883 accepted 0.11 64M 17014882 accepted 0.10 64M 17014879 accepted 0.10 64M 17011446 accepted 0.10 64M

## B. Uji Coba Efisiensi Waktu
Uji coba kinerja dilakukan dengan membuat data generator, untuk  membangun  contoh  persoalan  sesuai  dengan  batasan permasalahan.  Kemudian  dilakukan  pembandingan  kinerja program terhadap pertumbuhan jumlah pekerja dan pertumbuhan jumlah pekerjaan.
1) Pengaruh Banyaknya Pekerjaan Terhadap Waktu
Pada  uji  coba  ini  banyaknya  pekerjaan  dibuat  bervariasi antara 1000 hingga 9000. Jumlah pekerja ditetapkan sebanyak 1000. Waktu eksekusi program dicatat dalam satuan.
0 500 1000 1500 2000 W ak tu pr o
se s (m ili de ti k) Banyak Pekerjaan 1000 2000 3000
4000
5000 6000
Gambar  4.  Grafik  Hasil  Uji  Coba  Pengaruh  Jumlah  Pekerjaan  Terhadap Waktu Eksekusi Program
Dapat  dilihat  bahwa  grafik  cenderung  mendekati  kurva kuadratik.  Hal  menunjukkan  bahwa  algoritma  penyelesaian yang dipengaruhi secara kuadratik oleh jumlah pekerjaan.Pengaruh Banyaknya Pekerja Terhadap Waktu
Pada  uji  coba  ini  banyaknya  pekerjaan  dibuat  bervariasi antara 1000 hingga 9000. Jumlah pekerja ditetapkan sebanyak 1000. Waktu eksekusi program dicatat dalam satuan.
0 500 1000 1500 2000 2500 W ak tu pr os es ( m ili det ik )

## Banyak Pekerja
Gambar 5. Grafik Hasil Uji Coba Pengaruh Jumlah Pekerja Terhadap Waktu Eksekusi Program
Dapat  dilihat  bahwa  grafik  cenderung  mendekati  kurva kuadratik.  Hal  menunjukkan  bahwa  algoritma  penyelesaian yang dipengaruhi secara kuadratik oleh jumlah pekerja.

## V. KESIMPULAN
Dari  hasil  uji  coba  yang  telah  dilakukan  terhadap implementasi penyelesaian permasalahan Yet Another Assigment Problem dapat diambil kesimpulan sebagai berikut: 1. Permasalahan Yet  Another  Assignment  Problem pada situs  SPOJ  dapat  direpresentasikan  sebagai  sebuah bipartite  graph serta  Implementasi  algoritma Hopcroft - Karp dapat  menyelesaikan  permasalahan t ersebut dengan benar.
2. Kompleksitas  waktu  yang  dibutuhkan  untuk  seluruh proses  sistem  adalah pada buah
pekerjaan  dan    orang  pekerja  sehingga  algoritma  ini dipengaruhi  secara  kuadratik  baik  oleh  jumlah  pekerja maupun jumlah pekerjaan.

## UCAPAN TERIMA KASIH
Penulis  mengucapkan  terima  kasih  kepada  Tuhan  Yang Maha  Esa  atas  segala  karunia  dan  rahmat-Nya  yang  telah diberikan  selama  ini.  Penulis  juga  mengucapkan  terimakasih kepada  orang  tua,  saudara,  keluarga,  Bapak  Arya  Yudhi Wijaya  dan  Bapak  Rully  Soelaiman  selaku  pembimbing penulis dan semua pihak yang tidak bisa penulis sebutkan satu persatu  yang  talah  memberikan  semangat  serta  motivasi sehingga penulis dapat menyelesaikan penelitian ini.

## DAFTAR PUSTAKA
[1]   SPOJ,  "The  dilemma  of  Idli,"  March  2014.  [Online].  Available: http://www.spoj.com/problems/WPC5G/.
[2]   S.  Halim  and  F.  Halim,  "Competitive  Programming  3,"  Singapore,  Lulu Publisher, 2013.
[3]   D. Jungnickel, Graph s, Networks and Algorithms, 4th Edition ed., Berlin: Springer, 2012.
[4]   SPOJ,  " Yet  Another  Assignment  Problem ,"  June  2010.  [Online].
Available: http://www.spoj.com/problems/ASSIGN5/.
[5]   J. Bondy and U. Murty, Graph Theory, 3rd ed., Berlin: Springer, 2008.
[6]   H. A. Taha, Operations Research: An Introduction, 8th Edition ed., Upper Saddle River: Prentice Hall, 2007.