## IMPLEMENTASI ALGORITMA BRANCH AND BOUND DALAM PENENTUAN JUMLAH PRODUKSI UNTUK MEMAKSIMALKAN KEUNTUNGAN
Yusrah Nazari Firdaus 1 , Nintia Litano 2 , Agustira Hermansyah 3 , Ranti Nurhadiyati 4 , Ilham Falani 5 , Elfitria Wiratmani 6
Program Studi Teknik Industri, Universitas Indraprasta PGRI Jakarta yusrahfirdaus@gmail.com 1 , nintialitanoo@gmail.com 2 , agustira03@gmail.com 3 , rantinurhadiyati48@gmail.com 4 , ilhamfalani@gmail.com 5 , elfitriaw@gmail.com 6
Submitted May 10, 2019; Revised July 5, 2019; Accepted July 20, 2019

## Abstrak
Perencanaan  produksi  yang  optimal  bertujuan  untuk  memaksimalkan  keuntungan  yang  diperoleh, dengan  mempertimbangkan  keterbatasan  sumber  daya  yang  dimiliki.  UKM  Puguh  Jaya  merupakan usaha yang bergerak di bidang konveksi kain kasur. Terdapat beberapa jenis produk yang diproduksi di  antaranya:  Kain  tipe  120,  kain  tipe  140,  kain  tipe  160.  Perencanaan  produksi  di  UKM  ini  dapat dipandang  sebagai  model  program integer yang  bertujuan  memaksimalkan  keuntungan,  dengan menentukan jumlah produksi untuk masing-masing tipe serta mempertimbangkan semua keterbatasan sumber  daya  yang  ada.  Pencarian  solusi  untuk  model  ini  dilakukan  dengan  algoritma Branch  and Bound .  Berdasarkan  hasil  perhitungan  menggunakan software QM  for  Windows,  diketahui  bahwa penentuan  jumlah  produksi  dengan  menggunakan  algoritma branch  and  bound memberikan peningkatan  keuntungan  sebesar  18.7%  dibandingkan  dengan  keuntungan  UKM  Puguh  Jaya sebelumnya.
Kata Kunci : Optimasi, program integer , algoritma Branch and Bound

## Abstract
The  optimal  production  planning is  aimed  at  maximizing  expected  profit  by  taking  into  account  the limitation  on  available  resources.  UKM  (Small  and  Medium  Enterprise)  Puguh  Jaya  enganged  in mattress fabric confection business produces several types of products such as fabric type 120, fabric type  140  and  fabric  type  160.  Production  planning  in  the  UKM  can  be  considered  an  integer programming  model to  maximize  profit  by  determining  the  number  of  production  for  each  type and considering the limitation on available resources. The solution for this model is achieved by applying the Branch and Bound algorithm. Based on the calculation results using QM software for Windows, it is  known  that  the  determination  of  the  number  of  production  using  Branch  and  Bound  algorithm increases the profit of 18.7% compared to the one previously made by UKM Puguh Jaya. Keywords : Optimization, integer programming, Branch and Bound algorithm

