...

ALGORITMA OPTIMASI UNTUK MEMINIMALKAN SISA

by user

on
Category: Documents
2

views

Report

Comments

Transcript

ALGORITMA OPTIMASI UNTUK MEMINIMALKAN SISA
ALGORITMA OPTIMASI UNTUK MEMINIMALKAN SISA PEMOTONGAN BAR STEEL
PADA PERUSAHAAN KONSTRUKSI
Ahmad Juniar
Program Studi Sistem Informasi, STMI Jakarta
ahmadjuniar @gmail.com
ABSTRAK
Ukuran bar steel yang dihasilkan oleh pabrik baja tidak selalu sesuai dengan ukuran yang
dibutuhkan oleh perusahaan konstruksi sehingga bar steel harus dipotong-potong sesuai
kebutuhan. Penyusunan pola pemotongan sangat penting karena perbedaan pola pemotongan
dapat menghasilkan sisa bar steel terbuang yang berbeda-beda. Beberapa algoritma optimasi
dapat menyelesaikan permasalahan pola pemotongan bar steel. Dalam penelitian ini, dibuat
sebuah perangkat lunak yang mengimplementasikan algoritma optimasi tersebut. Perangkat
lunak ini mengimplementasikan algoritma optimasi brute force, greedy, dan program dinamis
untuk mencari solusi dalam rangka meminimalkan sisa bar steel yang terbuang. Setelah diuji,
perangkat lunak menunjukkan bahwa algoritma brute force selalu menghasilkan solusi
optimal, namun paling lambat dalam proses pencarian solusi. Algoritma greedy selalu paling
cepat dalam proses pencarian solusi, dan algoritma program dinamis adalah algoritma terbaik
secara keseluruhan karena algoritma ini menghasilkan solusi yang mendekati optimal dengan
proses yang cepat untuk tipe persoalan yang mirip dengan dunia nyata. Metode brute force
tidak muncul sebagai algoritma paling optimal karena kecepatan prosesnya yang bisa
mencapai lebih dari 1 hari untuk persoalan kompleks yang biasa dihadapi di dunia nyata.
Kata kunci: Pemotongan bar steel, optimasi, brute force, program dinamis.
1. PENDAHULUAN
Urbanisasi menyebabkan perkembangan kota-kota
di Indonesia menjadi semakin pesat. Kota-kota
besar Indonesia banyak sekali melakukan
pembangunan, baik gedung perkantoran, pusat
perbelanjaan dan sebagainya. Seiring dengan
pesatnya
pembangunan,
perusahaan
jasa
konstruksi juga semakin bertambah. Banyaknya
perusahaan jasa konstruksi yang berdiri di
Indonesia
membuat
persaingan
dalam
memenangkan tender proyek konstruksi menjadi
semakin berat. Perusahaan konstruksi yang
mengikuti tender harus mampu menyusun
anggaran yang minimal tanpa mengabaikan
standar kualitas agar dapat memenangkan tender
dan memperoleh keuntungan yang besar. Salah
satu optimasi yang dilakukan adalah pada
penggunaan bahan baku yaitu bar steel.
Menurut Brady, dkk (2002), Bar steel adalah
salah satu bahan baku utama pembentuk
bangunan saat ini. Bar steel dipakai untuk
penopang suatu bangunan. Bar steel yang
digunakan untuk mendirikan bangunan terdiri dari
berbagai macam panjang, sedangkan bar steel
yang disediakan oleh pabrik baja, memiliki
panjang standar. Untuk menyesuaikan kebutuhan
perusahaan konstruksi, bar steel yang telah dibeli
harus dipotong sesuai dengan kebutuhan
bangunan.
Pemotongan
bar
steel
pasti
menyisakan bar steel berukuran pendek yang
tidak dapat digunakan lagi. Untuk itu, perusahaan
konstruksi
harus
mengoptimalkan
pola
pemotongan bar steel untuk meminimalkan sisa
bar steel yang tidak dapat digunakan lagi. Dalam
penelitian ini, beberapa algoritma digunakan akan
dikaji yaitu: algoritma brute force, greedy, dan
program dinamis untuk mencari pola pemotongan
bar steel yang paling optimal, kemudian dibuat
perangkat lunak untuk analisis lebih lanjut.
2. LANDASAN TEORI
2.1 Bar Steel
Bar steel merupakan salah satu bahan dasar
bangunan yang memiliki peranan penting dalam
berdirinya suatu bangunan. Bar steel menjadi
dasar dari berdirinya bangunan karena hampir
dipakai di seluruh bagian bangunan. Pada tahap
awal konstruksi, bentuk bangunan dibuat dari
bermacam-macam bar steel, sesuai dengan
kebutuhan bangunan. Bar steel dibuat oleh pabrik
baja dengan panjang standar. Satu batang bar
steel yang dihasilkan oleh pabrik dengan panjang
standar tersebut biasanya dihitung sebagai satu rol
1
bar steel. Oleh karena itu, bar steel dipotongpotong sesuai dengan kebutuhan bentuk
bangunan. Saat perancangan, arsitek yang
merancang bangunan telah memilki perhitungan
mengenai panjang-panjang bar steel yang
digunakan, sehingga dapat ditentukan kebutuhan
panjang bar steel untuk konstruksi.
maka algoritma optimasi adalah metode yang
digunakan untuk menemukan nilai x, misalnya
menemukan kemungkinan yang terbesar (atau
terkecil) dari suatu fungsi f dengan constraint
yang diberikan oleh variabel (Horowitz, & Sartaj,
1978). Menurut Neapolitan & Richrad (1996),
nilai x, dapat berupa nilai skalar atau vektor dari
nilai yang kontinu atau nilai diskrit.
2.3 Algoritma brute force
Brute force adalah sebuah pendekatan yang
lempang (straightforward) untuk memecahkan
masalah, biasanya didasarkan pula pada
pernyataan masalah (problem statement) dan
definisi konsep yang dilibatkan. Menurut Munir
(2006), Algoritma brute force memecahkan
masalah dengan sangat sederhana, langsung dan
dengan cara yang jelas.
2.3 Algoritma greedy
Gambar 1 Pola pemotongan bar steel
Pabrik memproduksi bar steel dengan panjang
standar l. Perusahaan konstruksi mengerjakan
proyek sehubungan dengan pembangunan gedung
yang memerlukan panjang bar steel yang
bermacam-macam. Secara khusus, panjang bar
steel untuk kebutuhan proyek sebanyak m buah
dengan panjang li untuk i= 1, 2, ..., m seperti
ditunjukkan pada Gambar 1. Perusahaan
konstruksi berkeinginan untuk memotong rol
standar sedemikian sehingga memenuhi order dan
meminimalkan sisanya. Karena potongan sisa
tidak berguna bagi perusahaan konstruksi, maka
fungsi tujuan adalah untuk meminimalkan jumlah
bar steel standar yang diperlukan untuk memenuhi
order. Diketahui lembaran standar dengan panjang
l, memiliki banyak cara memotongnya. Cara yang
demikian disebut dengan pola pemotongan.
2.2 Algoritma optimasi
Jika diberikan suatu permasalahan yang solusinya
dapat diselesaikan dengan menggunakan fungsi f
dan solusi optimal yang diinginkan adalah f(x),
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 bisa diubah lagi pada langkah
selanjutnya (Dimayati, dkk, 1996). Contoh, jika
menggunakan
algoritma
greedy
untuk
menempatkan komponen diatas sirkuit, sekali
sebuah komponen telah ditetapkan posisinya,
komponen tersebut tidak dapat dipindahkan lagi.
Pendekatan yang digunakan di dalam algoritma
greedy
adalah
membuat
pilihan
yang
“tampaknya” memberikan perolehan terbaik, yaitu
dengan membuat pilihan local optimum pada
setiap langkah dengan harapan bahwa sisanya
mengarah ke solusi global optimum (Munir,
2006).
2.3 Algoritma program dinamis
Program dinamis adalah metode pemecahan
masalah dengan cara menguraikan solusi menjadi
sekumpulan langkah (step) atau tahapan (stage)
sedemikian sehingga solusi dari persoalan dapat
dipandang dari serangkaian keputusan yang saling
berkaitan. Menurut Munir (2006), penyelesaian
persoalan dengan program dinamis terdapat
sejumlah berhingga pilihan yang mungkin, solusi
pada setiap tahap dibangun dari hasil solusi tahap
sebelumnya, dan kita menggunakan persyaratan
2
optimasi dan kendala untuk membatasi sejumlah
pilihan yang harus dipertimbangkan pada suatu
tahap.
3. METODOLOGI PENELITIAN
Langkah langkah yang digunakan dalam
melakukan penelitian ini adalah sebagai berikut:
1. Merumuskan permasalahan pemotongan
bar steel pada perusahaan konstruksi
2. Melakukan
pengumpulan
data.
Pengumpulan data yang dilakukan dengan
cara mencatat beberapa ukuran bar steel
standar yang disediakan oleh pabrik baja.
Pengumpulan data selanjutnya adalah
mencatat ukuran bar steel yang
dibutuhkan oleh perusahaan konstruksi
beserta jumlahnya.
3. Selanjutkan
adalah
memodelkan
permasalahan untuk dapat diselesaikan
dengan algoritma brute force, greedy dan
program dinamis.
4. Data masukan diuji pada setiap model
sehingga diperoleh data keluaran untuk
dianalisis.
5. Analisis dilakukan untuk memperoleh
algoritma yang optimal dan waktu yang
dibutuhkan
untuk
menyelesaikan
permasalahan.
Selanjutnya
dipilih
algoritma yang paling sesuai dengan
kasus pemotongan bar steel di dunia
nyata.
6. Hasil analisis dijadikan dasar untuk
menarik kesimpulan dari penelitian ini.
4. PEMODELAN
4.1 Algoritma Brute Force
Algoritma brute force memecahkan masalah
dengan sangat sederhana, langsung dan dengan
cara yang jelas. Metode penyelesaian dengan
brute force ini pasti menghasilkan solusi yang
paling baik karena metode ini menelusuri dan
membandingkan seluruh kemungkinan yang ada,
sehingga solusi yang muncul pasti yang terbaik
dari semua metode. Untuk lebih jelasnya,
langkah-langkah
penyelesaian
persoalan
pemotongan bar steel menggunakan algoritma
brute force adalah sebagai berikut:
1)
Buat list daftar_solusi dan solusi,
kemudian diinisialisasi kosong.
2)
Buat variabel sisa untuk menghitung
jumlah sisa yang telah dihasilkan oleh
pola pemotongan. Buat juga variabel
sisaMin untuk membandingkan pola
mana yang menghasilkan pola minimal.
Inisisalisasi sisa adalah 0 dan sisaMin
adalah 999.
3)
Inisialisasi i=0.
4)
Masukkan pola[i] kedalam daftar_solusi.
Kurangi problem dengan pattern[i], lalu
tambah sisa dengan sisapola[i].
5)
Lakukan tahap 6 hingga terdapat minimal
satu nilai negatif pada problem. Nilai i
bertambah 1.
6)
Kembali ke tahap 6 hingga semua nilai
pada problem adalah 0. Hitung nilai sisa
kemudian bandingkan dengan sisaMin,
jika sisa lebih kecil maka nilai sisaMin
diganti dengan sisa, kosongkan solusi
kemudian copy daftar_solusi ke solusi.
7)
Hapus pattern[i] dari daftar_solusi dan
tambahkan nilai sisa dengan nilai
sisapola[i]. Nilai i bertambah 1. Kembali
ke tahap 8.
8)
Lakukan tahap 9 hingga nilai i sama
dengan jumlah pola hingga akhirnya
seluruh tahap pernah ditempati oleh
semua pola.
9)
Tampilkan daftar_solusi yang berisi
langkah-langkah
pemilihan
pola
pemotongan ke layar.
Penyelesaian persoalan menggunakan algoritma
brute
force
memiliki
kompleksitas
dengan n adalah jumlah pattern yang digunakan
dari sebuah permasalahan pemotongan dan k
adalah jumlah tahap pencarian hingga selesai.
4.2 Algoritma Greedy
Penyelesaian untuk persoalan diatas dengan
menggunakan algoritma greedy adalah dengan
memilih langkah yang terlihat paling mendekati
solusi, yaitu dengan memilih pola yang memiliki
sisa terkecil terlebih dahulu. Pada implementasi
algoritma greedy, yang dilakukan hanya memilih
pattern yang memiliki sisa yang paling kecil dan
menghasilkan bar steel paling panjang dari
kumpulan pattern yang masih mungkin
diterapkan.
Berikut
ini
langkah-langkah
penyelesaian persoalan pemotongan bar steel
menggunakan algoritma greedy:
1) Masukkan simpul awal ke dalam Open
List.
2) Open List berisi simpul awal dan Closed
List masih kosong.
3) Masukkan simpul awal ke Closed List dan
suksesornya pada Open List.
3
4) Ulangi langkah berikut sampai simpul
tujuan ditemukan dan tidak ada lagi simpul
yang akan dikembangkan.
5) Hitung nilai f simpul-simpul yang ada pada
Open List, ambil simpul terbaik (f paling
kecil).
6) Jika simpul tersebut sama dengan simpul
tujuan, maka sukses.
7) Jika tidak, masukkan simpul tersebut ke
dalam Closed List.
8) Bangkitkan semua suksesor dari simpul
tersebut.
9) Untuk setiap suksesor, kerjakan:
a. Jika suksesor tersebut belum
pernah dibangkitkan, evaluasi
suksesor tersebut, tambahkan ke
open list dan catat simpul parentnya.
b. Jika suksesor tersebut sudah
pernah dibangkitkan, ubah parentnya jika jalur melalui parent saat
ini lebih baik daripada jalur
melalui parent yang sebelumnya.
Selanjutnya perbaharui nilai untuk
suksesor selanjutnya.
Keterangan:
1) Simpul (node) merupakan representasi dari
area pencarian
2) Start node adalah posisi awal pencarian
3) Current node adalah simpul yang sedang
dijalankan.
4) Suksesor adalah simpul-simpul yang
berajasen dengan current node yang
merupakan simpul-simpul yang akan
diperiksa berikutnya.
5) Open list adalah tempat menyimpan data
simpul yang mungkin diakses dari starting
node maupun simpul yang sedang
dijalankan.
6) Closed list adalah tempat menyimpan data
simpul yang juga merupakan bagian dari
jalur terpendek yang telah berhasil
didapatkan.
7) Parent adalah current node dari suatu
suksesor.
4.3 Algoritma Program Dinamis
Penyelesaian dengan algoritma program
dinamis adalah dengan memilih langkah yang
memenuhi prinsip optimalitas. Dengan prinsip
optimalitas ini dijamin bahwa setiap keputusan
yang diambil pada suatu tahap adalah keputusan
yang benar untuk tahap-tahap selanjutnya juga,
tidak hanya benar untuk tahap itu saja.
Secara matematis, penyelesaian masalah ini
dengan program dinamis dapat dituliskan sebagai
berikut:
k adalah tahap (level) pencarian, s adalah status
yang berhubungan dengan masing-masing tahap
(level) yang merupakan simpul-simpul dalam graf
(x1, x2, x3, …, xn), cxks menyatakan bobot sisi dari
xk ke s, fk(xk,s) menyatakan total bobot lintasan
dari xk ke s, fk(s) adalah nilai minimal dari fk(xk,s),
dan n adalah jumlah tahap pencarian yang
dilakukan.
Implementasi algoritma program dinamis
menggunakan tabel-tabel pembandingan pada
setiap tahap pencarian. Kompleksitas yang
dimiliki algoritma program dinamis dalam
menyelesaikan masalah optimasi pemotongan
adalah O(k) dengan k adalah jumlah level yang
dijalankan oleh algoritma untuk menyelesaikan
sebuah permasalahan pemotongan.
5. ANALISIS DAN PEMBAHASAN
Jika diasumsikan perusahaan membutuhkan bar
steel untuk proyek konstruksi dengan panjang 5
meter sebanyak 3 buah, panjang 7 meter sebanyak
2 buah dan 8 meter sebanyak 2 buah sedangkan
panjang bar steel yang tersedia di pasar adalah
berukuran 10 meter dan 12 meter, maka Tabel 1
merupakan hasil performansi 3 algoritma optimasi
pemotongan bar steel.
Tabel 1: Perbandingan 3 algoritma optimasi
Algoritma
Kompleksitas
Sisa bar
(T (n, k))
steel
minimal
yang
tidak
terpakai
Brute force
7 meter
Greedy
Program
dinamis
9 meter
7 meter
Dengan berbagai data masukan yang telah
dilakukan pada saat pengujian perangkat lunak
dapat dilihat bahwa penyelesaian menggunakan
metode brute force selalu menghasilkan sususan
pola pemotongan yang menghasilkan sisa paling
4
sedikit. Hal itu terjadi karena algoritma brute
force membandingkan seluruh kemungkinan
solusi. Namun, ada konsekuensi dari hal metode
tersebut, yaitu waktu proses pencarian solusi yang
sangat lama. Hal ini dapat dilihat dari catatan
waktu proses yang dihasilkan brute force
meningkat tajam seiring bertambahnya data
masukan. Buruknya catatan waktu yang
dihasilkan algoritma brute force dalam
menyelesaikan masalah, membuat pencarian
algoritma lain yang lebih efisien menjadi penting.
Pada beberapa kasus algoritma greedy lebih
baik dibanding program dinamis, pada kasus lain
terjadi sebaliknya. Namun, catatan penting yang
harus diperhatikan adalah kecepatan performansi
yang dibuat oleh algoritma greedy. Hampir pada
semua kasus, baik yang kompleks ataupun
sederhana, waktu yang diperlukan oleh greedy
untuk menyelesaikan masalah tidak lebih dari 1
milidetik. Hal ini menjadi poin tersendiri bagi
algoritma greedy. Pada kasus dimana program
dinamis lebih baik dibanding greedy, data
masukan lebih masuk akal dan mirip dengan
dunia nyata. Data yang digunakan merupakan data
yang biasa digunakan perusahaan konstruksi. Ciriciri data tersebut adalah ukuran panjang yang
diinginkan tidak berurut, tetapi dengan berselisih
lebih dari 1. Untuk persoalan dengan data ukuran
bar steel yang dibutuhkan dimana antar ukuran
hanya berselisih 1 meter, greedy mengungguli
program dinamis dengan selisih yang tidak terlalu
besar.
6. KESIMPULAN DAN SARAN
Penelitian ini menghasilkan kesimpulan
sebagai berikut:
1.
Algoritma
brute
force
selalu
menghasilkan solusi optimal yaitu sisa
pemotongan bar steel yang paling
minimal. Hal ini dapat dilihat dari hasil
pengujian menggunakan beberapa tipe
persoalan, dimana algoritma brute force
selalu menghasilkan solusi optimal.
Namun demikian algoritma brute force
mempunyai sisis kelemahan yaitu sangat
lambat
dalam
menyelesaikan
permasalahan
dengan
data
yang
kompleks.
2.
Algoritma greedy adalah algoritma
paling efisien dalam menyelesaikan
persoalan pemotongan bar steel jika
dibandingkan dengan algoritma brute
force dan program dinamis, namun solusi
yang dihasilkan tidak global optimal.
3.
Algoritma program dinamis merupakan
algoritma
yang
terbaik
untuk
menyelesaikan
tipe
persoalan
pemotongan bar steel di dunia nyata
karena
mampu
menyelesaikan
permasalahan
dengan
cepat
dan
solusinya mendekati optimal meskipun
menggunakan
data
yang
sangat
kompleks.
7. DAFTAR PUSTAKA
Brady, G. S., Clauser, H. R., & Vaccari, J.
A. (2002). Materials Handbook
(15 edition). McGraw-Hill.
Dimayati, T. T., & Dimyati, A. (1992).
Operation Research: ModelModel Pengambilan Keputusan.
Bandung: Sinar Baru.
Horowitz, E., & Sartaj, S. (1978).
Fundamental of Computer
Algorithms. Pitman Publishing
Limited.
Munir, R. (2006). Strategi Algoritmik,
Program Studi Teknik Informatika,
2006. Bandung: STEI, Institut
Teknologi Bandung.
Neapolitan, & Richrad, R. (1996).
Foundations of Algorithms. D.C.
Heath and Company.
5
Fly UP