Karya Ilmiah Penerapan Metode Algoritma Genetika Untuk Penjadwalan Produksi

Karya Ilmiah Penerapan Metode Algoritma Genetika Untuk Penjadwalan Produksi

Konten [Tampil]
Karya Ilmiah Penerapan Metode Algoritma Genetika Untuk Penjadwalan Produksi 

Latar Belakang

Proses penjadwalanproduksi ataupun manufaktur dalam dunia industri merupakan hal yang sangat penting untuk diperhatikan. Pada dasarnya kegiatan Proses produksi dalam suatu Perusahaan manufaktur ataupun Jasa akan berjalan lancar  jika penyusunan jadwal sesuai dengan kebutuhan, serta kondisi di suatu lantai produksi tersebut. Proses penjadwalan di PT NAKAYAMA dilakukan secara continue dan merupakan hal yang rumit untuk dikerjakan secara manual. Selain itu penjadwalan yang manual akan memakan waktu yang lama karena banyaknya faktor yang harus dipertimbangkan.


Faktor-faktor tersebut antara lain adalah jumlah bahan baku yang disediakan, jumlah stasiun kerja, jumlah karyawan produksi, serta kebutuhan konsumen dan instansi lainnya juga menjadi pertimbangan dalam suatu penjadwalan. Misalnya, karyawan tidak boleh berkerja penuh dalam sehari, sehingga karyawan harus diberikan jeda atau waktu untuk beristirahat.

 

Distribusi jadwal proses produksi diharapkan dapat merata setiap harinya untuk setiap stasiun kerja dan merata juga untuk pembagian bahan baku agar tidak menumpuk jadwal produksinya dalam satu hari. Misalkan dalam satu hari bahan baku yang dianjurkan maksimal 2 kali atau sesuai peraturan yang diberikan oleh pihak perusahaan.

 

Selain itu sebuah jadwal dibentuk sedemikian rupa agar bahan baku tidak berhenti pada stasiun lainnya yang berbeda pada hari dan jam yang sama. Sebuah penjadwalan dikatakan baik apabila dapat memberikan solusi terhadap faktor-faktor tersebut, tentu saja tidak semua sistem penjadwalan memiliki permasalahan yang sama, karena disesuaikan dengan kebutuhan instansi ataupun tempat yang akan dilakukan penjadwalan.

 

