SKRIPSI JURUSAN MATEMATIKA JOB SHOP SCHEDULING PROBLEM


 " SKRIPSI JURUSAN MATEMATIKA "

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 nonlinier,
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.





NB : JIKA SOBAT INGIN VERSI LENGKAP DARI SKRIPSI INI SILAHKAN TINGGALKAN E-MAIL DI CHATBOX, SAYA AKAN MENGIRIMKAN GRATIS KE E-MAIL SOBAT..

TERIMA KASIH SUDAH BERKUNJUNG....................


Advertisement



1 Response to "SKRIPSI JURUSAN MATEMATIKA JOB SHOP SCHEDULING PROBLEM"