## Sistem Informasi Pemotongan Kayu menggunakan Algoritma Greedy

## Siti Munawaroh
Program Studi Teknik Informatika, Universitas Stikubank email : munawaroh2806@gmail.com

## Abstrak
Kayu  merupakan  salah  satu  kekayaan  alam  Indonesia  yang    sekarang  ini  menjadi  salah  satu kebutuhan masyarakat di Indonesia. Kegunaan kayu yang banyak membuat perusahaan yang bergerak pada bidang  pemotongan  kayu  ikut  andil  besar  pada  pemenuhan  kebutuhan  kayu  di  Indonesia.  Proses pemotongan kayu balok yang besar ke bagian yang lebih kecil, setiap perusahaan mempunyai teknik-teknik tersendiri.
Perusahaan biasanya akan memotong kayu ke bagian yang besar dulu, selanjutnya bila sudah tidak bisa  akan  di  potong  ke  ukuran  yang  lebih  kecil,  begitu  seterusnya  sampai  bagian  kayu  habis  terpotong. Teknik  pemotongan  dengan  cara  memotong  ke  ukuran  yang  besar  dilanjutkn  ke  ukuran  potongan  yang lebih kecil disebut teknik pemotongan dengan menggunakan Algoritma Greedy . Dari hasil potongan kayu ke  ukuran-ukuran  tertentu  tersebut,  perusahaan  dapat  memperkirakan  jumlah  pendapatan  yang  diperoleh. Terkadang perusahaan kesulitan dalam menentukan harga potongan kayu karena harga kayu yang semakin melambung  tinggi.  Dengan  adanya  sistem  pemotongan  kayu  dengan  menggunakan  algoritma  greedy perusahaan dapat memperkirakan harga jual kayu supaya perusahaan tetap mendapat laba, dan konsumen juga tidak merasa dibebani dengan harga kayu yang tinggi.
Kata Kunci : Pemotongan Kayu, Algoritma Greedy , Pendapatan

## PENDAHULUAN
Kayu  merupakan  salah  satu  kebutuhan yang  sangat  diperlukan.  Tidak  hanya  di  dalam negeri,  di  luar  negeri  juga  dibutuhkan.  Untuk sekarang  ini,  ekspor  kayu  jati  mentah  sudah tidak  diperbolehkan  lagi;  hanya  kayu  jati  yang sudah diolah yang diperbolehkan untuk diekspor.  Proses  pengolahan  ke  produk-produk jadi  memerlukan  kayu  yang  sudah  dipotong- potong ke bagian yang lebih kecil. Untuk proses pemotongan  kayu  ke  bagian  yang  lebih  kecil dengan ukuran tertentu memerlukan suatu teknik tersendiri.  Perusahaan  biasanya  akan  memotong kayu ke bagian yang besar dulu, selanjutnya bila sudah tidak bisa akan di potong  ke ukuran yang lebih  kecil,  begitu  seterusnya  sampai  bagian kayu  habis  terpotong.  Dari  hasil  potongan  kayu ke  ukuran-ukuran  tertentu  tersebut,  perusahaan dapat  memperkirakan  jumlah  pendapatan  yang diperoleh.  Terkadang  perusahaan  kesulitan dalam  menentukan  harga  potongan  kayu  karena harga  kayu  yang  semakin  melambung  tinggi.
Dengan adanya sistem pemotongan kayu dengan menggunakan  algoritma  greedy  perusahaan dapat  memperkirakan  harga  jual  kayu  supaya perusahaan  tetap  mendapat  laba,  dan  konsumen juga  tidak  merasa  dibebani  dengan  harga  kayu yang tinggi.
Berdasarkan  latar  belakang  di  atas,  maka diperlukan suatu sistem yang mampu memberikan  informasi  tentang  pemotongan kayu  menjadi potongan yang lebih  kecil dengan ukuran yang sudah ditentukan dan disamping itu sistem juga dapat memberikan informasi tentang pendapatan  yang  akan  diperoleh  dari  hasil potongan kayu, sehingga pihak perusahaan dapat menentukan  harga  untuk  potongan  kayu  yang akan dijual nantinya. Untuk itu diperlukan suatu cara  yang  akan  digunakan  untuk  melakukan pemotongan, yaitu dengan menggunakan algoritma greedy .

