## OPTIMALISASI KEUNTUNGAN DENGAN MENGGUNAKAN ALGORITMA BRANCH AND BOUND PADA PT XYZ
Nintia Litano 1 , Endang Suhendar 2
Program Studi Teknik Industri, Universitas Indraprasta PGRI Jakarta 1 dinilitano@gmail.com, endang_suhendar@unindra.ac.id
Submitted January 21, 2020; Revised March 22, 2020; Accepted June 8, 2020

## Abstrak
Dalam  memaksimalkan  keuntungan  yang  akan  diperoleh  perusahaan  perlu  adanya  perencanaan produksi  yang  optimal.  Perencanaan  tersebut  mempertimbangkan  ketersediaan  sumber  daya  pada perusahaan.  PT  XYZ  merupakan  perusahaan  yang  bergerak  di  bidang furniture .  Penelitian  ini  fokus kepada  pengoptimalan  perencanaan  produksi  pada  pembuatan  produk  pintu  di  PT.XYZ.  Terdapat beberapa jenis produk yang diproduksi di antaranya: Pintu tipe D1 , Pintu tipe D2, Pintu tipe D3, dan Pintu tipe D4. Perencanaan produksi di PT.XYZ ini dapat dikatakan sebagai model program integer , karena  semua  variabel  menghendaki  hasilnya  berupa  bilangan  bulat.  Program  tersebut  berhubungan dengan  pengoptimalan  ketersediaan  sumber  daya    bertujuan  untuk  memaksimalkan  keuntungan. Pengoptimalan yang dilakukan yaitu dengan menentukan jumlah produksi untuk masing-masing tipe serta mempertimbangkan semua ketersediaan 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  36.5%  dibandingkan  dengan keuntungan PT.XYZ sebelumnya.
Kata Kunci: Optimasi, program integer , Branch and Bound

## Abstract
In  maximizing  the  profits  to  be  obtained  the  company  needs  optimal  production  planning.  The  plan considers  the  resources  of  the  company.  PT  XYZ  is  a  furniture  company.  This  research  focuses  on optimizing  production  planning  on  the  manufacture of  door  products  at  PT.  XYZ.  There are several types of products issued in: D1 type door, D2 type door, D3 type door, and D4 type door. Production planning  at  PT.  XYZ  can  be  seen  as  an  integer  program  model,  which  is  a  method  related  to optimizing  resources  to  increase  profits.  Optimization  is  done  by  determining  the  amount  of production for each type and each calculating existing resources. The solution search for this model is done  by  the  Branch  and  Bound  algorithm.  Based  on  the  calculation  results  using  QM  software  for Windows, the amount corresponding to production is obtained by using Branches and Bound giving an increase of 36.5% compared to the acquisition of PT. XYZ before. Key Words: Optimization, integer programming, Branch and Bound.

