OPTIMASI MASALAH PENJADWALAN JOB-SHOP UNTUK INDUSTRI PERALATAN PENGOLAHAN HASIL PERTANIAN DENGAN MENGGUNAKAN ALGORITMA GENETIKA
Oleh
AYIP BAYU SATRIO F34103096
DEPARTEMEN TEKNOLOGI INDUSTRI PERTANIAN FAKULTAS TEKNOLOGI PERTANIAN INSTITUT PERTANIAN BOGOR BOGOR 2007
Ayip Bayu Satrio. F34103096. Optimasi Masalah Penjadwalan Job-Shop untuk Industri Peralatan Pengolahan Hasil Pertanian dengan Menggunakan Algoritma Genetika. Di bawah bimbingan Yandra Arkeman dan Hendra Gunawan. 2007.
RINGKASAN Penjadwalan produksi di dalam dunia industri, baik industri manufaktur maupun agroindustri, memiliki peranan penting sebagai bentuk pengambilan keputusan. Perusahaan berupaya untuk memiliki penjadwalan yang paling efekif dan efisien sehingga dapat meningkatkan produktivitas yang dihasilkan dengan total biaya dan waktu seminimum mungkin. Salah satu masalah dalam penjadwalan produksi adalah adanya kesulitan menemukan teknik yang paling tepat untuk membuat jadwal produksi yang paling baik, optimal, dan memenuhi segala kriteria-kriteria penjadwalan yang telah ditetapkan. Teknik-teknik penyusunan jadwal produksi yang sudah ada (teknik konvensional) tidak dapat dipakai karena teknik-teknik tersebut memiliki banyak kelemahan dalam menangani masalah berskala besar dan kompleks. Permasalahan penjadwalan job shop (job shop scheduling) dengan fungsi tujuan meminimumkan total waktu proses (makespan) dapat diterjemahkan sebagai memproses setiap pekerjaan (job) dari n job pada m mesin dengan urutan tertentu. Setiap pekerjaan terdiri dari serangkaian operasi. Setiap mesin dapat menangani tidak lebih dari satu pekerjaan pada suatu waktu dan setiap pekerjaan mengunjungi mesin hanya satu kali. Pada penelitian ini akan dicari solusi untuk menyelesaikan permasalahan penjadwalan job shop dengan menggunakan metode Genetic Algorithms (Algoritma Genetika). Prinsip kerjanya yaitu berdasarkan analogi evolusi biologi, yang terdiri dari proses penginisialisasian populasi, proses penyeleksian, proses penyilangan, dan proses mutasi. Keunggulan dari algoritma genetika ini adalah strukturnya yang sederhana, mudah mengimplementasikannya, dan cepat dalam pencapaian solusi yang optimum (efektif dan efisien). Penelitian ini bertujuan untuk mengaplikasikan algoritma genetika dalam bidang penjadwalan produksi tipe job shop berskala besar. Implementasi dari penelitian ini adalah perancangan program GA_JobShop (Genetic Algorithms for Job Shop Scheduling) yang dibuat menggunakan bahasa pemrograman Borland Delphi 7.0. Representasi kromosom menggunakan preference list based representation, proses penyilangan menggunakan Partially Mapped Crossover (PMX) yang telah dimodifikasi, proses mutasi menggunakan reciprocal exchange mutation yang telah dimodifikasi, dan seleksi menggunakan tournament selection. Kasus ke-1 merupakan numerical example, yaitu data yang digunakan sebagai verifikasi dan validasi program GA_JobShop. Data kasus 1 dibuat dengan mengikuti aturan permasalahan pada sebuah penjadwalan tipe job shop. Kasus 2 mengacu pada persoalan yang terdapat di dalam buku Genetic Algorithms and Engineering Design (Gen dan Cheng, 1997). Kasus ke-3 merupakan kasus riil di industri peralatan pengolahan hasil pertanian CV Mitra Niaga Indonesia, Bogor. Penjadwalan tipe job shop memiliki ruang pencarian (search space) sebesar (n!)m, dengan n adalah jumlah job dan m adalah jumlah mesin. Kasus 1 (3 job 2 mesin) memiliki ruang pencarian sebanyak 36 calon solusi. Kasus 2 (3 job
– 3 mesin) memiliki ruang pencarian sebesar 216 calon solusi. Kasus 3 (5 job – 12 mesin) memiliki ruang pencarian sebesar 8,92×1024 calon solusi. Hasil penilitian menunjukkan bahwa program GA_JobShop sangat efisien dalam penyelesaian masalah penjadwalan tipe job shop berskala kecil maupun besar. Program GA_JobShop telah terbukti valid, hal ini dibuktikan pada Kasus 1. Nilai makespan optimum pada Kasus 1 yang didapatkan dengan cara enumeratif (menghitung semua alternatif penjadwalan yang dapat terjadi) sama dengan nilai makespan optimum yang didapatkan dengan menggunakan algoritma genetika (program GA_JobShop), yaitu 11. Pada Kasus 2, solusi optimum dapat tercapai pada generasi ke-3 dengan nilai makespan 11. Algoritma genetika hanya mengeksplorasi 27,78 % ruang pencarian (search space) untuk mendapatkan nilai yang minimum pada Kasus 2. Semakin besarnya ruang pencarian (search space) maka penggunaan algoritma genetika akan semakin efisien, terlihat pada Kasus 3. Kasus 3 (5 job – 12 mesin) memiliki nilai makespan sebesar 3589 dalam satuan waktu menit.
Ayip Bayu Satrio. F34103096. The Optimization of Job Shop Scheduling Problems for Manufacture Industry of Agriculture Product Processing Machinery with Using Genetic Algorithms. Supervised by Yandra Arkeman and Hendra Gunawan. 2007.
SUMMARY Scheduling of production in industrial world, like in manufacture industry or agroindustry has an important role in making decision. The company is trying to have effective and efficient scheduling which can increase the productivity with small amount of cost and time. One of the problem in scheduling production is founding problem in deciding which is the right technique to make better, optimal, fulfill all the criteria in making production schedule. Techniques in arranging the production schedule that already exist (conventional techniques) cannot be used because they have a lot of weaknesses in handling large scale and complex problems. The problem of job shop scheduling with function to minimize the total of time process which can be translated to process every job from n jobs to m machines with certain sequence. Every job has its own sequence of operation. Every machine can handle no more than one job in a time and every job visit the machine only in one time. In this research will find the solution to solve the problem of job shop scheduling using Genetic Algorithms method. The basic principal is based on analogy of biological evolution, which contains initialization population process, selection process, crossover process, and mutation process. The benefits of genetic algorithms are the simple structure, easy to implement, and very quick in accomplishing the optimum solution (effective and efficient). The goal of this research is to applying genetic algorithms for large scale job shop scheduling of production. The implementation of this research is to design GA_JobShop (Genetic Algorithms for Job Shop Scheduling) program which is using Borland Delphi 7.0. The chromosome representation are using preference list based representation, crossover process are using partially mapped crossover (PMX) which is been modified, the mutation process are using reciprocal exchange mutation which is been modified, and the selection process are using tournament selection. The first case is numerical example that is the data which is being used as verification and validation of GA_JobShop program. The data of the first case is made by following job scheduling rules. The second case refer to the problem which is contain in the book of Genetic Algorithms and Engineering Design (Gen dan Cheng, 1997). The third case is a real case in manufacture industry of agriculture product processing machinery of CV Mitra Niaga Indonesia, Bogor. The job shop scheduling has a search space for about (n!)m , n as the amount of jobs and m as the amount of machines. Case 1 (3 jobs – 2 machines) has a search space for about 36 candidates of solutions. Case 2 (3 jobs – 3 machines) has a search space for about 216 candidates of solutions. Case 3 (5 jobs – 12 machines) has a search space for about 8,92×1024 candidates of solutions. This research shows that the GA_JobShop program is very efficient in solving problem of job shop scheduling even in large scale or small scale. GA_JobShop program has proven valid. This has been proven in the Case 1. The value of makespan optimum in the Case 1 which is has been made by enumerative
search equals with makespan optimum value by getting with using genetic algorithms (GA_JobShop program) is 11. In the Case 2, the optimum solution can be achieved in the third generation with makespan value on 11. Genetic algorithms only explored 27,78 % of search space to get minimum value in Case 2. More search space will be more efficient to use genetic algorithms, it showed on the Case 3. The Case 3 (5 jobs 12 machines) has makespan value for about 3589 in minutes.
FAKULTAS TEKNOLOGI PERTANIAN INSTITUT PERTANIAN BOGOR
OPTIMASI MASALAH PENJADWALAN JOB-SHOP UNTUK INDUSTRI PERALATAN PENGOLAHAN HASIL PERTANIAN DENGAN MENGGUNAKAN ALGORITMA GENETIKA
SKRIPSI
Sebagai salah satu syarat untuk memperoleh gelar SARJANA TEKNOLOGI PERTANIAN Pada Fakultas Teknologi Pertanian Institut Pertanian Bogor
Oleh AYIP BAYU SATRIO F34103096
Dilahirkan di Jakarta Pada tanggal 16 Agustus 1985
Tanggal kelulusan : 19 Desember 2007
Disetujui : Bogor, Januari 2008
Hendra Gunawan, S.TP
Dr. Ir. Yandra Arkeman, M.Eng
Pembimbing II
Pembimbing I
KATA PENGANTAR
Puji syukur kehadirat Allah SWT penulis panjatkan karena atas segala rahmat dan karunia-Nya, penulis dapat menyelesaikan skripsi ini. Penulis memilih topik Optimasi Masalah Penjadwalan Job Shop untuk Industri Peralatan Pengolahan Hasil Pertanian dengan Menggunakan Algoritma Genetika. Penulis mengucapkan terima kasih kepada pihak yang telah membantu dalam penyelesaian skripsi ini terutama kepada : 1. Dr. Ir. Yandra Arkeman, MEng, selaku dosen pembimbing I yang telah memberikan ide, saran, dan pengarahan kepada penulis. 2. Hendra Gunawan, S.TP, selaku pembimbing II yang telah banyak memberikan pengarahan serta bantuan dalam memberikan pemahaman kepada penulis. 3. Ir. Ade Iskandar, M.Si, selaku pembimbing praktek penelitian di industri peralatan pengolahan hasil pertanian CV Mitra Niaga Indonesia, Bogor. 4. Dr. Ir. Suprihatin, M.Si, selaku penguji pada ujian sidang sarjana. 5. Kedua orang tua, kakak dan adik penulis, yang selalu memberikan dorongan, motivasi dan doa dengan tulus. 6. Yuvi Andria, rekan sebimbingan yang telah banyak memberikan masukanmasukan yang bermanfaat dalam penyelesaian skripsi ini. 7. Ulfa Septianty yang selalu memberikan dorongan agar skripsi ini dapat terselesaikan dengan cepat. 8. Sahabat-sahabat penulis : Adhitia Kusuma, Fadil, Jiwo, Iqbal, Anggia Resha, Devan, yang selalu memberikan semangat dan doa kepada penulis. 9. Teman-teman RISDA. 10. Teman-teman TIN ’40, khususnya Amet, Ratih Bunda, Farah, Adit, Helmi, Derry, Arvi, Desminda, Imam, Puji, Budi, Reza, Fardian, Lucia, Adam, Vivi, , Devi, Mona,Silvy dan semuanya yang telah kompak semasa kuliah.. 11. Teman-teman HIMALOGIN (Himpunan Mahasiswa Teknologi Industri). 12. Seluruh panitia seminar “SIX SIGMA” tahun 2005. 13. Teman-teman satu seperjuangan PL : Syahrian, Elly, Eka, Irawan, Ratna, Iib, Shinta, Andri, Angga, Kiki, CB, dan lain-lain. 14. Like a Free Band : Chandra, Bugi, Uci, Au, Dhani, Ali dan Kanda.
15. Puzzle Band : Fadil, Dimas, Gulit, Bembi. 16. Para penghuni Wisma Galih, terutama Bang Riki, Aldo, Oza, Mas Ade, Budi, Ian, Uda Edwin, Uda Paul, Pak Amshor, Wita, Frans, Bian, Benny dan lainlain. 17. Mas Jerry, yang telah membantu dalam translate bahasa inggris. 18. Kemal, yang telah meminjamkan KTM UI Fakultas Teknik. 19. Ade, rekan bisnis yang setia bekerja sama di Blite Outlet and Stationery, Bateng, Kampus Dalam. 20. Seluruh pihak yang telah membantu penulis hingga akhir penyelesaian skripsi. Semoga skripsi ini dapat bermanfaat bagi kita semua.
Bogor,
Desember 2007
Ayip Bayu Satrio
RIWAYAT HIDUP
Penulis dilahirkan di Jakarta pada tangal 16 Agustus 1985 sebagai anak kedua dari tiga bersaudara, anak dari pasangan Ayip Muchlis dan Kussri Saparti. Selama 5 tahun pertama, Penulis dibesarkan di Jakarta dan kemudian berpindah ke Bekasi. Pada tahun 2003 Penulis lulus dari SMU Negeri 61 Jakarta Timur dan kemudian di tahun yang sama Penulis lulus ujian SPMB (Sistem Penerimaan Mahasiswa Baru) dengan memilih IPB (Departemen Teknologi Industri Pertanian) sebagai pilihan. Pada tahun kedua dan ketiga masa perkuliahan, Penulis aktif di dalam organisasi Himpunan Mahasiswa Teknologi Industri (Himalogin) sebagai salah satu staff PR (Public Relation). Penulis sempat menjadi ketua salah satu acara seminar yang diadakan oleh Himalogin (Seminar Six Sigma) tahun 2005. Penulis juga sempat berpengalaman sebagai MC (Master of Ceremonial) pada acara “Lepas Landas Sarjana Fateta IPB” tahun 2004 dan “Seminar Nasional Pemanfaatan Surfaktan Berbasis Minyak Sawit untuk Industri” tahun 2005. Pada tahun 2006 Penulis melakukan Praktek Lapangan di PT Alam Indah Bunga Nusantara, daerah Cipanas, Jawa Barat, dengan kajian “Mempelajari Aspek Manajemen Sumber Daya Manusia” selama 40 hari kerja (3 Juli – 25 Agustus).
DAFTAR ISI
Halaman KATA PENGANTAR ................................................................................
i
RIWAYAT HIDUP ....................................................................................
iii
DAFTAR ISI ..............................................................................................
iv
DAFTAR TABEL ...................................................................................... vii DAFTAR GAMBAR .................................................................................. viii DAFTAR LAMPIRAN ..............................................................................
xi
I. PENDAHULUAN .................................................................................
1
A. LATAR BELAKANG ......................................................................
1
B. TUJUAN PENELITIAN ...................................................................
3
C. RUANG LINGKUP .........................................................................
3
II. TINJAUAN PUSTAKA .......................................................................
4
A. PROSES PENJADWALAN PRODUKSI ..........................................
4
B. PENJADWALAN TIPE JOB SHOP .................................................
7
C. TEKNIK OPTIMASI ........................................................................
8
D. ALGORITMA GENETIKA ..............................................................
9
1. Prosedur Umum Algoritma Genetika ............................................ 10 2. Representasi Kromosom ............................................................... 12 3. Operator-operator Algoritma Genetika .......................................... 14 a. Seleksi dan Reproduksi ............................................................. 15 b. Penyilangan .............................................................................. 16 c. Mutasi ...................................................................................... 20 4. Fungsi Fitness ............................................................................... 21 5. Bilangan Acak ............................................................................... 22 6. Kriteria Penghentian ..................................................................... 22 7. Perbandingan Algoritma Genetika dengan Teknik Optimasi Konvensional ................................................................................ 22 E. PENELITIAN TERDAHULU .......................................................... 24 III. METODOLOGI PENELITIAN .......................................................... 26 A. KERANGKA PEMIKIRAN ............................................................. 26
