IMPLEMENTASI ALGORITMA CAT SWARM OPTIMIZATION DALAM

MENYELESAIKAN JOB SHOP SCHEDULING PROBLEM (JSSP)

KOMPETENSI FINANSIAL

SKRIPSI

I WAYAN RADIKA APRIANA

1108405016

JURUSAN MATEMATIKA

FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM

UNIVERSITAS UDAYANA

BUKIT JIMBARAN

2016

ii

LEMBAR PERSEMBAHAN

Semoga pikiran baik datang dari segala penjuru arah dan semoga

Tuhan Yang Maha Esa menyertai setiap langkah perjuangan

Saya persembahkan tulisan ini kepada kedua orang tua dan keluarga tercinta

Yang telah membesarkan dan merawat saya hingga saat ini

Banyak hal yang telah diberikan dan dikorbankan

Hingga kini saya dapat berada di posisi ini

Dan semoga pencapaian ini menjadi sebagian kecil kebahagiaan yang bisa saya

berikan serta menjadi awal dari kebahagiaan-kebahagiaan selanjutnya untuk mereka

iii

IMPLEMENTASI ALGORITMA CAT SWARM OPTIMIZATION DALAM

MENYELESAIKAN JOB SHOP SCHEDULING PROBLEM (JSSP)

KOMPETENSI FINANSIAL

[SKRIPSI]

Sebagai syarat untuk memperoleh gelar Sarjana Sains bidang Matematika pada

Fakultas Matematika dan Ilmu Pengetahuan Alam

Universitas Udayana

Tulisan ini merupakan hasil penelitian yang belum pernah dipublikasikan

I WAYAN RADIKA APRIANA

1108405016

Pembimbing II Pembimbing I

Kartika Sari, S.Si., M.Sc. Ni Ketut Tari Tastrawati, S.Si., M.Si.

NIP. 197007112003122001 NIP. 197405282002122002

iv

LEMBAR PENGESAHAN TUGAS AKHIR

Judul : Implementasi Algoritma Cat Swarm Optimization Dalam

Menyelesaikan Job Shop Scheduling Problem (JSSP)

Kompetensi : Finansial

Nama : I Wayan Radika Apriana

NIM : 1108405016

Fakultas/Jurusan : Matematika dan Ilmu Pengetahuan Alam/Matematika

Tanggal Seminar : 29 April 2016

Disetujui oleh :

Pembimbing II Pembimbing I

Kartika Sari, S.Si., M.Sc. Ni Ketut Tari Tastrawati, S.Si., M.Si.

NIP. 197007112003122001 NIP. 197405282002122002

Penguji I

Ir. Tjokorda Bagus Oka, Ph.D.

NIP. 195411261986031001

Penguji III Penguji II

Ir. I Putu Eka Nila Kencana, M.T. Luh Putu Ida Harini, S.Si., M.Sc.

NIP. 196506141992031004 NIP. 198002102003122001

Mengetahui,

Jurusan Matematika FMIPA Unud

Ketua,

Desak Putu Eka Nilakusmawati, S.Si., M.Si.

NIP. 197106111997022001

v

Judul : Implementasi Algoritma Cat Swarm Optimization Dalam

Menyelesaikan Job Shop Scheduling Problem (JSSP)

Nama : I Wayan Radika Apriana (NIM : 1108405016)

Pembimbing : 1. Ni Ketut Tari Tastrawati, S.Si., M.Si.

2. Kartika Sari, S.Si., M.Sc.

ABSTRAK

Algoritma Cat Swarm Optimization (CSO) merupakan salah satu algoritma

metaheuristik dengan dasar pemikirannya adalah dua perilaku kucing yaitu seeking

mode dan tracing mode. CSO dapat diimplementasikan dalam menyelesaikan kasus

optimasi. Salah satu permasalahan optimasi yang ada dalam kehidupan sehari-hari

adalah kasus Job Shop Scheduling Problem (JSSP).

Penelitian ini bertujuan untuk mengetahui kinerja algoritma CSO dalam

menyelesaikan kasus nyata JSSP. Data yang digunakan dalam penelitian ini adalah

data kasus 5 job – 12 mesin. Berdasarkan hasil penelitian, algoritma CSO efektif