## 1. PENDAHULUAN
Perencanaan  produksi  penting  dalam berlangsungnya  manajemen  perusahaan, agar  penjual  dapat  mengetahui  jenis  dan jumlah  produk  yang  akan  diproduksi  dan dijual sesuai dengan permintaan konsumen. Manajemen
produksi merupakan kegiatan untuk mengatur penggunaan  sumber  daya  secara  efektif
dan  efisien  untuk  menciptakan  dan menambah  kegunaan (utility) sesuatu barang atau jasa [1].
PT  XYZ  merupakan  sebuah  perusahaan yang  bergerak  dalam  bidang furniture interior design yang berlokasi  di Jl. Raya Cileungsi-Jonggol,  Kecamatan  Cileungsi, Kabupaten Bogor. Usaha ini tidak memiliki  metode  yang  pasti  dalam
menentukan jumlah produksi yang optimal pada  masing-masing  tipe  pintu.  Pada  PT XYZ terdapat kendala-kendala yang terjadi dalam  proses  produksi  di  antara  nya  yaitu ketersediaan  bahan  baku  yang  digunakan, waktu  produksi  yang  diperlukan,  jumalah tenaga  kerja  yang  ada  mempengaruhi jumlah produksi yang dihasilkan, kemampuan kapasitas produksi, dan jumlah permintaan produk yang beragam.
Kendala-kendala  yang  terjadi  pada  PT XYZ  dapat  dikatakan  sebagai integer programming dikarenakan  semua  variabel menghendaki  hasilnya  berupa  bilangan bulat.  Sesuai  dengan  namanya  metode  ini membatasi penyelesaian optimal yang akan menghasilkan  bilangan  pecahan  dengan cara membuat cabang atas atau bawah bagi masing-masing  variabel  keputusan  yang bernilai  bulat  sehingga  setiap  oembatasan akan  menghasilkan  cabang  baru  [2] . Pada penelitian ini dengan menggunakan algoritma Branch  and  Bound efektif  dan sederhana  untuk  menyelesaikan  model program integer [3]–[6].
Dengan  prinsip  kerja  metode Branch  and Bound yaitu mencabangkan variabel keputusan yang tidak memiliki penyelesaian bulat, percabangan dilakukan terus  hingga  diperoleh  penyelesaian  bulat sehingga  semua  variabel  keputusannya bernilai bulat dan menghasilkan keuntungan maksimal bagi perusahaan [6]. Maka  dari  itu  pada  penelitian  ini,  peneliti mencoba  menghitung  sebuah  optimalisasi hasil  produksi  dalam  produksi  pembuatan pintu  pada  PT  XYZ  menggunakan menggunakan Integer Linear Programming (ILP) dengan metode Branch and Bound.
Suatu  masalah  optimasi,  dikenal  fungsi objektif atau fungsi tujuan yang merupakan fungsi pengevaluasi yang ingin dioptimalkan [7]. Program integer digunakan untuk memodelkan permasalahan  yang  variabel-variabelnya tidak mungkin  berupa bilangan  yang tidak bulat  (bilangan  riil)  [8].  Menurut  [9]
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 [10].

## 2. METODE PENELITIAN
Dalam penelitian ini metode yang digunakan  yaitu  dengan  melakukan  studi pustaka  melalui  buku  maupun  penelitian yang  terdahulu  dalam  konsep  algoritma Branch  and  Bound dan  model Integer Linear Programing.
Kemudian diimplementasi  pada  PT  XYZ  untuk penentuan  jumlah  produksi  yang  optimal untuk memaksimalkan keuntungan. Pengolahan data dilakukan dengan menggunakan  perangkat  lunak QM  for Windows. Hasil  dari  pengolahan  data  dan analisis  diharapkan  dapat  menjadi  solusi dari  keputusan  penentuan  jumlah  produksi yang optimal.