## 1. PENDAHULUAN
Salah satu aspek penting dalam manajemen produksi  dalam usaha adalah perencanaan, tanpa  adanya  perencanaan  produksi  yang baik, maka tujuan tidak akan dapat dicapai dengan  efektif  dan  efisien.  UKM  Puguh Jaya  merupakan  usaha  yang  bergerak dalam  bidang  konveksi  kain  kasur  yang berlokasi  di  Kelapa  Dua,  Depok-Jawa Barat.  Usaha  ini  tidak  memiliki  metode yang  pasti  dalam  menentukan  jumlah produksi  yang  optimal  pada  masing- masing  tipe  kain  kasur.    Kendala-kendala
yang  terjadi  dalam  proses  produksi  di antara  nya  ketersediaan  bahan  baku  kain kasur, jumlah tenaga kerja yang mempengaruhi  jumlah produksi, dan fluktuasi permintaan yang beragam.
Permasalahan  pada  UKM  Puguh  Jaya dapat dipandang sebagai integer programming dikarenakan  semua  variabel menghendaki  hasilnya  berupa  bilangan bulat.  Masalah integer  programming adalah pemrograman linear dimana beberapa  atau  semua  variabel  diharuskan menjadi  bilangan  bulat  non-negatif  [10].
Meskipun  tidak  ada  metode  yang  secara efektif dalam menyelesaikan integer programming , pengalaman komputasi
menunjukkan  bahwa Branch  and  Bound jauh lebih sukses daripada metode Cutting Plane [7].  Pada  penelitian  ini  dengan menggunakan algoritma Branch and Bound efektif  dan  sederhana  untuk menyelesaikan model program integer [1], [4],  [5],  [9].  Maka  dari  itu,  algoritma Branch and Bound dapat digunakan dalam permasalahan UKM Jaya.
Suatu  masalah  optimasi,  dikenal  fungsi objektif atau fungsi tujuan yang merupakan fungsi pengevaluasi yang ingin dioptimalkan  [2].  Program integer atau program  bilangan  bulat  merupakan  solusi dalam  optimasi  pada  hal  yang  tidak  dapat diterima  secara  logika  apabila  hasil perhitungan  bernilai  desimal  (pecahan).
Menurut [10] Integer Programming
(Pemrograman  Bilangan  Bulat)  adalah pemrograman linear di mana beberapa atau semua variabel diharuskan menjadi bilangan bulat non negatif. Semua variabel harus  bilangan  bulat  disebut  masalah pemrograman  bilangan  bulat  murni  ( pure integer programming ) dan integer programming dimana  hanya  beberapa variabel  yang  diperlukan  untuk  menjadi bilangan bulat disebut masalah pemrograman  bilangan  bulat  campuran ( mixed  integer  programming )  [6],  [10]. Secara  matematis  penulisan  model Integer Programming sebagai berikut [10]:
Fungsi  Tujuan:  Maksimasi  atau  Minimasi dari:
Fungsi kendala:
Keterangan :
Z    :  Fungsi  tujuan  yang  dimaksimumkan atau diminimumkan.
c j : Kenaikan nilai untuk fungsi tujuan. x j : Variabel keputusan ke- j . a ij :  Banyaknya  sumber i yang  diperlukan untuk menghasilkan setiap unit keluaran aktivitas j . b i : Banyaknya sumber  (fasilitas)  i  yang tersedia  untuk  dialokasikan  kesetiap jenis aktivitas.
i : Nomer setiap  macam  sumber  atau fasilitas yang tersedia (i=1,2,...,m).
j :  Nomer  setiap  macam  aaktivitas  yang menggunakan  sumber  atau  fasilitas yang tersedia.
n : Macam aktivitas  yang  menggunakan sumber atau fasilitas tersebut.
m :  Macam  batasan-batasan  seumber  atau fasilitas yang tersedia.
Menurut [7] Integer Programming
didasarkan  pada  eksploitasi  keberhasilan komputasi  linear programming yang  luar biasa. Strategi ini melibatkan tiga langkah, yaitu:
1. Mengendurkan  ruang  solusi integer programming dengan mengganti variabel  biner  y  dengan  rentang kontinu  0  <y  <1,  dan  menghapus batasan integer pada  semua  variabel integer .  hasil  relaksasi  adalah  linear programming biasa.
2. Memecahkan  linear programming dan mengidentifikasi optimal terus menerus.
3. Mulai  dari  titik  optimal  kontinu, tambahkan  kendala  khusus,  iteratif memodifikasi ruang solusi linear programming dengan  cara  yang  pada akhirnya akan memberikan titik ekstrim optimal yang memenuhi persyaratan bilangan bulat. Dua  model  umum  telah  dikembangkan untuk menghasilkan kendala khusus sebagaimana  dimaksud  dalam  langkah  3. Model umum penyelesaian Integer Programming , sebagai berikut:
1. Model Branch-and-Bound .
2. Model Cutting Plane.
Konsep  dasar  yang  mendasari  model branch  and  bound adalah  membagi  dan menghilangkan.  Oleh  karena  kasus  awal yang  besar  terlalu  sulit  utuk  diselesaikan secara  langsung,  kasus  tersebut  dibagi menjadi  subkasus  yang  lebih  kecil  sampai subkasus  ini  dapat  diatasi.  Pembagian ( branching )  dilakukan  dengan  membagi keseluruhan himpunan solusi layak menjadi himpunan bagian yang lebih kecil. Penghilangan ( fathoming ) sebagian dilakukan  dengan  membatasi  ( bounding ) seberapa baik solusi terbaik dalam himpunan bagian dan kemudian membuang  himpunan  bagian  apabila batasnya mengindikasikan bahwa himpunan  bagian  tersebut  tidak  mungkin berisi  suatu  solusi  optimal  untuk  kasus awal [3]. Sedangkan menurut [8] Algoritma branch  and  bound adalah pendekatan  solusi  yang  membagi  ruang solusi  yang  layak  menjadi  himpunan bagian  solusi  yang  lebih  kecil.  Algoritma branch  and  bound dilakukan  secara berulang hingga membentuk pohon pencarian  ( search  tree )  dan  dilakukan proses  pembatasan  ( bounding )  dengan menentukan  batasan  ( bounding )  dalam mencari solusi optimal.
Alur dari langkah-langkah algoritma branch  and  bound  secara  umum  ada  lah sebagai berikut:
1. Memformulasikan kendala-kendala yang ada  dalam bentuk integer programming .
2. Selesaikan  formulasi  tersebut  dengan integer programming .
3. Jika  hasil integer  programming adalah infeasible  (tidak  memiliki  solusi  yang
layak)  [7]  maka  formulasi integer programming perlu di fathom/bounding lalu  di branching .  Jika feasible maka integer programming sudah selesai. 4. Apabila  hasil  percabangan/ branching sudah fathom (hasil  percabangan  akhir semua infeasible atau feasible )  maka formulasi integer  programming sudah selesai.
5. Pilih solusi optimal dari hasil percabangan  yang  sudah integer atau menghasilkan  nilai  maksimum  atau minimum,  dimana  nilai  fungsi  tujuan sebagai acuan dalam pemilihannya.