## PUSTAKA
Teori yang digunakan merupakan
penjelasan  mengenai  Kayu  dan  Algoritma Greedy .
Kayu
Kayu merupakan hasil hutan dari kekayaan  alam,  merupakan  bahan  mentah  yang mudah  diproses  untuk  dijadikan  barang  sesuai kemajuan  teknologi.  Kayu  memiliki  beberapa sifat  sekaligus,  yang  tidak  dapat  ditiru  oleh bahan-bahan  lain.  Pengertian  kayu  disini  ialah sesuatu  bahan,  yang  diperoleh  dari  hasil pemungutan  pohon-pohon  di  hutan,  yang merupakan  bagian  dari  pohon  tersebut,  setelah diperhitungkan  bagian-bagian  mana  yang  lebih banyak  dimanfaatkan  untuk  sesuatu  tujuan penggunaan.  Baik  berbentuk  kayu  pertukangan, kayu industri maupun kayu bakar. (Dumanauw.J.F, 1990)
Algoritma Greedy
Persoalan  optimasi ( optimization problems ): persoalan  yang  menuntut  pencarian  solusi optimum.
Persoalan optimasi ada dua macam:
1. Maksimasi ( maximization )
2. Minimasi ( minimization )
Solusi optimum (terbaik) adalah solusi yang bernilai  minimum  atau  maksimum  dari sekumpulan alternatif solusi yang mungkin.
Elemen persoalan optimasi:
1. kendala ( constraints )
2. fungsi objektif(atau fungsi optiamsi)
Solusi  yang  memenuhi  semua  kendala disebut solusi  layak ( feasible  solution ).
Solusi  layak  yang  mengoptimumkan  fungsi optimasi disebut solusi optimum .
Algoritma greedy merupakan  metode  yang paling populer untuk memecahkan persoalan optimasi.
Greedy = rakus, tamak, loba, ….
Prinsip greedy adalah:  “ take  what  you  can get now! ”.
Contoh masalah sehari-hari yang menggunakan prinsip greedy :
o Memilih beberapa jenis investasi (penanaman modal)
o Mencari  jalur  tersingkat  dari  Bandung ke Surabaya
o Memilih jurusan di Perguruan Tinggi
o Bermain kartu remi
Algoritma greedy membentuk  solusi langkah per langkah ( step by step ).
Terdapat banyak pilihan yang perlu dieksplorasi pada setiap langkah solusi. Oleh karena itu, pada setiap  langkah  harus dibuat keputusan  yang  terbaik  dalam  menentukan pilihan.  Keputusan  yang  telah  diambil  pada suatu  langkah  tidak  dapat  diubah  lagi  pada langkah selanjutnya.
Pendekatan  yang  digunakan  di  dalam algoritma greedy adalah  membuat  pilihan yang  “tampaknya”  memberikan  perolehan terbaik,  yaitu  dengan  membuat  pilihan optimum  lokal ( local optimum ) pada setiap langkah  dengan  harapan  bahwa  sisanya mengarah ke solusi optimum global ( global optimm ).
Algoritma greedy adalah  algoritma  yang memecahkan  masalah  langkah  per  langkah, pada setiap langkah:
1. mengambil  pilihan  yang  terbaik  yang dapat  diperoleh  pada  saat  itu  tanpa memperhatikan  konsekuensi  ke  depan (prinsip “ take what you can get now! ”)
2. berharap bahwa dengan memilih optimum lokal pada setiap langkah akan berakhir dengan optimum global.
Pada  setiap  langkah  diperoleh optimum lokal . Bila algoritma berakhir, kita berharap optimum lokal menjadi optimum global .
Contoh 1 (Masalah Penukaran uang):
Persoalan :  Diberikan  uang  senilai A .  Tukar A dengan koin-koin uang yang ada. Berapa jumlah minimum koin yang diperlukan untuk penukaran tersebut?
Contoh: tersedia koin-koin 1, 5, 10, dan 25
Uang  senilai  32  dapat  ditukar  dengan  cara berikut:
32 = 1 + 1 + … + 1     (32koin)  32 = 5 + 5 + 5 + 5 + 10 + 1 + 1  (7 koin)
32 = 10 + 10 + 10 + 1 + 1  (5 koin)
… dan seterusnya
Minimum:  32  =  25  +  5  +  1  +  1              )  hanya  4 koin
Strategi greedy yang digunakan  adalah:
Pada  setiap  langkah,  pilihlah  koin  dengan nilai sebesar mungkin dari himpunan koin yang tersisa dengan syarat (kendala) tidak melebihi nilai uang yang ditukarkan.
Tinjau  masalah  menukarkan  uang  32  dengan koin 1, 5, 10, dan 25:
Langkah 1 : pilih 1 buah koin 25  (Total = 25)
Langkah 2 : pilih 1 buah koin 5   (Total = 25 + 5 = 30)
Langkah  3 :  pilih  2  buah  koin  1    (Total  = 25+5+1+1= 32)
Solusi:  Jumlah  koin  minimum  =  4  (solusi optimal!)
Pada setiap langkah di atas kita memperoleh  optimum  lokal,  dan  pada  akhir algoritma  kita  memperoleh  optimum  global (yang  pada  contoh  ini  merupakan  solusi optimum).