## 3. HASIL DAN PEMBAHASAN
Pada pengolahan data dalam menyelesaikan  permasalahan  pada  PT XYZ  untuk  memaksimalkan  keuntungan produksi  dibutuhkan  pengumpulan  data yang  lengkap  mengenai  proses  produksi seluruh tipe pintu.
Pada PT XYZ terdapat beberapa tipe pintu yaitu antara lain pintu tipe D1, D2, D3, dan D4. Dalam rangka memaksimalkan keuntungan, perusahaan harus menentukan jumlah  produksi  pintu  tiap  tipe  yang sebaiknya  diproduksi.  Pada  penelitian  ini, yang merupakan variabel keputusan adalah Pintu  D1  (x 1 ),  Pintu  D2,  (x 2 ),  Pintu  D3 (x 3 ),  Pintu  D4  (x 4 ).  Berikut  adalah  uraian permasalahan  yang  biasa  terkendala  pada PT XYZ:
Tabel 1. Uraian Kendala PT XYZ Uraian Kendala Pintu D1 Pintu D2 Pintu D3 Pintu D4 Kapasitas Satuan Keuntungan 161.2 100.5 115 130 Kayu 20 20 20 6 1000 m 2 Kaca - - - 6 50 m 2 Gagang pintu 1 1 1 1 300
Pcs Engsel 2 2 2 2 600 Pcs Cat 2 2 2 2 15
Kg Waktu Produksi 100 100 100 100 2880 Menit
Tenaga kerja 5 5 5 5 60
Pekerja
Mesin 2 2 2 2 16 Mesin
Permintaan D1 480 0 0 0 1200 Pcs Permintaan D2
0 1128 0 0 1200 Pcs Permintaan D3 0 0 648 0 1200
Pcs Permintaan D4 0 0 0 480 1200 Pcs
Kapasitas produksi 1 1 1 1 1200
Pcs
Sumber: PT XYZ
Setelah mendefinisikan variabel keputusan dan  mengetahui  uraian  kendala,  maka langkah  selanjutnya  adalah  menentukan Fungsi  Tujuan  dan  Fungsi  Kendala  dari penelitian, sebagai berikut:
Fungsi Tujuan: Z maks =161200x 1 +  100500x 2 +  115000x 3 + 130000x 4
Fungsi Kendala : 20x 1 + 20x 2 + 20x 3 + 6x 4 ≤1000 (Kayu) 6x 4 ≤50 (Kaca)
x 1 + x 2 + x 3 + x 4 ≤ 300
(Gagang pintu)
2x 1 + 2x 2 + 2x 3 + 2x 4
≤ 600
(Engsel pintu)
100x 1 +  100x 2 +  100x 3 +  100x 4 ≤  2880 (Waktu)
2x 1 + 2x 2 + 2x 3 + 2x 4 ≤ 15
(Cat)
2x 1 + 2x 2 + 2x 3 + 2x 4 ≤ 16
(Mesin)
5x 1 + 5x 2 + 5x 3 + 5x 4 ≤ 60
(Tenaga Kerja)
x 1 + x 2 + x 3 + x 4 ≤  1200
(Kapasitas Produksi)
480 x 1 ≤ 1200   (Permintaan Tipe D1)
1128 x 2 ≤ 1200   (Permintaan Tipe D2)
648 x 3 ≤ 1200   (Permintaan Tipe D3) 480 x 4 ≤ 1200   (Permintaan Tipe D4) x 1 , x 2 , x 3 , x 4 ≥ 0 x 1 , x 2 , x 3 , x 4
Є I
Kemudian  setelah  mengetahui  secara matematis  Fungsi  Tujuan  dan  Fungsi Kendala di  atas, data diolah  menggunakan software QM for Windows dengan pemilihan    menu Integer  &  Mixed  Integer Programming dan  memasukan  nilai-nilai fungsi  tujuan  memaksimalkan  dan  fungsi kendala pada gambar sebagai berikut :
Sumber : POM-QM
Gambar 1. Original Problem Table With Solution
Pada  gambar  di  atas  dapat  dilihat  bahwa tiap  variabel  keputusan  dibatasi  sebagai bilangan  bulat (integer). Sebelum  solusi tersebut  terdapat  hasil  iterasi  yang  didapat sebagai berikut:

## Sumber : POM-QM
Gambar 2. Iteration Result
Dari  hasil  iterasi  tersebut  sebanyak  4  kali iterasi  dan  dinyatakan  integer,  didapatlah hasil percabangan yaitu sebagai berikut:
Sumber: Penelitian

## Gambar 3. 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- 9  dimana  hasil  dari  iterasi  tersebut memperoleh  hasil  yang  tidak  layak  dan nilai    kurang  dari  batas  bawah  sehingga tidak  dapat  dilakukan  percabangan  lagi. Diperoleh  percabangan  yang  optimal  pada iterasi  ke-4  dengan  penambahan  kendala yakni D 4 ≤ 2 dengan nilai:
D1 = 2, D2 = 1, D3 = 1, dan D4 = 2. Lalu disubstitusikan nilai tersebut : = 161.200 (2) + 100.500 (1) + 115.000 (1) + 130.000 (2) = Rp 797.900
Berdasarkan fungsi tujuan tersebut, diperoleh  informasi  sebagai  berikut:  laba yang diperoleh dari produksi pintu tipe D1 sebesar  Rp  322.400  per  unit,  pintu  D2
sebesar Rp 100.500 per unit, pintu tipe D3 sebesar Rp 115.000 per unit dan pintu tipe D4  sebesar  Rp  260.000  per  unit  tiap  hari untuk memaksimalkan keuntungan dengan total keseluruhan keuntungan yang diterima PT XYZ dari semua tipe yaitu Rp 797.900  per  hari.  Jika  dibandingkan dengan  keuntungan  sebelumnya  yaitu  Rp. 506,700  namun  setelah  menggunakan algoritma Branch  and  Bound menjadi  Rp. 797,900.  Maka  dapat  dikatakan  terjadinya peningkatan keuntungan setelah menggunakan algoritma Branch and Bound yaitu sebesar 36,5%.

