Job shop scheduling problem dapat diselesaikan dengan metode algoritma genetik

BAB I

PENDAHULUAN

1.1         Latar Belakang Masalah

Penjadwalan merupakan suatu proses pengaturan sumber daya untuk menyelesaikan tugas-tugas dengan melibatkan pekerjaan, sumber daya, dan waktu.  Pekerjaan diproses pada setiap sumber daya dengan urutan tertentu selama waktu tertentu.  Tujuan dari masalah penjadwalan antara lain: meminimumkan waktu penyelesaian semua tugas (makespan), meminimumkan keterlambatan pengerjaan, meminimumkan waktu tunggu pada mesin, meminimumkan biaya, dan lain-lain.

Masalah penjadwalan merupakan salah satu aspek penting pada lingkungan industri. Misalkan suatu percetakan akan memproduksi brosur, koran, dan majalah dengan menggunakan 3 sumber daya, yaitu mesin cetak, mesin potong, dan mesin jilid.  Misal brosur hanya melalui mesin cetak, sementara koran setelah dicetak perlu dipotong, sedangkan majalah setelah dicetak, dijilid, lalu dipotong.  Pada beberapa masalah penjadwalan, pekerjaan memiliki batas waktu,  sehingga mempengaruhi prioritas pemrosesan.  Salah satu solusi untuk menyelesaikan masalah percetakan tersebut, dapat dimulai dengan menempatkan majalah pada mesin cetak, karena majalah memiliki urutan proses yang terpanjang.  Setelah majalah dicetak, proses untuk majalah dilanjutkan dengan menempatkan majalah pada mesin jilid, sementara akan ditentukan apakah brosur atau koran yang akan ditempatkan pada mesin cetak.  Penempatan brosur pada mesin cetak akan lebih baik dari pada koran, karena jika koran yang ditempatkan terlebih dahulu pada mesin cetak, maka kemungkinan koran dan majalah akan tiba di mesin potong pada waktu yang bersamaan.  Setelah brosur dicetak maka pemrosesan brosur selesai, dan koran dapat ditempatkan pada mesin cetak, sementara majalah ditempatkan pada mesin potong.  Proses dari majalah selesai setelah pemotongan, dan sebagai proses terakhir, koran ditempatkan pada mesin potong.  Masalah percetakan tersebut hanya menggunakan tiga sumber daya untuk menyelesaikan tiga pekerjaan, jika suatu masalah dengan pekerjaan dan sumber daya yang lebih banyak, maka pemrosesan akan menjadi lebih kompleks.

Job shop scheduling problem merupakan salah satu masalah penjadwalan yang memiliki kendala urutan pemrosesan tugas, dan setiap tugas harus melalui setiap mesin tepat satu kali.  Terdapat dua jenis metode yang biasa digunakan untuk menyelesaikan masalah job shop scheduling problem.  Metode eksak, seperti pemrograman linier dan pemrograman non-linier, dapat digunakan untuk ukuran job shop scheduling problem yang kecil.  Sedangkan untuk ukuran masalah yang besar, digunakan suatu pendekatan secara aproksimasi, seperti local search, simulated annealing, genetic algorithm, tabu search, dan ant colony optimization. Hal ini disebabkan karena untuk ukuran masalah yang besar, kompleksitasnya akan semakin besar.

Pada skripsi ini, pendekatan yang digunakan adalah algoritma genetik, dengan menerapkan teknik local search.  Algoritma genetik ditemukan oleh John Holland pada tahun 1960.  Algoritma ini menerapkan suatu proses evolusi biologi.  Banyak percobaan dalam menyelesaikan job shop scheduling problem dengan menggunakan metode algoritma genetik, tetapi masih terdapat beberapa percobaan yang menghasilkan solusi yang tidak layak.  Pada metode dalam skripsi ini, ketidaklayakan dari solusi dapat dihindari dengan menggunakan suatu skema yang menjaga urutan pemrosesan tugas. Kualitas dari solusi akan diuji dengan menggunakan beberapa masalah uji yang biasa dipakai untuk menyelesaikan job shop scheduling problem.

            Terdapat tiga operator dasar yang digunakan pada algoritma genetik, yaitu reproduksi, crossover, dan mutasi.  Reproduksi digunakan untuk menyeleksi solusi-solusi yang akan diproses, crossover digunakan untuk memperoleh solusi-solusi melalui proses perkawinan, dan mutasi digunakan untuk mengubah kualitas dari suatu solusi.  Pada skripsi ini, akan digunakan suatu operator crossover yang sederhana dan efisien, yang memastikan bahwa setiap solusi baru yang dihasilkan akan selalu layak.  Pada tahap mutasi, akan digunakan suatu operator yang mengarah pada suatu proses pencarian local search, dengan harapan akan meningkatkan kualitas dari solusi.

1.2       Perumusan Masalah

                        Apakah job shop scheduling problem dapat diselesaikan dengan menggunakan algoritma genetik, dan apakah pemilihan antara menggunakan mutasi sederhana dengan local search mutator akan mempengaruhi kinerja dari algoritma.

1.3       Tujuan Penulisan

            Penulisan skripsi ini bertujuan untuk melihat kemampuan dari local search genetic algorithm dalam menyelesaikan job shop scheduling problem dengan menggunakan suatu masalah uji yang biasa dipakai untuk menguji kinerja dari suatu program untuk menyelesaikan job shop scheduling problem.  Selain itu, akan dilihat juga perbandingan kinerja dari local search genetic algorithm antara hanya menggunakan crossover, menggunakan crossover dan mutasi sederhana, dan dengan menggunakan crossover dan local search mutator.

1.4       Pembatasan Masalah

            Job shop scheduling problem yang akan dibahas adalah job shop scheduling problem dengan tujuan meminimumkan makespan.  Sedangkan untuk pengujian, masalah uji yang digunakan dibatasi hanya untuk 3 masalah.

1.5       Sistematika Penulisan

                        Sistematika pembahasan skripsi ini adalah sebagai berikut: Bab I membahas tentang latar belakang, tujuan dari skripsi, batasan masalah, dan sistematika penulisan; Bab II membahas definisi dan teori dasar dari masalah penjadwalan, job shop scheduling problem, algoritma genetik, dan local search; Bab III membahas tentang local search genetic algorithm dalam menyelesaikan job shop scheduling problem; Bab IV membahas implementasi algoritma dan beberapa hasil eksperimen; dan terakhir Bab V membahas kesimpulan yang berdasarkan pada hasil eksperimen.

 Ayo Pesan Skripsi SEKARANG juga !