Algoritma Genetik Dengan Interger Programming

PENDAHULUAN Disini penulis mengembangkan penelitian dari Tugas Akhir (TA) dari mahasiswa Teknik Industri yang bernama Robert Simons (960403035). Penulis mengembangkan data yang diperoleh dari Tugas Akhir (TA) yang berjudul “Aplikasi Algoritma Genetik untuk Job Sequencing pada Penjadwalan di PT. Intan Andalas Wood Industri” . Literatur tambahan yang digunakan penulis untuk mendukung landasan teori berdasarkan jurnal internet yang berjudul “Algoritma Genetik Hibrida dalam Penyelesaian Job-Shop Schedulling” dan “Algoritma Branch and Bound untuk

Adapun permasalahan yang dihadapi pihak perusahaan adalah perusahaan harus merencanakan ulang penjadwalan produksi setiap kali order datang. Setiap order baru datang, perusahaan harus mempertimbangkan apakah perusahaan sanggup memenuhi batas waktu penyelesaian (due date) yang disepakati dengan konsumen sesuai dengan sumber daya yang ada di perusahaan. Pihak perusahaan harus mengambil keputusan apakah menerima atau menolak order tersebut. Disisi lain, setiap kedatangan order akan mempengaruhi penjadwalan pada mesin dan peralatan pada lantai

Perumusan Masalah Bagaimana mendapatkan penjadwalan

yang baik sehingga dapat memenuhi due date setiap order yang datang. Bagaimana mendapatkan penjadwalan yang baik tanpa mengurangi efektivitas penggunaan mesin produksi. Bagaiamana mendapatkan pengurutan pekerjaan (job sequencing) yang dapat mengurangi makespan produksi dan meningkatkan efektivitas penggunaan (utilitas) mesin dengan pendekatan interger.

Tujuan Penelitian Tujuan Umum Mengaplikasikan algortima genetik untuk job sequencing pada penjadwalan di PT. Intan Andalas Wood Industri dengan metode interger. Tujuan Khusus Melakukan penjadwalan ulang (rescheduling) terhadap order lama yang sedang dikerjakan pada saat order baru datang. Menentukan semua model pengurutan job (job sequencing) yang mampu memenuhi kriteria yang ditentukan terhadap order yang baru diterima perusahaan. Mempersingkat waktu proses produksi dari job order dengan melakukan penjadwalan yang baik.

Pembatasan Masalah Rescheduling dilakukan jika terjadi

kedatangan order baru ditengah-tengah jalannya kegiatan. Kriteria penjadwalan yang digunakan hanya berupa pengurutan job (job sequencing) dengan dasar penilaian fungsi makespan dan utilitas rata-rata mesin sementara diabaikan. Kriteria optimalitas penjadwalan yang digunakan dibatasi pada minimisasi makespan dan maksimisasi utilitas mesin. Panjadwalan dilakukan utuk mesin-mesin

Asumsi Yang Digunakan

Asumsi untuk karakteristik job Setiap job mempunyai waktu penyerahan yang tertentu sesuai perjanjian dengan konsumen. Teknologi pembuatan produk telah diketahui. Asumsi untuk karakteristik mesin Mesin siap dibebani secara kontinu selama periode sequencing. Hal-hal yang dapat menyebabkan penundaan selama penugasan mesin seperti kerusakan mesin tidak diperhitungkan Asumsi untuk Karakteristik Proses Waktu set-up termasuk dalam waktu proses. Sistem produksi berjalan ormal dan tidak mengalami gangguan.

METODOLOGI PENELITIAN Metodologi Pengumpulan Data Pengumpulan data dilakukan dengan cara sebagai berikut : Melakukan pengamatan langsung terhadap objek yang diteliti. Variabel yang diteliti dan diukur adalah waktu pengerjaan tiap komponen produk yang sedang diproduksi. Melakukan wawancara dengan pihak perusahaan yang dapat memberikan informasi yang diperlukan untuk menunjang penyelesaian masalah. Pengumpulan dokumen atau arsip yang dimiliki perusahaan yang digunakan dalam penelitian.

Data Primer Data primer pada umumnya merupakan data yang dikumpulkan melalui pengamatan, wawancara atau eksperimen melalui sampling. Data primer yang dikumpulkan dalam penelitian berupa : Waktu pemrosesan komponen produk Jenis mesin yang dipergunakan Urutan proses tiap job order

Instrumen yang digunakan dalam data primer adalah wawancara.

