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