dalam menyelesaikan kasus nyata JSSP untuk penjadwalan 5 job – 12 mesin di

industri peralatan pengolahan hasil pertanian CV Mitra Niaga Indonesia. Dalam

mengimplementasikan algoritma CSO pada kasus JSSP, pemilihan nilai parameter

yang tepat dapat menghasilkan solusi yang optimal. Selain itu, semakin besar

jumlah job dan mesin yang digunakan maka semakin sulit dan rumit permasalahan

JSSP yang harus diselesaikan.

Kata kunci : Cat Swarm Optimization, Job Shop Scheduling Problem, Makespan

vi

Title : Implementation Cat Swarm Optimization Algorithm to

Solve Job Shop Scheduling Problem (JSSP)

Name : I Wayan Radika Apriana (NIM : 1108405016)

Supervisor : 1. Ni Ketut Tari Tastrawati, S.Si., M.Si.

2. Kartika Sari, S.Si., M.Sc.

ABSTRACT

Cat Swarm Optimization (CSO) algorithm is a metaheuristic algorithm which

is based on two behaviors of cat, seeking and tracing. CSO algorithm is used in

solving optimization problems. One of the optimization problems which can be seen

in daily life is Job Shop Scheduling Problem (JSSP).

This study aimed to observe the performance of CSO algorithm in solving

JSSP. This study focused on 5 job-12 machine cases. According to this study, CSO

algorithm was effective in solving real case of JSSP in 5 jobs – 12 machines

scheduling at CV Mitra Niaga Indonesia agriculture tools industry. In implementing

CSO algorithm in JSSP, a correct parameter choosing could lead to an optimal

result. On other hand, the greater the number of jobs or machines the more complex

and difficult the JSSP that needed to be solved.

Keyword : Cat Swarm Optimization, Job Shop Scheduling Problem, Makespan

vii

KATA PENGANTAR

Puji syukur penulis panjatkan ke hadapan Ida Sang Hyang Widhi Wasa

karena berkat rahmat-Nya penulis dapat menyelesaikan Tugas Akhir yang berjudul

“Implementasi Algoritma Cat Swarm Optimazion Dalam Menyelesaikan Job

Shop Scheduling Problem (JSSP)”.

Dalam penulisan Tugas Akhir ini, penulis banyak mendapat bantuan dari

berbagai pihak, baik berupa dorongan semangat maupun sumbangan pemikiran.

Oleh karena itu, sehubungan dengan terselesaikannya tugas akhir ini, maka penulis

mengucapkan terima kasih kepada berbagai pihak yang telah membantu penulis,

antara lain :

1. Ibu Ni Ketut Tari Tastrawati, S.Si., M.Si. selaku Dosen Pembimbing I dan

Ibu Kartika Sari, S.Si., M.Sc. selaku Dosen Pembimbing II yang telah banyak

membantu, membimbing, serta memberikan semangat selama penyusunan

Tugas Akhir ini.

2. Bapak Ir. Tjokorda Bagus Oka, Ph.D. selaku penguji I, Ibu Luh Putu Ida Harini,

S.Si., M.Sc. selaku penguji II, dan Bapak Ir. I Putu Eka Nila Kencana, M.T.

selaku penguji III yang telah memberikan bimbingan dan masukan dalam

penyempurnaan Tugas Akhir ini.

3. Bapak dan Ibu dosen Jurusan Matematika serta pegawai Fakultas MIPA

Universitas Udayana yang telah memberikan dukungan, saran dan motivasi

ilmu selama penulis menjadi mahasiswa.

viii

4. Peneliti-peneliti sebelumnya yang tidak dapat disebutkan satu persatu yang

telah membantu saya memahami metode dan kasus yang saya gunakan dalam

penyelesaian Tugas Akhir ini.

5. Teman-teman di Jurusan Matematika yang telah memberikan dukungan

moral dalam penyelesaian Tugas Akhir ini.

6. Teman-teman yang tidak dapat disebutkan satu persatu yang telah

memberikan dukungan dalam penyelesaian tugas akhir ini.

Penulis menyadari penulisan Tugas Akhir ini masih jauh dari kesempurnaan,

oleh karena itu saran dan kritik yang membangun dari berbagai pihak sangat

diharapkan dalam penyempurnaan Tugas Akhir ini. Besar harapan penulis skripsi