Data Sekunder Data ini dikumpulkan dengan mencatat data dan informasi dari laporan-laporan perusahaan yang ada atau dengan cara mereview laporan tersebut, yang mencakup data kedatangan dan due date order, baik order lama maupun order baru, serta jumlah order atas komponen yang diteliti. Instrumen yang digunakan dalam data mengambil data sekunder adalah laporan data-data yang ada.

Metodologi Analisis Perumusan Masalah dan Penetapan Tujuan Masalah yang akan diselesaikan adalah bagaimana mendapatkan penyesuaian penjadwalan yang optimum bila waktu kedatangan order tidak menentu. Sedangkan tujuan penelitian yang ingin dicapai adalah mendapatkan model penjadwalan yang optimum berdasarkan kriteria optimalitas yang ditetapkan.

Studi Orientasi dan Studi Literatur Studi Orientasi merupakan studi ke pabrik dengan melakukan pengamatan dan penelitian ke pabrik, wawancara dengan pihak perusahaan, sehingga dapat melihat permasalahan dengan lebih jelas. Studi literatur merupakan studi atas teori-teori yang akan digunakan untuk memecahakan masalah yang mencakup teori pengukuran sistem kerja, penjadwalan mesin dengan metode algoritma genetik, dan metode interger programming.

Pengumpulan Data Mengidentifikasi order yang datang dalam 1 bulan, yang terdiri atas jenis dan jumlah order, data waktu kedatangan dan due date order. Mengumpulkan data mengenai stasiun kerja dan urutan proses tiap produk yang ditinjau. Melakukan pengukuran waktu dengan menggunakan stop watch terhadap operator yang mengerjakan tiap order pada tiap mesin. Melakukan pengamatan terhadap kondisi kerja dan operator dalam setiap stasiun

Prosedur Penelitian Menjelaskan latar belakang penelitian. Menjelaskan tujuan penelitian. Identifikasi permasalahan yang terjadi. Teliti ruang lingkup permasalahan, dan cari solusiya dengan landasan teori dari literatur. Lakukan pengumpulan data. Lakukan pengolahan data. Lakukan pemecahan masalah dengan algoritma genetik dan metode interger dengan algoritma branch and bound. Lakukan pengujian untuk mengetahui kebenaran dari pemecahan masalah. Lakukan analisis dari pemecahan dan pengujian yang dilakukan. Ambil kesimpulan.

Latar Belakang Penelitian

Tujuan Penelitian

Identidikasi Permasalahan

Ruang Lingkup Permasalahan

Landasan Teori

Pengumpulan Data

Pengolahan Data

Pemecahan Masalah

Pengujian

Analisis

Kesimpulan

Gambar. Blok Diagram Metodologi Penelitian

Pengolahan Data  Tentukan input yang akan dimasukkan dalam data yang dikelolah.  Tentukan waktu kedatangan order yang diambil dari pengumpulan data.  Identifikasi order yang merupakan hasil pengumpulan data.  Melakukan penjadwalan awal (jadwal inisial) untuk order yang lebih dahulu datang.  Mendapatkan model optimisasi penjadwalan terhadap tiap job/ order baik yang lama maupun yang baru dengan bantuan program komputer dengan metode interger.  Melakukan perhitungan simulasi dengan algoritma genetika untuk memperoleh urutan job berdasarkan kriteria performansi penjadwalan, yaitu fungsi maksimisasi utilitas rata-rata mesin dan minimisasi makespan. Dengan asumsi 65 % probabilitas makespan dan 35 % probabilitas rata-rata utilitas mesin.  Mencari solusi optimal dengan metode Branch and Bound pada interger programming terhadap pemenuhan due date order apakah formasi terbaik yang dihasilkan merupakan

Mulai Input n, t, tjk, dh Tentukan t sebagai waktu kedatangan order Identifikasi Order yang berasal dari pengumpulan data

Penjadwalan Ulang Tentukan optimisasi Tentukan urutan job dengan algoritma Genetik diperik Ya

sa?

Tentukan Solusi optimal dengan metode interger

Tidak

Lakukan pengerjaan order sesuai jadwal

diperik sa?

Ya

Stop

Gambar. Blok Diagram Pengolahan Data

Tidak

Pembahasan Masalah Pada tahatapan ini dilakukan perbandingan antara kinerja penjadwalan aktual perusahaan dengan kinerja penjadwalan usulan. Membuat Kesimpulan

LANDASAN TEORI Definisi Penjadwalan Pengertian penjadwalan secara umum dapat diartikan seperti “Scheduling is the allocation of resources overtime to perform collection of risk”, yang artinya penjadwalan adalah pengalokasian sumberdaya yang terbatas untuk mengerjakan sejumlah pekerja

