BAB I
PENDAHULUAN

I.1 Latar Belakang Masalah
Pada sebuah sistem produksi yang kompleks dapat terjadi penumpukan barang atau pekerjaan yang membentuk antrian panjang yang belum tentu dapat diselesaikan secara optimal. Sistem produksi yang melibatkan banyak mesin dan banyak proses dengan waktu yang bervariasi akan menemui banyak hambatan bila tidak ada metode penjadwalan yang tepat. Sistem yang tidak dapat bekerja secara efektif dan efisien, pada akhirnya dapat mempengaruhi proses produksi secara keseluruhan.
Job-shop Scheduling Problem (JSP) atau masalah penjadwalan job-shop adalah salah satu dari teori penjadwalan mesin yang ada. JSP secara umum dapat didefinisikan sebagai masalah pengalokasian sejumlah pekerjaan yang harus diproses melalui sejumlah mesin. Proses dari suatu pekerjaan pada suatu mesin disebut dengan operasi. Setiap pekerjaan terdiri dari satu set operasi dengan waktu tertentu dan urutan-urutan operasi pada mesin sudah terspesifikasi. Permasalahannya adalah menentukan urutan pengerjaan yang menghasilkan solusi terbaik bedasarkan kriteria tertentu, yaitu lama waktu total penyelesaian seluruh pekerjaan (completion time atau makespan).
JSP dapat digolongkan sebagai masalah optimasi kombinasi yang sulit, karena untuk mendapatkan makespan minimum harus dilakukan kombinasi operasi agar dapat diselesaikan oleh suatu mesin, dengan tetap memenuhi urutan proses operasi. Prosedur heuristik merupakan solusi alternatif yang dapat digunakan untuk menangani kompleksitas dari masalah penjadwalan, karena mampu mengeliminasi beberapa kemungkinan solusi tanpa harus mengeksplorasinya secara penuh. Teknik heuristik juga dapat membantu memutuskan kemungkinan solusi yang pertama kali perlu dievaluasi. Algoritma yang bersifat pendekatan dan probabilistik terhadap solusi yang ingin dicari biasanya dikenal dengan algoritma heuristik. Algoritma heuristik tidak selalu memberikan hasil yang diinginkan, tetapi secara ekstrim bernilai pada pemecahan masalah. Heuristik yang bagus dapat mengurangi waktu yang dibutuhkan dengan cara mengeliminasi kebutuhan untuk mempertimbangkan kemungkinan solusi yang tidak diperlukan. Algoritma genetika merupakan suatu metode penyelesaian masalah yang tergolong heuristik. Algoritma genetika dapat memberikan kemungkinan penyelesaian masalah yang sangat banyak dengan mempertimbangkan semua kemungkinan tersebut dalam mengambil keputusan.
Masalah penjadwalan job-shop yang ada pada dunia nyata melibatkan parameter yang tidak pasti sehingga lebih efektif jika mengenalkan logika fuzzy dan merumuskan masalah menjadi optimasi fuzzy. Logika fuzzy dikembangkan untuk menangani permasalahan-permasalahan yang himpunan penyelesaiannya tidak tepat (kabur). Pada banyak permasalahan, logika fuzzy dipilih karena toleransinya terhadap ketidaktepatan data. Setiap permasalahan yang bisa diselesaikan dengan fuzzy, penentuan tipe dan parameter himpunan fuzzy dilakukan secara subjektif. Akibatnya, setiap orang akan mempunyai kesimpulan yang berbeda untuk masalah yang sama karena himpunan fuzzynya berbeda. Penerapan logika fuzzy pada masalah penjadwalan job-shop atau fuzzy job-shop scheduling (FJSP), diharapkan dapat merepresentasikan penyelesaian optimal dengan memperhitungkan kemungkinan parameter yang belum pasti.

1.2 Maksud dan Tujuan Penulisan
Penyusunan skripsi ini dimaksudkan sebagai salah satu syarat untuk memperoleh derajat sarjana S1 Program Studi Matematika Jurusan Matematika, sedangkan tujuan penulisan skripsi ini adalah untuk membahas masalah penjadwalan job-shop dengan fuzzy dan menyelesaikannya dengan menggunakan algoritma genetika.

I.3 Rumusan Masalah
Masalah penjadwalan Job-shop merupakan masalah dalam menentukan urutan proses operasi pada tiap mesin dengan tujuan meminimumkan waktu penyelesaian maksimum. Untuk mendapatkan hasil penjadwalan yang optimal, maka digunakan algoritma genetika. Algoritma genetika menyelesaikan masalah dengan membentuk populasi awal secara acak kemudian dibangkitkan menjadi jadwal aktif dengan menggunakan Algoritma Giffler dan Thompson, mengevaluasi fungsi tujuan dan melakukan perbaikan generasi. Penerapan logika fuzzy pada JSP dapat mengcover kemungkinan dari ketidaktepatan parameter penjadwalan. Masalah yang akan dibahas pada skripsi ini adalah masalah penjadwalan job-shop fuzzy dan selanjutnya diselesaikan dengan algoritma genetika.

