PERANCANGAN APLIKASI PERMAINAN BIN PACKING PROBLEM YANG DILENGKAPI TUTORIAL DENGAN ALGORITMA NEXT-FIT, FIRST FIT DAN BEST FIT
SKRIPSI
Oleh: RISKY FIRDESON NIM.1144123
PROGRAM STUDI TEKNIK INFORMATIKA SEKOLAH TINGGI MANAJEMEN INFORMATIKA DAN KOMPUTER STMIK TIME MEDAN 2015
i
ABSTRAK
Sasaran dari permasalahan bin packing adalah memasukkan setiap item ke dalam bin sedemikian sehingga ukuran bin yang digunakan adalah paling minimum. Permasalahan ini dapat diselesaikan dengan menggunakan algoritma First Fit, Next Fit dan Best Fit. Pendekatan rata-rata paling sederhana untuk menyelesaikan bin packing problem adalah dengan menggunakan algoritma Next Fit. Sebuah algoritma lainnya yang lebih baik adalah algoritma First Fit. Algoritma paling bagus adalah dengan menggunakan algoritma Best Fit. Hasil dari penelitian ini adalah sebuah aplikasi yang mampu menampilkan proses kerja dari algoritma First Fit, Next Fit dan Best Fit. Selain itu, juga disediakan sebuah interface untuk menyelesaikan permainan bin packing problem.
Kata Kunci: bin packing, First Fit, Next Fit, Best Fit
i
ii
ABSTRACT
The goal of bin packing problem is to insert every item to bin so that total weight of bin used are minimum. This problem could be solved by using First Fit, Next Fit and Best Fit algorithm. The simple approximate algorithm to solve bin packing problem is by using Next Fit. Another better algorithm is by using First Fit algorithm. The best algorithm is by using Best Fit algorithm. The result of this research is an application that could show the process of First Fit, Next Fit and Best Fit algorithm. Besides that, the system also provides an interface for solving bin packing problem. Keywords: bin packing, First Fit, Next Fit, Best Fit
ii
KATA PENGANTAR
Puji syukur kepada Tuhan Yang Maha Esa yang telah memberikan kesehatan kepada saya penulis dan berkat kebajikan yang telah diperbuat selama ini sehingga saya dapat menjelaskan skripsi yang merupakan salah satu pemenuhan kurikulum program studi Teknik Informatika pada STMIK TIME Medan. Adapun judul dari skripsi ini adalah “Perancangan Aplikasi Permainan Bin Packing Problem yang Dilengkapi Tutorial dengan Algoritma Next-Fit, First Fit dan Best Fit”. Dalam penyusunan skripsi ini, penulis banyak menerima bantuan baik bimbingan maupun petunjuk serta saran nasehat dari berbagai pihak. Melalui kesempatan ini penulis ingin menyampaikan rasa terima kasih yang sebesar – besarnya kepada : 1.
Bapak Robet, M.Kom, selaku Dosen Pembimbing I yang telah membantu dan membimbing penulis dalam menyelesaikan skripsi ini.
2.
Bapak Rudiyanto Tanwijaya, SE, selaku Dosen Pembimbing II yang telah membantu dan membimbing penulis dalam menyelesaikan skripsi ini.
3.
Bapak Simon Kanggali, selaku Ketua Yayasan STMIK TIME Medan.
4.
Bapak Prof. Chainur Arrasyid, SH, selaku Ketua BPH STMIK TIME Medan.
5.
Bapak Prof. Harlem Marpaung, Ph.D, selaku Ketua STMIK TIME Medan.
6.
Bapak Jackri Hendrik, ST, M.Kom, selaku Puket I STMIK TIME Medan.
7.
Bapak Hendri, M.Kom, selaku Ketua Program Studi Teknik Informatika STMIK TIME Medan.
iii
8.
Seluruh Dosen STMIK TIME Medan, yang telah banyak memberikan ilmu pengetahuan kepada penulis selama perkuliahan.
9.
Orang tua tercinta dan saudara – saudara yang senantiasa mendukung dan memberikan motivasi kepada penulis.
10. Teman – teman yang turut membantu dalam memberikan inspirasi maupun motivasi kepada penulis. Meskipun telah disusun, penulis menyadari bahwa isi dan teknik penulisan skripsi ini masih memerlukan perbaikan untuk menyempurnakannya baik dari segi tata bahasa manapun materi yang terkandung didalamnya. Oleh karena itu setiap kritik dan saran akan diterima dengan senang hati agar dapat dijadikan bahan perbaikan untuk penulisan selanjutnya. Akhir puji dan syukur daya ucapkan kepada Tuhan Yang Maha Esa, semoga kita selalu dalam lindungan dan karuniaNya.
Medan, April 2015 Penulis
(Risky Firdeson)
iv
DAFTAR ISI
ABSTRAK ..............................................................................................................
i
ABSTRACT ............................................................................................................. ii KATA PENGANTAR ............................................................................................ iii DAFTAR ISI ........................................................................................................... v DAFTAR GAMBAR .............................................................................................. viii DAFTAR TABEL ................................................................................................... x DAFTAR LAMPIRAN .......................................................................................... xi BAB I
PENDAHULUAN ........................................................................... 01 1.1. Latar Belakang Masalah ............................................................ 01 1.2. Identifikasi Masalah .................................................................. 02 1.3. Batasan Masalah ........................................................................ 02 1.4. Tujuan dan Manfaat Penelitian ................................................. 03 1.4.1. Tujuan Penelitian............................................................. 3 1.4.2. Manfaat Penelitian........................................................... 3 1.5. Sistematika Penulisan ................................................................ 04
BAB II
LANDASAN TEORI ...................................................................... 05 2.1. Perancangan .............................................................................. 05 2.2. Aplikasi ..................................................................................... 05 2.3. Permainan .................................................................................. 7 2.3.1. Permainan Komputer....................................................... 7 2.3.2. Pembagian Permainan Komputer .................................... 9 2.4. Tutorial ..................................................................................... 11 2.4.1. Tujuan Tutorial ............................................................... 12 2.4.2. Jenis-jenis Aplikasi Tutorial ........................................... 14 2.4.3. Komponen-komponen Tutorial ...................................... 16 2.5. Algoritma .................................................................................. 17 2.6. Bin Packing Problem ................................................................ 19
BAB III
METODE PENELITIAN ............................................................... 21 3.1. Tempat dan jadwal penelitian ................................................... 21
v
3.2. Kerangka kerja .......................................................................... 21 3.3. Identifikasi masalah .................................................................. 22 3.4. Pengumpulan data ..................................................................... 23 3.5. Analisa sistem ........................................................................... 23 3.6. Perancangan sistem ................................................................... 24 3.7. Pembangunan sistem ................................................................. 24 3.8. Uji coba sistem .......................................................................... 24 BAB IV
ANALISA DAN PERANCANGAN .............................................. 26 4.1. Analisa ..................................................................................... 25 4.1.1. Analisa Persyaratan ......................................................... 25 4.1.2. Alur Kerja Perangkat Lunak ............................................. 26 4.1.3. Proses Kerja dari Algoritma Bin Packing Problem ......... 27 4.1.4. Aturan Permainan ............................................................ 30 4.2. Perancangan ............................................................................. 32 4.2.1. Perancangan Menu ......................................................... 32 4.2.2. Perancangan Tampilan ................................................... 34 4.2.2.1 Form Main ........................................................... 35 4.2.2.2 Form Teori ........................................................... 36 4.2.2.3 Form Input ........................................................... 37 4.2.2.4 Form Proses ......................................................... 39 4.2.2.5 Form Pilih Pemain ............................................... 40 4.2.2.6 Form Kesulitan .................................................... 41 4.2.2.7 Form Permainan ................................................... 41 4.2.2.8 Form High Score ................................................. 43 4.2.2.9 Form About .......................................................... 43 4.2.3. Perancangan Database .................................................... 44
vi
BAB V
HASIL DAN PEMBAHASAN ....................................................... 46 5.1. Hasil ........................................................................................... 46 5.1.1. Spesifikasi Perangkat Keras dan Perangkat Lunak ......... 46 5.1.2. Hasil ................................................................................. 46 5.2. Pembahasan ............................................................................... 56 5.3. Algoritma ................................................................................... 57
BAB V1
KESIMPULAN DAN SARAN ....................................................... 59 6.1. Kesimpulan................................................................................. 59 6.2. Saran ........................................................................................... 59
DAFTAR PUSTAKA LAMPIRAN
vii
DAFTAR GAMBAR
Gambar 3.1.
Kerangka Kerja ................................................................................. 22
Gambar 4.1.
Diagram Alur dari Perangkat Lunak ................................................. 27
Gambar 4.2.
Diagram Konteks Sistem ................................................................... 39
Gambar 4.3.
Data Flow Diagram (DFD) Level 0 dari Sistem ............................... 30
Gambar 4.4.
Rancangan Menu pada Perangkat Lunak .......................................... 34
Gambar 4.5.
Rancangan Form ‘Main’ ................................................................... 35
Gambar 4.6.
Rancangan Form ‘Teori’ ................................................................... 36
Gambar 4.7.
Rancangan Form ‘Input’ ................................................................... 37
Gambar 4.8.
Rancangan Form ’Proses’ ................................................................. 39
Gambar 4.9.
Rancangan Form Pilihan Pemain ...................................................... 40
Gambar 4.10. Rancangan Form Kesulitan ............................................................... 41 Gambar 4.11. Rancangan Form ‘Permainan’ ........................................................... 42 Gambar 4.12. Rancangan Form ‘High Score’ .......................................................... 43 Gambar 4.13. Rancangan Form ‘About’ .................................................................. 44 Gambar 5.1.
Tampilan Form Awal ........................................................................ 47
Gambar 5.2.
Tampilan Form Menu Tutorial .......................................................... 47
Gambar 5.3.
Tampilan Form Input Data ................................................................ 48
Gambar 5.4.
Tampilan Form Input Data Setelah Pengisian Data .......................... 49
Gambar 5.5.
Tampilan Form Tutorial .................................................................... 50
Gambar 5.6.
Tampilan Form Tutorial pada Saat Menampilkan Proses Kerja Algoritma .......................................................................................... 50
Gambar 5.7.
Tampilan Form Tutorial pada Setelah Proses First Fit Selesai ......... 51
Gambar 5.8.
Tampilan Form Tutorial pada Setelah Proses Next Fit Selesai ......... 51
Gambar 5.9.
Tampilan Form Tutorial pada Setelah Proses Best Fit Selesai.......... 52
Gambar 5.10. Tampilan Form Pilih Pemain ............................................................ 52 Gambar 5.11. Tampilan Input Box .......................................................................... 53 Gambar 5.12. Tampilan Tingkat Kesulitan .............................................................. 53 Gambar 5.13. Tampilan Permainan ......................................................................... 54 Gambar 5.14. Tampilan Permainan pada Saat Bermain .......................................... 54
viii
Gambar 5.15. Tampilan Pesan Kesalahan................................................................ 55 Gambar 5.16. Tampilan Form High Score ............................................................... 55 Gambar 5.17. Tampilan Form About ...................................................................... 56
ix
DAFTAR TABEL
Tabel 3.1
Jadwal Penelitian .................................................................................. 21
Tabel 4.1
Uraian Kebutuhan Fungsional .............................................................. 25
Tabel 4.2
Uraian Kebutuhan Non-Fungsional ..................................................... 26
Tabel 4.3
Tabel HighScore ................................................................................... 44
Tabel 4.4
Tabel UserList ...................................................................................... 45
x
DAFTAR LAMPIRAN
CD program Surat keputusan dosen pembimbing skripsi Daftar riwayat hidup mahasiswa Listing program
xi
BAB I PENDAHULUAN
1.1.
Latar Belakang Masalah Dalam sebuah perusahaan ekspedisi sering ditemukan permasalahan untuk
menentukan setiap barang harus dimasukkan ke dalam container mana sehingga total berat barang yang diangkut adalah yang paling maksimal. Permasalahan ini sering disebut sebagai bin packing problem, yang dapat dideskripsikan sebagai berikut, diberikan n buah item dan n buah bin, dengan perincian wj adalah berat dari item j dan c adalah kapasitas dari setiap bin. Sasarannya adalah masukkan setiap item ke dalam bin sedemikian sehingga ukuran bin yang digunakan adalah paling minimum. Manfaat dari penyelesaian bin packing problem ini adalah perusahaan ekspedisi tersebut dapat memaksimalkan pemanfaatan container-nya dalam setiap kali pengiriman barang. Agar dapat lebih memahami mengenai proses kerja dari bin packing problem, maka dapat dirancang sebuah aplikasi permainan sederhana sehingga dapat digunakan untuk mempelajari mengenai bin packing problem. Aplikasi permainan ini akan dilengkapi dengan fasilitas tutorial sehingga dapat menampilkan simulasi penyelesaian dari persoalan bin packing problem yang diberikan. Pendekatan rata-rata paling sederhana untuk menyelesaikan bin packing problem adalah dengan menggunakan algoritma Next Fit. Item pertama akan dimasukkan ke dalam bin 1 Item 2 … n dianggap sebagai indeks berurutan secara menaik. Jika dapat masuk, maka setiap item akan dimasukkan ke dalam sebuah bin. Jika tidak dapat masuk, maka akan dipilih bin lainnya. Sebuah algoritma
1
2
lainnya yang lebih baik adalah algoritma First Fit. Algoritma akan mencari bin yang cukup besar untuk ditempati item dan proses pencarian selalu dimulai dari bin pertama. Sementara algoritma Next Fit tidak akan mengecek bin yang telah dicek sebelumnya. Algoritma paling bagus adalah dengan menggunakan algoritma Best Fit. Algoritma akan mengecek semua bin dan memilih bin terkecil yang dapat ditempati oleh item. Berdasarkan uraian dan alasan di atas, maka ingin dirancang sebuah perangkat lunak yang dapat mensimulasikan proses penyelesaian bin packing problem sekaligus menyediakan interface untuk bermain bin packing problem. Oleh karena itu, penulis mengambil skripsi dengan judul “Perancangan Aplikasi Permainan Bin Packing Problem yang Dilengkapi Tutorial dengan Algoritma Next-Fit, First Fit dan Best Fit”.
1.2.
Identifikasi Masalah Berdasarkan uraian latar belakang pemilihan judul di atas, maka
permasalahan dalam penyusunan skripsi ini dapat dirumuskan sebagai berikut: 1. Bagaimana merancang algoritma Next-Fit, First Fit dan Best Fit untuk menyelesaikan bin packing problem. 2. Bagaimana merancang interface untuk bermain bin packing problem.
1.3.
Batasan Masalah Masalah yang akan dibahas dalam skripsi ini mencakup:
1. Jumlah bin dibatasi minimal 2 buah dan maksimal 12 buah. 2. Jumlah item dibatasi minimal 2 buah dan maksimal 12 buah.
3
3. Bagian tutorial akan menampilkan penyelesaian dengan menggunakan algoritma Next-Fit, First Fit dan Best Fit. 4. Permainan akan dimainkan dengan menggunakan batasan waktu dan sisa waktu akan diakumulasikan ke level berikutnya. 5. Perangkat
lunak
akan
dikembangkan
dengan
menggunakan
bahasa
pemrograman Microsoft Visual Basic.NET 2010. 6. Database yang digunakan untuk menyimpan nilai pemain akan dirancang dengan aplikasi Microsoft Access 2007.
1.4.
Tujuan dan Manfaat Penulisan
1.4.1. Tujuan Penelitian Tujuan penyusunan skripsi ini adalah: 1. Membuat sebuah aplikasi yang menerapkan algoritma Next-Fit, First Fit dan Best Fit untuk menyelesaikan bin packing problem. 2. Membuat interface untuk bermain bin packing problem.
1.4.2. Manfaat Penelitian Manfaat dari penyusunan skripsi ini, yaitu: 1. Membantu pemahaman mengenai proses kerja dari algoritma Next-Fit, First Fit dan Best Fit. 2. Perangkat lunak dapat dijadikan sebagai sarana hiburan untuk mengisi waktu luang.
4
1.5.
Sistematika Penulisan Agar pembahasan lebih sistematika, maka tulisan ini dibuat dalam enam
bab, yaitu : BAB I
PENDAHULUAN Berisi latar belakang pemilihan judul, identifikasi masalah, tujuan dan manfaat, batasan masalah dan sistematika penulisan.
BAB II
LANDASAN TEORI Berisi tentang penjelasan singkat mengenai topik yang dibahas.
BAB III
METODE PENELITIAN Berisi tentang tempat dan jadwal penelitian, kerangka kerja, metode pengumpulan data, analisa sistem, perancangan sistem, pembangunan sistem,
uji coba sistem dan
implementasi sistem. BAB IV
ANALISA DAN PERANCANGAN Berisi tentang pembahasan mengenai proses kerja dan perancangan tampilan antarmuka.
BAB V
HASIL DAN PEMBAHASAN Berisi tentang algoritma dan implementasi dari perangkat lunak.
BAB VI
KESIMPULAN DAN SARAN Berisi tentang kesimpulan dan saran-saran yang diambil penulis setelah menyelesaikan skripsi.
BAB II LANDASAN TEORI
2.1.
Perancangan ”Perancangan sistem merupakan penggambaran, perencanaan dan
pembuatan sketsa atau pengaturan dari beberapa elemen yang terpisah ke dalam satu kesatuan yang utuh dan berfungsi”. (Hartono, 2010: 196) Tahap perancangan sistem mempunyai dua maksud atau tujuan utama yaitu: 1. Untuk memenuhi kebutuhan kepada pemakai sistem. 2. Untuk memberikan gambaran yang jelas dan rancang bangun yang lengkap kepada pemograman komputer dan ahli-ahli teknik lainnya yang terlibat. Untuk memahami tujuan ini, analisis sistem harus dapat mencapai sasaransasaran sebagai berikut: 1. Perancangan sistem harus berguna, mudah dipahami dan nantinya mudah digunakan. 2. Perancangan sistem harus dapat mendukung tujuan utama perusahaan sesuai dengan yang didefiniskan pada tahap perencanaan sistem yang dilanjutkan pada tahap analisis sistem.
2.2.
Aplikasi Aplikasi adalah suatu perangkat lunak komputer yang memanfaatkan
kemampuan komputer langsung untuk melakukan suatu tugas yang diinginkan pengguna. Biasanya dibandingkan dengan perangkat lunak sistem yang
5
6
mengintegrasikan berbagai kemampuan komputer, tapi tidak secara langsung menerapkan kemampuan tersebut untuk mengerjakan suatu tugas yang menguntungkan pengguna. Contoh utama perangkat lunak adalah pengolah kata, lembar kerja dan pemutar media. Beberapa aplikasi yang digabung bersama menjadi suatu paket kadang disebut sebagai application suite. Contohnya adalah Microsoft Office dan OpenOffice.org, yang menggabungkan suatu apliaksi pengolah kata, lembar kerja, serta beberapa aplikasi lainnya. Aplikasi-aplikasi dalam suatu paket biasanya memiliki antarmuka pengguna yang memiliki kesamaan sehingga memudahkan pengguna untuk mempelajari dan menggunakan tiap aplikasi. Sering kali, mereka memiliki kemampuan untuk saling berinteraksi satu sama lain sehingga menguntungkan pengguna. Contohnya, suatu lembar kerja dapat dimasukkan dalam suatu dokumen pengolah kata walaupun dibuat pada aplikasi lembar kerja yang terpisah. Menurut Presman (2002: 10), aplikasi dapat didefinisikan menjadi beberapa pengertian berikut: 1. Aplikasi adalah suatu unit perangkat lunak yang dibuat untuk melayani kebutuhan akan beberapa aktivitas seperti sistem perniagaan, game pelayanan masyarakat, periklanan, atau semua proses yang hampir dilakukan manusia. 2. Aplikasi adalah kumpulan perintah program yang dibuat untuk melakukan pekerjaan-pekerjaan tertentu. 3. Aplikasi adalah alat bantu untuk mempermudah dan mempercepat proses pekerjaan dan bukan merupakan beban bagi penggunanya.
2.3.
Permainan Menurut Clark Abt, permainan adalah sebuah konteks dengan aturan-
aturan di antara lawan-lawan yang mencoba untuk memenangkan objektif.
7
Sedangkan, menurut Bernard Suits, bermain suatu game adalah usaha sukarela untuk mengatasi rintangan / halangan yang tidak perlu. Chris Crawford dalam bukunya yang berjudul ‘The Art of Computer Game Design’ memberikan definisi yang panjang termasuk kualitas dari representasi, interaksi, konflik dan keamanan. Di salah satu bagian, dia menuliskan bahwa ‘game adalah sebuah pendekatan sistem formal yang merepresentasikan secara subjektif bagian-bagian dari realitas’. Elliot Avedon dan Brian Sutton-Smith dalam bukunya ‘The Study of Games’ menyatakan bahwa game adalah suatu latihan dari sistem kontrol yang sukarela, di mana terdapat suatu kontes adu tenaga, dibatasi oleh aturan-aturan untuk
menghasilkan
sebuah
hasil
yang
tidak
sama.
(http://www.ummi.ac.id/ti/konvert_pdf.php?kode=VGxFOVBRPT0=)
2.3.1. Permainan Komputer Pada tahun 1952, A.S. Douglas mengajukan gelar kesarjanaan Ph.D-nya di Universitas Cambridge dengan menulis topik mengenai “Interaksi Antara Manusia dan Komputer”. Douglas menciptakan game komputer berbasis grafis pertama – sebuah versi Tic-Tac-Toe. Game ini diprogram pada komputer EDSAC yang menggunakan tabung vakum yang mempunyai display berupa tabung sinar katoda. William Higinbotham menciptakan video game pertama pada tahun 1958. Game-nya diberi nama “Tennis for Two”, dibuat dan dimainkan pada sebuah osiloskop di Brookhaven National Laboratory. Pada tahun 1962, Steve Russel menciptakan “SpaceWar” yang merupakan game pertama yang ditujukan untuk
8
dimainkan dengan komputer. Russel menggunakan sebuah komputer mainframe PDP-1 di Massachusetts Institute of Technology (MIT) untuk mendesain gamenya. Diperlukan sekitar 200 jam kerja untu menulis dan mendesain versi dari SpaceWar. Steve Russell membuat SpaceWar pada PDP-1, sebuah mini komputer interaktif dari Digital Equipment Corporation (DEC) yang menggunakan tampilan tabung sinar kotada dan sebagai inputnya adalah keyboard. Komputer ini merupakan sumbangan dari DEC untuk MIT, dengan tujuan agar MIT dapat memberikan sesuatu ide atas produk mereka. Russel tidak pernah mengambil keuntungan atas game SpaceWar-nya. Sistem operasi PDP-1 memungkinkan beberapa user untuk memakai komputer secara simultan. Sistem ini sangat cocok untuk memainkan game SpaceWar. Pada tahun 1967, Ralph Baer membuat video game pertama yang dimainkan pada televisi, sebuah game yang diberi nama “Chase”. Ralph Baer merupakan anggota Sanders Associates, sebuah firma elektronik militer. Ralph Baer pertama kali mengajukan idenya pada tahun 1951 ketika bekerja pada Loral, sebuah perusahaan televisi. Kemudian pada tahun 1971, Nolan Bushnell bersama dengan Ted Dabney, membuat game arcade pertama. Game tersebut disebut “Computer Space”, didasari oleh game SpaceWar Steve Russell. Game arcade “Pong” ditulis dan dirilis oleh Nolan Bushnell (diprogram dengan A1 Alcorn) satu tahun kemudian. Nolan Bushnell dan Ted Dabney memulai membuat game “Pong” pada mesin Atari pada tahun yang sama. Pada tahun 1975, Atari merilis ulang “Pong” sebagai sebuah basis video game yang dapat dimainkan di rumah.
9
Pada tahun 1972, konsol video game komersial pertama yang dapat dimainkan di rumah, Odyssey dirilis oleh Magnavox dan didesain oleh Ralph Baer. Mesin game ini didesain ketika Ralph Baer masih berada di Sanders Associates pada tahun 1966. Mesin Odyssey diprogram dengan jumlah game sebanyak dua belas buah. Pada tahun 1976, Fairchild merilis konsol game rumah pertama yang dapat diprogram yang dikenal dengan Fairchild Video Entertainment System dan kemudian diubah namanya menjadi Channel F. Pada tahun 1980-an dikenal sebuah game yang disebut Tetris yang dibuat oleh perusahaan Capcom dari Jepang.
2.3.2. Pembagian Permainan Komputer Dalam sebuah game ada beberapa komponen yang ada, misalnya jenis game, karakter, background, suara gerakan, atau bahkan movie. Semua komponen tersebut sangat sangat penting dalam pembuatan game, sehingga kalau kita membuat setiap komponen menarik, maka tentu saja game yang kita buat akan menarik dan tidak membosankan. Game yang sekarang dikenal ada beberapa jenis, yaitu : 1. Side Scrolling Game Merupakan jenis game dimana karakter dapat bergerak ke samping ataupun ke atas dan ke bawah mengikuti gerakan background. Contoh jenis game ini adalah Sonic, Contra, Super Mario, dan sebagainya. 2. Shooting Game Shooting game adalah game yang bertipe menembak musuh. Berdasarkan sudut pandangnya, ada dua jenis tipe sudut pandang dalam shooting game ini,
10
yaitu first person View (sudut pandang orang pertama, dimana kita dijadikan seperti karakter yang kita mainkan) dan Third Person View (sudut pandang orang ketiga, dimana kita bisa melihat karakter dalam game, dan kita dapat menggerakkannya sesuai keinginan kita). Contoh jenis game ini adalah Counter Strike, Virtual Cop, Time Crisis, house of The Dead, dan lain sebagainya). 3. RPG (Role Playing Game) Merupakan jenis game lebih bertipe cerita dan biasanya kita diajak masuk ke dalam cerita tersebut untuk menyelesaikan misi. Dalam game tipe ini, jikalau kita bertemu dengan musuh, kita harus masuk ke dalam suatu lembaran baru atau frame baru. Contoh game ini adalah final fantasy, Ragnarok, Wild Arms, dan Sebagainya. 4. RTS (Real Time Strategy) Merupakan jenis game yang bertipe strategi, dimana kita diajak berpikir untuk bergerak pintar agar misi yang kita jalankan dapat sukses. Sebagian besar game ini bertipe strategi perang. Contoh game ini adalah Warcraft, Final fantasy Tactic, dan lain sebagainya. 5. Simulation Merupakan jenis game yang mengambil simulasi seperti keadaan sebenarnya, di beberapa game jenis ini biasanya kita diajak menciptakan suasana lingkungan yang kita inginkan. Contoh game jenis ini adalah Sims, Sim City, dan game Sim lainnya.
11
6. Racing Merupakan game yang berjenis balapan, yang biasanya teknik kita dalam memainkan dijadikan patokan keberhasilan dalam misi. Contoh game jenis ini adalah CTR (Crash Time Racing), Grand Turismo, Top Gear, dan lain sebagainya. 7. Fighting Merupakan jenis game yang biasanya ada dua karakter yang bertarung untuk memperoleh kemenangan atau tercapainya suatu misi. Contoh jenis game ini adalah Tekken, Street Fighter, Guilty Gear, dan lain sebagainya. (Diginnovac, 2009: 1-3)
2.4.
Tutorial Seiring dengan perkembangan peradaban manusia dan kemajuan pesat di
bidang teknologi, tanpa disadari komputer telah ikut berperan dalam dunia pendidikan terutama penggunaannya sebagai alat bantu pengajaran. Percobaan penggunaan komputer untuk proses belajar dimulai di Amerika Serikat pada akhir tahun 1950-an dan awal tahun 1960-an. Kemudian penelitian selanjutnya dilakukan oleh Harvard University bekerja sama dengan IBM pada tahun 1965. Setelah munculnya komputer mikro, sistem pengajaran dengan komputer menjadi semakin meluas pada pengembangan aplikasi perangkat lunak ajar yang dikenal dengan istilah perangkat ajar. Perangkat ajar dengan komputer muncul dari sejumlah disiplin ilmu, terutama ilmu komputer dan psikologi. Dari ilmu komputer dan matematika muncul program-program yang membuat semua perhitungan dan fungsi lebih mudah dan bermanfaat. Sedangkan dari ilmu
12
psikologi muncul pengetahuan mengenai teori belajar, teknik belajar, serta motivasi yang baik. Banyak istilah yang dipakai untuk menyatakan perangkat ajar dengan komputer, seperti Computer Assisted Instruction ( CAI ), Computer Based Instruction ( CBI ), Computer Based Education ( CBE ), Computer Assisted Learning ( CAL ), atau Computer Based Training ( CBT ).
2.4.1. Tujuan Tutorial Hampir semua aplikasi CBT mampu meningkatkan efisiensi dan efektivitas belajar. Peningkatan efisiensi dimaksudkan untuk menggunakan sumber daya yang terbatas. Sedangkan peningkatan efektivitas dimaksudkan untuk mendapatkan hasil belajar yang lebih baik. Kedua peningkatan ini merupakan tujuan umum dari CBT. Tujuan tersebut digolongkan lagi menjadi tujuan yang lebih khusus, yaitu : 1. Peningkatan pengawasan CBT melakukan peningkatan pengawasan dalam hal pemakaian dan penyelesaian suatu materi, peningkatan standarisasi suatu pelatihan, serta pengawasan kemampuan belajar. Dengan pemakaian komputer dalam pelatihan, diharapkan keseragaman materi bisa tercapai dan memiliki nilai standarisasi yang tinggi. 2. Penggunaan sumber daya Dengan pelatihan pada beberapa tempat atau kantor cabang dapat mengurangi kebutuhan fasilitas latihan dan tenaga pengajar. Pelatihan ini untuk menangani
13
sejumlah pelajar maka tentu saja dapat dilakukan lagi penanganan jumlah pelajar yang lebih banyak. 3. Individualisasi Dengan adanya CBT, maka pelajar dapat belajar sendiri kapan saja sesuai dengan kemampuannya. Selain itu, pelajar dapat memilih topik mana yang hendak mereka pelajari dan bebas berlatih dengan materi yang diinginkan. 4. Ketepatan waktu dan tingkat ketersediaan Masalah utama dalam pelatihan, harus dapat memberikan materi pada waktu dan tempat yang tepat. CBT memungkinkan memberi pelatihan dengan cepat. 5. Pengurangan waktu latihan Menurut suatu penelitian, pelatihan yang dilakukan dengan komputer hanya memerlukan waktu 30% dari waktu pelatihan yang dilakukan tanpa komputer. Dengan adanya CBT, setiap orang dapat berlatih kapan saja tanpa menghabiskan waktu di perjalanan menuju ke tempat pelatihan. 6. Perbaikan hasil kerja CBT dapat dipakai untuk perbaikan hasil kerja secara langsung maupun tidak langsung. Secara langsung, untuk melatih dalam keahlian khusus yang diperlukan dalam suatu pekerjaan. Secara tidak langsung, untuk menyediakan pelatihan yang lebih umum daripada biasanya dan meluaskan hasil kerja. 7. Alat yang nyaman dipakai CBT akan membantu pengguna komputer dalam menghadapi masalah dengan sistem komputer mereka dengan antarmuka dan aplikasi yang ramah.
14
8. Pengganti cara belajar Kini, banyak perusahaan yang memperbolehkan karyawannya membawa komputer ke rumah. Hal ini dimaksudkan agar mereka tidak hanya belajar dan bekerja pada waktu atau tempat tertentu saja, tetapi bisa juga bisa melakukannya di rumah. 9. Peningkatan kepuasan belajar Program aplikasi CBT yang interaktif membuat para pelajar umumnya merasa puas dan betah. Keinteraktifan ini dikarenakan CBT mampu memberikan respon dan jawaban, serta mampu memberikan petunjuk dalam belajar. Timbulnya motivasi belajar dengan CBT ini sangat penting selama waktu pelatihan untuk memacu semangat belajar. 10. Pengurangan waktu pengembangan Pengembangan dan perbaikan yang diterapkan dalam CBT sangat mudah, hanya perlu dilakukan dari database pusat saja dan waktunya juga relatif singkat.
2.4.2. Jenis-jenis Aplikasi Tutorial Jenis pemakaian komputer untuk perangkat ajar digolongkan menjadi tiga bagian, yaitu : 1. Pengujian Dalam jenis CBT, komputer digunakan untuk memberikan penilaian dan analisis tes, membuat soal tes, membuat nilai acak, tes interaksi, dan tes adaptasi. Jenis ini sering disebut dengan Computer Assisted Testing (CAT).
15
2. Manajemen Jenis pemakaian ini disebut dengan Computer Managed Instruction(CMI), dimana komputer digunakan untuk mengatur kemajuan peserta pelatihan dan alat-alat yang dipakai. CMI biasanya digunakan untuk meningkatkan pengawasan dan efisiensi dalam sistem pelatihan. 3. Instruksi Ada dua bentuk yang hampir sama mengenai pengguna komputer untuk instruksi. Yang pertama, Computer Assisted Instruction ( CAI ), menganggap komputer sebagai media penyimpanan instruksi sama seperti slide, tape, video atau buku-buku. Menurut sudut pandang CAI, masalah utamanya adalah bagaimana menyusun bahan-bahan instruksi yang akan ditampilkan oleh komputer dengan cara yang paling efektif. Ada tiga jenis CAI, yakni : a. Drill and Practice Merupakan cara yang paling mudah, terdiri dari tahap-tahap penampilan permasalahan, penerimaan respon pengguna, pemberian hasil analisis, umpan balik, dan pemberian pertanyaan lain. Secara umum jenis ini tidak menampilkan informasi baru tapi memberikan latihan dari konsep yang sudah ada. b. Tutorial Jenis ini berisi konsep atau prosedur yang disertai dengan pertanyaan atau latihan pada akhir dari pelatihan. Selama pelatihan, komputer mengajarkan informasi-informasi yang baru kepada siswa seperti layaknya seorang guru pembimbing. Setelah itu, pemahaman siswa diukur melalui serangkaian
16
tes dan komputer melanjutkan pengajaran berdasarkan hasil pengukuran tadi. c. Socratic Berisi komunikasi antara pengguna dan komputer dalam natural language. Jenis ini sebenarnya berasal dari penelitian dalam bidang intelijensia semu (Artificial Intelligence). Socratic mampu melakukan interaksi dalam natural language dan bisa memahami apa yang ditanyakan pengguna.
2.4.3. Komponen-komponen Tutorial Ada empat komponen utama CBT yang berhubungan erat satu dengan yang lainnya. Kurangnya suatu komponen membuat komponen lain menjadi tidak berarti. Keempat komponen itu adalah : 1. Perangkat keras ( hardware ) Perangkat keras meliputi semua peralatan fisik yang berhubungan dengan CBT termasuk disk drive, printer, peralatan multimedia, dan sebagainya. 2. Perangkat lunak ( software ) Perangkat lunak meliputi program-program yang memperbolehkan sistem mengoperasikan dan melakukan fungsi-fungsi instruksional. Komponen ini diklasifikasikan menjadi perangkat lunak sistem. 3. Perangkat ajar ( courseware ) Perangkat ajar juga biasa disebut lessonware atau teachware. Perangkat ajar merupakan program yang melengkapi presentasi instruksional. Perangkat ajar sebenarnya juga merupakan perangkat lunak. Perangkat ajar pada CBT
17
dibedakan dari perangkat lunak yang memiliki aturan khusus untuk merepresentasikan suatu kurikulum. 4. Manusia ( humanware ) Komponen ini mencakup orang-orang yang memiliki keahlian khusus dalam hal mengembangkan, mengoperasikan, memelihara, atau mengevaluasi suatu CBT.
2.5.
Algoritma “Kata algoritma berasal dari nama seorang ahli matematika berkebangsaan
Persia yang hidup pada abad ke-9 yang bernama Abu Abdullah Muhammad bin Musa Al-Khawarizmi” (Hariyanto, 2003). Pada awalnya, kata ‘algorism’ diartikan sebagai aturan-aturan untuk melakukan proses aritmatika menggunakan numerik Arab. Kata ‘algorism’ diubah menjadi kata ‘algorithm’ pada abad ke-18. Sekarang, pengertian dari kata ini mencakup semua prosedur terhingga untuk menyelesaikan problema atau melakukan pekerjaan. Penerapan pertama dari algoritma yang ditulis untuk sebuah komputer adalah ‘Ada Byron’s notes on the analytical engine’ yang ditulis pada tahun 1842, di mana Ada Byron dianggap oleh kebanyakan orang sebagai programmer pertama di dunia. Walaupun, sejak Charles Babbage tidak menyelesaikan analytical engine-nya, algoritma ini tidak pernah diimplementasikan lagi. Algoritma adalah suatu kumpulan terhingga (finite set) dari instruksi yang terdefinisi dengan baik (well-defined instructions) untuk menyelesaikan beberapa
18
pekerjaan di mana diberikan state awal (initial state) dan akan dihentikan pada saat ditemukan state akhir (end-state) yang dikenal. Algoritma dapat diimplementasikan dalam pembuatan program komputer. Kesalahan dalam merancang algoritma untuk menyelesaikan suatu problema dapat menyebabkan program gagal dalam implementasinya. Konsep dari suatu algoritma sering diilustrasikan dengan mengambil contoh sebuah resep, walaupun banyak algoritma yang jauh lebih kompleks. Algoritma
sering memiliki beberapa
langkah perulangan (iterasi) atau
memerlukan pengambilan keputusan seperti logika (logic) atau perbandingan (comparison) sampai pekerjaan diselesaikan. Menerapkan suatu algoritma secara benar belum tentu dapat menyelesaikan problema. Hal ini dikarenakan adanya kemungkinan algoritma tersebut rusak atau cacat, atau penerapannya tidak cocok (tidak tepat) untuk menyelesaikan problema. Sebagai contoh, sebuah algoritma hipotesis untuk membuat sebuah salad kentang akan gagal jika tidak terdapat kentang. Suatu pekerjaan dapat diselesaikan dengan menggunakan algoritma yang berbeda dengan kumpulan instruksi (set of instructions) yang berbeda dengan perbedaan waktu akses, efisiensi tempat, usaha dan sebagainya. Sebagai contoh, diberikan dua buah resep yang berbeda untuk membuat salad kentang, resep pertama mengupas kulit kentang terlebih dahulu sebelum memasak kentang tersebut, sementara resep lainnya dilakukan dengan langkah yang terbalik, dan kedua resep akan mengulangi kedua langkah tersebut dan akan dihentikan pada saat salad kentang siap untuk dimakan.
19
Algoritma adalah hal yang mendasar untuk komputer dalam memproses informasi, karena sebuah program komputer adalah sebuah algoritma yang memberitahukan kepada komputer langkah-langkah spesifik yang akan dijalankan (dalam urutan spesifik) untuk melakukan pekerjaan tertentu, misalnya menghitung gaji karyawan atau mencetak rapor murid. Oleh karena itu, algoritma dapat dianggap sebagai beberapa operasi sekuensial (terurut) yang dapat dijalankan oleh sebuah sistem lengkap Turing.
2.6.
Bin Packing Problem Menurut Martello, et. al. (1990: 221), Bin Packing Problem dapat
dideskripsikan sebagai berikut: diberikan n buah item dan n buah bin, dengan perincian wj adalah berat dari item j dan c adalah kapasitas dari setiap bin. Sasarannya adalah masukkan setiap item ke dalam bin sedemikian sehingga jumlah bin yang digunakan adalah paling minimum. Terdapat beberapa algoritma yang dapat diterapkan untuk mencari solusi dari problema ini, yaitu: 1. First-Fit Algorithm Algoritma akan mencari bin yang cukup besar untuk ditempati item dan proses pencarian selalu dimulai dari bin pertama. Item pertama akan dimasukkan ke dalam bin 1 Item 2 … n dianggap sebagai indeks berurutan secara menaik. Jika dapat masuk, maka setiap item akan dimasukkan ke dalam sebuah bin. Jika tidak dapat masuk, maka akan dipilih bin lainnya. Keunggulannya adalah algoritma ini menemukan solusi paling cepat dibandingkan algoritma-algoritma lain.
20
2. Next-Fit Algorithm Mekanisme algoritma ini sama dengan first-fit algorithm, hanya tidak dimulai di awal tetapi dari posisi terakhir kali menemukan bin paling cocok. Simulasi oleh Bays (1977) menunjukkan next-fit algorithm berkinerja lebih buruk dibandingkan first-fit algorithm. 3. Best-Fit Algorithm Algoritma akan mengecek semua bin dan memilih bin terkecil yang dapat ditempati oleh item. Algoritma ini mencoba menemukan bin terkecil yang mendekati ukuran yang diperlukan. Kelemahan dari algoritma ini adalah Best-fit sangat lambat dibandingkan dengan first-fit karena selalu men-scan seluruhnya setiap kali dipanggil.
BAB III METODE PENELITIAN
3.1.Tempat dan Jadwal Penelitian Penelitian ini dimulai dari bulan November 2014 dan akan berlangsung sekitar 6 bulan. Kegiatan penelitian ini bertujuan untuk mengumpulkan data yang diperlukan dalam proses perancangan dan pembuatan sistem. Berikut ini dijabarkan jadwal penelitian yang dapat dilihat pada Tabel 3.1. Tabel 3.1 Jadwal Penelitian
Waktu Kegiatan
1
November
Desember
Januari
Februari
Maret
April
2014
2014
2015
2015
2015
2015
2
3
4
1
2
3
4
1
2
3
4
1
2
3
4
1
2
3
4
1
2
3
4
Identifikasi Masalah Pengumpulan Data Analisa Sistem Perancangan Sistem Pembangunan Sistem Uji Coba Sistem
3.2.Kerangka Kerja Adapun tahapan dan langkah-langkah pengembangan perangkat lunak ini dapat digambarkan dalam bentuk diagram alir seperti diperlihatkan pada gambar 3.1.
21
22
Identifikasi Masalah
Pengumpulan data
Analisa Sistem
Perancangan Sistem
Pembangunan Sistem
Uji Coba Sistem
Gambar 3.1 Kerangka Kerja
3.3.Identifikasi Masalah Sebelum merancang sebuah sistem, maka perlu dilakukan proses identifikasi terhadap permasalahan yang sedang dan akan dihadapi dalam proses pembangunan sistem. Tujuan dari proses identifikasi masalah ini adalah untuk memprediksi kemungkinan-kemungkinan yang dapat terjadi dalam proses pembuatan perangkat lunak.
23
3.4.Pengumpulan Data Di tahap pertama, penulis mengumpulkan bahan yang diperlukan dalam penyusunan skripsi dari berbagai sumber, seperti buku dan karya ilmiah dari internet. Proses dimulai dengan mengumpulkan data-data yang diperlukan dalam penelitian. Adapun metode pengumpulan data dalam penelitian dilakukan melalui Penelitian Kepustakaan (library research), dimana penulis mengumpulkan datadata melalui berbagai referensi seperti internet dan buku-buku yang relevan yang berhubungan dengan topik yang dibahas.
3.5.Analisa Sistem Tahap berikutnya ialah menganalisis kebutuhan-kebutuhan sistem. Perangkat dan teknik-teknik tertentu akan membantu penganalisis menentukan kebutuhan. Perangkat yang dimaksud ialah penggunaan diagram alir data untuk menyusun daftar input, proses, dan output fungsi bisnis dalam bentuk grafik terstruktur. Pada tahap ini penulis akan menganalisis permasalahan lebih mendalam mengenai masalah yang muncul pada sistem berjalan, sehingga dapat dirancang sebuah sistem baru untuk menyelesaikan permasalahan tersebut.
3.6.Perancangan Sistem Dalam tahap desain dari siklus hidup pengembangan sistem, penganalisis sistem menggunakan informasi-informasi yang terkumpul sebelumnya untuk mencapai desain sistem informasi yang logik. Penganalisis merancang prosedur
24
data-entry sedemikian rupa sehingga data yang dimasukkan ke dalam sistem informasi benar-benar akurat. Selain itu, penganalisis menggunakan teknik-teknik bentuk dan perancangan layar tertentu untuk menjamin keefektifan input sistem informasi.
3.7.Pembangunan Sistem Dalam tahap keempat dari siklus hidup pengembangan sistem, pemrogram akan mengembangkan suatu perangkat lunak awal yang diperlukan. Teknik terstruktur yang digunakan untuk merancang dan mendokumentasikan perangkat lunak meliputi adalah flowchart. Penganalisis sistem menggunakan perangkat ini untuk menjabarkan apa yang perlu diprogram. Proses dilanjutkan dengan melakukan coding terhadap perangkat lunak. Perangkat lunak ini dirancang dengan menggunakan bahasa pemrograman Microsoft Visual Basic 2010 dengan perincian sebagai berikut : 1. Data ditampilkan dengan menggunakan label dan textbox. 2. Proses perhitungan waktu akan diatur dengan menggunakan timer.
3.8.Uji Coba Sistem Setiap aplikasi perangkat lunak yang telah dibangun harus dilakukan uji coba terlebih dahulu sebelum digunakan, untuk mengetahui apakah aplikasi perangkat lunak yang dibangun sudah sesuai dengan yang diharapkan dan bekerja dengan baik atau masih terdapat kesalahan (error). Setiap kesalahan (error) yang terjadi akan diperbaiki kembali.
BAB IV ANALISA DAN PERANCANGAN
3.9.Analisa Sebelum merancang perangkat lunak, maka perlu dilakukan analisa persyaratan terhadap perangkat lunak yang mencakup analisa fungsional dan non fungsional. Kemudian, baru dilakukan analisa alur kerja perangkat lunak dan menjelaskan prosedur kerja dari algoritma yang digunakan serta deskripsi aturan permainan.
3.9.1
Analisa Persyaratan Analisa persyaratan terhadap sistem mencakup analisa fungsional yang
mendeskripsikan fungsionalitas yang harus dipenuhi oleh perangkat lunak dan analisa non fungsional yang mendeskripsikan persyaratan non fungsional yang berhubungan dengan kualitas sistem. Tabel 4.1 menunjukkan beberapa persyaratan fungsional yang harus dipenuhi oleh sistem. Tabel 4.1 Uraian Kebutuhan Fungsional No
Analisa Fungsional
1.
Menampilkan proses kerja dari algoritma Next-Fit, First Fit dan Best Fit
2.
Menampilkan interface untuk bermain bin packing problem
3.
Memiliki fitur interaktif pada bagian tutorial seperti proses, pause dan back
25
26
Tabel 4.2 menunjukkan beberapa persyaratan non-fungsional yang harus dipenuhi oleh sistem. Tabel 4.2 Uraian Kebutuhan Non-Fungsional No
Kebutuhan Non-Fungsional
1.
Perangkat lunak harus intuitif dan mudah dimengerti.
2.
Perangkat lunak tidak memerlukan perangkat dukung tambahan lainnya dalam proses eksekusinya. Perangkat lunak yang dibutuhkan hanya Microsoft Visual Basic 2010.
3.
Perangkat lunak akan menampilkan pesan kesalahan apabila terdapat kesalahan atau kegagalan sistem.
3.9.2
Alur Kerja Perangkat Lunak Aplikasi permainan bin packing problem ini menjelaskan proses alokasi
memori dengan menggunakan First-fit algorithm, Next-fit algorithm, dan Best-fit algorithm. Proses kerja dari perangkat lunak ini dimulai dengan menampilkan form ‘Main’ yang berisi menu-menu yang berfungsi untuk menghubungkan formform yang ada pada perangkat lunak. Apabila pemakai ingin menampilkan teori-teori yang berhubungan dengan algoritma Next-Fit, First Fit dan Best Fit, maka dapat mengklik menu ‘Teori’ dan memilih sub menu jenis teori yang diinginkan. Setelah itu, perangkat lunak akan menampilkan form ‘Teori’. Apabila pemakai ingin melakukan peng-input-an keadaan awal dari proses simulasi, maka dapat mengklik menu ‘Tutorial’ dan memilih sub menu ‘Input Data’. Setelah itu, perangkat lunak akan menampilkan
27
form ‘Input’. Sedangkan, apabila pemakai ingin menampilkan proses simulasi dari algoritma Next-Fit, First Fit dan Best Fit, maka dapat mengklik menu ‘Proses Kerja’ dan memilih sub menu algoritma yang diinginkan. Setelah itu, perangkat lunak akan menampilkan form ‘Proses’. Untuk menyelesaikan bin packing problem secara manual atau bermain bin packing problem, maka pemakai dapat mengklik menu ‘Permainan’. Sedangkan, untuk melihat data-data pribadi dari pembuat perangkat lunak maka dapat mengklik menu ‘About’ dan untuk keluar dari perangkat lunak dapat mengklik menu ‘Keluar’. Alur kerja dari perangkat lunak ini dapat dilihat pada penjabaran dalam bentuk gambar seperti berikut ini :
Gambar 4.1 Diagram Alur dari Perangkat Lunak
3.9.3
Proses Kerja dari Algoritma Bin Packing Problem Alokasi harus mencari bin yang ukurannya mencukupi memuat item
barang yaitu bin kosong yang sama atau lebih besar dibandingkan ukuran item
28
barang. Terdapat beragam algoritma yang dapat digunakan untuk melakukan proses bin packing, antara lain First-fit algorithm, Next-fit algorithm, dan Best-fit algorithm. Pada First-fit algorithm, akan di-scan sampai menemukan bin yang mencukupi penempatan proses. Mekanisme Next-fit algorithm sama dengan Firstfit algorithm, hanya saja perbedaannya alokasi memori untuk proses kedua dan selanjutnya dimulai dari posisi pointer terakhir kali ditemukan bin yang cocok. Sedangkan, Best-fit algorithm mencari sampai akhir dan mengambil bin terkecil yang dapat memuat item barang. Algoritma ini mencoba menemukan bin yang mendekati ukuran yang diperlukan. Penjelasan dari ketiga algoritma diatas yaitu : 1. First-fit algorithm menemukan bin lebih cepat dibandingkan dengan next-fit algorithm atau best-fit algorithm. 2. Next-fit algorithm berkinerja lebih buruk dibandingkan first-fit algorithm. 3. Best-fit algorithm menghasilkan solusi terbaik karena Best-fit algorithm selalu mengisi bin kecil yang tak digunakan. Tutorial algoritma bin packing problem ini memiliki tahapan proses sebagai berikut : 1. Proses pencarian bin yang dapat ditempati oleh item barang. a. Untuk algoritma First-fit, proses akan mencari bin yang mampu menempatkan item barang tersebut. Proses akan dihentikan apabila ditemukan sebuah bin yang mampu untuk menempatkan item barang tersebut. Proses pencarian bin untuk item barang selanjutnya akan dimulai dari awal.
29
b. Untuk algoritma Next-fit, proses akan mencari bin yang mampu menempatkan proses tersebut. Proses akan dihentikan apabila ditemukan sebuah bin yang mampu untuk menempatkan proses tersebut. Proses pencarian bin untuk item barang selanjutnya akan dimulai dari posisi terakhir ditemukan bin kosong. c. Untuk algoritma Best-fit, proses akan mencari bin terkecil yang mampu untuk menempatkan item barang tersebut. Proses akan mencari sampai bin terakhir dan memilih sebuah bin memori terkecil yang mampu untuk ditempati oleh item barang. 2. Proses penempatan item barang ke dalam bin tersebut.
Prosedur kerja dari sistem yang dirancang dapat digambarkan seperti terlihat pada diagram konteks dan data flow diagram (DFD) berikut ini:
Gambar 4.2 Diagram Konteks Sistem
30
Diagram konteks diatas dapat dirincikan lebih lanjut seperti terlihat pada gambar DFD Level 0 berikut ini:
Gambar 4.3 Data Flow Diagram (DFD) Level 0 dari Sistem
3.9.4
Aturan Permainan Aturan permainan yang terdapat pada permainan bin packing problem
yang akan dibangun dapat dirincikan sebagai berikut:
31
1. Permainan dimulai dari level 1 (satu) dengan jumlah item barang yang harus dimasukkan ke bin minimal sebanyak 2 buah. Jumlah bin minimal terdapat sebanyak 4 buah. 2. Berat item barang dan bin akan dihasilkan secara otomatis oleh komputer. 3. Jumlah maksimal item barang adalah sebanyak 12 buah. Hal ini berarti bahwa apabila jumlah item barang telah mencapai 12 buah, maka tidak akan terjadi penambahan item barang lagi untuk level berikutnya. 4. Pemain tidak boleh memakai ukuran berat bin yang melebihi ukuran berat bin maksimal yang telah ditentukan berdasarkan pemilihan tingkat kesulitan. 5. Permainan ini terdiri dari tiga jenis kesulitan, yaitu: a. Tingkat ‘Mudah’, dimana berat keranjang maksimum pada permainan yang dimainkan akan dihasilkan dengan menggunakan algoritma First Fit. b. Tingkat ‘Sedang’, dimana berat keranjang maksimum pada permainan yang dimainkan akan dihasilkan dengan menggunakan algoritma Next Fit. c. Tingkat ‘Susah’, dimana berat keranjang maksimum pada permainan yang dimainkan akan dihasilkan dengan menggunakan algoritma Best Fit. 6. Pada level 1, pemain diberikan 30 detik untuk menyelesaikan permainan untuk mencapai batasan nilai tertentu. 7. Sisa waktu pada setiap level akan diakumulasikan ke level berikutnya. 8. Jumlah waktu akan semakin berkurang seiring dengan semakin tinggi level permainan. Waktu akan berkurang 1 detik per kenaikan level, hingga jumlah waktu mencapai 30 detik. Setelah itu, tidak akan terjadi pengurangan waktu lagi pada saat kenaikan level.
32
9. Aplikasi juga akan menyimpan daftar nilai yang diperoleh pemain sehingga dapat ditampilkan daftar nilai tertinggi yang diperoleh pemain.
3.10.
Perancangan Perancangan sistem yang dibuat dapat dikelompokkan menjadi beberapa
bagian, yaitu perancangan menu, perancangan tampilan dan perancangan database.
3.10.1 Perancangan Menu Perangkat lunak bantu pemahaman ini dirancang dengan menggunakan bahasa pemrograman Microsoft Visual Basic 2010 dan menggunakan fasilitas menu strip untuk membuat dan mengatur tampilan menu. 1 : Menu ‘Teori’, berfungsi untuk menampilkan teori-teori yang berhubungan dengan bin packing problem. Menu ini memiliki beberapa sub menu antara lain : a. Sub menu ‘Algoritma First-fit‘, berfungsi untuk menampilkan teori mengenai algoritma First-fit. b. Sub menu ‘Algoritma Next-fit‘, berfungsi untuk menampilkan teori mengenai algoritma Next-fit. c. Sub menu ‘Algoritma Best-fit‘, berfungsi untuk menampilkan teori mengenai algoritma Best-fit. 2 : Menu ‘Tutorial’, memiliki beberapa sub menu antara lain : a. Sub menu ‘Input Data’, berfungsi untuk melakukan peng-input-an data keadaan awal yang diperlukan dalam tutorial.
33
b. Sub
menu
‘Algoritma
First-fit’,
berfungsi
untuk
menampilkan
penyelesaian bin packing problem dengan menggunakan algoritma Firstfit. c. Sub
menu
‘Algoritma
Next-fit’,
berfungsi
untuk
menampilkan
penyelesaian bin packing problem dengan menggunakan algoritma Nextfit. d. Sub
menu
‘Algoritma
Best-fit’,
berfungsi
untuk
menampilkan
penyelesaian bin packing problem dengan menggunakan algoritma Bestfit. 3 : Menu ‘Permainan’, berfungsi untuk menampilkan interface bagi pemain yang ingin bermain mencari solusi dari bin packing problem, memiliki beberapa sub menu antara lain : a. Sub menu ‘Pilih Pemain’, berfungsi untuk memilih nama pemain ataupun membuat nama pemain baru. b. Sub menu ‘Bermain’, berfungsi untuk bermain bin packing problem sesuai dengan tingkat kesulitan yang dipilih. c. Sub menu ‘High Score’, berfungsi untuk menampilkan 10 nilai tertinggi yang diperoleh pemain. 4 : Menu ‘About’, berfungsi untuk menampilkan data-data pribadi dari pembuat perangkat lunak. 5 : Menu ‘Keluar’, berfungsi untuk menutup perangkat lunak. Secara ringkas, menu-menu yang terdapat pada perangkat lunak ini dapat digambarkan seperti gambar berikut ini :
34
Gambar 4.4 Rancangan Menu pada Perangkat Lunak
3.10.2 Perancangan Tampilan Perangkat lunak ini dirancang dengan menggunakan beberapa buah form, yaitu: 1. Form ‘Main’, yang memiliki fasilitas menu dan merupakan tempat tampilan semua proses eksekusi dan animasi. 2. Form ‘Input’, yang digunakan untuk meng-input data-data keadaan awal dari proses simulasi. 3. Form ‘Proses’, yang digunakan untuk menampilkan proses simulasi terhadap algoritma alokasi memori. 4. Form ‘Teori’, yang digunakan untuk menampilkan teori-teori yang berhubungan dengan algoritma alokasi memori. 5. Form ‘Pilih Pemain’, yang digunakan untuk memilih nama pemain yang akan digunakan dalam permainan. 6. Form ‘Kesulitan’, yang digunakan untuk memilih tingkat kesulitan dari permainan. 7. Form ‘Permainan’, yang digunakan untuk bermain mencari solusi dari bin packing problem.
35
8. Form ‘High Score’, yang digunakan untuk menampilkan daftar 10 nilai tertinggi. 9. Form ‘About’, yang digunakan untuk menampilkan data-data pribadi dari penyusun.
4.2.2.1. Form Main Fungsi dari form ini adalah sebagai penghubung ke form-form lainnya pada perangkat lunak. Form ini merupakan form utama dari perangkat lunak yang berisi menu-menu. Rancangan form ‘Main’ ini dapat dilihat pada gambar 4.5 berikut ini :
Gambar 4.5 Rancangan Form ‘Main’ Keterangan : 1 : Title bar. 2 : Tombol ‘X’, berfungsi untuk keluar dari perangkat lunak. 3 : Menu bar.
36
4.2.2.2. Form Teori Fungsi dari form ini adalah untuk menampilkan teori-teori yang berhubungan dengan bin packing problem. Form ini akan menampilkan teori dari algoritma Next-Fit, First Fit dan Best Fit. Rancangan form ini dapat dilihat pada gambar 4.6 berikut ini :
Gambar 4.6 Rancangan Form ‘Teori’ Keterangan : 1 : Title bar, berisikan tulisan ‘Teori …’. 2 : Tombol ‘X’, berfungsi untuk menutup form dan kembali ke form ‘Main’. 3 : Daerah tampilan judul teori 4 : Daerah tampilan teori. 5 : Tombol ‘<< Back’, berfungsi untuk menampilkan halaman teori sebelumnya. 6 : Tombol ‘Next >>’, berfungsi untuk menampilkan halaman teori selanjutnya. 7 : Tombol ‘Keluar’, berfungsi untuk menutup form dan kembali ke form ‘Main’.
37
4.2.2.3. Form Input Fungsi dari form ini adalah sebagai tempat peng-input-an data keadaan awal yang diperlukan dalam tutorial. Rancangan form ini dapat dilihat pada gambar 4.7 berikut ini :
Gambar 4.7 Rancangan Form ‘Input’ Keterangan : 1 : Title bar, berisikan tulisan ‘Input Keadaan Awal …’. 2 : Tombol ‘X’, berfungsi untuk menutup form dan kembali ke form ‘Main’. 3 : Textbox ‘Ukuran Bin’, berfungsi sebagai tempat pengisian ukuran bin.
38
4 : Tombol ‘Masukkan ke Tabel’, berfungsi untuk memasukkan ukuran bin ke dalam tabel. 5 : Tombol ‘Hapus dari Tabel’, berfungsi untuk menghapus ukuran bin yang dipilih pada tabel dari database. 6 : Tabel ‘Bin’, berfungsi untuk menampilkan data ukuran dari setiap bin. 7 : Tombol ‘Kosongkan’, berfungsi untuk mengosongkan ukuran bin. 8 : Tombol ‘Acak’, berfungsi untuk mengisi ukuran bin secara acak. 9 : Textbox ‘Ukuran Barang’, berfungsi sebagai tempat pengisian ukuran barang. 10: Tabel ‘Item Barang’, berfungsi untuk mengisi ukuran item barang. 11: Tombol ‘Masukkan ke Tabel’, berfungsi untuk memasukkan ukuran barang ke dalam tabel. 12: Tombol ‘Hapus dari Tabel’, berfungsi untuk menghapus ukuran barang dari tabel. 13: Tombol ‘Kosongkan’, berfungsi untuk mengosongkan tabel item barang. 14: Tombol ‘Acak’, berfungsi untuk mengisi ukuran item barang secara acak. 15: Tombol ‘Set’, berfungsi untuk menyimpan semua data input. 16: Tombol ‘Batal’, berfungsi untuk menutup form dan kembali ke form ‘Main’.
4.2.2.4. Form Proses Fungsi dari form ini adalah untuk menampilkan proses kerja dari algoritma pencarian solusi bin packing problem. Rancangan form ini dapat dilihat pada gambar 4.8 berikut ini :
39
Gambar 4.8 Rancangan Form ‘Proses’ Keterangan : 1 : Daerah tampilan gambar barang yang akan dimasukkan. 2 : Daerah tampilan langkah yang sedang dilakukan. 3 : Daerah visualisasi. 4 : Tombol ‘Proses’, berfungsi untuk memulai proses simulasi. 5 : Tombol ‘Keluar’, berfungsi untuk menutup form dan kembali ke form ‘Main’. 6 : Radiobutton, dipilih apabila ingin menggunakan algoritma First Fit dalam mencari solusi. 7 : Radiobutton, dipilih apabila ingin menggunakan algoritma Next Fit dalam mencari solusi. 8 : Radiobutton, dipilih apabila ingin menggunakan algoritma Best Fit dalam mencari solusi. 9 : Daerah tampilan lama waktu eksekusi.
40
4.2.2.5. Form Pilih Pemain Form ‘Pilih Pemain’, yang berfungsi untuk menampilkan sepuluh nilai tertinggi yang diperoleh pemain. Rancangan tampilan dari form ‘Pilih Pemain’ ini dapat dilihat pada gambar 4.9 berikut ini:
Gambar 4.9 Rancangan Form Pilihan Pemain Keterangan : 1 : listbox ‘Nama Pemain’ berfungsi untuk menampilkan daftar nama pemain yang tersimpan dalam database. 2 : tombol ‘Tambah’ yang berfungsi untuk menambah nama pemain baru. 3 : tombol ‘Pilih’ yang berfungsi untuk menyimpan nama pemain yang dipilih ke dalam memori sementara, sehingga dapat digunakan pada form ‘Kuis’. 4 : tombol ‘Hapus’ yang berfungsi untuk menghapus nama pemain yang dipilih. 5 : tombol ‘Batal’ yang berfungsi untuk menutup form dan kembali ke form Main.
41
4.2.2.6. Form Kesulitan Form ‘Kesulitan’, yang berfungsi sebagai tempat pemilihan tingkat kesulitan. Rancangan tampilan dari form ‘Kesulitan’ ini dapat dilihat pada gambar 4.10 berikut ini:
Gambar 4.10 Rancangan Form Kesulitan
4.2.2.7. Form Permainan Fungsi dari form ini adalah untuk bermain mencari solusi dari bin packing problem. Rancangan form ini dapat dilihat pada gambar 4.11 berikut ini :
42
2
1 Waktu (detik)
4
3
Sisa Item
Berat Keranjang Maksimum
5 x
Nilai
Level 6
7
Total Item
Berat buah yang sudah dipindahkan
8
Berat Keranjang Terpakai
9
Gambar 4.11 Rancangan Form ‘Permainan’ Keterangan : 1 : Label untuk menampilkan sisa waktu permainan. 2 : Label untuk menampilkan sisa item yang belum diambil. 3 : Label untuk menampilkan berat keranjang maksimum dari permainan. 4 : Label untuk menampilkan nilai yang diperoleh pemain. 5 : Tombol ‘x’, berfungsi untuk mengakhiri permainan. 6 : Label untuk menampilkan level permainan. 7 : Daerah permainan. 8 : Label untuk menampilkan berat buah yang sudah dipindahkan. 9 : Label untuk menampilkan total item yang sudah dipindahkan. 10: Label untuk menampilkan berat keranjang yang sudah terpakai.
10
43
4.2.2.8. Form High Score Form ‘High Score’, yang berfungsi untuk menampilkan sepuluh nilai tertinggi yang diperoleh pemain. Rancangan tampilan dari form ‘High Score’ ini dapat dilihat pada gambar 4.12 berikut ini:
Gambar 4.12 Rancangan Form ‘High Score’ Keterangan: 1 : listview ’Nilai’, untuk menampilkan nilai yang diperoleh pemain. 2 : tombol ’Hapus’, untuk menghapus data nilai pemain yang tersimpan dalam database. 3 : tombol ’Keluar’, untuk menutup form.
4.2.2.9. Form About Fungsi dari form ini adalah untuk menampilkan data-data pribadi mengenai pembuat perangkat lunak (programmer). Rancangan form ini dapat dilihat pada gambar 4.13 berikut ini :
44
Gambar 4.13 Rancangan Form ‘About’ Keterangan : 1 : nama perangkat lunak. 2 : nama jurusan dan nama kampus. 3 : tombol ’Tutup’, untuk menutup form.
3.10.3 Perancangan Database Perancangan database dilakukan dengan menggunakan Microsoft Access 2007. Desain database dimaksudkan untuk mendefinisikan isi atau struktur tabel. Adapun entitas yang digunakan dalam perancangan database adalah sebagai berikut. 1. Tabel HighScore yang digunakan untuk menyimpan data 10 nilai tertinggi dari user. Tabel 4.3 menunjukkan struktur tabel HighScore pada database. Tabel 4.3 Tabel HighScore Field Name
Data Type
NamaUser
Text
45
Nilai
Number
Tingkat
Number
2. Tabel UserList yang digunakan untuk menyimpan data user yang terdaftar dalam sistem. Tabel 4.4 menunjukkan struktur tabel UserList pada database. Tabel 4.4 Tabel UserList Field Name
Data Type
NamaUser
Text
Keterangan
Text
BAB V HASIL DAN PEMBAHASAN
5.1.
Hasil Berikut dijabarkan spesifikasi perangkat keras dan perangkat lunak yang
digunakan untuk menjalankan aplikasi dan tampilan output dari sistem.
5.1.1. Spesifikasi Perangkat Keras dan Perangkat Lunak Perangkat keras dan perangkat lunak yang digunakan untuk menjalankan aplikasi permainan Bin Packing Problem yang dilengkapi tutorial dengan algoritma Next-Fit, First Fit dan Best Fit ini memiliki spesifikasi sebagai berikut: 1.
Prosesor Dual Core 2.9 GHz.
2.
Memory 1 GB.
3.
Monitor dengan resolusi 1028 × 768 pixel.
4.
Keyboard dan Mouse.
5.
Harddisk 100 GB.
6.
Speaker Perangkat lunak ini direkomendasikan untuk dijalankan di sistem operasi
Microsoft
Windows
XP/7.
Software
pendukung
yang
digunakan
yaitu
Microsoft.NET Framework 4.0.
5.1.2. Hasil Untuk menjalankan aplikasi permainan Bin Packing Problem yang dilengkapi tutorial dengan algoritma Next-Fit, First Fit dan Best Fit, maka dapat
46
47
mengklik file ‘BinPacking.exe’ sehingga sistem akan menampilkan tampilan awal berikut:
Gambar 5.1 Tampilan Awal Untuk belajar mengenai langkah kerja dari algoritma First Fit, Next Fit dan Best Fit, maka dapat mengklik menu ‘Tutorial’ seperti terlihat pada gambar berikut:
Gambar 5.2 Tampilan Menu Tutorial Sebelum dapat menampilkan tutorial proses kerja dari setiap algoritma, maka harus dilakukan pengisian data keadaan awal terlebih dahulu. Caranya adalah dengan mengklik sub menu ‘Input Data’ sehingga sistem akan menampilkan form Input Data seperti terlihat pada gambar berikut:
48
Gambar 5.3 Tampilan Form Input Data Isikan data ‘Ukuran Bin’ dan ‘Ukuran Item Barang’ yang terdapat dalam sistem tutorial. Caranya adalah mengetikkan ukuran bin dan item barang pada textbox yang bersesuaian dan klik tombol ‘Masukkan ke Tabel’. Sementara itu, apabila ingin menghapus data ukuran bin dan item barang yang telah dimasukkan dalam tabel, maka dapat mengklik tombol ‘Hapus dari Tabel’. Apabila pemakai tidak ingin melakukan pengisian data dan ingin agar data ukuran bin dan item barang dihasilkan secara otomatis oleh sistem, maka dapat mengklik tombol ‘Acak’, sehingga sistem akan menghasilkan data ‘Ukuran Bin’ dan ‘Ukuran Item Barang’ secara acak. Sementara itu, apabila ingin mengosongkan semua data input, maka dapat mengklik tombol ‘Kosongkan’.
49
Terakhir, pemakai dapat memilih jenis algoritma yang ingin ditampilkan tutorial proses kerjanya dan mengklik tombol ‘Set’ untuk menyimpan semua data input keadaan awal ke dalam memori sementara. Tampilan form Input Data setelah pengisian data dapat dilihat pada gambar berikut:
Gambar 5.4 Tampilan Form Input Data Setelah Pengisian Data Setelah selesai melakukan pengisian data, maka pemakai dapat menampilkan tutorial proses kerja dengan cara mengklik sub menu ‘Proses’ sehingga sistem akan menampilkan form Tutorial berikut:
50
Gambar 5.5 Tampilan Form Tutorial Klik tombol ‘Proses’ untuk memulai proses simulasi. Tampilan form akan terlihat seperti gambar berikut:
Gambar 5.6 Tampilan Form Tutorial pada Saat Menampilkan Proses Kerja Algoritma
51
Setelah proses kerja selesai, maka sistem akan menampilkan informasi mengenai hasil output dari algoritma yang dijalankan seperti terlihat pada gambar berikut:
Gambar 5.7 Tampilan Form Tutorial pada Setelah Proses First Fit Selesai
Gambar 5.8 Tampilan Form Tutorial pada Setelah Proses Next Fit Selesai
52
Gambar 5.9 Tampilan Form Tutorial pada Setelah Proses Best Fit Selesai Untuk bermain Bin Packing Problem, maka pemakai harus memasukkan nama pemain terlebih dahulu, sehingga sistem akan menampilkan form ‘Pilih Pemain’, seperti terlihat pada gambar berikut:
Gambar 5.10 Tampilan Form Pilih Pemain
53
Apabila pemakai ingin memasukkan nama pemain baru, maka sistem akan menampilkan input box berikut:
Gambar 5.11 Tampilan Input Box
Setelah itu, pemakai dapat mengklik menu ‘Permainan’, sehingga sistem akan menampilkan form Tingkat Kesulitan berikut.
Gambar 5.12 Tampilan Tingkat Kesulitan
Kemudian, pemakai mengklik tombol ‘Set’ untuk melanjutkan ke form permainan seperti terlihat pada gambar berikut.
54
Gambar 5.13 Tampilan Permainan Pemain harus memilih ukuran bin yang paling mendekati ukuran item barang yang ditampilkan agar ukuran keranjang yang dipakai tidak melebihi berat keranjang maksimum. Tampilan permainan pada saat bermain dapat dilihat pada gambar berikut:
Gambar 5.14 Tampilan Permainan pada Saat Bermain
55
Pemain harus memindahkan semua barang sebelum waktu yang diberikan habis dan total berat keranjang terpakai harus lebih kecil atau sama dengan berat keranjang maksimum. Apabila pemain mampu menyelesaikan permainan sebelum waktu berakhir dan sesuai dengan ketentuan, maka permainan akan dilanjutkan ke level berikutnya. Apabila pemain tidak dapat menyelesaikan permainan dalam batasan waktu yang ditentukan, maka sistem akan menampilkan pesan kesalahan berikut:
Gambar 5.15 Tampilan Pesan Kesalahan Kemudian, pemakai dapat menampilkan daftar 10 nilai tertinggi yang diperoleh pemain dengan mengklik menu ‘Permainan’ >> ‘High Score’ sehingga sistem akan menampilkan form berikut:
Gambar 5.16 Tampilan High Score
56
Terakhir, apabila pemain ingin menampilkan data pribadi dari pembuat perangkat lunak, maka dapat mengklik menu ‘About’ sehingga sistem akan menampilkan form About seperti terlihat pada gambar berikut:
Gambar 5.16 Tampilan Form About
5.2.
Pembahasan Beberapa informasi yang dapat diperoleh dari hasil konstruksi perangkat lunak, yaitu:
1. Metode Best Fit akan selalu menghasilkan solusi terbaik dari bin packing problem. 2. Aplikasi dapat digunakan untuk mempelajari mengenai cara penyelesaian bin packing problem dengan menggunakan algoritma Next-Fit, First Fit dan Best Fit. 3. Aplikasi dapat digunakan untuk bermain bin packing problem. Sedangkan, kelemahan dari aplikasi permainan Bin Packing Problem yang dilengkapi tutorial dengan algoritma Next-Fit, First Fit dan Best Fit ini yaitu: 1. Software tidak dapat dimainkan pada jaringan komputer ataupun internet.
57
2. Software tidak menyediakan fasilitas penentuan ukuran bin dan item barang untuk permainan. 3. Aplikasi permainan ini tidak dapat dimainkan pada perangkat mobile berbasis android.
5.3.
Algoritma Algoritma yang digunakan dalam merancang aplikasi permainan Bin
Packing Problem yang dilengkapi tutorial dengan algoritma Next-Fit, First Fit dan Best Fit ini dapat dibagi menjadi 3 bagian yaitu : 1. Algoritma First Fit. Algoritma ini akan menggunakan algoritma First Fit untuk mencari solusi dari bin packing problem. Rincian langkah kerja dari algoritma ini adalah: For i = 1 To ArrBarang.GetUpperBound(0) nIndex = 0 Do nIndex += 1 Loop Until (ArrBin(nIndex).Berat >= ArrBarang(i) And ArrBin(nIndex).Isi = "") Or nIndex = ArrBin.GetUpperBound(0) If ArrBin(nIndex).Berat >= ArrBarang(i) And ArrBin(nIndex).Isi = "" Then ArrBin(nIndex).Isi = i Hasil += ArrBin(nIndex).Berat Else Return 0 End If Next
2. Algoritma Next Fit. Algoritma ini akan menggunakan algoritma Next Fit untuk mencari solusi dari bin packing problem. Rincian langkah kerja dari algoritma ini adalah sebagai berikut: nIndex = 0 For i = 1 To ArrBarang.GetUpperBound(0)
58
Do nIndex += 1 If nIndex > ArrBin.GetUpperBound(0) Then nLoop += 1 nIndex -= ArrBin.GetUpperBound(0) End If Loop Until (ArrBin(nIndex).Berat >= ArrBarang(i) And ArrBin(nIndex).Isi = "") Or nLoop = 2 'Or nIndex > ArrBin.GetUpperBound(0) If ArrBin(nIndex).Berat >= ArrBarang(i) And ArrBin(nIndex).Isi = "" Then ArrBin(nIndex).Isi = i Hasil += ArrBin(nIndex).Berat Else Return 0 End If Next
3. Algoritma Best Fit. Algoritma ini akan menggunakan algoritma Best Fit untuk mencari solusi dari bin packing problem. Rincian langkah kerja dari algoritma ini adalah sebagai berikut: For i = 1 To ArrBarang.GetUpperBound(0) 'Cari semua bin nSolusiIndex = 0 For j = 1 To ArrBin.GetUpperBound(0) If ArrBarang(i) <= ArrBin(j).Berat And ArrBin(j).Isi = "" And ArrBin(j).Berat < nSolusi Then nSolusi = ArrBin(j).Berat nSolusiIndex = j End If Next If nSolusiIndex > 0 Then ArrBin(nSolusiIndex).Isi = i Hasil += ArrBin(nSolusiIndex).Berat Else Return 0 End If Next
BAB VI KESIMPULAN DAN SARAN
6.1.Kesimpulan Setelah selesai mengkonstruksi perangkat lunak, penulis dapat mengambil beberapa kesimpulan berikut: 4. Metode Best Fit akan selalu menghasilkan solusi terbaik dari bin packing problem, jika dibandingkan dengan metode First Fit dan Next Fit. Hal ini dikarenakan metode Best Fit selalu akan mencari ukuran bin terkecil yang dapat mengisi item barang yang akan dimasukkan. 5. Aplikasi dapat digunakan untuk mempelajari mengenai cara penyelesaian bin packing problem dengan menggunakan algoritma Next-Fit, First Fit dan Best Fit. 6. Aplikasi dapat digunakan untuk bermain bin packing problem.
6.2.Saran Penulis ingin memberikan beberapa saran sehubungan dengan pengembangan perangkat lunak, seperti: 4. Aplikasi dapat dikembangkan dengan merancang permainan agar dapat dimainkan pada jaringan komputer ataupun internet. 5. Aplikasi dapat dikembangkan dengan memungkinkan pemain untuk menentukan sendiri ukuran bin dan item barangnya. 6. Aplikasi permainan ini dapat dikembangkan lagi sehingga dapat dimainkan pada perangkat mobile.
59
DAFTAR PUSTAKA
Diginnovac, M. Arry dan N. Karina, 2009, Draw and Animate with Flash, PT Elex Media Komputindo, Jakarta. Hariyanto, B., 2003, Struktur Data, Edisi Kedua, Informatika, Bandung. Hartono, J., 2010, Analisa & Desain Sistem Informasi : Pendekatan Terstruktur Teori dan Praktek Aplikasi Bisnis, Andi, Yogyakarta. Martello S. and Toth P., 1990, Knapsack Problems : Algorithms and Computer Implementations, John Wiley & Sons. Pressman, R.S., 2002, Rekayasa Perangkat Lunak : Pendekatan Praktisi (Buku Satu), Mc Graw-Hill Companies, Inc, Penerbit ANDI. http://www.ummi.ac.id/ti/konvert_pdf.php?kode=VGxFOVBRPT0=