## 2. METODE PENELITIAN
Metodologi yang digunakan dalam penelitian  ini  adalah  metode  studi  pustaka untuk mempelajari  konsep algoritma Branch  and  Bound dan  model Integer Linear  Programing. Dari  hasil  studi pustaka ini dilakukan sebuah implementasi algoritma Branch  and  Bound untuk menentukan  variasi  produk  yang  optimal .
Implementasi
dilakukan dengan menggunakan  perangkat  lunak QM  for
Windows .    Hasil  dari      penelitian    ini diharapkan  dapat  membantu  UKM  untuk menentukan variasi produk dan mendapatkan keuntungan yang maksimal..

## 3. HASIL DAN PEMBAHASAN
Dalam  menyelesaikan  permasalahan  untuk memaksimalkan keuntungan produksi dibutuhkan  data  lengkap  proses  produksi kain  kasur  pada  UKM  Puguh  Jaya  selama satu  minggu  (6  hari  kerja).  Berikut  adalah uraian  kendala  yang  terjadi  pada  UKM Puguh Jaya:

## Tabel 1. Data Kendala UKM Puguh Jaya
Jenis Kendala x 1 x 2 x 3 x 4 Kapasitas Tersedia Satuan Bahan Baku 5,2 6 6,8 7,6 1000 m 2 Benang 100 100 105 105 15700 gram Waktu 19 19 19 19 2880 menit Tenaga Kerja 1 1 1 1 171 pekerja Kapasitas Produksi 1 1 1 1 150 Pcs Permintaan Tipe 120 67 0 0 0 3120 Pcs Permintaan Tipe 140 0 100 0 0 3600 Pcs Permintaan Tipe 160 0 0 50 0 1020 Pcs Permintaan Tipe 180 0 0 0 50 1140 Pcs Keuntungan per Unit 32000 36000 46000 52000 Rupiah Sumber : UKM Puguh Jaya
Keterangan: x 1 = Kain kasur tipe 120
x 2 = Kain kasur tipe 140
x 3 = Kain kasur tipe 160 x 4 = Kain kasur tipe 180
Langkah-langkah penyelesaian yaitu: Fungsi Tujuan: Z maks =  32.000x 1 +  36.000x 2 +  46.000x 3 + 52.000x 4
Fungsi Kendala: 5,2x 1 + 6x 2 + 6,8x 3 + 7,6x 4 ≤1000
100x 1 + 100x 2 + 105x 3 + 105x 4 ≤ 15700 19x 1 + 19x 2 + 19x 3 + 19x 4
≤ 2880 x 1 + x 2 + x 3 + x 4 ≤ 171
x 1 + x 2 + x 3 + x 4 ≤ 150 67x 1 ≤ 3120 100x 2 ≤ 3600 50x 3 ≤ 1020 50x 4 ≤ 1140 x 1 , x 2, x 3 , x 4 ≥ 0 x 1 , x 2, x 3 , x 4 ϵ I
Langkah  selanjutnya  dalam  penyelesaian dari  masalah  di  atas  yaitu  menggunakan software  QM  for  Windows dengan Modul tree Integer & Mixed Integer
Programming dan  memasukan  nilai-nilai fungsi tujuan dan fungsi kendala pada tabel sebagai berikut :
Tabel 2. Original Problem Table With Solution
x 1 x 2 x 3 x 4 RHS Maximize 32000 36000 46000 52000 Bahan baku 5,2 6 6,8 7,6 <= 1000 Benang 100 100 105 105 <= 15700 Waktu 19 19 19 19 <= 2880 Tenaga Kerja 1 1 1 1 <= 171 Kapasitas Produksi 1 1 1 1 <= 150 Permintaan Tipe x 1 67 0 0 0 <= 3120 Permintaan Tipe x 2 0 100 0 0 <= 3600 Permintaan Tipe x 3 0 0 50 0 <= 1020 Permintaan Tipe x 4 0 0 0 50 <= 1140 Variable type (click to set) Integer Integer Integer Integer Solution-> 46 36 20 22 Optimal Z-> 4832000
Tabel di atas merupakan hasil input uraian kendala di QM for windows, dan dari tabel
bisa terlihat bahwa tiap variabel dibatasi sebagai bilangan bulat (integer).