## PEMBAHASAN
Pembahasan  mengenai  Rekayasa  Sistem Pemotongan  Kayu  menggunakan  Algoritma Greedy adalah :
Diskripsi Sistem
Pada  Sistem  pemotongan  kayu  yang pertama  kali  dilakukan  adalah  Admin  semua informasi  mengenai  kayu  ke  sistem  Informasi Pemotongan Kayu, meliputi : Input User ( untuk user  admin  bisa  memasukkan  user  siapa  saja yang akan memakai sistem dengan menginputkan  nama  user  dan password ). Disamping  itu  admin  juga  bisa  menginput  jenis kayu serta input  bentuk kayu. Pemakai atau user
dapat  memasukkan  data  kayu  yang  akan dipotong  meliputi  jenis  kayu,  panjang  kayu, lebar kayu dan tinggi kayu.
Data Flow Diagram Sistem Pemotongan Kayu
Data  Flow  Diagram  Sistem  Pemotongan Kayu  dengan  menggunakan  Algoritma Greedy di gambarkan seperti  gambar 3.1 berikut ini :
Gambar 3.1. Diagram Context Sistem Pemotongan Kayu
Dari  Diagram Context diatas  terdiri  dari dua  external  entity  yaitu  admin  dan  user  serta memiliki  1  proses  yaitu  sistem  informasi pemotongan kayu. Admin yang berhak memasukkan data kayu yaitu meliputi jenis kayu dan  bentuk  kayu.    Admin  juga  memasukkan identitas user yang bisa  memakai sistem dengan menginputkan nama  user  dan password . Sedankan  User  yang  bisa  masukkan  ke  sistem adalah  user  yang  sudah  didaftarkan  oleh  admin. User  bisa  memasukkan  data  kayu  yang  akan dipotong,  kemudian  sistem  akan  memproses sesuai dengan algoritma greedy akan  memotong ukuran  yang  lebih  besar  dulu  sampai  dengan ukuran yang paling  kecil. Dari sistem user akan mendapatkan infrmasi mengenai hasil pemotongan
kayu yang perhitungan pendapatannya.
Diagram  context  akan  diturunkan  ke  digram level  berikutnya  seperti  yang  terlihat  pada gambar 3.2 berikut:

## Gambar 3.2. Diagram Level 1 Sistem
Pemotongan Kayu Arsitektur Sistem Pemotongan Kayu menggunakan Algoritma Greedy
Sistem Pemotongan Kayu dengan menggunakan Algoritma  Greedy  mempunyai  arsitektur  seperti yang digambarkan pada gambar 3.3. berikut :
Gambar 3.3. Arsitektur Sistem Pemotongan Kayu Flowchart Sistem Pemotongan Kayu menggunakan Algoritma Greedy
User  sendiri  pada  waktu  mengoperasikan Sistem  Pemotongan  sistem  harus  memasukkan data  kayu  (ukuran  kayu  balok  besar)  yang  akan dipotong.  Setelah  data  kayu  yang  akan  potong dimasukkan,  user  harus  mengisi  kayu  apa  yang
akan dipotong, karena setiap kayu punya ukuran potongan  sendiri.  Untuk  ukuran  potongan  kayu sudah  diinput  oleh  admin  dan  disimpan  di database.  Jika  data  kayu  dan  jenis  kayu  sudah dimasukkan,  sistem  akan  melakukan  proses pemotongan berdasarkan urutan ukuran potongan  yang  paling  besar  dulu,  jika  ukuran besar sudah tidak bisa dipotong akan dilanjutkan dengan ukuran yang berikutnya. Proses pemotongan  akan  dilakukan  sampai  ukuran sudah  tidak  mencukupi  lagi  untuk  dipotong.
Setelah  didapatkan  potongan-potongan  kayu dengan  ukuran  tertentu,  setiap  ukuran  akan dikalikan  dengan  harga  kayu  perkubik  sehingga akan didapatkan pendapatan setiap jenis potongan  kayu.  Pendapatan-pendapatan  kayu kemudian  akan  dijumlah  secara  keseluruhan sehingga  mendapatkan  pendapatan  total  dari semua  jumlah  potongan  kayu.  Untuk  lebih jelasnya  flowchart  untuk  user  bisa  diperhatikan gambar 3.4.
Gambar 3.4. Flowchart program dari Sistem Pemotongan Kayu untuk User
3.5.  Entity  Relationship  Diagram  Sistem Pemotongan Kayu
Entity  Relationship  Diagram  dari Sistem  Pemotongan  Kayu  adalah  seperti  di gambarkan pada gambar 3.5.
Gambar 3.5. Entity Relationship Diagram