ini dapat bermanfaat bagi semua pihak khususnya para pembaca di Universitas

Udayana terutama di Jurusan Matematika. Akhir kata penulis ucapkan terima

kasih.

Bukit Jimbaran, 29 April 2016

Penulis

ix

BIODATA ALUMNI

Nama Lengkap : I Wayan Radika Apriana

NIM : 1108405016

Jenis Kelamin : Laki-laki

Tempat/Tanggal Lahir : Denpasar/18 April 1993

Alamat Asal : Jl. Gandaria No. 18 Denpasar

Alamat Sekarang : Jl. Gandaria No. 18 Denpasar

Agama : Hindu

Tanggal Lulus : 26 April 2016

Tanggal Wisuda : 27 Agustus 2016

Kompetensi : Finansial

IP Kumulatif : 3,20

Predikat Kelulusan : Sangat Memuaskan

Nilai TOEFL Lokal : 477

Alamat Email : viruezradikaviruez@gmail.com

Nomor HP : 083119593065

Nama Ayah : I Wayan Astawa

Nama Ibu : Ni Made Gendri

Alamat Ayah/Ibu : Jl. Gandaria No. 18 Denpasar

x

DAFTAR ISI

Halaman

LEMBAR JUDUL ....................................................................................... i

LEMBAR PERSEMBAHAN ...................................................................... ii

LEMBAR PERNYATAAN ......................................................................... iii

LEMBAR PENGESAHAN ......................................................................... iv

ABSTRAK ................................................................................................... v

ABSTRACT ................................................................................................. vi

KATA PENGANTAR ................................................................................. vii

BIODATA ALUMNI ................................................................................... ix

DAFTAR ISI ................................................................................................ x

DAFTAR TABEL ........................................................................................ xii

DAFTAR GAMBAR ................................................................................... xiii

DAFTAR LAMPIRAN ................................................................................ xv

BAB I PENDAHULUAN ........................................................................ 1

1.1 Latar Belakang ...................................................................... 1

1.2 Rumusan Masalah ................................................................ 3

1.3 Batasan Masalah ................................................................... 3

1.4 Tujuan Penelitian ................................................................... 4

1.5 Manfaat Penelitian ................................................................. 4

BAB II TINJAUAN PUSTAKA .............................................................. 5

2.1 Job Shop Scheduling Problem (JSSP) .................................. 5

2.2 Formulasi Masalah Job Shop Statik ..................................... 8

2.3 Cat Swarm Optimization ...................................................... 13

2.4 Inertia Weight (𝑤) ................................................................ 19

BAB III METODE PENELITIAN ............................................................ 20

3.1 Sumber dan Jenis Data ......................................................... 20

3.2 Variabel Penelitian ............................................................... 20

3.3 Metode Analisis ..................................................................... 20

xi

3.3 Implementasi ........................................................................ 22

BAB IV HASIL DAN PEMBAHASAN ................................................... 23

4.1 Membuat Solusi JSSP Awal yang Valid .............................. 23

4.1.1 Menyatakan Data ke dalam Bentuk Matriks Informasi 24

4.1.2 Solusi Acak Awal ........................................................ 29

4.1.3 Proses Koreksi ............................................................. 30

4.1.4 Menghitung Makespan ................................................ 30

4.2 Menerapkan Algoritma Cat Swarm Optimization ................ 37

4.2.1 Uji Parameter ................................................................ 37

4.2.2 Penjadwalan 3 Job – 2 Mesin ...................................... 40

4.2.3 Penjadwalan 5 Job – 12 Mesin .................................... 42

BAB V SIMPULAN DAN SARAN ......................................................... 45

5.1 Simpulan ................................................................................ 45

5.2 Saran ..................................................................................... 45

DAFTAR PUSTAKA .................................................................................. 47

xii

DAFTAR TABEL

Tabel Halaman

2.1 Contoh Model Job Shop Statik ............................................................. 6

4.1 Waktu Proses, Urutan Mesin, dan Uurtan Proses pada

Kasus Penjadwalan 3 Job – 2 Mesin .................................................... 24

4.2 Waktu Proses, Urutan Mesin, dan Uurtan Proses pada

Kasus Penjadwalan 5 Job – 12 Mesin .................................................. 26