## Tabel 3. Hasil Iterasi
Iteration Level Added Constraint Solution Type Solution Value X1 X2 X3 X4 Optimal 4832000 46 36 20 22 1 0 NONinteger 4910150 46,57 36 20,4 22,8 2 1 X1<= 46 NONinteger 4892000 46 36 20,4 22,8 3 2 X3<= 20 NONinteger 4873600 46 36 20 22,8 4 3 X4<= 22 INTEGER 4832000 46 36 20 22 5 3 X4>= 23 Infeasible 6 2 X3>= 21 Infeasible 7 1 X1>= 47 Infeasible

## Gambar 1. Hasil Percabangan
Berdasarkan  pengolahan  data  di  atas didapatkan  hasil  produksi  dan  penjualan yang  optimal  dengan  keterbatasan  sumber daya yang tersedia pada proses percabangan tersebut terakhir di iterasi ke- 7  dimana  hasil  dari  iterasi  tersebut memperoleh  hasil  yang  tidak  layak  dan nilai    kurang  dari  batas  bawah  sehingga tidak dapat dilakukan percabangan lagi.
Sehingga  diperoleh  percabangan  yang optimal pada iterasi ke-4 dengan
penambahan  kendala  yakni  x 4 ≤  22  dan diperoleh nilai:
x 1 =46 x 2 =36 x 3 =20 x 4 =22
Lalu  subtitusikan  hasil  variabel  di  atas pada fungsi tujuan maka:
32.000x 1 +36.000x 2 +46.000x 3 +52.000x 4 = 32.000(46)+36.000(36)+46.000(20)+52.00 0(22)=1.656.000  +  1.296.000  +  920.000  + 1.144.000= Rp 4.832.000
Maka  didapatkan  keuntungan  maksimal adalah Rp 4.832.000.
Dari  hasil  di  atas,  dapat  juga  diketahui jumlah  fungsi  kendala  dan  yang  tersisa, dengan cara mensubtitusikan hasil variabel ke  dalam  fungsi  kendala  masing-masing. Maka jumlah perhitungannya adalah sebagai berikut: Tabel 4. Hasil perhitungan fungsi kendala Jenis Kendala Tipe 120 Tipe 140 Tipe 160 Tipe 180 Kapasitas Tersedia Total Sisa Bahan baku (m²) 239,2 216 136 167,2 1000 758,4 241,6 Benang (gram) 4600 3600 2100 2310 15700 12610 3090 Waktu (menit) 874 684 380 418 2880 2356 524 Tenaga Kerja (orang) 46 36 20 22 171 124 47 Kapasitas Produksi (pcs) 46 36 20 22 150 124 26 Permintaan Tipe 120 (pcs) 3082 0 0 0 3120 3082 38 Permintaan Tipe 140 (pcs) 0 3600 0 0 3600 3600 0 Permintaan Tipe 160 (pcs) 0 0 1000 0 1020 1000 20 Permintaan Tipe 180 (pcs) 0 0 0 1100 1140 1100 40 Dari  tabel  diatas  dapat  diketahui  bahan baku  yang  digunakan  dalam  1  minggu adalah sebagai berikut: 5,2x 1 + 6x 2 + 6,8x 3 + 7,6x 4 ≤  1000 5,2(46) + 6(36) + 6,8(20) + 7,6(22) ≤ 1000 292,2 + 216 + 136 + 167,2               ≤ 1000 758,4 ≤ 1000
Jadi  bahan  baku  yang  digunakan  dalam  1 minggu  adalah  758,4  m²  dan  bahan  yang tersedia  selama  seminggu  adalah  1000  m² berarti  sisa  bahan  baku  yaitu    241,6  m². Dengan  cara  yang  sama  juga  dapat dihitung  sisa  untuk  kendala  yang  lain seperti dikolom bahan baku.