## Sistem Pemotongan Kayu

## 3.6. Transformsi Entity Relationship Diagram
Transformasi  Entity  Relationship  Diagram  dari gambar  3.5.  didefinisikan  pada  tabel  3.1. berikut:
Tabel 3.1.Transformasi Entity Relationship Diagram Tabel Jenis Kayu Idkayu Namakayu Tabel Bentuk Kayu Idbe ntuk Idk ayu Ha rga Namab entuk Panj ang Le bar Tin ggi 3.7. Rancangan Database Perancangan  Database  dari  Sistem Pemotongan Kayu dengan menggunakan Algoritma Greedy
dan perhitungn
pendapatannya adalah sebagai berikut :
1. File Bentuk Kayu
Primary key : Idbentuk
Foreign key : Idkayu
Tabel 3.2. File Bentuk Kayu

## 2. File Jenis Kayu
File Bentuk kayu mempunyai Primary key : Idbentuk
Tabel 3.3. File Jenis Kayu
3.8 Arsitektur Implementasi Untuk  Implementasi  Sistem  Pemotongan  Kayu disini yang bisa dilakukan adalah :
1. Login admin
Login  untuk  admin  mempunyai  arsitektur seperti gambar 3.6. berikut:
Gambar 3.6. Arsitektur Login Admin
2. Jenis Kayu
Untuk  menginput  jenis  kayu  menggunakan arsitektur seperti gambar 3.7. dibawah ini :
Gambar 3.7. Arsitektur untuk memasukkan jenis kayu 3. Bentuk Kayu Bentuk kayu diinput menggunakan arsitektur seperti gambar 3.8.berikut ini :
Gambar 3.8. Arsitektur untuk memasukkan bentuk kayu
4. Perhitungan Potongan
Perhitungan  potongan  mempunyai  tampilan prediksi  potongan  seperti  gambar  3.9. dibawah ini :
Gambar 3.9. Arsitektur  untuk memasukkan prediksi potongan
KESIMPULAN
Rekayasa  Sistem  Pemotongan  kayu menggunakan  Algoritma Greedy merupakan pemotongan  kayu  dari  kayu  yang  berukuran besar  menjadi  potongan-potaongan  kayu  yang lebih  kecil.  Ukuran  kayu  yang  akan  dipotong diinput,  demikian  juga  dengan  ukuran  potongan kayu  yang  diinginkan  (reng,  usuk,  papan,  dll). Cara kerja dari Algoritma Greedy adalah dengan cara  mengambil  dulu  luas  dari  kayu  yang potongannya paling besar. Jika ukuran potongan yang  paling  besar  sudah  tidak  ditemukan  akan dilanjutkan dengan ukuran yang lebih kecil. Jika ukuran  yang  lebih  kecil  sudah  tidak  ditemukan lagi, sistem akan melakukan analisa pemotongan untuk bagian yang lebih kecil berikutnya sampai tidak  bisa  di  potong  lagi  begitu  seterusnya sampai  bagian  semua  bagian  dari  kayu  yang besar  tersebut  habis.  Dari  hasil  pemotongan kayu  ke  potongan  yang  lebih  kecil  akan diketahui  harga  dari  kayu  potongan  perkubik. Hasil  Potongan  kayu  dikalikan  dengan  harga akan  didapatkan  harga  kayu  per  ukuran potongan. Kemudian Sistem juga akan menjumlahkan  harga  semua  kayu  yang  sudah dipotong-potong,  sehingga  dari  sistem  itu  akan diketahui  pendapatan  dari  pemotongan  kayu dengan mengggunakan algoritma Greedy .

## DAFTAR PUSTAKA
Brassard,  G.,  Bratley,P., Fundamentals of Algorithmics , 1996, Prentice-Hall
International.
Sunardi,  B.S.F. Ilmu  Kayu ,  1977,  Fakultas Kehutanan UGM, Yogyakarta.
Jariyanto,  Optimasi  Pemotongan  Balok  Kayu dengan  Pola  Pemotongan  Satu  Dimensi menggunakan  Teknik  Pembangkit  Kolom ( Column Generation Technique ),  2008,
Universitas Negeri Yogyakarta.
http://repository.usu.ac.id/bitstream/123456789/ 18677/3/Chapter%20II.pdf
Purwanto,  E.B.,    Perancangan  dan  Analisis Algoritma, 2008, Graha Ilmu, Yogyakarta