PERANCANGAN PROGRAM APLIKASI OPTIMASI PELETAKAN POSISI LABEL KERTAS ATAU PLASTIK MENGGUNAKAN METODE A* HEURISTIC Wulan Permata Sari Program Ganda Teknik Informatika dan Matematika Bina Nusantara University Jalan KH. Syahdan No.9 Palmerah, Jakarta Barat 11480, Indonesia +6253696969
[email protected] Wulan Permata Sari; Wikaria Gazali, S.Si.,M.T.; Dr.Ir.Haryono Soeparno,M.Sc.
ABSTRACT
Optimization is intended that the basic material used can be used for a minimum and maximum label printing patterns. Labels can be made from raw materials of paper or plastic. Various patterns of label that can be made in this matter, that the pattern of square, rectangle, triangle, ellips, and circle size can be selected and their respective amounts. To resolve the optimization problem laying position paper or plastic labels must use appropriate methods in order to get the appropriate results. By using A * with heuristic function node search results not need any direction and get results more quickly and accurately in a laying position label. Keywords: optimization, paper or plastic label, A * Heuristic methods
ABSTRAK
Optimasi ini bertujuan agar bahan dasar yang digunakan dapat digunakan minimum dan pencetakan pola label yang maksimal. Label dapat dibuat dari bahan dasar kertas atau plastik. Macam-macam pola label yang dapat dibuat dalam masalah ini, yaitu pola persegi, persegi panjang, segitiga, ellips, dan lingkaran yang dapat dipilih ukurannya dan jumlahnya masingmasing. Untuk menyelesaikan masalah optimasi peletakan posisi label kertas atau plastic ini harus menggunakan metode yang tepat agar mendapatkan hasil yang sesuai. Dengan
menggunakan metode A* dengan fungsi heuristic hasil pencarian node tidak perlu ke segala arah dan mendapatkan hasil yang lebih cepat dan tepat dalam peletakan posisi label. Kata kunci: optimasi, label kertas atau plastik, metode A* Heuristic
PENDAHULUAN Setiap produk makanan, minuman, pakaian, elektronik, dan berbagai jenis barang lainnya memerlukan penempelan atau pemasangan label disetiap produk yang diproduksinya sebagai penanda, informasi produk, alamat, iklan, peringatan, dan komunikasi lainnya. Pencetakan label bisa pada bahan dasar kertas atau plastik. Pada industri pembuatan label diperlukan penekanan atau meminimumkan penggunaan bahan dasar tersebut dan dapat menghasilkan banyak label. Label sangat diperlukan dan terdapat berbagai macam model, jenis, serta fungsinya. Sehingga banyak perusahaan yang membuat usaha percetakan label untuk berbagai jenis produk. Untuk mendapatkan hasil yang optimal dalam percetakan banyak pola label diperlukan pengaturan peletakan posisi label yang tepat, sehingga tidak banyak bahan dasar yang terbuang saat pemotongan label dilakukan. Diperlukan sebuah rancangan program aplikasi yang dapat membuat satu gambaran pola label dalam sekali pencetakan dapat menghasilkan hasil yang optimal. Banyak jenis simbol pada kemasan pelabelan, baik secara nasional maupun secara standar internasional. Dan berbagai macam pola label, seperti pola lingkaran, persegi, persegi panjang, segitiga, dan sebagainya. Pencetakan label diperlukan bahan dasar yang sesuai dengan produk yang akan ditempelkan label, misalnya pada produk makanan menggunakan cetak label kertas atau plastik yang aman untuk jenis makanan, dan pada baju dapat menggunakan cetak label pada kain atau kertas. Dengan semakin banyaknya perusahaan yang bergerak dalam jasa pembuatan label dan banyaknya perusahaan label yang mencetak secara manual menjadi kurang optimal dalam peletakan label. Maka, penulis ingin membantu dengan membuat perancangan program aplikasi optimasi peletakan posisi label untuk mengoptimalkan peletakan posisi label dengan hasil pencetakan yang maksimal dengan waktu yang minimal. Label yang beraneka ragam pola dan ukurannya ini memerlukan peletakan posisi yang optimal untuk mengoptimalisasikan produksi pembuatan label. Dalam menyelesaikan program aplikasi optimasi peletakan posisi label digunakan metode A* dengan fungsi heuristic agar peletakan posisi label tidak perlu mencari ke segala arah tetapi langsung menempati posisi yang kosong yang berada didekat posisi label sebelumnya. Penulis berharap perancangan program aplikasi optimasi peletakan posisi label menggunakan metode A* heuristic dapat membantu perusahaan jasa pembuatan label dalam mengoptimalkan pencetakan label dan mempermudah pembuatan label dengan pola dan ukuran label yang berbeda.
METODE PENELITIAN a.
Metode Studi Kepustakaan Penulis mencari sumber buku, artikel, dan literatur internet yang terkait dengan optimasi, label, penyelesaian masalah metode A* heuristic, dan pembuatan program menggunakan bahasa C#. Kemudian mempelajari dan memahaminya sebagai penunjang penyusunan proposal skripsi.
b.
c.
Metode Analisis Dan Pembelajaran Setelah mencari sumber materi yang terkait, penulis melakukan analisa dan pembelajaran bahasa pemrograman C#, metode A* heuristic, pengertian label beserta pola dan cara pembuatan label. Metode Perancangan Penulis melakukan perancangan algoritma A* heuristic dan langkah-langkah dalam setiap tahapan dan melakukan perhitungan optimasi peletakan label, serta membuat perancangan program aplikasi yang mudah digunakan untuk perusahaan jasa pembuatan label.
HASIL DAN BAHASAN Menurut Wikipedia, label adalah sepotong kertas, polymer, kain, logam, atau bahan lain yang ditempelkan pada wadah atau benda yang dicetak sebagai informasi produk, alamat, dan lainlain. Label juga dapat langsung dicetak pada wadah atau benda. Sedangkan, pelabelan adalah setiap komunikasi tertulis, elektronik, atau gambar pada kemasan atau terpisah dari label terkait. Dalam ilmu komputer, A* (dibaca : A star) adalah sebuah graph atau metode tree search yang digunakan untuk mencari jalan dari sebuah node awal ke node tujuan yang telah ditentukan, metode ini mengunakan “estimasi heuristic” h(n) pada setiap node untuk mengurutkan setiap node n berdasarkan estimasi rute terbaik yang melalui node tersebut.
Gambar 1 Pseudocode Algoritma A* Metode A* hanya membangun rute yang mungkin digunakan untuk mencapai tujuan. Untuk mengetahui rute mana yang memungkinkan mengarah ke titik akhir, A* menggunakan estimasi heuristik jarak dari sembarang node ke node tujuan. Prinsip algoritma ini adalah mencari jalur terpendek dari sebuah simpul awal (starting point) menuju simpul tujuan dengan memperhatikan harga (F) terkecil. Secara umum, Depth First Search (DFS) dan Breadth First Search (BFS) adalah dua kasus spesial dari metode A*. Algoritma Dijkstra’s merupakan kasus spesial dari A*, dimana h(n) = 0, untuk semua n.
Menurut Amit. J. Patel (2003, p1), heuristic merupakan aturan-aturan untuk memilih cabang-cabang yang memiliki kemungkinan mengarah pada pemecahan masalah. Heuristic dapat membantu menunjukkan arah yang tepat bagi suatu algoritma, tetapi mungkin juga gagal dalam memberikan petunjuk kepada algoritma tersebut. A* mempertahankan sebagian dari solusi, sebagai contoh jalur pada graph dimulai dari node awal, dan akan disimpan dalam sebuah queue yang disebut priority queue. Prioritas yang diberikan ke sebuah jalur n ditentukan oleh fungsi : f(n) = g(n) + h(n) Dimana, g(n) adalah nilai cost dari path yang telah ditemukan, yaitu berat atau bobot dari jalur antar node yang telah dilalui. h(n) adalah estimasi heuristic dari nilai cost paling minimal yang digunakan atau didapat untuk menapai goal dari n. semakin besar nilai f(n), maka semakin besar prioritasnya. Pada kasus ini, fungsi f(n) = g(n) + h(n) didefinisikan sebagai berikut: • g(n) adalah heuristic luas g(n) = width_pola * height_pola Perhitungan ini untuk menentukan pola label mana yang akan diletakkan pertama kali. • h(n) adalah fungsi heuristic h(n) = (((kel_alas – batas_alas) + (kel_pola – batas_alas)) – pola_dempet) + nilai_tambahan nilai h(n) pertama dibandingkan dengan h(n) yang lainnya, hingga ditemukan nilai h(n) yang paling minimal. kel_alas = keliling alas kertas atau plastik batas_alas = pola label yang terkena pembatas alas kel_pola = keliling pola label pola_dempet = pola label yang saling berdempetan nilai_tambahan = pemberian nilai tambah agar tidak saling bersinggungan/berdempetan. Terdapat banyaknya permasalahan dari berbagai perusahaan tempat pembuatan label tersebut, maka dibuat sebuat software yang dapat membantu peletakkan posisi label kertas atau plastik yang akan dibuat menjadi optimal. Dengan permasalahan yang telah diketahui, maka software yang akan dikembangkan memiliki kemampuan sebagai berikut : 1. Memaksimalkan penggunaan bahan kertas atau plastik yang tersedia dan meminimalkan bahan yang tidak terpakai dengan batasan-batasan yang ada. 2. Label yang diletakkan berupa pola persegi, persegi panjang, lingkaran, segitiga, dan ellips dengan berbagai macam ukuran dan jumlah yang tidak melebihi ukuran bahan kertas atau plastik yang dipergunakan. Dengan dikembangkannya software optimasi peletakan posisi label kertas atau plastik ini dapat membantu para perusahaan pembuatan label untuk mendapatkan hasil yang optimal, lebih cepat, akurat, serta efisien.
Gambar 2 Skema Rancangan Program
Gambar 3 Use Case Diagram
Program ini dibuat dengan tujuan mencari peletakan posisi label yang optimal dari bahan kertas atau plastik. Dengan mengetahui peletakan posisi label tersebut maka penulis dapat mengetahui letak posisi yang optimal untuk label.
Jika user ingin mulai membuat program user hanya menekan button “Create Your Label” pada layar menu utama. Lalu akan terbuka layar Create Label, pada layar ini program diharuskan memilih pola label yang ingin dibuat, meng-input width, height, dan qty label yang ingin dibuat. Setelah itu user menekan button “Add”, maka data-data yang telah di-input akan tampil pada label list. Untuk melihat hasil optimasi peletakkan posisi label user menekan button “view”, maka akan terbuka layar view label yang berupa gambar hasil optimasi yang telah dihitung menggunakan metode A* heuristic. Jika user ingin menyimpan hasil optimasi user hanya menekan button “Save”, maka akan tersimpan dalam format JPEG (*.jpg) dan menekan button “Cancel” untuk menutup layar view label. Pada pilihan menu terdapat menu File dan Help. Pada menu File terdapat menu item Save dan Exit. Menu item save untuk menyimpan data dan menu item exit untuk menutup seluruh layar. Menu Help berisi menu item About yang berisi data informasi yang dapat user baca.
Gambar 4 Tampilan layar create label
Pada layar ini, user diminta untuk memilih pola label, width, height, dan qty label yang ingin dibuat. Jika data belum terisi semua maka ketika menekan button “Add” akan tampil message box “data must filled!!!”.
Gambar 5 Tampilan layar data yang telah diisi
Dan untuk menyimpan data-data yang telah di-add, user harus click menu File kemudian terdapat menu item Save. Setelah click menu item Save maka akan muncul kotak save file dialog dan setelah di save akan tampil message box yang berisi “Save Success!!!”. Tampilan layar View Label akan muncul seperti di bawah ini dengan hasil optimasi peletakkan posisi label berdasarkan data-data yang telah di-input oleh user.
Gambar 6 Tampilan layar view label Jika user menekan button “Cancel” maka layar view label akan tertutup, dan Jika user ingin menyimpan hasil optimasi maka user harus menekan button “Save” dan akan muncul save file dialog. Hasil optimasi akan tersimpan dalam file dengan format JPEG (*.jpg). Walaupun program aplikasi optimasi peletakan posisi label memiliki beberapa kelebihan, tetapi program ini masih belum dapat dinyatakan sebagai sebuah program yang paling optimal karena sampai saat ini pun masih belum ada sebuah program yang dapat dinyatakan paling optimal. Selain itu, program ini hanya dapat digunakan bagi pengguna atau perusahaan yang menyangkut dalam pembuatan atau produksi label, kecepatan waktu untuk output tergantung dari jumlah pola dan ukuran pola yang di pilih, dan pemakaian memori yang digunakan akan lebih banyak jika jumlah yang dipilih semakin banyak.
SIMPULAN DAN SARAN Berdasarkan hasil pengujian terhadap program aplikasi dan pembahasan, maka dapat ditarik kesimpulan sebagai berikut : 1. Perangkat lunak ini dapat diimplementasikan dengan cukup baik dengan arti dapat memberi keputusan untuk mendapatkan hasil yang optimal pada peletakan posisi label kertas atau plastik. 2. Program mampu melakukan perhitungan dimulai dari meng-input sampai menemukan posisi yang optimal. 3. User dapat melihat hasil eksekusi program optimasi peletakan posisi label kertas atau plastik menggunakan metode A* heuristic. 4. Metode dan algoritma A* heuristic dapat digunakan dan diimplementasikan untuk mencari solusi yang optimal dalam permasalahan peletakan posisi label kertas atau plastik.
5. 6.
Proses optimasi dengan menggunakan metode A* heuristic akan memakan waktu yang lebih lama, jika banyaknya ukuran dan jumlah pola label yang digunakan. Perancangan program aplikasi optimasi peletakan posisi label kertas atau plastik menggunakan metode A* heuristic ini dapat menghemat waktu, meminimalkan ruang kosong, serta menghemat biaya produksi.
Adapun saran yang dapat ditambahkan untuk meningkatkan kinerja program ini agar menjadi lebih baik tiap tahapannya, adalah sebagai berikut : 1. Program yang telah dibuat ini tentunya masih mempunyai beberapa kekurangan yang dikarenakan oleh keterbatasan waktu, kemampuan, pengetahuan, serta masalah non-teknis lainnya yang terjadi dalam pembuatan program ini. 2. Dalam pengembangan program selanjutnya diharapkan dengan sistem yang memiliki Graphic User Interface yang lebih baik dari yang digunakan dalam program ini. 3. Program ini hanya mencetak hasil pola dalam bentuk dua dimensi, sehingga diharapkan bisa mencetak pola label dengan bentuk tiga dimensi atau berbagai bentuk lainnya. 4. Program aplikasi ini dapat dilanjutkan dengan tidak hanya membuat pola label saja tetapi juga dapat desain gambar dan tulisan pada label, dan bahan yang digunakan bukan hanya terbuat dari kertas atau plastik. 5. Diharapkan pada program selanjutnya, proses hasil eksekusi dapat lebih cepat dan memori yang digunakan tidak terlalu banyak walaupun dengan banyaknya pola, ukuran, serta jumlah label yang digunakan.
REFERENSI Adit. (2008). Implementasi Algoritma A* Pada Permasalahan Optimasi Solusi Dynamic Water Jug. Aimyaya. (2013). Definisi Problem Optimasi. URL : http://aimyaya.com/id/komputer/definisiproblem-optimasi/. Akses : 17 Juni 2013 Amalia, Deisy. (2012). Best First Search. URL : http://deisyamalia.blogspot.com/2012/03/bestfirst-search.html . Akses : 15 Juli 2013. Anonymous. (2012). A* Search Algorithm. URL : http://en.wikipedia.org/wiki/A*_search_algorithm. Akses : 5 Desember 2012 Anonymous. (2013). Algoritma. URL : http://id.wikipedia.org/wiki/Algoritma. Akses : 17 Januari 2013 Anonymous. (2013). C Sharp. URL : http://id.wikipedia.org/wiki/C_sharp. Akses : 17 Januari 2013 Anonymous. (2012). Label. URL : http://en.wikipedia.org/wiki/Label. Akses : 19 Desember 2012 Anonymous. (2012). Label. URL : http://pdfcast.net/label. Akses : 19 Desember 2012 Anonymous. (2013). NP-Hard. URL : http://en.wikipedia.org/wiki/NP-hard. Akses : 10 Juli 2013 Anonymous. (2013). Pathfinding. URL : http://en.wikipedia.org/wiki/Pathfinding. Akses : 10 Juli 2013 Anonymous. (2011). Pengertian Dasar Tentang Optimasi. URL : http://duniaoptimasi.blogspot.com/2011/03/pengertian-dasar-tentang-optimasi.html. Akses : 17 Januari 2013 Anonymous. (2012). Penggunaan Berbagai Jenis Label. URL : http://id.prmob.net/produk/label/pengepakan-dan-pelabelan-112666.html. Akses : 17 Januari 2013 Anonymous. (2013). Unified Modeling Language. URL : http://id.wikipedia.org/wiki/Unified_Modeling_Language. Akses : 10 Juli 2013
Ariana,
Erika. (2009). Analisis Algoritma Pada Masalah Sorting. URL : http://id.scribd.com/doc/9710352/Analisis-Algoritma-Pada-Masalah-Sorting. Akses : 8 Juni 2013 Bentley, L. D., & Whitten, J. L. (2010). Systems Analysis & Design For The Global Enterprise 7 th Edition. New York : McGraw-Hill Companies Inc. Hart, P. E.; Nilsson, N. J.; Raphael, B. (1968). "A Formal Basis for the Heuristic Determination of Minimum Cost Paths". IEEE Transactions on Systems Science and Cybernetics SSC4 (2): pp. 100–107. Hidayat, Arif. (2013). Jenis Perangkat Lunak Beserta Fungsinya. URL : http://basicartikel.blogspot.com/2013/01/jenis-perangkat-lunak-beserta-fungsinya_24.html. Akses : 12 Juli 2013 Husse, Christoph. (2010). Fast A star 2D Implementasion for C. URL : http://www.codeproject.com/Articles/118015/Fast-A-Star-2D-Implementation-for-C. Akses : 5 Juli 2013 Kadarusman, Lulita. (2007). “Perancangan Program Aplikasi Opltimalisasi Dua Dimensi Cutting Box Pada Alas Mobil Box Menggunakan Metode A* Heuristic <Studi Kasus Pt Indonesia Bisnis Mandiri>”. Jakarta : Universitas Bina Nusantara. Krisna, Vamsi. (2012). Heuristic Function For Finding Path Using A Star . URL : http://stackoverflow.com/questions/9140860/heuristic-function-for-finding-the-path-usinga-star?rq=1. Akses : 10 Juli 2013 Nurmanto. (2011). Pengertian Heuristic Searching. URL : http://nurmanto.com/pengertianheuristic-seacrching/. Akses : 5 Juli 2013 Lester, Patrick. (2012). A* Pathfinding for Beginners. URL : http://www.policyalmanac.org/ games/aStarTutorial.htm. Akses : 5 Desember 2012 Patel, Amit.J. (2003). Amit’s Game Programmer Information. URL : http://www.csstudents.stamford.edu/~amitp/gameprog.html. Akses : 5 Juli 2013 Reydika, Ilham; Aryuanto Soetedjo; Ahmad Faisol. (2011). “Pengembangan Aplikasi Pencarian Rute Terpendek Dengan Metode Algoritma A* Berbasis Web”. Jurnal Elektro ELTEK (2) : pp. 171-175. Rofingun, Mat. (2007). Kemasan dan Label Produk. URL: http://matrofingun.wordpress.com/ 2007/06/25/kemasan-dan-label-produk. Akses : 6 Januari 2013 Svong. Definisi Algoritma dan Struktur Data. URL : http://id.shvoong.com/internet-andtechnologies/software/2114453-definisi-algoritma-dan-struktur-data. Akses : 17 Januari 2013 Widjaja, Eka Surya. (2012). “Perancangan Program Aplikasi Optimasi Penggambaran Pola Molding Pada Mesin Pencetakan Plastik Dengan Metode Tabu Search”. Jakarta : Universitas Bina Nusantara. Wipriyance, Luksie. (2011). What Is C#?. URL : http://binarycodecimal.blogspot.com/2011_04_01_archive.html. Akses : 17 Desember 2012 Yuliana; Ananda; Ibnu Surya. (2011). “Implementasi Algoritma A Star pada Pemecahan Puzzle 8”. Riau : Politeknik Caltek.
RIWAYAT PENULIS Wulan Permata Sari lahir di kota Jakarta pada tanggal 5 Juni 1991. Penulis menamatkan pendidikan S1 di Bina Nusantara University dalam jurusan Teknik Informatika dan Matematika.