## 4. SIMPULAN
UKM  Puguh  Jaya  memiliki  9  kendala dalam  proses  produksinya.  Perencanaan produksi  pada  UKM  Puguh  Jaya  dapat dipandang sebagai masalah integer programming. Penentuan  jumlah  produksi dengan  menggunakan  algoritma Branch and  Bound sangat  membantu  UKM  dalam menentukan  jumlah  produksi  untuk  tiap- tiap  tipe,  sehingga  diperoleh  keuntungan yang maksimal. Berdasarkan hasil perhitungan  dengan  aplikasi QM  for Windows didapatkan keuntungan maksimal sebesar Rp 4.832.000 dengan
memproduksi tipe kain 120, 140, 160, 180 berturut-turut adalah 46 pcs, 36 pcs, 20 pcs dan  22  pcs.  Penentuan  jumlah  produksi dengan  algoritma Branch  and  Bound menghasilkan peningkatan keuntungan sebesar  18,7%  dibandingkan  keuntungan sebelumnya.

## DAFTAR PUSTAKA
[1] Akram,  S.  A.,  dan  Jaya,  A.  I. Optimalisasi  Produksi  Roti  dengan Menggunakan  Metode  Branch  and Bound  (Studi  Kasus  Pada  Pabrik  Roti
Syariah  Bakery,  Jl.  Maleo,  Lrg.VIII
No. 68 Palu). Jurnal Ilmiah Matematika  dan  Terapan ,  13(2)  :  98- 107. 2016. [2] Falani,  I.  Penentuan  Nilai  Parameter Metode Exponential Smoothing
dengan  Algoritma  Genetik  dalam Meningkatkan  Akurasi  Forecasting.
Journal  of  Computer  Engineering System  and  Science ,  3(1)  :  14–16.
2018.
[3] Hillier,  F.  S.,  dan  Lieberman,  G.  J. Operations  Reasearch .  Edisi  ke-8. Terjemahan  oleh  Parama  Kartika Dewa, dkk. Yogyakarta: ANDI. 2005.
[4] Jiao, H. W., dkk. An Effective Branch and  Bound  Algorithm  for  Minimax Linear Fractional Programming.
Journal  of  Applied  Mathematics , Volume 2014 : 8. 2014.
[5] Mehdizadeh,  E.,  dan  Jalili,  S.  An Algorithm  Based  on  Theory  of Constraints and Branch and Bound for
Solving Integrated Product-Mix- Outsourcing  Problem. Journal  of Optimization in Industrial Engineering , 12(1) : 167-172. 2019.
[6] Puryani.,  dan  Ristono,  A. Penelitian Operasional . Yogyakarta: Graha Ilmu. 2012.
[7] Taha,  H.  A. Operations  Research:  An
Introduction . Edisi ke-8. United States of America: Prentice-Hall International, INC. 2007. [8] Taylor, B. W. Introduction to Management  Science .  Edisi  ke-11. United  States  of  America:  Prentice- Hall International, INC. 2013.
[9] Williams,  H.  P.  The  Problem  with Integer  Programming. Journal  of Management  Mathematics ,  22(3)  : 213-230. 2011.
[10] Winston, W. L. Operations Research:
Applications  and  Algorithms .  Edisi Keempat. Canada: Brooks/Cole- Thomson Learning. 2004.