4.3 Job yang Diproduksi pada Kasus Penjadwalan 5 Job – 12 Mesin ....... 27

4.4 Mesin-Mesin yang Digunakan pada

Kasus Penjadwalan 5 Job – 12 Mesin .................................................. 27

4.5 Kombinasi Parameter Terbaik Kasus Penjadwalan 3 Job – 2 Mesin ... 39

4.6 Kombinasi Parameter Terbaik Kasus Penjadwalan 5 Job – 12 Mesin . 39

4.7 Hasil Simulasi 1 Algoritma CSO pada

Kasus Penjadwalan 3 Job – 2 Mesin .................................................... 41

4.8 Hasil Simulasi 2 Algoritma CSO pada

Kasus Penjadwalan 3 Job – 2 Mesin .................................................... 41

4.9 Hasil Simulasi Algoritma CSO pada

Kasus Penjadwalan 5 Job – 12 Mesin .................................................. 43

xiii

DAFTAR GAMBAR

Gambar Halaman

2.1 Ilustrasi Model Job Shop Statik ............................................................ 7

2.2 Bentuk Solusi Umum JSSP ................................................................... 8

2.3 Contoh Representasi Solusi .................................................................. 10

2.4 Solusi Baru yang Valid ......................................................................... 10

2.5 Penempatan Job 1 Operasi 1 pada Mesin 2 .......................................... 11

2.6 Penempatan Job 2 Operasi 1 pada Mesin 1 .......................................... 11

2.7 Penempatan Job 1 Operasi 2 pada Mesin 1 .......................................... 12

2.8 Penempatan Job 2 Operasi 2 pada Mesin 2 .......................................... 12

2.9 Bagan Cat Swarm Optimization ........................................................... 18

4.1 Ilustrasi Alur Proses pada Kasus Penjadwalan 3 Job – 2 Mesin .......... 25

4.2 Ilustrasi Alur Proses pada Kasus Penjadwalan 5 Job – 12 Mesin ........ 28

4.3 Solusi Acak Awal 3 Job – 2 Mesin ...................................................... 29

4.4 Solusi Acak Awal 5 Job – 12 Mesin .................................................... 29

4.5 Solusi Valid 3 Job – 2 Mesin ................................................................ 30

4.6 Solusi Valid 5 Job – 12 Mesin .............................................................. 30

4.7 Operasi Pertama (Operasi 1 pada Job 1) ............................................... 31

4.8 Penempatan Job 1 Operasi 1 pada Mesin 1 .......................................... 31

4.9 Operasi Kedua (Operasi 2 pada Job 1) .................................................. 32

4.10 Penempatan Job 1 Operasi 2 pada Mesin 2 .......................................... 32

4.11 Operasi Ketiga (Operasi 1 pada Job 2) .................................................. 33

xiv

4.12 Penempatan Job 2 Operasi 1 pada Mesin 2 .......................................... 33

4.13 Operasi Keempat (Operasi 2 pada Job 2) .............................................. 34

4.14 Penempatan Job 2 Operasi 2 pada Mesin 1 .......................................... 34

4.15 Operasi Kelima (Operasi 1 pada Job 3) ................................................. 35

4.16 Penempatan Job 3 Operasi 1 pada Mesin 1 .......................................... 35

4.17 Operasi Keenam (Operasi 2 pada Job 3) ............................................... 36

4.18 Penempatan Job 3 Operasi 2 pada Mesin 2 .......................................... 36

4.19 GANT Chart Solusi Kasus Penjadwalan 3 Job – 2 Mesin .................... 42

4.20 GANT Chart Solusi Kasus Penjadwalan 5 Job – 12 Mesin ................. 44

xv

DAFTAR LAMPIRAN

Lampiran

1 Matriks Informasi Kasus Penjadwalan 5 Job – 12 Mesin

2 Uji Parameter Kasus Penjadwalan 3 Job – 2 Mesin

3 Uji Parameter Kasus Penjadwalan 5 Job – 12 Mesin

4 Simulasi Program 1 Kasus Penjadwalan 3 Job – 2 Mesin

5 Simulasi Program 2 Kasus Penjadwalan 3 Job – 2 Mesin

6 Simulasi Program Kasus Penjadwalan 5 Job – 12 Mesin