Tujuan Pejadwalan - Meningkatkan penggunaan sumber daya atau mengurangi waktu tunggunya. - Mengurangi persediaan barang setengah jadi atau mengurangi sejumlah pekerjaan yang menunggu dalam antrian ketika sumberdaya yang ada masih mengerjakan tugas yang lain. - Mengurangi beberapa keterlambatan pada pekerjaan yang mempunyai batas waktu penyelesaian sehingga akan meminimisasi penalty cost (biaya keterlambatan). - Membantu pengambilan keputusan mengenai perencanaan kepasitas pabrik dan jenis kapasitas yang dibutuhkan sehingga penambahan biaya dapat dihindarkan.

Model Penjadwalan Menurut Baker (1974), Model penjadwalan dibedakan menjadi 4 jenis keadaan, yaitu : Mesin yang digunakan dapat berupa proses dengan mesin tunggal atau proses dengan mesin majemuk. Pola aliran proses dapat berupa aliran identik atau sembarang. Pola kedatangan pekerjaan statis atau dinamis. Sifat informasi yang diterima dapat bersifat deterministic atau stokastik.

Penjadwalan Mesin dengan Algoritma Genetik Metode ini termasuk salah satu metode yang bekerja berdasarkan pada prinsip seleksi alam dan teknik evolusi. Penelitian metodologi terhadap algoritma genetik terdiri atas penelitian dan aplikasi yang memperhatikan analogi-analogi ilmiah, analisis matematika,

Perubahan susunan genetik individu dipengaruhi oleh sifatsifat pengerjaan genetik yang terdiri atas tiga faktor, yaitu :  Reproduksi Merupakan proses terjadinya peniruan terhadap individu induk lain berdasarkan besarnya kemampuan individu tersebut untuk bertahan hidup.  Pindah Silang Dalam pindah silang, individu terlebih dahulu mencari pasangannya secara random (acak) , kemudian dilakukan pemilihan lokasi silang, juga dilakukan secara random. Berdasarkan hal ini dilakukan pindah silang adalah yang mempunyai kemampuan.  Mutasi Mutasi merupakan perubahan apapun dalam bahan genetik yang disebabkan oleh aberasi kromosom (penyimpangan kromosom) yang menyebabkan perubahan bagian kromosom seperti inversi, translokasi, dan duplikasi, serta perubahan dalam jumlah kromosom.

Elemen -elemen dari penjadwalan dengan metode algoritma genetik adalah sebagai berikut : Data waktu proses pengerjaan tiap job pada masingmasing mesin. Data jumlah order (job) yang masuk serta due date dari masing-masing job. Data waktu set-up mesin untuk tiap proses. Data jumlah order yang dikerjakan serta mesin yang digunakan. Data pendukung proses seperti jumlah mesin, kondisi mesin, dan hal-hal yang lebih dahulu dibatasi dan diasumsikan. Teori dasar penjadwalan dan pengurutan job, teori dasar algoritma genetik, teori pemograman, keilmuan lain yang berinteraksi dengan kondisi ini yang terlebih dahulu diasumsikan dan dibatasi.  Kondisi tempat penelitian serta gambaran umum perusahaan tempat penelitian. Objek-objek lain yang mungkin termasuk dalam penelitian, namun tidak terlalu berpengaruh karena

Penjadwalan Mesin dengan Interger Programming Model program interger membutuhkan keseluruhan asumsi mutlak pada program linier terkecuali bahwa variabel spesifik tidak harus bernilai interger non negatif pada solusi optimal. Jika keseluruhan variabel harus bernilai interger, model merupakan program interger murni, dimana subset harus interger, model tesebut disebut model mixed interger programming. Teknik numerik harus dapat dikembangkan untuk menyelesaikan model program interger.

Algoritma Branch and Bound Branch and Bound adalah suatu prosedur yang paling umum untuk mencari solusi optimal pada masalah optimasi kombinatorial seperti masalah penjadwalan. Dalam masalah yang dibahas di sini, n buah pekerjaan diproses dengan menggunakan m buah mesin tak berelasi. Setelah sekumpulan pekerjaan diserahkan kepada mesin, pencarian urutan pekerjaan tidak diperlukan lagi dalam mesin tersebut, karena yang menjadi tujuan utama adalah untuk meminimisasi Cmax dan tidak tergantung dengan waktu pengurutan. Oleh karena itu, algoritma branch and bound dikembangkan untuk menentukan penyerahan pekerjaan secara optimal kepada mesin. Di dalam algoritma Branch and Bound, terdapat tiga buah bagian utama, yaitu : ekspresi batas