BAB 2 LANDASAN TEORI
2.1
Permasalahan NP-Hard dan NP-Complete Salah satu ukuran biaya dalam pengeksekusian sebuah algoritma adalah lamanya
waktu yang diperlukan. Pengukuran waktu yang diperlukan dalam mengeksekusi suatu algoritma dinamakan kompleksitas waktu (time complexity) algoritma tersebut. Namun juga masih ada ukuran–ukuran lainnya, misalnya besarnya memori yang diperlukan untuk mengeksekusi algoritma tersebut (Liu, C.L, 1995, p272). Besarnya waktu yang dibutuhkan algoritma untuk menyelesaikan sebuah permasalahan sebanding dengan jumlah inputan yang diberikan untuk permasalahan tersebut. Semakin besar data maka akan semakin besar waktu yang diperlukan. (Weiss, Mark Allen, 1996, p149). Waktu yang dibutuhkan algoritma terbaik untuk menghasilkan solusi dari banyak problem (permasalahan) dapat dibagi menjadi dua kelompok. Kelompok pertama terdiri dari problem di mana waktu yang dibutuhkan untuk menghasilkan solusinya terbatas pada waktu polynomial dalam tingkat kecil disebut juga Polynomial Problem (P), seperti permasalahan evaluasi polynomial dengan O(n), pengurutan (sorting) dengan O(n log n) dan string editing dengan O(mn). Kelompok kedua terdiri dari permasalahan dengan algoritma Non Polynomial (NP), seperti permasalahan traveling sales person dengan O(n22n) dan permasalahan Knapsack dengan O(2n/2). Dalam pencarian untuk mengembangkan algoritma yang efisien, tidak satupun yang dapat mengembangkan algoritma dengan waktu polynomial untuk permasalahan kelompok kedua. Hal ini sangat penting karena algoritma yang waktu pencarian solusinya lebih besar dari polynomial (biasanya waktu pencarian adalah eksponensial) membutuhkan waktu yang cukup lama
5 untuk menjalankan problem skala menengah. (Horowitz, Sahni dan Rajasekaran, 1998, pp 495-553). Algoritma Non Polynomial (NP) dibagi menjadi dua kelas yaitu NP-hard dan NP-complete. Suatu problem yang termasuk kedalam NP-complete memiliki sifat dapat dipecahkan dalam waktu polynomial jika dan hanya jika seluruh problem NP-complete juga dapat dipecahkan dalam waktu polynomial. Jika sebuah problem NP-hard dapat dipecahkan dalam waktu polynomial maka seluruh problem NP-complete dapat dipecahkan dalam waktu polynomial. Seluruh problem NP-complete merupakan problem NP-hard, tetapi sebagian problem NP-hard belum tentu menjadi problem NP-complete (Horowitz, Sahni dan Rajasekaran, 1998, pp 495-553). Hubungan antara P, NP, NPcompelete dan NP-hard dapat dilihat dengan jelas dengan gambar berikut.
Gambar 2.1 Relasi antara P, NP, NP-complete dan NP-hard
6 2.2
Definisi Heuristic Definisi Heuristic yang didapat dari berbagai sumber diterangkan pada
penjelasan berikut ini: 1. Sebuah algoritma heuristic adalah suatu aturan untuk mengetahui bagaimana memecahkan permasalahan tertentu, tidak memberikan instruksi yang spesifik tetapi panduan umum untuk bermacam pendekatan yang mungkin dapat bekerja. (http://thesaurus.maths.org) 2. Istilah heuristic digunakan untuk algoritma di mana mencari solusi melalui semua kemungkinan yang ada, tetapi dalam pencariannya tidak bisa dijamin ditemukan solusi yang terbaik, oleh karena itu heuristic dapat dianggap algoritma perkiraan. Algoritma ini biasanya mencari solusi yang dekat dengan solusi terbaik dan proses pencariannya cepat dan mudah. Terkadang algortima ini dapat menjadi akurat dan menemukan solusi terbaik, tetapi algoritma ini tetap disebut heuristic hingga solusi terbaik itu terbukti untuk menjadi yang terbaik. (http://students.ceid.upatras.gr/)
2.3
0-1 Knapsack Problem Knapsack
problem
adalah
suatu
masalah
dalam
persoalan
optimasi
kombinatorial. Knapsack problem memperoleh namanya dari suatu masalah seorang pendaki gunung yang hanya dapat membawa barang pada tasnya maksimal pada berat tertentu, misalkan 15 kg dan ia harus membawa beberapa macam barang yang memiliki berat dan harga tertentu untuk ia jual, sehingga ia mendapatkan hasil keuntungan yang maksimal.
7 Knapsack problem (Martello, 1990, p13) ini bila diformulasikan secara matematis dengan banyaknya jumlah barang dari 1 sampai n dan sebuah vektor variabel biner xj (j = 1,...,n) sehingga berarti:
xj =
{
1
jika objek j dipilih
0
jika sebaliknya
Kemudian, jika pj ukuran keuntungan yang diberikan barang j, wj adalah berat dari barang tersebut dan c adalah kapasitas maksimum yang dapat ditampung maka: n
∑
j =1
w jx
j
≤ c,
dan persamaan yang menghasilkan keuntungan maksimum adalah: n
∑
j =1
p jx j.
xj = 0 atau 1. Jika dimisalkan ada suatu persoalan dengan n = 8, dimana: (pj)
= (15, 100, 90, 60, 40, 15, 10, 1),
(wj)
= ( 2, 20, 20, 30, 40, 30, 60, 10),
c
= 102
Maka hasil optimal yang dihasilkan adalah x = (1, 1, 1, 1, 0, 1, 0, 0), dengan nilai keuntungan maksimum z = 280.
2.4
Bin Packing Dalam problem ini diberikan obyek sebanyak n (element) yang harus
ditempatkan pada bin (tempat penyimpanan) dengan kapasitas L. Obyek i membutuhkan
8 unit li dari kapasitas bin. Tujuan bin packing adalah untuk menentukan jumlah bin yang dibutuhkan untuk menampung seluruh obyek n. tidak boleh ada obyek yang ditempatkan sebagian di dalam suatu bin dan sebagian lain di dalam bin lainnya. Three
dimensional
Bin
Packing
Problem
juga
digolongkan
kedalam
permasalahan NP-Hard. Digolongkan kedalam NP-Hard karena secara teori dan prakteknya sangat sulit dipecahkan. Apabila contoh permasalahan hanya sedikit maka dapat ditemukan solusinya secara mudah, tetapi dalam dunia nyata permasalahan sangatlah banyak dan kompleks, oleh karena itu dilakukan pendekatan heuristic. Pendekatan heuristic yang paling umum dan mendekati pemecahan problem ialah wall building algorithm.
2.4.1
Wall Building Heuristic Wall building heuristic mengisi kontainer dengan sejumlah layer yang sejajar
dengan kedalaman kontainer. Algoritma ini hanya mempertimbangkan layer dengan kedalaman (d) tertentu yang sesuai dengan dimensi kotak, hal ini disebut normalized layer depth (Pisinger, 2002, p4). Untuk lebih jelasnya dapat dilihat pada gambar 2.2 berikut.
9
Gambar 2.2 wall building algorithm
Tetapi kedalaman sebuah layer harus diseleksi secara teliti, hal ini dilakukan agar tercapainya solusi yang baik. Oleh karena itu ketika membuat sebuah layer, algoritma ini menerapkan aturan pengurutan untuk memilih nilai d. Diantara kotak yang tersisa, akan dipilih kotak yang memiliki dimensi terbesar. Alasan utama kenapa hal ini dilakukan karena kotak tersebut akan sulit untuk dimuat apabila dilakukan urutan terakhir didalam prosedur pengepakan. Setelah kedalaman layer ditentukan, akan dilakukan pengepakan dengan metode greedy per baris secara horizontal (horizontal strip) disetiap potongan layer. Setiap potongan akan dimasukkan kotak yang tersisa secara berurutan berdasarkan urutan panjang kotak yang terbesar terlebih dahulu. Seperti dijelaskan pada gambar 2.3 berikut
10
Gambar 2.3 setiap layer diisi oleh beberapa baris horizontal box
2.4.2
Tree Search Algoritma ini adalah pengembangan dari algoritma wall building dengan
menggunakan algoritma tree search (Pisinger, 2002, p5-9) untuk menentukan layer depth dan strip width yang akan menghasilkan pengisian yang paling optimal. Idealnya untuk mendapatkan hasil yang terbaik semua normalized layer depth dan strip perlu dipertimbangkan, tetapi hal ini akan memerlukan kemampuan komputasi yang amat besar. Oleh karena itu untuk mengurangi kompleksitas komputasi diterapkan pendekatan m-cut dimana hanya sub-node tertentu saja yang dapat dipertimbangkan dari setiap branching node. Kemudian pada setiap branching node dipertimbangkan M1 layer depth berbeda yang dipilih berdasarkan suatu ranking rule. Lalu setiap layer tersebut diisi dengan beberapa strip, dimana setiap strip tersebut dapat disusun secara vertikal ataupun horizontal. Hanya M2 strips width tertentu yang dipertimbangkan. Ketika layer depth dan strip width telah ditentukan, strip tersebut segera diisi secara optimal dengan menggunakan Knapsack Problem. Dari M1 layer depth yang telah diisi itu dipilihlah sebuah layer yang memiliki hasil volume yang paling optimal. Setelah itu dilanjutkan dengan memproses layer yang berikutnya. Nilai dari M1 adalah 4 dan M2 adalah 8 nilai
11 yang memiliki kualitas solusi terbaik dan waktu komputasi yang paling efisien, kedua nilai itu diperoleh dari berbagai eksperimen yang telah dilakukan oleh pencipta algoritma ini. Pada setiap branching node terdapat tiga buah fungsi untuk menentukan ranking depth dan width yang terbaik pada suatu layer atau strip, yaitu: •
Fungsi frekuensi f1 mengembalikan nilai hasil perbandingan suatu dimensi k dengan dimensi-dimensi lainnya dengan membandingkan semua dimensi wi, hi, di pada kotak-kotak yang lain.
untuk k = α,..., β •
Fungsi frekuensi f2 mengembalikan nilai hasil perbandingan suatu dimensi k dengan dimensi yang terbesar pada setiap kotak lainnya.
untuk k = α,..., β •
Fungsi frekuensi f3 mengembalikan nilai hasil perbandingan suatu dimensi k dengan dimensi yang terkecil pada setiap kotak lainnya.
untuk k = α,..., β
wi, hi, di = ukuran lebar, tinggi dan panjang suatu kotak k = ukuran salah satu sisi kotak α = ukuran sisi paling kecil pada seluruh kotak β = ukuran sisi paling besar pada seluruh kotak
12 Kemudian berdasarkan ketiga fungsi frekuensi tersebut dapat ditentukan sejumlah aturan prioritas. Tujuan dari seluruh aturan ini adalah untuk memilih kotak yang memiliki ukuran/dimensi yang terbesar lebih dahulu atau memilih kotak yang memiliki frekuensi paling banyak. Setelah itu strip tersebut dapat diisi baik secara vertikal ataupun horizontal Pengisian strip yang berukuran width w’ dan depth d’ tersebut dapat dianggap sebagai Knapsack Problem. Pertama-tama setiap kotak j dapat diputar ke salah satu arah dari enam kemungkinan arah putaran dimana wj ≤ w’, dj ≤ d’ dan h’ telah diminimalkan. Jika masih tidak memungkinkan untuk memasukkan kotak j pada w’ × d’ maka masukkan kotak tersebut pada daftar kotak yang tidak dapat dimasukkan, D. Atau dengan menentukan aj = hj= weight cj = vj = wjhjdj = profit Untuk setiap kotak yang ada dimana kotak j ∈ N\D. Sehingga strip packing problem tersebut menjadi maximize
∑c
j∈ N \ D
subject to
∑
j
xj
a jx j ≤ b
j∈ N \ D
x j ∈ {0 ,1}, j ∈ N \ D
dimana N\D adalah kumpulan kotak yang dapat dimasukkan dan b adalah strip height. Lalu hasil yang diperoleh dapat lebih dioptimalkan lagi dengan cara memasangkan
kotak-kotak
tersebut
dua
dua
ketika
memungkinkan.
Karena
13 kekompleksitasan dari algoritma ini O(n2) cara ini hanya dapat dilakukan sekali untuk setiap layer yang memiliki depth d’. Ketika sebuah kotak j telah diputar sedemikian rupa sehingga depth dj adalah kemungkinan yang paling memuaskan, dj ≤ d’. Suatu cara untuk mengetahui seberapa baik kotak tersebut dapat mengisi depth tersebut adalah α(j) = vj/(wjhjd’) = dj/d’ dengan tujuan dapat mengoptimalkan pengisian dengan memasangkan kotak j dengan kotak lain misalkan kotak i. Sehingga untuk setiap kotak i ≠ j semua kemungkinan rotasi dari i dan j juga dipertimbangkan dimana di + dj ≤ d’, setiap kali menghitung rasio β(i,j) = (vi + vj)/(d’ max{wi,wj} max {hi,hj}) Jika β(i,j) ≤ α(j) untuk semua kotak i dan semua rotasi, maka kotak j tetap dibiarkan sendiri tanpa dipasangkan dengan kotak lain. Sebaliknya jika β(i,j) > α(j) maka sebuah kotak baru, kotak k telah terbentuk dengan dimensi wk = max{wi,wj};
hk = max{hi,hj};
dk = d’
Sedangkan kedua kotak asalnya dikeluarkan dari daftar kotak untuk menghindari kotakkotak tersebut digunakan untuk kedua kalinya.
2.5
Pemodelan Piranti Lunak Pemodelan dalam suatu rekayasa piranti lunak merupakan suatu hal yang
dilakukan ditahap awal. Pemodelan ini akan mempengaruhi pekerjaan-pekerjaan dalam rekayasa piranti lunak ini selanjutnya. Menurut Pressman (2005): Perangkat lunak adalah (1) perintah (program komputer) yang bila dieksekusi akan memberikan fungsi dan unjuk kerja seperti yang diinginkan. (2) struktur data yang
14 memungkinkan program memanipulasi informasi secara proporsional, dan (3) dokumen yang menggambarkan operasi dan kegunaan program. Salah satu cara perancangan perangkat lunak adalah dengan menggunakan model air terjun (waterfall model). Menurut Sommerville (1995), tahap-tahap utama dalam model air terjun dapat digambarkan dalam aktivitas dasar pengembangan seperti berikut ini: •
Analisis dan penentuan kebutuhan Tugas, kendala dan tujuan sistem ditentukan melalui konsultasi dengan pengguna sistem, kemudian ditentukan cara yang dapat dipahami baik oleh pengguna maupun staf pengembang.
•
Desain sistem dan perangkat lunak Proses desain sistem terbagi dalam kebutuhan perangkat keras dan perangkat lunak. Hal ini menentukan arsitektur perangkat lunak secara keseluruhan. Desain perangkat lunak mewakili fungsi sistem perangkat lunak dalam suatu bentuk yang dapat ditranformasikan ke dalam satu atau lebih program yang dapat dieksekusi.
•
Implementasi dan pengujian unit Dalam tahap ini, desain perangkat lunak direalisasikan dalam suatu himpunan program atau unit-unit program pengujian, mencakup kegiatan verifikasi terhadap setiap unit sehingga memenuhi syarat spesifikasinya.
•
Integrasi dan pengujian sistem Unit program secara individual diintegrasikan dan diuji sebagai satu sistem yang lengkap untuk memastikan bahwa kebutuhan perangkat lunak telah terpenuhi.
15 Setelah pengujian, sistem perangkat lunak disampaikan kepada pengguna. •
Pengoperasian dan pemeliharaan Secara normal, walaupun tidak perlu, tahap ini merupakan fase siklus hidup yang terpanjang. Sistem telah terpasang dan sedang dalam penggunaan. Pemeliharaan mencakup perbaikan kesalahan yang tidak ditemukan dalam tahap-tahap ini sebelumnya, meningkatkan implementasi unit-unit sistem dan mempertinggi pelayanan sistem sebagai kebutuhan baru yang ditemukan.
Analisis dan pemenuhan kebutuhan Desain sistem dan perangkat lunak Implementasi dan pengujian unit Integrasi dan pengujian sistem Pengoperasian dan pemeliharaan
Gambar 2.4
Perancangan Perangkat Lunak Model Waterfall Sumber : Sommerville (1995).
2.6
Alat Bantu Perancangan
2.6.1
Diagram Alir (Flowchart) Diagram alir adalah sebuah skema yang merepresentasikan sebuah algoritma
atau sebuah proses (http://en.wikipedia.org/wiki/Flowchart).
16 Adapun simbol-simbol dari diagram alir yang digunakan dalam ilmu komputer seperti pada gambar 2.4.
Simbol untuk mulai dan selesai Simbol untuk menentukan aliran data yang dilakukan Simbol untuk langkah proses
Simbol untuk input ataupun output
Simbol untuk merepresentasikan sebuah kondisi atau keputusan. Biasanya berisi pertanyaan ya/tidak atau test benar/salah Gambar 2.5 Simbol-simbol Diagram Alir (http://en.wikipedia.org/wiki/Flowchart)
2.6.2
Pseudocode Pseudocode adalah suatu bahasa pemrograman yang informal dan sangat
fleksibel, yang tidak dimaksudkan untuk dieksekusi pada mesin, tetapi hanya digunakan untuk mengatur pemikiran program sebelum melakukan pengkodean (Page-Jones, 1980, p11).
17 Pseudocode dapat merupakan alternatif lain dalam perancangan perangkat lunak disamping alat-alat bantu berupa diagram. Tidak ada standarisasi dalam hal penulisan pseudocode. Pemrogram dapat menulisnya dalam bahasa apa saja yang mereka sukai dengan dipadukan dengan bahasa pemrograman tertentu. Pemrogram juga bebas menggunakan teknik dan aturannya sendiri. Robertson (1993, p6-7) menulis pseudocode-nya dengan menggunakan perjanjian sebagai berikut: 1. Pernyataan ditulis dalam bahasa Inggris sederhana. 2. Setiap perintah ditulis pada baris tersendiri. 3. Kata kunci atau identasi (penulisan yang menjorok ke dalam) digunakan untuk menandai struktur kontrol khusus. 4. Setiap himpunan perintah ditulis dari atas ke bawah dengan hanya satu awal dan satu akhir program. 5. Kumpulan pernyataan-pernyataan dapat dibentuk dalam modul-modul yang diberi nama tertentu.
