BAB 2 KAJIAN LITERATUR TENTANG BIN PACKING
Pada bab ini akan dibahas kajian literatur tentang bin packing, karena algoritma yang akan digunakan untuk persoalan zona terlarang nantinya merupakan adaptasi dari algoritma online bin packing. Dalam persoalan bin packing, misalkan N = { 1, 2,. . ., n} himpunan item dan L = {s1, s2,. . ., sn } himpunan ukuran item sj , dimana 0 < sj ≤ 1, ∀j ∈ N. Tujuannya adalah untuk meminimalkan jumlah bin yang digunakan untuk packing item di N ke sebuah bin sehingga total ukuran item dalam bin tidak melebihi kapasitas bin. Asumsikan bin mempunyai kapasitas sama dengan satu. Persoalan bin packing adalah persoalan NP-Complete (Garey dan Johnson, 1979). Berikut ini ditinjau beberapa heuristik untuk persoalan bin packing atau Bin Packing Problem (BPP). Algoritma online diterapkan setelah item tiba dan item yang tidak dapat dikemas ulang. Yao (1980) menunjukkan bahwa tidak ada algoritma online memiliki rasio asimtotik worst case lebih baik dari 23 . Yao juga mengusulkan algoritma online yang disebut First Fit Disempurnakan yang memiliki O(nlogn) waktu dengan rasio asimtotik worst case tidak lebih besar dari 5 . 3
Liang (1980) menyajikan batas bawah untuk online packing sebesar 1,53635.
Algoritma online untuk bin packing yang ada adalah Next Fit (NF), Harmonic Fit (HF), First Fit (FF), dan Best Fit (BF). Metode semi-online merileksasikan kendala bahwa item tidak dapat dikemas ulang. Hal ini memungkinkan item dikemas untuk bergerak setelah pengemasan. Jumlah gerakan tergantung pada desain dari algoritma. Algoritma semi-online dapat menghasilkan algoritma yang lebih baik daripada algoritma online. Dua algoritma semi-online dibahas sebagai berikut:
5 Universitas Sumatera Utara
6 1. Harmonic Fit (HF): Gambosi et al. (1990) memodifikasi algoritma Harmonic dari online untuk semi-online dengan memungkinkan item yang dikemas untuk dikemas ulang tidak lebih dari sekali. Gambosi mengusulkan dua jenis HF sebagai berikut: i) empat partisi HF di mana dibuktikan bahwa rasio worst case asimtotik yang sama dengan
3 2
dan memerlukan operasi
O(n), dan ii) enam-partisi HF di mana dibuktikan bahwa rasio worst case asimtotik yang sama dengan
5 4
dan memerlukan operasi O(n logn).
2. Algoritma MMP: Ivkovic dan Lloyd (1998) mengusulkan MMP dan membuktikan bahwa rasio asimtotik worst case sama dengan 54 . Kompleksitas MMP adalah O(logn) dengan penyisipan atau penghapusan item. MMP lebih kompleks daripada algoritma dari Gambosi et.al. (1990).
Algoritma Offline, memiliki asumsi yang berbeda dari pada algoritma online, offline diterapkan setelah item terakhir tiba dan memungkinkan item yang akan diurutkan sebelum pengemasan(packing). Hal ini menghasilkan kinerja worst case lebih baik dibandingkan dengan algoritma online atau semi-online seperti yang dibahas oleh Coffman et al. (1997). Algoritma offline yang ada saat ini Next Fit Decreasing (NFD), First Fit Decreasing (FFD) dan Best Fit Decreasing (BFD). Tabel 2.1 merangkum heuristik dan rasio worst case asymptoticnya untuk masalah bin packing. Selanjutnya ditinjau algoritma First Fit Decreasing. Pertama, Johnson et al. (1974) menunjukkan bahwa rasio kinerja worst case asimtotik untuk First Fit (FF) dan Best Fit (BF) tidak lebih dari
1 , 10
dan tidak lebih dari
11 9
baik untuk First Fit
Decreasing (FFD) atau Best Fit Decreasing (BFD). Johnson membuktikan bahwa FFD(L) ≤
11 9
OPT(L) + 4, ∀ L, dimana L adalah daftar item di BPP, OPT(L)
adalah jumlah minimum yang diperlukan bin untuk daftar L, dan FFD(L) adalah jumlah bin yang digunakan oleh heuristik FFD. Untuk menunjukkan kinerja worst case heuristik ini digunakan fungsi pembobotan. Fungsi bobot tergantung pada ukuran item dan lokasi pengepakan. Friesen dan Langston (1991) menggunakan teknik baru yang disebut fungsi bobot rata-rata untuk membuktikan kinerja worst case dari algoritma FFD dan
Universitas Sumatera Utara
7 B2F (Best two Fit) yang masing-masing sama dengan
11 9
dan
5 . 4
Friesen dan
Langston mengusulkan algoritma kompleks, yang menggabungkan algoritma FFD dan B2F keduanya di daerah dimana algoritma tersebut lebih unggul. Kemudian, dibuktikan dengan fungsi pembobotan bahwa kinerja worst case adalah tidak lebih dari
6 5
dan memperpendek panjang bukti dengan mengurangi ukuran dari item
terakhir untuk interval ( 16 , 1). Yue (1991) mengusulkan bukti sederhana dan memberikan batas dengan FFD(L) ≤
11 9
OPT(L) + 1, ∀ L. Buktinya didasarkan pada fungsi pembobotan
dan contoh konter minimal. Yue menunjukkan bahwa contoh konter tidak ada untuk teoremanya. Selain itu, yue juga mengurangi jumlah interval ukuran item terakhir dengan tiga. Penelitian yang disebutkan di atas terfokus pada unit-kapasitas masalah bin packing. Di sisi lain, bin packing variabel-size umumnya lebih banyak. Rinciannya dibahas dalam Chu dan La (2001) dan Seiden et al. (2003). Tabel 2.1 Ringkasan heuristik untuk bin packing problem Tipe Online
Algoritma Next Fit Next k Fit Best k Fit First Fit Best Fit Harmonic Fit Harmonic Fit Harmonic Fit Bounded best k Fit Refined First Fit Any Online Algorithm Any Online Algorithm Any Online Algorithm Semi-Online Harmonic Fit with 4 Partition Harmonic Fit with 6 Partition MMP Offline Next Fit Decreasing First Fit Decreasing Best Fit Decreasing Refined First Fit Decreasing Best Two Fit First Fit Decresing-Best Two Fit
∞ rA 2 17/10 17/10 17/10 17/10 1.6910 1.58887... 1.58889... 17/10 5/3 ≥ 3/2 ≥ 1.536... ≥ 1.54... 3/2 5/4 5/4 1.691... 11/9 11/9 < 11/9 5/4 6/5
Universitas Sumatera Utara
8 Beberapa peneliti tertarik dalam studi empiris seperti dibahas dalam Falkenauer (1996) dan Gent (1998), yang menunjukkan hasil empiris memecahkan BPP oleh algoritma genetika dan metode pencarian lengkap. Selain itu, BPP Dua Dimensi dibahas dalam Berkey dan Wang (1987), sedangkan Martello et al. (2000) dan Lim dan Ying (2001) mempelajari BPP Tiga-Dimensi. Aplikasi dari BPP dapat ditemukan dalam berbagai masalah sebagai berikut: i) Masalah Penjadwalan seperti yang dibahas dalam Coffman et al. (1997); ii) Vehicle routing dan masalah penjadwalan seperti dibahas dalam Federgruen dan Ryzin (1997); iii) Masalah vehicle routing seperti dibahas dalam Anily dan Bramel (1999), dan iv) Masalah inventory-routing sebagaimana dibahas dalam Chan et al. (1998a). Anily et al. (1994) dan Coffman dan Leuker (1991) menyatakan bahwa BPP adalah setara dengan Vehicle Routing Problem (VRP) sebagai berikut: Misalkan L = (s1 , s2 , . . ., sn ) menjadi daftar n bilangan real di mana 0 < si ≤ 1 adalah ukuran item i. Item dialokasikan di satu unit kapasitas bin sehingga dapat meminimalkan total biaya semua bin. Biaya bin adalah fungsi dari jumlah item yang dialokasikan dengan monoton increasing dan sifat konkavitas. Dalam VRP, jumlah kendaraan yang digunakan adalah setara dengan jumlah bin yang digunakan. Bramel dan Simchi-Levi (2001) menunjukkan analisis worst-case dan averagecase heuristik yang meminimalkan jumlah bin untuk BPP. Bramel et al. (1992) menunjukkan bahwa VRP berkapasitas adalah kasus khusus dari BPP dengan kapasitas kendaraan sama dengan satu dan permintaan untuk setiap pelanggan tidak lebih dari satu. Permintaan setiap pelanggan harus diisi oleh satu kendaraan dan tidak dapat terpecah. Hal ini juga dikenal sebagai VRP berkapasitas dengan Permintaan tidak dapat dibagi. Karena permintaan tidak dapat dibagi, maka dapat diperkenalkan BPP untuk memecahkan masalah ini. Biaya rute yang dihasilkan tergantung pada panjang tur dan jumlah pelanggan di setiap tur. Masalah ini lebih realistis dibandingkan dengan VRP dengan Permintaan yang sama, yang dijelaskan oleh Anily dan Bramel (1999) dan itu adalah masalah penentuan berapa banyak item yang dikirim ke kapasitas tetap kendaraan dari sebuah
Universitas Sumatera Utara
9 gudang yang ditetapkan pelanggan. Permintaan diasumsikan identik dan sama untuk setiap pelanggan. Oleh karena itu, permintaan dapat dibagi berdasarkan kendaraan. Bramel et al. (1992) menemukan bahwa heuristik BPP seperti Next-Fit, First-Fit, Best-Fit, First-Fit Decreasing, Best-Fit Decreasing, Next-Fit Increasing dan Next-Fit Decreasing memiliki rasio kinerja worst-case kurang dari dua. Analisis average-case VRP dilakukan dengan memecahkan masalah bin packing sehingga kapasitas kendaraan sama dengan satu dan permintaan untuk setiap pelanggan kurang dari satu. Ada sebuah solusi dari VRP berkapasitas sesuai dengan BPP untuk setiap rute. Bienstock et al. (1993) menunjukkan bahwa algoritma untuk VRP dengan permintaan unsplit mirip dengan Next Fit untuk BPP yang bukan asimtotik optimal. Rhee (1987) dan Coffman dan Leuker (1991), membahas kinerja probabilistik bin packing heuristik. Loulou (1984) mempelajari perilaku probabilistik dari bin packing optimal. Bramel dan Simchi-Levi (2001) menunjukkan bahwa di BPP, RFFD tidak lebih dari
3 2
, sementara Johnson et al. (1974) menunjukkan bahwa R∞ FFD =
11 . 9
Chan et al. (1998b) menunjukkan bahwa solusi optimal untuk BPP adalah tidak lebih dari
4 3
nilai solusi optimal yang diperoleh dari pemecahan program linier
relaksasi perumusan set-partisi. Beberapa peneliti telah mengimplementasikan model bin packing dan mengembangkannya seperti Parra dan Burtseva (2009), yang mengimplementasikan model bin packing untuk material election dalam membaca pergantian perencanaan produksi, dan mengusulkankan heuristik algoritma offline untuk menemukan jumlah, jenis dan urutan packing kontainer, set fragmen digabung dengan kontainer dan bin, dimana kapasitas bin tidak mempengaruhi algoritma. Sedangkan Liu dan Baskiyar (2008) menggunakan bin packing untuk penjadwalan tugas independen dengan prioritas yang berbeda dan kendala deadline dalam komputasi grid. Liu dan Baskiyar mengusulkan heuristik algoritma Residual Capacity Maximization Scheduling (RCMS) yang mengintegrasikan ide-
Universitas Sumatera Utara
10 ide algoritma bin packing klasik (Best Fit) dan pendekatan model mixed integer quadratic programming. Algoritma RCMS dirancang untuk jadwal tugas berat sambil memaksimalkan jumlah tugas ringan yang dapat memenuhi deadline. Sementara Regin dan Rezgui (2011) mengembangkan model bin packing dengan menyajikan model Constraint Programing (CP) dan mengenalkan kendala pertubing model tertentu dan beberapa aturan : 1). Membatasi penugasan beberapa item untuk beberapa bin. 2). Beberapa item harus cocok dengan bin yang sama dari beberapa bin yang lain. 3). Beberapa item tidak dapat masuk kedalam bin yang sama dari bin yang lain. Selanjutnya juga ditinjau literatur terkait persoalan online bin packing dan algoritmanya. Seiden (2002) telah mengembangkan metode uniform analisis algoritma online bin packing berdasarkan harmonic. Seiden mengembangkan algoritma baru pada sebuah kasus dari super harmonic yaitu algoritma harmonic++ dan memiliki asimptotik performa rasio paling besar 1.58889, yang dianggap memiliki kinerja terbaik dari setiap algoritma online bin packing hingga saat ini. Penelitian lainya berkaitan online bin packing dilakukan oleh Bein et al. (2012) yang mempelajari persoalan mengalokasikan memori server dipusat data berdasarkan permintaan online untuk penyimpanan. Bein mengusulkan sebuah algoritma k-Binary yang menggunakan bin lebih sedikit dibandingkan algoritma yang diusulkan oleh Epstein (Small Modified Harmonic dan Tiny Modified Harmonic). Pada saat yang sama k-Binary bekerja lebih baik daripada kedua algooritma yang diusulkan sebelumnya.
Universitas Sumatera Utara