## 4. SIMPULAN
Dalam  proses  produksinya  PT  XYZ memiliki 13 kendala. Perencanaan produksi  pada  perusahaan  dengan  upaya memaksimalkan keuntungan menggunakan algoritma Branch  and  Bound cukup membantu  untuk  menjadi  solusi  dalam penentuan  jumlah  produksi  untuk  tiap-tiap tipe pintu, sehingga menghasilkan keuntungan  yang  maksimal.  Berdasarkan pengolahan  data  menggunakan  software QM  for  Windows didapatkan  keuntungan maksimal  sebesar  Rp  797.900  dengan pintu  tipe  D1  memproduksi    2  unit,  pintu tipe D2 memproduksi  1 unit, pintu tipe D3 memproduksi    1  unit,  dan  pintu  tipe  D4 memproduksi 2 unit. Dengan menggunakan algoritma Branch and Bound terjadi  peningkatan  keuntungan yaitu sebesar 36,5% dibandingkan keuntungan  yang  diperoleh  perusahaan sebelumnya.

## DAFTAR PUSTAKA
[1] S.  Assauri,  “Manajemen  Produksi dan  Operasi,” Jakarta Lemb. Penerbit Fak. Ekon. Univ. Indones. , 2008.
[2] Wayne  L.  Winston, Operations Research: Applications and
Algorithms, Forth Edition . 2004.
[3] A. Akram, A. Sahari, and A. I. Jaya,
“Optimalisasi Produksi Roti dengan Menggunakan  Metode  Branch  and Bound    (Studi  Kasus  Pada  Pabrik Roti  Syariah  Bakery,  Jl.  Maleo, Lrg.VIII No. 68 Palu),” J. Ilm. Mat. DAN Terap. , 2016, doi: 10.22487/2540766x.2016.v13.i2.72 09.
[4] H.  W.  Jiao,  F.  H.  Wang,  and  Y.  Q. Chen,  “An  effective  branch  and bound algorithm for minimax linear fractional  programming,” J.  Appl. Math. ,  vol.  2014,  2014,  doi: 10.1155/2014/160262.
[5] H.  P.  Williams,  “The  problem  with integer  programming,” IMA  J. Manag.  Math. ,  vol.  22,  no.  3,  pp. 213–230, 2011, doi: 10.1093/imaman/dpq014. [6] Y.  N.  Firdaus,  N.  L.  Buyung,  A. Hermansyah,  R.  Nurhadiyati,  I.
Falani, and E. Wiratmani, “Implementasi  Algoritma  Branch and Bound dalam Penentuan Jumlah Produksi  untuk  Memaksimalkan Keuntungan,” STRING (Satuan Tulisan  Ris.  dan  Inov.  Teknol. , 2019, doi: 10.30998/string.v4i1.3717. [7] I. Falani, “Penentuan Nilai Parameter Metode Exponential Smoothing Dengan Algoritma Genetik Dalam Meningkatkan Akurasi Forecasting,” Comput. Eng.
Sci.  Syst.  J. ,  vol.  3,  no.  1,  p.  14, 2018, doi: 10.24114/cess.v3i1.8268.
[8] E.  Mehdizadeh  and  S.  Jalili,  “An algorithm  based  on  theory  of constraints  and  branch  and  bound for  solving  integrated  product-mix- outsourcing  problem,” J.  Optim. Ind.  Eng. ,  vol.  12,  no.  1,  pp.  167– 172, 2019, doi: 10.22094/JOIE.2018.664.1429. [9] B.  W.  Taylor, Introduction  to Management  Science  11e ,  vol.  58,
no. 3. 2013. [10]  D.  Reyniers  and  H.  A.  Taha, “Operations Research: An Introduction  (4th  Edition),” The Journal of the Operational
Research Society , vol. 40, no. 11. p.
1054, 1989, doi: 10.2307/2583144.