Permasalahan di atas biasanya terjadi di Stasiun Pengecoran dan Peleburan Baja. Dari permasalahan-permasalahan tersebut diharapkan terdapat sistem yang mampu memecahkan setiap detail masalah yang muncul dalam proses penjadwalan di Stasiun Pengecoran dan Peleburan Baja. Banyak metode yang dapat digunakan dalam menyelesaikan masalah penjadwalan seperti metode tabu search (Betrianis & Aryawan, 2003), metode particle swarm optimization (Wati & Rochman, 2013), metode algoritma genetika (Sam'ani, 2012) serta metode optimasi koloni semut dan optimasi fuzzy (Ramadhan & Hamsi, 2013).

 

Dalam penelitian ini penulis akan menggunakan metode Algoritma Genetika untuk memecahkan masalah penjadwalan ini. Algoritma genetika merupakan salah satu metode optimasi yang kuat dan bisa digunakan pada berbagai macam studi kasus, baik kasus yang sederhana hingga kasus yang rumit karena menggunakan prinsip teori evolusi (Pradnyana, Sunaryono, & Munif, 2012). Penggunaan metode algoritma genetika pada penelitian ini diharapkan dapat membantu mengoptimalkan dan memenuhi segala permasalahan dalam penjadwalan produksi.

 

Selain itu dapat membuat sistem melakukan proses penjadwalan secara otomatis. Berdasarkan latar belakang di atas, maka penulis berusaha merancang sebuah sistem penjadwalan menggunakan metode algoritma genetika dan mengangkatnya menjadi sebuah penelitian yang berjudul Sistem Penjadwalan Produksi Spareparts Menggunakan Algoritma Genetika di PT NAKAYAMA.

 

Rumusan Masalah

Berdasarkan latar belakang yang telah dikemukakan, maka bisa dirumuskan masalah sebagai berikut:

  1. Bagaimana menerapkan metode algoritma genetika untuk menyelesaikan masalah optimasi penjadwalan produksi spareparts?
  2. Bagaimana menentukan representasi kromosom yang paling efisien untuk permasalahan optimasi penjadwalan produksi spareparts?
  3. Bagaimana parameter algoritma genetika yang paling optimal untuk menyelesaikan masalah optimasi penjadwalan produksi spareparts?

 

Batasan Masalah

  1. Batasan masalah yang akan dijadikan sebagai pedoman dalam pelaksanaan penelitian ini adalah sebagai berikut:
  2. Jenis produksi hanya terbatas pada spareparts otomotif dan kelompok sparepart  yang ada diminta oleh pasar.
  3. Parameter masukan berupa proses produksi, bahan baku dan jenis produk jadinya yang dipilih untuk diproses menggunakan algoritma genetika sehingga dihasilkan output berupa rekomendasi komposisi jenis produk beserta proporsi proses produksi dan prediksi keuntungan.
  4. Data yang dijadikan perhitungan dalam optimasi adalah data kuantitatif meliputi biaya produksi, bahan baku minimal dan hasil produksi pada masing-masing produk.

 

Tujuan dan Manfaaat Penelitian

1. Tujuan

Dari uraian pada latar belakang dan batasan masalah, maka tujuan dari penelitian ini adalah:

  1. Mengimplementasikan algoritma genetika untuk merekomendasikan proporsi proses produksi yang optimal untuk penjadwalan produksi spareparts.
  2. Mengetahui representasi kromosom yang efisien untuk permasalahan optimasi penjadwalan produksi spareparts.
  3. Menganalisa dan menguji penerapan algoritma genetika untuk optimasi penjadwalan produksi spareparts.

 

2. Manfaat

Hasil dari penelitian ini diharapkan dapat membantu proses penjadwalan produksi spareparts yang dilakukan di PT NAKAYAMA agar lebih cepat dan  mempermudah pembuatan jadwal produksi, selain itu bahan baku tidak akan squencing dalam sehari penuh dan para karyawan tidak dijadwalakan berurutan dalam sehari maka jadwal yang dihasilkan dapat memberikan jeda waktu karyawan dan permesinan dalam aktifitas proses produksi tersebut.

  

Tinjauan Pustaka

1. Algoritma Genetika

Algoritma Genetika (GA) digunakan untuk mengoptimasi parameter yang optimal dengan ruang lingkup yang besar, dengan pemilihan para-meter yang tepat algoritma genetika akan lebih optimal (Wang et al., 2013). Algoritma genetika memiliki kelemahan yaitu pemilihan parameter yang salah dapat mengurangi akurasi yang dihasilkan.

 

Permasalahan yang sering dihadapi oleh algoritma genetika adalah memperoleh solusi optimal setelah serangkaian melakukan perulangan, tetapi kejadian ini dapat dihindari dengan memilih nilai-nilai parameter yang tepat. GA adalah menemukan popularitas sebagai alat desain karena fleksibilitas, intuitif dan kemampuan untuk memecahkan sangat non-linear, optimasi mixed integer masalah (Khoshahval et al., 2011). Algoritma Genetika digunakan untuk meng-optimasi parameter yang optimal dengan ruang lingkup yang besar, dengan pemilihan parameter yang tepat algoritma genetika akan lebih optimal (Wang et al., 2013).

 

Algoritma genetika merupakan evolusi/perkembangan dunia komputer dalam bidang kecerdasan buatan (artificial intelligence). Sebenarnya kemunculan algoritma genetika ini terinspirasi oleh teori evolusi Darwin (walaupun pada kenyatanya teori tersebut terbukti keliru) dan teori-teori dalam ilmu biologi, sehingga banyak istilah dan konsep biologi yang digunakan.

 

Karena itu sesuai dengan namanya, proses-proses yang terjadi dalam algoritma genetika sama dengan apa yang terjadi pada evolusi biologi. Algoritma genetika merupakan teknik pencarian nilai optimum secara stochastic berdasarkan mekanisme seleksi alam. Algoritma genetika berbeda dengan teknik konvergensi konvensional yang lebih bersifat deterministic.

Metodenya sangat berbeda dengan kebanyakan algoritma optimasi lainnya, yaitu mempunyai ciri-cirinya sebagai berikut:

  1. Menggunakan hasil pengkodean dari parameter, bukan parameter itu
  2. sendiri.
  3. Bekerja pada populasi bukan pada sesuatu yang unik.
  4. Menggunakan nilai satu-satunya pada fungsi dalam prosesnya. Tidak
  5. mengunakan fungsi luar atau pengetahuan luar lainnya.
  6. Menggunakan fungsi transisi probabilitas, bukan sesuatu yang pasti

 


Alogritma genetika berbeda dengan teknik pencarian konvensional, dimana pada algoritma genetika kondisi diawali dengan setting awal solusi acak yang disebut populasi. Tiap individu dalam populasi disebut kro-mosom, yang mempresentasikan suatu solusi atas permasalahan. Kromosom berevolusi melalui iterasi berkelanjutan, yang disebut generasi. Selama tiap generasi, kromosom dievaluasi menggunakan beberapa ukuran fitness.

 

Untuk menghasilkan generasi berikutnya, kromosom baru yang disebut offspring, dibentuk baik melalui penyatuan dua kromosom dari generasi awal menggunakan operator perkawinan silang (crossover) atau memodifikasi kromosom menggunakan operator mutasi (mutation). Suatu generasi baru dibentuk melalui proses seleksi beberapa induk (parents) dan anak (offspring), sesuai dengan nilai fitness, dan melalui eliminasi kro-mosom lainya agar ukuran populasi tetap konstan. Kromosom yang sesuai memiliki kemungkinan tertinggi untuk dipilih. Setelah beberapa generasi, algoritma menghasilkan kromosom-kromosom terbaik yang diharapkan mewakili solusi optimal atau sub optimal atas permasalahan.

 

Komponen-Komponen Algoritma Genetika

Ada beberapa komponen dalam algoritma genetika, yaitu:

Inisialisasi populasi awal merupakan suatu metode untuk menghasilkan kromosom-kromosom awal. Jumlah individu pada populasi awal meru-pakan masukan dari pengguna. Setelah jumlah individu pada populasi awal ditentukan, dilakukan inisialisasi terhadap kromosom yang ter-dapat pada populasi tersebut. Inisialisasi dilakukan secara acak, namun tetap memperlihatkan domain solusi dan kendala permasalahan yang ada.

 

Fungsi evaluasi dalam algoritma genetika merupakan sebuah fungsi yang memberikan penilaian kepada kromosom (Fitnes value) untuk dijadikan suatu acuan dalam mencapai nilai optimal pada algoritma genetika. Nilai Fitness ini kemudian menjadi nilat bobot suatu kromosom. Ada dua hal yang harus dilakukan dalam melakukan evaluasi kromosom, yaitu: evaluasi fungsi objektif, fungsi tujuan dan konversi fungsi objektif dengan nilai yang tidak negatif, jika ternyata nilai fungsi objektif bernilai negatif maka perlu ditambahkan suatu konstanta x agar nilai fitness yang terbentuk tidak bernilai negatif. Pada evolusi alam individu yang bernilai fitness tinggi yang akan bertahan hidup. Sedangkan individu yg bernilai fitness rendah akan mati. Bias dibangkitkan dengan persamaan (1)

 

Pada masalah optimasi, jika solusi yang akan dicari adalah memaksimalkan fungsi h (dikenal sebagai masalah makasimasi) sehingga nilai fitness yang digunakan adalah nilai dari fungsi h tersebut, yakni f=h (di mana f adalah nilai fitness). Tetapi jika masalahnya adalah meminimalkan fungsi h (masalah minimasi), maka fungsi h tidak bisa digunakan secara langsung. Hal ini disebabkan adanya aturan bahwa individu yang memiliki nilai fitness tinggi lebih mampu bertahan hidup pada generasi berikutnya. Oleh karena itu nilai fitness yang bisa digunakan adalah f=1/h, yang artinya semakin kecil nilai h, semakin besar nilai f. tetapi hal ini akan menjadi masalah jika h bisa bernilai 0, yang mengakibatkan f bisa bernilai tak hingga. Untuk mengatasinya, h perlu ditambah sebuah bilangan yang dianggap kecil [0-1] sehingga nilai fitness dapat ditunjukkan dengan persamaan. (2)

Fitness = 1/(1 + a) atau,

Fitness = 1/(1 + total kesalahan) (2)

Dapat ditunjukkan pada persamaan (3)

Fitness = (L* Î±i * Penalti 1 – Î±i penalti 2 (3)

Keterangan:

L          = Luas lahan produksi yang dimiliki

Xi        = proporsi luas Stasiun kerja[i]

K[i]      = Keuntungan Mesin Produksi ke [i]

1          = Konstanta 1

 

dengan a adalah bilangan yang kecil dan bervariasi [0-1] sesuai dengan masalah yang akan diselesaikan [1 1]. Oleh karena itu fungsi fitness menjadi masalah atau penentu utama keberhasilan algoritma genetika. Pada penelitian ini batasan atau constrain dalam penyusunan jadwal produksi yang dijadikan fungsi objektifnya yaitu meminimumkan penumpukan pada proses produksi terhadap constrain yang telat ditentukan. Nilai fitness inilah yang nantinya akan digunakan pada tahap seleksi berikutnya (Kusumadewi, 2003).

 

Seleksi merupakan proses pemilihan orang tua untuk reproduksi (biasanya didasarkan pada nilai fitness). Pada tahap ini menjadi : Total nilai fitness = nilai fitness k1 + nilai fitness k2 +...+ n dengan n = jumlah kromosom yang ditentukan dan k = kromosom. Dapat ditunjukkan pada persamaan (4)

dengan n = jumlah kromosom yang ditentukan.

Interval nilai [0-1] = probabilitas kromosom 1 + probabilitas kromosom 2

 

 

Pindah silang atau crossover adalah sebuah proses yang membentuk kromosom baru dari dua kromosom induk dengan menggabungkan

bagian informasi dari masing-masing kromosom. Crossover meng-hasilkan kromosom baru yang disebut kromosom anak (offspring). Crossover bertujuan untuk menambah keanekaragaman string dalam satu populasi dengan penyilangan antar string yang diperoleh dari reproduksi sebelumnya. Pindah silang juga berakibat buruk jika ukuran populasinya sangat kecil.

 

Untuk mengatasi masalah ini digunakan suau bahwa pindah silang hanya bisa dilakukan dengan probabilitas tertentu (probabilitas crossover). Artinya pindah silang bias dilakukan hanya jika suatu bilangan random [0-1] yang dibangkitkan kurang dari probabilitas crossover (Pc) yang ditentukan. Pada umumnya Pc diset mendekati 1, misalnya 0,8 [1 1].

 

Probabilitas crossover (Pc) bertujuan untuk mengendalikan operator crossover. Jika n adalah banyaknya string pada populasi, maka sebanyak (Pc) x n string akan mengalami crossover. Semakin besar nilai (Pc), semakin cepat pula string baru muncul dalam populasi. Dan juga jika (Pc) terlalu besar, string yang merupakan kandidat solusi terbaik mungkin dapat hilang lebih cepat pada generasi berikutnya.

Dan dapat dibangkitkan dengan persamaan (5)

C1 = P1 + Î± (P2 – P1)

C2 = P2 + Î± (P1 – P2)  (5)

 

Mutasi merupakan proses mengubah secara acak nilai dari satu atau beberapa gen dalam suatu kromosom. Mutasi adalah operator algoritma genetika yang bertujuan untuk membentuk individu-individu yang baik atau memiliki kualitas diatas rata-rata. Selain itu mutasi dipergunakan untuk mengembalikan kerusakan materi genetik akibat proses cross-over. Pada mutasi terdapat satu parameter yang sangat penting, yaitu probabilitas mutasi (Pm) yang bertujuan untuk mengendalikan operator mutasi.

 

Probabilitas mutasi didefinisikan sebagai persentasi dari jumlah total gen dalam populasi yang akan mengalami mutasi. Disetiap generasi diperkirakan terjadi mutasi sebanyak (Pm) x n string. Pada seleksi alam murni, mutasi jarang sekali muncul sehingga probabilitas mutasi yang digunakan umumnya kecil, lebih kecil dari probabilitas crossover. Pm biasanya diset antara [0-1], misalnya 0.1 [1 1]. Misalkan offspring yang terbentuk adalah 100 dengan jumlah gen setiap kro-mosom adalah 4 dan peluang mutasi adalah 0.10, maka diharapkan terdapat 40 kromosom dari 400 gen yang ada pada populasi tersebut akan mengalami mutasi.

Dapat ditunjukkan pada persamaan (6)

X’i = X’i + r (max i – min j) (6)

 

Metode Penelitian

Metodologi penelitian merupakan rangkaian tahapan penelitian yang tersusun secara sistematis. Tujuan dari metodologi penelitian adalah agar pelaksanaan penelitian mendapatkan hasil yang sesuai dengan tujuan penelitian.

Rangkaian tahapan yang akan dilakukan adalah sebagai berikut:

1. Tempat dan Waktu Penelitian

Penelitian ini dilakukan di PT NAKAYAMA, Jln. Brajan No 12 Wonokromo, Bantul, Yogyakarta, mulai bulan Februari sampai Juni 2016.

2. Metode Penelitian

Penelitian dilakukan dengan berbagai metode, mulai dari wawancara, analisis metode pemodelan, inisialisasi parameter, desain masalah, studi pustaka dan pengolahan data.

3. Metode Wawancara

Merupakan metode pengumpulan data langsung dengan memberi pertanyaan kepada beberapa orang guna mendapatkan data peneltian awal. Salah satu diantaranya adalah bagian HRD (Human Resources Development) atau Personalia Kepegawaian dari PT NAKAYAMA. Wawan-cara ini dilakukan guna melakukan validasi awal untuk membuat inisialisasi parameter yang akan dijadikan sebagai metode pemodelan untuk desain masalahnya.

 

Analisis Metode Pemodelan

1. Pengkodean Kromosom

Kromosom yang akan dihasilkan dari penelitian ini meru-pakan representasi dari jadwal mingguan di PT NAKAYAMA, Pada data kromosom dapat dilihat bahwa terdapat sejumlah n karyawan yang akan dijadwalkan yaitu P1, P2,…Pn. Dalam penjadwalan ini akan digunakan pola mingguan yang terdiri atas 6 hari (hari Senin sampai Sabtu).

 

Penentuan fungsi fitness, Fungsi fitness digunakan untuk mengukur ketangguhan setiap kromosom di dalam suatu populasi. Fungsi fitness merupakan ukuran kinerja dari suatu individu agar tetap bertahan hidup yaitu mengukur kelayakan sebuah kromosom untuk dipelihara atau ditiadakan. Fungsi fitness harus memperhatikan pada fungsi objektifnya. Pada penelitian ini fungsi objektifnya adalah meminimalkan penalty yang dihasilkan oleh pelanggaran terhadap batasan yang telah ditentukan.

 

Inisialisasi Parameter

1. Penentuan Parameter Genetika

Jumlah populasi (pop_size) merupakan angka yang menu-njukkan jumlah kromosom.

Jumlah generasi (max_gen) merupakan angka yang menun-jukkan jumlah generasi yang diproses

Probabilitas crossover (Pc) menunjukkan kemungkinan kromo-som dalam satu populasi untuk melakukan pindah silang.

Probabilias mutasi (Pm) digunakan untuk menunjukkan kemungkinan banyak gen yang akan mengalami mutasi

Tahap Inisialisasi (Pembentukan Populasi Awal) Teknik peng-kodean yang digunakan pada TSPPC adalah konsep peng-kodean dengan bilangan bulat. Pada pengkodean ini setiap struktur kromosom merupakan sebuah string bilangan bulat dari 1 sampai banyaknya titik. Misalkan pada tiap kro-mosom berisi 7 gen, maka pengkodean gen pada kromosom dapat diperlihatkan.

 

Tipe Penelitian

Tipe penelitian ini adalah diskriptif yang bertujuan untuk memberikan gambaran mengenai kondisi stasiun produksi yang terjadi di PT NAKAYAMA sekarang ini, dukungan dan potensi yang ada dalam pengembangan model sistematik penjadwalan, berbagai kendala yang dihadapi oleh karyawan baik yang bersifat teknis maupun manajerial dan upaya pengembangan lebih lanjut mengenai penjadwalan produksi di PT NAKAYAMA.

 

Studi Literatur Data Sekunder

Data sekunder diperoleh dengan mengumpulkan sumber tertulis atau dokumen dari Kantor PT NAKAYAMA, Surat Usaha, Dinas Per-industrian, dan dari berbagai buku pustaka yang ada kaitan dengan penelitian ini.

 

Teknik Pengumpulan Data

Data penelitian diperoleh melalui observasi dan dokumentasi, wawancara mendalam dan data sekunder yang ada. Observasi dan dokumentasi dilakukan untuk memperoleh gambaran mengenai kondisi umum mengenai desain masalah yang ada di PT NAKAYAMA. Wawancara mendalam dilakukan untuk mengetahui lebih jauh mengenai kondisi permasalahan optimasi penjdwalan produksi spareparts, baik mengenai potensi, dukungan yang ada dan berbagai kendala yang ada dan untuk melakukan validasi terhadap hasil pengumpulan.

 

Wawancara mendalam dilakukan terhadap Kepala bagian Supervisor beberapa ang-gota Kepala Produksi, pejabat dari dinas/instansi terkait di PT NAKAYAMA. Data sekunder untuk melengkapi gambaran umum mengenai kondisi penjadwalan produksi yang berasal dari berbagai data dan dokumentasi yang sudah ada.

 

Teknik Analisis Data

Analisis adalah suatu proses penyusunan data agar dapat ditafsirkan. Analisis yang digunakan terhadap data yang diperoleh dalam penelitian kualitatif ini adalah menggunakan analisis data secara induktif. Proses analisis data dimulai dengan menelaah seluruh data yang dihimpun melalui wawancara dan observasi lapangan maupun dokumen resmi dari beberapa instansi terkait dengan penelitian.

 

Setelah ditelaah dan dipelajari kemudian digenerasikan ke dalam suatu kesimpulan yang bersifat umum yang didasarkan atas fakta-fakta yang empiris tentang lokasi penelitian. Tahap terakhir dari analisis data adalah mengadakan pemeriksaan keabsahan data. Dalam penelitian ini digunakan teknik pengumpulan populasi dan parameter pemodelan dan parameter pengkodean dengan sumber yaitu dengan membandingkan dan mengecek balik derajat kepercayaan suatu informasi yang diperoleh.

 

Jadwal Penelitian

Tabel 7.1 Jadwal Penelitian

 

No

Kegiatan

Februari

Maret

April

Mei

Juni

1

Menentukan Tema dan Identifikasi Masalah

2

Menentukan Lokasi Penelitian

 





3

Pengurusan Izin

4

Penyusunan Instrumen

5

Pengumpulan Data

6

Pengolahan dan Analisis Data

7

Penyusunan Proposal Penelitian

8

Penyajian Proposal

 





9

Pengumpulan Laporan Proposal

10

Seminar dan Ujian Proposal

 

Daftar Pustaka

  • Afandi, Fachrudin. “Penerapan Algoritma Genetika Untuk Masalah Penjadwalan Job Shop pada Lingkungan Industri Pakaian”. Skripsi Sarjana, Fakultas Teknologi Informasi Institut Teknologi Sepuluh November (ITS), Surabaya, 2009.
  • Buliali, JL, Herumurti. D, Wiriapraja, .G. 2008. “Penjadwalan mata kuliah dengan menggunakan algoritma genetika dan constraint satisfaction”. Jurnal Teknik Industri, Surabaya.
  • Fadlisyah, Arnawan, Faisal. Algoritma Genetika. Graha Ilmu, Yogyakarta, 2009.
  • Janata, Ari. “Sistem Penjadwalan Outsourcing Menggunakan Algoritma Genetika (Studi Kasus : PT. Syarikatama)”. Jurnal CoreIT, Vol.1, No.2, Pekanbaru, Desember 2015
  • Tasidjawa, Arens F. “Analisa Sistem Informasi Atma Jaya Yogyakarta (Siatma) Dengan Mengunakan Model Kesuksesan Delone Mclean”. Skripsi,  Fakultas Teknologi Industri Universitas Atma Jaya Yogyakarta, Yogyakarta, 2015
  • Uktaviya, Rina. 2012. Penerapan Metode Pindah Silang Cycle Crossover (CX) Untuk Travelling Salesman Problem (TSP). Skripsi tidak diterbitkan. Malang: Universitas Negeri Malang.