BAB 2 LANDASAN TEORI
2.1
Problem, Algoritma dan analisis algoritma
2.1.1
Definisi Problem Problem (permasalahan) adalah suatu tujuan yang dinyatakan dalam konteks
yang jelas tetapi tidak dapat dengan serta merta dicapai. Suatu permasalahan dikatakan telah selesai apabila tujuan telah dicapai atau sudah tidak ada lagi (Psquet, Sebastian, 2001, p1).
2.1.2
Definisi Algoritma Algoritma berasal dari kata Algoris dan Ritmis, yang pertama kali diungkapkan
oleh Abu Ja’far Mohammad Ibn Musa Al Khowarizmi dalam buku Al-jabr wa’almuqabala (Horowittz, Ellis dan Sartaj Sahni, 1978, pl). Ada beberapa definisi yang diberikan mengenai pengertian algoritma (Horowittz, Ellis dan Sartaj Sahni, 1978, pl), antara lain sebagai berikut: 1. Menurut Abu Ja’far Mohammad Ibn Musa Al Khowarizmi Algoritma adalah suatu metode khusus untuk menyelesaikan suatu permasalahan. 2. Menurut Goodman Hedetniemi Algoritma adalah urut-urutan terbatas dari operasi–operasi yang terdefinisi dengan baik, yang masing-masing membutuhkan memori dan waktu yang terbatas untuk menyelesaikan suatu permasalahan.
6
7 3. Dalam ilmu komputer Algoritma adalah suatu metode yang terdiri dari serangkaian langkah–langkah yang terstruktur dan dituliskan secara sistematis yang akan dikerjakan untuk menyelesaikan masalah dengan bantuan komputer.
Masalah
Algoritma
Solusi
Gambar 2.1 Hubungan Masalah, Algoritma dan Solusi
2.1.3
Definisi Analisis Algoritma Algoritma tidak selalu memberikan hasil terbaik yang mungkin diperoleh, maka diharapkan adanya suatu evaluasi mutu hasil dari algoritma tersebut (Liu, C.L, 1995, p271). Sekali sebuah algoritma diberikan kepada sebuah permasalahan dan dijamin akan memberikan hasil yang diharapkan, maka langkah penting selanjutnya adalah menentukan besar biaya yang diperlukan algoritma tersebut untuk memperoleh hasil itu. Proses inilah yang disebut dengan analisis algoritma (Weiss, Mark Allen, 1996, p149) Ukuran biaya eksekusi suatu algoritma yang paling sering digunakan adalah lamanya waktu diperlukan. Namun juga masih ada ukuran–ukuran lainnya, misalnya besarnya memori yang diperlukan untuk mengeksekusi algoritma tersebut (Liu, C.L, 1995, p272). Maksud dilakukannya analisis algoritma adalah untuk (Horowitz, Elis dan Sartaj Sahni, 1978, p1):
8 1. Memenuhi aktivitas intelektual. 2. Meramalkan suatu hal yang akan terjadi atau yang akan didapat dari algoritma tersebut. 3. Mengetahui efektifitas suatu algoritma dibanding dengan algoritma yang lain untuk persoalan yang sama.
2.1.4
Kompleksitas Waktu Algoritma dan Masalah 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 (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. Sebagai contoh, diperlukan waktu yang lebih besar untuk mengurutkan 10.000 buah data dibanding dengan 10 buah data. Akan tetapi, pada keadaan sebenarnya, nilai dari suatu algoritma ditentukan dari banyak faktor, misalnya kecepatan komputer yang dipakai, kualitas compiler dan dalam beberapa kasus, kualitas program itu sendiri (Weiss, Mark Allen, 1996, p149). Dua buah algoritma yang berbeda dapat digunakan memecahkan masalah yang sama dan mungkin saja, mempunyai kompleksitas waktu (time complexity) yang sangat berbeda (Liu, C.L, 1995, p274). Kompleksitas waktu algoritma terbaik untuk memecahkan masalah tersebut dinamakan sebagai kompleksitas waktu suatu masalah (time complexcity of problem) (Liu, C.L, 1995, p277).
9 Berdasarkan pengertian problem (masalah) diatas, tidak semua masalah dapat dipecahkan, dengan kata lain mempunyai algoritma solusi. Ada dua buah klasifikasi permasalahan (Leahy, Billy., 2000, pp21-24), yaitu sebagai berikut: 1. Permasalahan yang dapat dipecahkan (decidable / solvable problem) Permasalahan yang termasuk klasifikasi ini adalah semua jenis permasalahan yang mempunyai algoritma solusi, walaupun kadang kala tidak praktis. Dari segi komputasi, permasalahan dalam klasifikasi ini dapat dibedakan menjadi tiga kategori yaitu: 1.1 Permasalahan Tractable (mudah dari segi komputasi) Suatu masalah dikatakan tractable jika masalah tersebut dapat dipecahkan oleh suatu algoritma yang efisien. Contoh permasalahan trackable antara lain adalah masalah penentuan bilangan terbesar diantara n bilangan, pengurutan n bilangan, penentuan lintasan terpendek antara dua buah vertex didalam sebuah graph dan lain sebagainya. 1.2 Permasalahan Intractable (sukar dari segi komputasi) Suatu masalah dikatakan intractable jika tidak ada algoritma yang efisien untuk memecahkan masalah tersebut. 1.3 Permasalahan NP-Complete (NP singkatan dari Non-Deterministik Polinomial) Suatu masalah dikatakan NP-Complete apabila masalah itu telah berhasil dibuktikan termasuk dalam masalah intractable. Contohnya adalah permasalahan pewarnaan graf.
10 2. Permasalahan yang tidak dapat dipecahkan (undecidable / unsolveable problem) Permasalahan yang termasuk dalam klasifikasi ini adalah semua permasalahan yang tidak mempunyai algoritma solusi, maksudnya adalah tidak dapat dilakukan perhitungan, atau tidak dapat diperoleh jawaban dalam waktu yang terbatas. Contohnya adalah permasalahan unbounded tiling. Ada beberapa definisi yang diberikan pengukuran kompleksitas suatu masalah (Weiss, Mark Allen, 1996, p161), yaitu sebagai berikut:
1. Big-Oh Definisi: T(n) = O(F(n)), jika ada konstanta positif c dan No dimana T(n) < cF(n) ketika N > No 2. Big-Omega Definisi: T(n) = Ω(F(n)), jika ada konstanta positif c dan No dimana T(n) > cF(n) ketika N > No 3. Big-Theta Definisi: T(n) = Θ(F(n)), jika dan hanya jika T(n) = O(F(n)) dan T(n) = Ω(F(n)) 4. Little-Oh Definisi: T(n) = o(F(n)), jika dan hanya jika T(n) = O(F(n)) dan T(n) ≠ Θ(F(n))
11 Dari keempat definisi yang diberikan diatas, definisi pertama yang sering digunakan dalam mengukur kompleksitas suatu permasalahan (Weiss, Mark Allen, 1996, p161)
Tabel 2.1 Fungsi kompleksitas suatu masalah dalam urutan ascending. Fungsi
2.2
Nama
C
Konstanta
Log N
Logaritma
Log2 N
Logaritma Kuadrat
N
Linear
N Log N
N Logaritma N
N2
Kuardatis
N3
Kubik
2N
Eksponensial
Permasalahan NP- Hard dan NP- Complete Waktu yang dibutuhkan algoritma terbaik untuk menghasilkan solusi dari banyak
problem (permasalahan) dapat dibagi menjadi dua kelompok. Kelompok pertama terdiri dari problem dimana 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
12 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 untuk menjalankan problem skala menengah (Horowitz, Sahni dan Sanguthevar Rajasekaran, 1998, pp495-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 dipecahakan dalam waktu polynomial. Seluruh problem NP-complete merupakan problem NP-hard, tetapi sebagian problem NP-hard belum tentu menjadi problem NPcomplete (Horowitz, Sahni dan Sanguthevar Rajasekaran, 1998, pp495-553). Hubungan antara P, NP, NP-compelete dan NP-hard dapat dilihat dengan jelas dengan gambar berikut.
13 NP-complete
NP-hard P
NP gambar 2.2 relasi antara P, NP, NP-complete dan NP-hard
2.3
Bin Packing Dalam problem ini diberikan obyek sebanyak n yang harus ditempatkan pada
bin (tempat penyimpanan) dengan kapasitas L. Obyek i membutuhkan 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 disatu bin dan sebagian lain di bin lainnya. Three
dimensional
Bin
Packing
Problem
juga
digolongkan
kedalam
permasalahan NP-Hard (Verweij, 1996, p1). 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.
14 2.4
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/mmkb/entry.html?action=entryById&id=747) 2. Istilah heuristic digunakan untuk algoritma dimana 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/~papagel/project/kef5_5.htm)
Setiap algoritma memiliki matrik untuk perhitungan untuk Heuristic algoritma mempunyai matrik, dalam perhitungan matrik menggunakan array 2 dimensi seperti berikut: Array A[1..m][1..n], TL[i][j] jumlah dari kotak A[1..i][1..j]
15
A
TL
-3
1
2
-3
-2
0
2
-1
0
-1
-1
1
0
-2
1
-1
-3
0
Perhitungan matrik adalah : For i=2 to n do For j=1 to n do A[i][j] = A[i][j] + A[i-1][j] A
A’
-3
1
2
-3
-1
2
2
-1
0
-1
0
2
0
-2
1
-1
-2
3
for i = 2 to n do for j = 1 to n do A’[j][i] = A’[j][i] + A’[j][i-1]
16 A’
TL
-3
1
2
-3
-2
0
-1
0
2
-1
-1
1
-1
-2
3
-1
-3
0
2.5
Wall Building Heuristic
2.5.1
Vertical layer wall building Vertical 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.3 berikut.
Gambar 2.3 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,
17 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.4 berikut
Gambar 2.4 setiap layer diisi oleh beberapa baris horizontal box
2.5.2
Horizontal layer wall building Metode heuristic lainnya mengisi kontainer mulai dari bawah hingga atas,
sehingga layer sejajar dengan ketinggian kontainer. Saat mengisi kontainer metode ini mencoba untuk mempertahankan susunan yang rata pada bagian depan. Setiap langkah pengepakan akan ditentukan ruang kosong yang akan diisi, semua cargo yang ada dan beserta kemungkinan posisi didalam kontainer (orientation) di analisis, kemudian kotak yang paling sesuai dipilih untuk dimasukkan kedalam kontainer (Erhan Baltacioglu, 2001). Sebelum mulai proses layer packing, algoritma tersebut akan menganalisis kotak yang belum dimasukkan kedalam kontainer untuk memilih ketebalan layer yang tepat sehingga volume yang terbuang bisa dikurangi. Ketinggian layer yang dipilih mudah
18 disesuaikan dan dapat bertambah untuk memenuhi ketinggian kotak yang dipilih. Kemudian proses packing pada layer dapat menghasilkan permukaan yang tidak rata, hal ini dikarenakan ketinggian kotak yang dipilih tidak sama atau karena kotak yang akan dipacking memang heterogen. Jika hal itu terjadi akan dilakukan pendekatan layer in layer. Pendekatan Layer in layer dalam proses packing sublayer pada ruang kosong yang tersisa dari layer sebelumnya. Hal ini merupakan hal penting dari metode heuristic yang diadaptasi dari kebiasaan dan kecerdasan manusia dalam menentukan kotak yang akan di packing (Erhan Baltacioglu, 2001).
Gambar 2.5 Layer in layer packing 2.5.3
Iterasi Didalam horizontal maupun vertical layer wall building memiliki langkah-
langkah persiapan dan pengeksekusian iterasi. Untuk persiapan iterasi dibuat suatu koleksi data layer sebagai array yang memiliki dua komponen yaitu layerdim yang merupakan nilai ketinggian dari suatu layer dan layereval yang menggambarkan kedekatan dari seluruh kotak dengan ketinggian layer jika nilai tersebut dipilih sebagai
19 ketinggian layer saat packing barang. Penghitungan nilai layerdim dan layereval seperti berikut: 1. Ambil suatu kotak dan salah satu dimensinya, periksa dengan nilai layerdim sebelumnya didalam array. Jika tidak sama simpan nilai dimensi tersebut sebagai elemen baru nilai layerdim didalam array. 2. Lalu ambil satu nilai dimensi kotak-kotak berikutnya dan tambahkan nilai absolut dari selisih layerdim dengan dimensi tersebut. Lakukan hal tersebut pada seluruh kotak. 3. Untuk nilai dimensi kotak yang lebih besar dari dimensi kontainer diabaikan. 4. layerdim dengan nilai layereval yang terkecil merupakan nilai ketebalan layer yang paling sesuai, oleh karena itu sorting nilai layereval secara ascending.
2.5.3.1 Eksekusi Iterasi Setelah
persiapan
iterasi
dilakukan
maka
langkah
selanjutnya
ialah
pengeksekusian iterasi tersebut. Setiap iterasi mulai packing dengan nilai layerdim pertama sesuai hasil persiapan sebelumnya. Packing dilakukan sepanjang sumbu.X dan sumbu.Z . Metode heuristic dapat menelusuri topologi yang terakhir, saat kotak dipacking data koordinat ikut berubah, hal ini mempunyai tujuan algoritma hanya menelusuri tepi kontainer yang sedang dipacking, dan mengindari terjadinya overlap layer dan tepi kontainer. Proses packing dimulai dengan mencari nilai Z yang terkecil dalam kordinat dan mencari celah di dalam layer untuk diisi. Proses pencarian nilai Z yang terkecil dapat dilihat lebih jelas pada gambar berikut:
20
Nilai yang ditemukan untuk Z terkecil Gambar 2.6 pencarian nilai Z yang terkecil
Kandidat kotak yang akan diisi dalam celah tersebut diperiksa (analyze box) terlebih dahulu sesuai dengan orientasinya (box orientations) dan dengan ketebalan layer dicari kotak yang dapat mengisi celah tanpa melebihi ketebalan layer sekecil mungkin. Jika tidak ditemukan kotak yang dapat mengisi celah tersebut, maka celah tersebut diabaikan. Dalam memeriksa kotak (analyze box) terdapat beberapa hal yang diutamakan dan sesuai dengan urutan yaitu: 1. Diutamakan kotak dengan dimensi-Y terdekat dengan ketinggian layer (Hy), tetapi tidak melebihi ketinggian maksimum kontainer (Hmy). 2. Kemudian kotak dengan dimensi-X terdekat dengan ruang pada dimensi tersebut, tetapi tidak melebihi panjang maksimum panjang yang tersisa (Hmx) 3. Dan terakhir kotak dengan dimensi-Z terdekat dengan lebar yang tersisa (Hz), tetapi tidak melebihi lebar maksimum yang tersisa (Hmz)
Dalam hal ini algoritma lebih mempertimbangkan dimensi-Y, setelah memiliki ketinggian yang sama maka akan memperhatikan dimensi-X. Setelah memiliki ketinggian dan panjang yang sama maka kemudian melihat dimensi-Z. Untuk lebih
21 jelasnya dapat diihat gambar di bawah yang menerangkan batas maksimum dan pendekatan yang optimal dari masing-masing dimensi pada kontainer dalam packing kotak.
Gambar 2.7 hal yang diperhatikan dalam analisis kotak
Algoritma menghitung selisih antara dimensi celah yang ada dengan dimensi kotak yang ada dan memilih kotak dengan selisih yang terkecil sebagai kotak yang tepat untuk dimasukkan kedalam celah. Untuk kotak yang lebih tinggi dari tebal layer tetapi perbedaan tingginya tidak terlalu besar dapat dipacking kedalam layer tersebut, dengan pertimbangan yang lebih. Oleh karenanya dikembangkan metode layer-in-layer untuk mengakomodir ketinggian yang tidak rata. Ketebalan layer akan bertambah jika dipacking kotak dengan ketinggian melebihi layer. Ketika bertambah maka total penambahan ketebalan layer mulai dari awal hingga akhir akan disimpan, dan setelah packing layer aktif selesai dan nilai pertambahan itu lebih besar dari nol maka dilakukan packing pada ketebalan layer-inlayer tersebut.
22 2.6 Multiple Destinations Dalam proses packing barang ke dalam kontainer, peletakan barang harus disesuaikan dengan tujuan dari barang-barang terserbut. Suatu kontainer dapat membawa barang dengan tujuan yang sama, selain itu kontainer dapat juga membawa barang dengan tujuan yang berbeda. Sehingga susunan barang yang ada didalam kontainer harus disesuaikan dengan urutan tujuan barang tersebut. Untuk barang dengan tujuan yang terdekat akan ditempatkan di bagian depan, dan untuk barang dengan tujuan paling akhir akan ditempatkan pada kontainer paling dalam. Setiap barang yang akan dikirim harus memiliki tujuan, berdasarkan pendapat Bram Verweij (1996, pp6-7) untuk mengatasi permasalahan tersebut dengan
cara
mengelompokkan tujuan dari barang–barang tersebut ke dalam kontainer. Jika kontainer sudah penuh tetapi masih ada barang yang memiliki tujuan yang sama seperti sebelumnya maka buka kontainer baru, masukkan barang-barang ke dalam kontainer tersebut. Dengan adanya pengelompokkan tujuan ada kemungkinan penggunaan ruang kontainer menjadi tidak optimal, karena proses pencarian kotak sewaktu proses packing dibatasi dengan kelompok kotak pada satu tujuan terlebih dahulu dan seterusnya hingga seluruh kelompok kotak habis.
2.7 Industri Shipping Menurut Capt.R.P.Suyono pada industri shipping atau pengangkutan barang dengan kapal laut ada beberapa macam barang yang menunjang pada industri ini. Container (Petikemas) adalah suatu kemasan yang dirancang secara khusus dengan
23 ukuran tertentu, dapat dipakai berulang kali, dipergunakan untuk menyimpan dan sekaligus mengangkut muatan yang ada didalamnya. Ada beberapa jenis cargo: 1. General cargo container adalah petikemas yang dipakai untuk mengangkut muatan umum. 2. Thermal container adalah petikemas yang dilengkapi dengan pengaturan suhu untuk muatan tertentu. 3. Tank container adalah tanki yang ditempatkan dalam kerangka petikemas yang dipergunakan untuk memuat muatan cair 4. Dry bulk container adalah general container yang dipergunakan khusus untuk mengangkut muatan curah 5. Platform container adalah petikemas yang terdiri dari lantai dasar 6. Specials container adalah petikemas yang khusus dibuat untuk muatan tertentu, seperti petikemas untuk ternak ataupun kendaraan Sebagian besar barang–barang yang berukuran besar dan akan dikirim dengan container disertai dengan pallete. Pallete adalah sebuah papan terbuat dari kayu dan digunakan untuk dasar dari barang–barang. Pallete digunakan agar barang–brang tersebut lebih mudah diangkat dengan forklift . Forklift adalah alat untuk mengangkat barang maupun untuk memindahkan Container. Container Freight Station (CFS) merupakan gudang consolidasi / deconsolidasi barang-barang yang ekspor atau impor. Less then Container Load (LCL) bisnis LCL digunakan untuk pengirim/shipper merasa tidak efisien jika mempunyai sedikit cargo untuk dilakukan pengiriman namun harus menyewa satu container sehingga menyebabkan banyak space dari container tersebut yang tidak terpakai.
24 2.8 Normalisasi Basisdata Dalam perancangan basisdata (database) ada beberapa hal yang penting yang harus diperhatikan. Selain untuk kecepatan bertransaksi dan kemudahan dalam perawatan yang paling utama adalah mengurangi data redundancy dan menghemat tempat penyimpanan yang pada akhirya akan menghemat biaya. Untuk merancang database yang baik, dilakukan proses normalisasi (Conolly, 2002, pp 375-396) Dalam membuat suatu database, normalisasi harus digunakan dalam menyusun dan merancang database. Normalisasi adalah proses yang dilakukan untuk meminimalisasi duplikasi data. Untuk menguji apakah skema tersebut sudah memenuhi syarat – syarat pada bentuk normal sehingga dihasilkan stuktur relasi database yang baik. Proses nomalisasi dilakukan dengan cara top-down dengan cara mengevaluasi setiap relasi terhadap criteria pada bentuk normal, meracang ulang relasi tersebut. Ada empat hal umum yang digunakan dalam proses normalisasi tabel data, form normal pertama (1NF), kedua (2NF) dan tiga (3NF) form normal dan Boyce-codd normal form(BCNF). Namun untuk database yang masih sederhana dalam artian database tersebut hanya terdiri dari beberapa table saja, pada umumnya bentuk normal ketiga sudah dianggap cukup.
2.8.1
Bentuk normal pertama Bentuk normal pertama menyatakan setiap domain dari sebuah atribut hanya
boleh mengandung nilai–nilai atomik dan nilai dari setiap atribut daalm tabel harus berupa nilai tunggal dari domain tersbut. Bentuk normal pertama tidak mengizinkan adanya nilai tunngal, satu tabel nilai, atau kombinasi keduanya sebagi nilai atribut dari sebuah tabel. Nilai atribut yang diizinkan oleh bentuk normal pertama adalah nilai
25 atomik. Hal ini bisa dicapai dengan cara menghilangkan repetition group. Pada tahap ini juga dicari primary key, sehingga semua atribut bukan key tergantung pada primary key tersebut.
2.8.2
Bentuk normal kedua Bentuk normal kedua didasarkan pada konsep full functional dependency. Fungsi
x → y disebut full functional dependency jika salah satu atau beberapa atribut A dari x dihapus, maka tidak terjadi dependency lagi. Fungsi x → y disebut partial functional dependency jika salah satu atau beberapa atribut A dari x dihapus, namun masih terdapat dependency. Dengan kata lain untuk relasi dimana primary key terdiri dari beberapa atribut, tidak ada atribut bukan key yang tergantung kepada fungsionalitas primary key. Pada tahap kedua ini functional dependency harus dihilangkan. Cara yang bisa dilakukan untuk memenuhi persyaratan pada bentuk normal kedua adalah dengan merancang ulang dan membuat relasi baru untuk setiap partial key dengan atributnya masing-masing. Namun harus tetap menjaga relasi dengan primary key sebelumnya.
2.8.3
Bentuk normal ketiga Bentuk normal ketiga didasarkan pada konsep transitive dependency. Functional
dependency x → y dalam relasi R disebut transitive dependency jika terdapat satu set atribut Z yang merupakan candidat key atau subset dari setiap key dari R. Selain itu juga terjadi hubungan x → z dan z → y. Pada tahap ketiga ini, transitive dependency harus dihilangkan. Cara yang bisa dilakukan untuk memenuhi persyaratan pada bentuk normal ketiga adalah dengan merancang ulang dan membuat relasi baru yang mencangkup atribut bukan key yang secara fungsional mempengaruhi atribut bukan key lainnya.
26 2.9 Tiga Dimensi Gambar tiga dimensi merupakan gambaran sifat dari gambar dua dimensi (2D) yang lebih kompleks. Gambar tiga dimensi (3D) sangat komplek
karena
adanya
penambahan pada bagian dimmensi dan pada kenyataanya karena sebenarnya tampilan adalah gambar 2D. Solusi sangat tidak seimbang antara objek 3D dan tampilan 2D tetapi jika mempergunakan proyeksi maka dapat lebih jelas dalam tampilan 3D. Pada tampilan 3D sangat dipertajam pada tampilan volume. Dasar penggunaan 2D dan 3D pada grafik komputer adalah transformasi geometri. Translation, scaling, rotation transformasi adalah suatu proses dalam merubah bentuk, posisi ataupun orientasi objek. ( James D. Foley, 1995, p229 ) 2.9.1
Translasi Mengubah ukuran benda 2D maupun 3D dengan rumus [B]=[A][T(dx,dy,dz)], dimana Y
dy
dx X dz
Z
Gambar 2.8 Translasi benda tiga dimensi
27 1 0 0 [T(dx,dy,dz)] =
0 1
0
0 0
0 0 1
0
dx dy dz 1 2.9.2
Rotasi Rotasi perputaran benda menurut sumbu x,y dan z . Y
θ
X Z
Rotasi terhadap sumbu Y
Gambar 2.9 Rotasi benda tiga dimensi Cosθ 0 -Sinθ 0 [Ry,θ] =
0
1
0
0
Rotasi terhadap sumbu Y
Sin θ 0 Cos θ 0
[Rx,θ] =
0
0
0
1
0
0
1
0
0 Cosθ Sinθ 0 0
0
Rotasi terhadap sumbu X
-Sin θ Cos θ 0 0
0
Cosθ -Sinθ
0 0
[Rz,θ] = -Cosθ Sinθ
0 0
0
0
0 0
0
0
0 1
1
Rotasi terhadap sumbu Z
28
2.9.3
Scaling / Penyekalaan Penyekalaan adalah memproyeksikan benda dengan ukuran skala Y
X Z
Gambar 2.10 Scaling benda tiga dimensi
Sx 0 [S(Sx,Sy,Sz)] =
2.9.4
0
0
0 Sy 0 0 0
0
Sz 0
0
0
0
1
Rotasi terhadap suatu sumbu yang sejajar sumbu koordinat Untuk memutar sebuah benda 3D harus melalui beberapa cara. Contoh: putar benda terhadap sumbu X’ yang sejajar sumbu X
29 Y’ Y Yc X’ X Zc Z
Gambar 2.11 Rotasi sumbu x Y’ Y
X’ Z’
X
Zc Z
Gambar 2.12 Translasi sumbu x
1. Translasikan benda sehingga sumbu X’ berimpit dengan sumbu kordinat X [T(0,-Yc,-Zc)] 3. Rotasi benda terhadap sumbu X [Rx(θ) ] 4. Transalasi kembali ke posisi semula [T(0,Y,Z)]
Matrik transformsi : [M] = [T(0,-Yc,-Zc)] [Rx(θ) ] [T(0,Y,Z)]
2.10 Penelitian sebelumnya yang berhubungan Sebelumnya telah dilakukan beberapa penelitian yang berhubungan dengan penelitian ini, diantaranya:
30 1. “The distributers three dimensional pallet packing problem: a human intelligence based heuristic approach ”, Erhan Baltacioglu, 2001. Penelitian ini dilakukan di Air Force
Institude
Of
Technology,
Ohio.
Penelitian
ini
bertujuan
untuk
mengoptimalkan penempatan benda pada pallet, yang digunakan untuk air shipping. Penelitian ini mengembangkan algoritma heuristic dengan mengadaptasi kecerdasan manusia. Penelitian ini menggunakan layer saat packing secara horizontal dengan tujuan saat kotak dipacking mempunyai panjang yang seragam dengan kontainer, sesuai dengan kedalaman kontainer. Hal ini yang akan digunakan untuk analisis permasalahan pada bab 3. 2. “Heuristic for the container loading problem”, David Pisinger, 2002. Penelitian ini dilakukan di Dept.Of Computer Science, University of Copenhagen. Penelitian ini mengembangkan algoritma branch and bound untuk mencari solusi three dimensional bin packing. Beberapa aturan pengurutan digunakan untuk menentukan ketebalan layer dan panjang strips yang terbaik. Algoritma heuristic yang digunakan berdasarkan pendekatan wall building, hanya kedalaman layer yang sama dengan dimensi kotak yang dipertimbangkan. Kemudian kotak dipacking secara vertikal, vertikal packing inilah yang akan digunakan untuk analisis permasalahan pada bab 3. 3. “Multiple Destination Bin Packing”, Bram Verweij, 1996. Jurnal Penelitian ini tentang algoritma on-line and off-line untuk mencari solusi permasalahan bin packing baik dua maupun tiga dimensi. Dengan batasan-batasan yang sesuai kasus ialah proses loading truk dengan beberapa urutan yang harus di unload pada berbagai tujuan. Proses loading dengan berbagai tujuan inilah yang akan digunakan untuk analisis permasalahan pada bab 3.