1.4 Batasan Masalah
Skripsi ini membahas pengertian algoritma genetika, operator dalam algoritma genetika dan prinsip kerja algoritma genetika pada penjadwalan job-shop. Kemudian dibahas masalah penjadwalan job-shop fuzzy dan diselesaikan menggunakan algoritma genetika.
Pada algoritma genetika ini dibentuk populasi awal yang dibangkitkan menjadi jadwal aktif dengan menggunakan algoritma Giffler dan Thompson. Untuk mengurutkan kromosom dari yang terbaik hingga kromosom terburuk digunakan seleksi rangking. Pada proses evolusi menggunakan perkawinan silang dengan metode partial schedule exchange crossover, dan mutasi dengan metode job-pair exchange mutation sedangkan kriteria berhenti yang digunakan adalah berhenti pada generasi tertentu.

1. 5 Metode penelitian
Penulisan skripsi ini dilakukan penulis, dengan melihat dan mengkaji bagaimana suatu penyelesaian masalah penjadwalan Job-shop fuzzy dengan menggunakan algoritma genetika. Metode penulisan yang digunakan adalah studi pustaka melalui beberapa buku dan artikel dari internet yang berkaitan dengan permasalahan yang dihadapi. Selanjutnya dirumuskan masalah penjadwalan job-shop dengan tambahan logika fuzzy didalamnya. Untuk menyelesaikannya digunakan algoritma genetika yang diproses dengan program Delphi 7. Output yang diperoleh dianalisa lebih lanjut dan dikembalikan pada permasalahan. Pada pelaksanaannya untuk mendapatkan pengarahan dan pendalaman materi, penulis juga senantiasa berkonsultasi dengan dosen pembimbing.

I.6 Tinjauan Pustaka
Beberapa referensi diambil dari publikasi lewat internet misalnya karangan Yogi Yogaswara yang berjudul “Modifikasi Algoritma Genetika Untuk Penjadwalan n JOB m Mesin Flowshop”, karangan Carole Fayad dan Sanja Petrovic yang berjudul “A Genetic Algorithm for the Real-World Fuzzy Job Shop Scheduling”.
Buku karangan Matoshi Sakawa yang berjudul “Genetic Algorithms and Fuzzy Multiobjective Optimization” yang menjelaskan tentang masalah penjadwalan job-shop dengan dan tanpa fuzzy yang diselesaikan dengan menggunakan algoritma genetika. Selain itu digunakan juga buku karangan Mitsuo Gen dan Runwei Cheng yang berjudul ”Genetic Algorithms and Engineering Optimization” yang menjelaskan tentang masalah penjadwalan job-shop dengan menggunakan algoritma genetika.
Konsep algoritma genetika juga dibahas dalam beberapa skripsi Oskar (Oskar, 1999) yang berjudul Penerapan Algoritma Genetika dalam Penyelesaian Masalah NP-Complete, skripsi Rochmanah (Rochmanah, 2003) yang berjudul “Implementasi Algoritma Genetika pada Masalah Penjadwalan Kerja Job-shop”, selanjutnya digunakan juga sebagai referensi skripsi Dwi Susilowati yang bejudul ” Penyelesaian Program Linear Multitujuan Fuzzy pada Masalah Knapsack dengan Algoritma Genetika Biner”.
Artikel Obitko yang berjudul “Introduction to Genetic Algorithma”. Artikel Widodo yang berjudul “program Linear Multi Objektif Fuzzy Interaktif”.
Pembahasan himpunan fuzzy, bilangan fuzzy, dan keputusan fuzzy menggunakan buku karangan Masatoshi Sakawa yang berjudul ”Fuzzy sets and interactive multiobjective optimization”. Penjelasan fungsi kontinu dan fungsi monoton menggunakan buku karangan Bartle dan Sherbert [1982] yang berjudul ”Introduction to Real Analysis”.
Publikasi lewat internet karangan Arwan Ahmad Khoirudin yang berjudul ”Algoritma Genetika untuk Menentukan Jenis Kurva dan Parameter Himpunan Fuzzy” menjelaskan tentang permasalahan yang bisa diselesaikan dengan fuzzy menggunakan algoritma genetika.

I. 7 Sistematika Penulisan
Penulisan skripsi ini disajikan dalam lima bab yaitu :

BAB I PENDAHULUAN
Bab I menjelaskan tentang latar belakang masalah, maksud dan tujuan penulisan, rumusan masalah, batasan masalah, metode penelitian, tinjauan pustaka, dan sistematika penulisan.
BAB II DASAR TEORI
Bab II menjelaskan tentang dasar-dasar teori yang akan digunakan pada penulisan bab-bab selanjutnya.
BAB III ALGORITMA GENETIKA PADA MASALAH PENJADWALAN JOB-SHOP
Bab III membahas tentang definisi, struktur umum, operator dan parameter dalam algoritma genetika pada masalah penjadwalan job-shop.
BAB IV MASALAH PENJADWALAN JOB-SHOP FUZZY
Bab IV membahas masalah implementasi algoritma genetika pada masalah penjadwalan job-shop dengan fungsi tujuan fuzzy.
BAB V PENUTUP
Bab terakhir berisi kesimpulan mengenai hasil pembahasan penggunaan algoritma genetika dalam menyelesaikan masalah penjadwalan job-shop fuzzy dan saran-saran untuk penelitian algoritma genetika selanjutnya.