ABSTRAK
Job shop scheduling problem merupakan salah satu masalah penjadwalan yang memiliki kendala urutan pemrosesan tugas. Pada skripsi ini, metode yang akan digunakan untuk menyelesaikan job shop scheduling problem adalah algoritma genetik. Algoritma genetik merupakan suatu algoritma pencarian yang menerapkan proses evolusi biologi untuk menemukan solusi terbaik dari suatu masalah, dengan melibatkan tiga operator dasar, yaitu reproduksi, crossover, dan mutasi. Terdapat dua jenis mutasi yang akan dilakukan, yaitu mutasi sederhana dan local search mutator, sehingga algoritma ini disebut dengan local search genetic algorithm. Kedua operator crossover dan mutasi tidak harus selalu dilakukan, bergantung pada parameter yang ditentukan. Dari hasil percobaan, diperoleh bahwa algoritma yang melakukan local search mutator akan lebih cepat konvergen. Kemampuan dari algoritma ini diuji dengan menggunakan masalah uji yang umum dipakai untuk masalah job shop scheduling problem.
Kata kunci: algoritma genetik, job shop scheduling problem, local search. vii + 45 hlm. ; lamp. Bibliografi: 6 (1989 – 2004)
iii
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
1
2
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
3
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.
4
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.
5
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.
BAB II DEFINISI DAN TEORI DASAR
2.1
Masalah Penjadwalan
Penjadwalan merupakan suatu proses pengaturan sumber daya untuk menyelesaikan tugas-tugas dengan melibatkan waktu. Terdapat berbagai bentuk sumber daya dan tugas pada suatu organisasi. Sumber daya dapat berupa mesin pada suatu workshop, landasan terbang pada suatu bandara, processing units pada suatu lingkungan komputasi, dan masih banyak lagi. Tugas dapat berupa operasi pada suatu proses produksi, pemberangkatan dan pendaratan pada suatu bandara, eksekusi pada program komputer, dan lain-lain. Masing-masing tugas mempunyai suatu tingkat prioritas tertentu, waktu mulai pengerjaan, dan batas waktu pengerjaan. Tujuan dari penjadwalan ini pun beragam, antara lain: meminimumkan waktu penyelesaian semua tugas, meminimumkan keterlambatan pengerjaan, meminimumkan waktu tunggu, meminimumkan biaya dan lain-lain. Pada masalah penjadwalan, banyaknya pekerjaan dan sumber daya (yang selanjutnya pada skripsi ini disebut mesin) berhingga. Jumlah dari pekerjaan dinyatakan dengan n dan jumlah mesin dinyatakan dengan m. Biasanya, indeks j mengacu pada pekerjaan sedangkan indeks i mengacu
6
7
pada mesin. Jika suatu pekerjaan mensyaratkan sejumlah langkah pemrosesan atau operasi, maka pasangan terurut (i, j) merujuk pada langkah pemrosesan atau operasi dari pekerjaan j pada mesin i, dan biasa disebut dengan tugas (i, j). Tugas merupakan kombinasi pekerjaan dengan mesin. Misalkan suatu pekerjaan harus melalui 3 buah mesin, maka pekerjaan tersebut terdiri dari tiga tugas. Data-data yang berhubungan dengan pekerjaan j, antara lain: processing time (pij) yaitu waktu yang dibutuhkan untuk menyelesaikan pekerjaan j pada mesin i, release date (rj) yaitu waktu awal untuk memproses pekerjaan j, due date (dj) yaitu batas waktu untuk menyelesaikan pekerjaan j, dan weight (wj) yaitu bobot prioritas pekerjaan j. Terdapat setidaknya tiga jenis penjadwalan, yaitu: flow shop, job shop, dan open shop. Pada flow shop, terdapat m mesin yang terurut, semua pekerjaan harus diproses pada setiap mesin dengan urutan yang sama. Pada job shop dengan m mesin, setiap pekerjaan harus diproses pada setiap mesin tepat satu kali dengan urutannya masing-masing. Sedangkan pada open shop, terdapat m mesin, dimana setiap pekerjaan dapat diproses lebih dari satu kali pada setiap mesin dengan urutannya masing-masing. Masalah penjadwalan yang akan dibahas pada skripsi ini adalah jenis penjadwalan job shop.
8
2.2
Job Shop Scheduling Problem
Di dalam Job shop scheduling problem, diberikan suatu masalah dengan n pekerjaan dan m mesin. Setiap pekerjaan harus diproses tepat satu kali pada setiap mesin sesuai dengan urutannya masing-masing. Karena tugas adalah kombinasi dari pekerjaan dan mesin, maka dua tugas dari suatu pekerjaan tidak boleh dikerjakan pada waktu yang bersamaan, dan setiap mesin hanya dapat memproses paling banyak satu pekerjaan pada satu waktu. Tujuan dari job shop scheduling problem adalah mencari suatu jadwal yang meminimumkan waktu yang dibutuhkan untuk menyelesaikan semua pekerjaan (makespan). Job shop scheduling problem merupakan salah satu masalah optimisasi kombinatorik, jadwal diperoleh dengan permutasi dari seluruh pekerjaan pada sembarang mesin. Karena terdapat m mesin, maka ruang pencarian solusi sebesar (n!)m. Sehingga job shop scheduling problem dikarakteristikkan sebagai masalah NP-hard. Metode yang digunakan untuk menyelesaikan masalah NP-hard ini, antara lain dengan: pendekatan secara eksak dan pendekatan secara aproksimasi. Pendekatan secara eksak yang digunakan seperti pemrograman linier, pemrograman non-linier, dan lain-lain. Sedangkan pendekatan secara aproksimasi yang biasa digunakan yaitu pendekatan heuristik, antara lain dengan menggunakan local search, simulated annealing, genetic algorithm, dan tabu search.
9
Untuk menghitung makespan suatu jadwal pada masalah job shop scheduling problem, digunakan suatu grafik yang dinamakan Gantt-Chart. Gantt-Chart adalah suatu grafik yang menampilkan durasi dari tugas terhadap perubahan waktu. Pada contoh 2.1, diberikan suatu masalah job shop scheduling.
Contoh 2.1: Diberikan suatu masalah yang terdiri dari 2 pekerjaan dan 3 mesin. Urutan pekerjaan dan waktu yang dibutuhkan untuk menyelesaikan pekerjaan, diberikan pada Tabel 2.1 dengan P menyatakan pekerjaan, m menyatakan mesin, dan t menyatakan waktu.
Tabel 2.1 Urutan pekerjaan dan waktu proses untuk contoh 2.1. M,t m,t m,t P1
2,3
3,4
1,6
P2
1,4
3,5
2,2
Data dari Tabel 2.1 menunjukkan setiap pekerjaan harus diproses pada setiap mesin dengan urutannya masing-masing. Urutan pemrosesan pekerjaan 1 yaitu oleh mesin 2 selama 3 satuan waktu, mesin 3 selama 4 satuan waktu, dan mesin 1 selama 6 satuan waktu. Sedangkan urutan pemrosesan untuk pekerjaan 2 yaitu oleh mesin 1 selama 4 satuan waktu, mesin 3 selama 5 satuan waktu, dan mesin 2 selama 2 satuan waktu.
10
Ruang solusi pada masalah job shop adalah (n!)m, sehingga masalah pada contoh 2.1 memiliki (2!)3 = 8 jadwal yang mungkin. Dua dari delapan jadwal yang mungkin, dengan format (pekerjaan, mesin), antara lain: (1,2) (2,1) (1,3) (2,3) (1,1) (2,2) (2,1) (1,2) (2,3) (1,3) (2,2) (1,1) Jadwal yang pertama menyatakan bahwa pemrosesan jadwal diawali dengan pekerjaan 1 pada mesin 2, pekerjaan 2 pada mesin 1, pekerjaan 1 pada mesin 3, dan seterusnya hingga pekerjaan 2 pada mesin 2. Sedangkan jadwal yang kedua dikerjakan dengan urutan pemrosesannya sendiri.
m3 m2 m1
m3 m2 m1 waktu
3
waktu
12
Gambar 2.1.a
Gambar 2.1.d
m3 m2 m1
m3 m2 m1 4
waktu
13 waktu
Gambar 2.1.b
Gambar 2.1.e
m3 m2 m1
m3 m2 m1 7
Gambar 2.1.c
waktu
14
Gambar 2.1.f
Gambar 2.1 Gantt-Chart dari jadwal (1,2)(2,1)(1,3)(2,3)(1,1)(2,2)
waktu
11
Gambar 2.1 menunjukkan tahap pembentukan Gantt-Chart dari jadwal (1,2)(2,1)(1,3)(2,3)(1,1)(2,2). Tahap pembentukan Gantt-Chart dimulai dari pekerjaan 1 pada mesin 2 selama 3 satuan waktu, seperti pada Gambar 2.1.a. Pada Gambar 2.1.b, pembentukan dilanjutkan dengan pekerjaan 2 pada mesin 1 selama 4 satuan waktu. Pada Gambar 2.1.c, dibentuk pekerjaan 1 pada mesin 3 selama 4 satuan waktu setelah pekerjaan 1 pada mesin 2 selesai. Pekerjaan 2 pada mesin 3 selama 5 satuan waktu dibentuk setelah mesin 3 selesai mengerjakan pekerjaan 1, seperti terlihat pada Gambar 2.1.d. Pada Gambar 2.1.e, pembentukan pekerjaan 1 pada mesin 1 selama 6 satuan waktu setelah pekerjaan 1 pada mesin 3 selesai, dan terakhir pembentukan pekerjaan 2 pada mesin 2 selama 2 satuan waktu setelah pekerjaan 2 pada mesin 3 selesai, seperti terlihat pada Gambar 2.1.f. Sehingga diperoleh makespan sebesar 14.
m3 m2 m1 19
Gambar 2.2 Gantt-Chart dari jadwal (2,1) (1,2) (2,3) (1,3) (2,2) (1,1) Ket : P1
P2
Gambar 2.2 merupakan Gantt-Chart dari jadwal (2,1) (1,2) (2,3) (1,3) (2,2) (1,1), dengan makespan sebesar 19. Sehingga terlihat bahwa makespan jadwal yang pertama lebih baik dari makespan jadwal yang kedua.
waktu
12
2.3
Algoritma Genetik
Algoritma genetik adalah suatu algortima pencarian yang menerapkan proses evolusi biologi dengan tujuan untuk menemukan solusi terbaik dari suatu masalah. Istilah-istilah yang sering digunakan pada algoritma genetik adalah gen, kromosom, populasi, generasi, dan fitness. Gen adalah rangkaian yang membentuk suatu kromosom, kromosom menyatakan suatu solusi dari masalah, populasi adalah kumpulan dari kromosom-kromosom dengan ukuran yang telah ditentukan, dan generasi menyatakan keturunan. Fungsi tujuan yang biasa dipakai pada algoritma genetik adalah fungsi fitness, yaitu fungsi yang menyatakan kekuatan dari suatu kromosom. Ide dasar dari algoritma ini adalah membentuk suatu populasi awal secara acak, yang akan diproses melalui tiga operator dasar dari algoritma genetik, sehingga menghasilkan populasi baru untuk generasi berikutnya. Tiga operator dasar tersebut adalah: reproduksi, crossover, dan mutasi. Reproduksi digunakan untuk menyeleksi kromosom-kromosom yang akan diproses, crossover digunakan untuk mengawinkan pasangan kromosom sehingga menghasilkan kromosom-kromosom baru, dan mutasi digunakan untuk mengubah satu atau lebih gen pada suatu kromosom. Algoritma genetik dapat digunakan untuk menyelesaikan masalah optimisasi seperti masalah penjadwalan, transportasi, permainan komputer, traveling salesman problem, dan lain-lain. Yang membedakan antara
13
algoritma genetik dengan metode optimisasi dan pencarian lainnya adalah: algoritma genetik bekerja dengan suatu pengkodean dari himpunan parameter, algoritma genetik mencari dari suatu populasi titik (bukan dari suatu titik), dan algoritma genetik menggunakan aturan transisi probabilistik, bukan aturan deterministik.
2.3.1
Pembentukan Populasi Awal
Dalam menjalankan algoritma genetik pada suatu masalah, pembentukan suatu populasi awal merupakan salah satu bagian yang penting. Populasi awal diperoleh dengan cara mengambil kromosomkromosom secara acak sebanyak popSize, dimana popSize adalah ukuran populasi yang diinginkan. Terdapat banyak jenis format dari kromosom, tergantung pada masalahnya. Salah satunya ialah dengan menggunakan untaian bilangan biner, seperti 01101.
2.3.2
Reproduksi
Reproduksi adalah suatu operator genetik yang memilih kromosom-kromosom dari populasi generasi saat ini yang akan diproses untuk masuk ke populasi generasi berikutnya. Pemilihan suatu kromosom dilakukan berdasarkan pada kekuatan (fitness) dari kromosom tersebut,
14
semakin kuat suatu kromosom maka semakin besar kemungkinan kromosom tersebut terpilih, sebaliknya semakin lemah suatu kromosom maka semakin kecil kemungkinan kromosom tersebut terpilih. Beberapa tipe dari operator reproduksi antara lain: roda roulette dan random. Roda roulette adalah satu dari tipe operator reproduksi yang paling sering digunakan. Pada roda roulette, setiap kromosom dari populasi memiliki suatu ukuran tempat pada diagram pie yang sesuai dengan proporsi dari persentasi nilai fitness-nya. Reproduksi diperoleh dengan memutar roda roulette sebanyak k kali (dimana k adalah ukuran populasi). Operator reproduksi random membentuk suatu populasi yang baru dengan memilih kromosom-kromosom dari populasi secara acak. Penggunaan roda roulette untuk memproduksi suatu populasi dengan ukuran populasi 4 kromosom diberikan pada contoh 2.2.
Contoh 2.2: Misalkan diberikan suatu populasi dimana kromosom-kromosomnya ditulis dalam bilangan biner dan nilai fitness-nya merupakan nilai numerik dari untaian biner tersebut. Proporsi dari masing-masing kromosom merupakan persentasi dari nilai fitness terhadap total fitness. Nilai fitness dan proporsi dari masing-masing kromosom diberikan pada Tabel 2.2.
15
Tabel 2.2 Nilai fitness dan persentasi total fitness tiap kromosom pada populasi untuk contoh 2.2. Kromosom Nilai Fitness % Total Fitness 01101
13
18,6
01110
14
20,0
11000
24
34,3
10011
19
27,1
Total
70
100
Diagram pie pada Gambar 2.3 merupakan roda roulette yang dibentuk berdasarkan proporsi yang diperoleh pada Tabel 2.2. Reproduksi dilakukan dengan memutar roda roulette sebanyak 4 kali (sesuai dengan ukuran populasi) dengan harapan kromosom dengan proporsi terbesar, yaitu kromosom 11000 (dengan proporsi sebesar 34,3%), memiliki probabilitas terpilih yang lebih besar dibandingkan dengan kromosom lainnya.
18,6% 27,1%
20,0%
34,3%
Gambar 2.3 roda roulette untuk Tabel 2.2.
16
2.3.3
Crossover
Operator crossover adalah suatu operator genetik yang mengawinkan dua kromosom (sebut parent) untuk menghasilkan dua kromosom baru (sebut child). Dilakukan atau tidaknya suatu operator crossover bergantung pada suatu parameter yang disebut dengan probabilitas crossover (Pc). Ide dibalik operator crossover adalah perkawinan dari dua kromosom parent akan menghasilkan dua kromosom child yang lebih baik jika karakteristik-karakteristik terbaik dari masing-masing parent diambil. Akan tetapi pada beberapa tipe operator crossover, karakteristikkarakteristik tersebut tidak terlalu diperhatikan, sehingga tidak ada jaminan bahwa kromosom-kromosom yang baru akan lebih baik. Beberapa tipe dari operator crossover antara lain: one point, two point, dan uniform. One point adalah satu dari tipe operator crossover yang paling sering digunakan. One point dilakukan dengan memilih satu cross point secara acak, kemudian kromosom dari dua parent bertukar tempat pada point ini untuk menghasilkan dua kromosom child yang baru. Operator crossover two point hampir sama dengan one point, bedanya pada two point dipilih dua cross point secara acak. Pada operator crossover uniform, digunakan suatu rasio untuk menentukan gen yang akan diturunkan berasal dari kromosom parent yang mana. Pembentukan dua kromosom child dari dua kromosom parent dengan menggunakan operator crossover one point, ditunjukkan pada contoh 2.3.
17
Contoh 2.3: Misal diberikan dua kromosom parent P1 dan P2, dan misal secara acak terpilih suatu cross point adalah 3. Maka crossover dilakukan dengan menggabungkan gen-gen dari kromosom P1 sebelum cross point dan gengen dari kromosom P2 setelah cross point, untuk menghasilkan kromosom child, C1. Sedangkan C2 diperoleh dengan cara sebaliknya. P1 :
1 1 0 0 0
P2 :
1 0 0 1 1
C1 :
1 1 0 1 1
C2:
1 0 0 0 0
Operator crossover yang akan digunakan untuk menyelesaikan job shop scheduling problem pada local search genetic algorithm adalah taskCrossover, penjelasan lebih lanjut tentang taskCrossover akan dibahas pada Sub-Subbab 3.1.4.
2.3.4
Mutasi
Operator mutasi adalah suatu operator genetik yang mengubah satu atau lebih nilai gen pada suatu kromosom dari keadaan awal. Dilakukan
18
atau tidaknya suatu operator mutasi bergantung pada suatu parameter yang disebut dengan probabilitas mutasi (Pm). Beberapa tipe dari operator mutasi antara lain: swap mutation, flip bit, dan boundary. Swap mutation adalah salah satu tipe operator mutasi yang paling sering digunakan. Swap mutation dilakukan dengan menukar dua posisi gen yang terpilih secara acak, sehingga diperoleh suatu kromosom yang baru. Flip bit dilakukan dengan cara membalikkan nilai dari suatu gen yang terpilih secara random (0 menjadi 1 dan 1 menjadi 0), flip bit hanya dapat digunakan pada gen-gen biner. Operator mutasi boundary dilakukan dengan mengganti nilai dari suatu gen yang terpilih secara acak dengan batas atas atau batas bawah dari gen tersebut, boundary hanya dapat digunakan pada gen-gen yang merupakan bilangan bulat. Untuk menyelesaikan job shop scheduling problem pada local search genetic algorithm akan digunakan dua operator mutasi yang akan dipilih secara acak, yaitu mutasi sederhana dan suatu operator mutasi yang menerapkan pendekatan local search. Penjelasan mengenai local search akan diberikan secara umum pada Subbab 2.4, mengenai mutasi sederhana dan local search mutator akan dibahas pada Sub-Subbab 3.1.5 dan Subbab 3.3. Contoh 2.4 dibawah ini menunjukkan penggunaan swap mutation pada suatu kromosom dari populasi.
19
Contoh 2.4: Misal diberikan suatu kromosom 11000, dan misal terpilih gen ke-2 dan ke-4 secara acak. Maka swap mutation dilakukan dengan menukar posisi dari gen ke-2 dengan gen ke-4.
1 1 0 0 0
2.4
1 0 0 1 0
Local Search
Local search merupakan salah satu teknik pencarian yang sederhana. Tujuan dari local search adalah untuk memperoleh suatu solusi yang memiliki nilai optimal. Proses pencarian dimulai dari solusi awal yang layak, penentuan solusi awal bergantung pada permasalahan. Selanjutnya dibangun suatu lingkungan dari solusi saat ini, yaitu himpunan solusi-solusi yang dapat diperoleh dengan satu langkah dari solusi tersebut. Himpunan solusi-solusi ini disebut tetangga (neighborhood) dari solusi saat ini. Pada lingkungan tersebut dipilih suatu solusi baru yang merupakan solusi terbaik, kemudian dari solusi baru tersebut akan dibangun lingkungan yang baru. Proses tersebut akan terus berulang hingga kriteria berhenti ditemukan, dan solusi terakhir merupakan solusi yang mempunyai nilai optimal. Meskipun mempunyai peran penting dalam menyelesaikan masalah optimisasi, teknik ini masih memiliki kelemahan, yaitu dapat terjebak pada solusi lokal.
BAB III LOCAL SEARCH GENETIC ALGORITHM DALAM MENYELESAIKAN JOB SHOP SCHEDULING PROBLEM
Bab ini akan membahas tentang penggunaan algoritma genetik untuk job shop scheduling problem. Masing-masing jadwal baik yang sudah layak maupun yang tidak layak (dalam algoritma genetik, jadwal disebut kromosom) pada populasi akan melalui proses pembentukan menjadi suatu jadwal yang layak dengan menggunakan suatu skema yang dinamakan Task Assignment Scheme (TAS), yang akan dibahas pada subbab 3.2. Kemudian masingmasing jadwal tersebut akan menjalani suatu proses evolusi hingga diperoleh suatu jadwal dengan makespan minimum yang mungkin. Pada bagian evolusi akan diterapkan tiga operator dasar algoritma genetik, yaitu reproduksi, crossover, dan mutasi. Suatu operator mutasi yang mengarah pada metode local search akan digunakan dengan harapan memperoleh suatu jadwal yang optimal. Rincian mengenai local search mutator, akan dijelaskan pada subbab 3.3.
20
21
3.1
Penyajian Kromosom dan Operasi Algoritma Genetik
3.1.1 Penyajian dan Pembuatan Populasi Awal
Seperti telah dijelaskan pada sub-subbab 2.3.1, bahwa pembentukkan populasi awal merupakan salah satu bagian yang penting. Pada masalah job shop scheduling, kromosom ditampilkan sebagai suatu rangkaian dari tugas, yaitu kombinasi pekerjaan dengan mesin. Kromosom diperoleh secara acak dengan memperhatikan urutan dari masing-masing pekerjaan. Kromosom ditulis dalam format (pekerjaan, mesin, waktu proses) seperti ditunjukkan pada contoh 3.1.
Contoh 3.1: Salah satu kromosom dari masalah pada contoh 2.1 adalah: (1,2,3) (2,1,4) (1,3,4) (2,3,5) (1,1,6) (2,2,2) Untuk pembacaan yang lebih mudah serta untuk mengefisienkan komputasi dan penyimpanan, format (pekerjaan, mesin, waktu proses) dari kromosom dapat di sederhanakan dengan menghilangkan waktu proses, sehingga contoh kromosom diatas dapat ditulis sebagai berikut: (1,2) (2,1) (1,3) (2,3) (1,1) (2,2)
22
Seperti diberikan pada contoh 2.1, suatu masalah job shop scheduling dapat disajikan dalam bentuk tabel, dimana baris menyatakan mesin dan waktu proses dari tiap pekerjaan, dan kolom menyatakan urutan untuk tiap pekerjaan pada sembarang mesin. Suatu populasi awal diperoleh dengan permutasi pada tiap kolom. Permutasi tersebut dilakukan sebanyak popSize kali, dimana popSize adalah ukuran populasi yang ditentukan. Salah satu populasi awal yang mungkin, yang dapat diperoleh dari masalah pada contoh 2.1, diberikan pada contoh 3.2 dibawah ini.
Contoh 3.2: Misal telah ditentukan popSize adalah 4. Dengan melakukan permutasi tiap kolom dari masalah pada contoh 2.1, akan diperoleh suatu populasi awal seperti pada Tabel 3.1. Nilai makespan dari masing-masing kromosom diperoleh dengan menggunakan Gantt-Chart, sedangkan nilai fitness diperoleh berdasarkan penghitungan fungsi fitness pada sub-subbab 3.1.2 Tabel 3.1 Makespan dan nilai fitness tiap kromosom pada populasi untuk contoh 3.2. Kromosom
Makespan
Nilai fitness
(1,2) (2,1) (2,3) (1,3) (2,2) (1,1) (2,1) (1,2) (1,3) (2,3) (1,1) (2,2) (2,1) (1,2) (1,3) (2,3) (2,2) (1,1) (2,1) (1,2) (2,3) (1,3) (2,2) (1,1)
19 14 14 19
1 6 6 1
23
3.1.2 Penghitungan Nilai Fitness dari Kromosom
Dalam aplikasi algoritma genetik, perlu adanya suatu fungsi yang menentukan probabilitas kelangsungan hidup dari suatu individu untuk masuk ke generasi berikutnya. Fungsi tujuan ini oleh ahli biologi biasa disebut sebagai fungsi fitness. Nilai fitness dari suatu kromosom x untuk job shop scheduling problem ditentukan dengan cara: F(x) = (max_length – T(x)) + small_int Dimana max_length adalah makespan terburuk dari kromosom-kromosom pada generasi saat ini. T(x) adalah makespan dari kromosom x. Sedangkan small_int adalah nilai fitness terkecil dan merupakan suatu nilai parameter yang tetap. Sehingga, dari contoh 3.2 dengan max_length adalah 19, yaitu makespan terburuk pada populasi, dan misal ditentukan small_int adalah 1, maka nilai fitness dari masing-masing kromosom dapat dilihat pada Tabel 3.1. Nilai-nilai fitness tersebut nantinya akan mempengaruhi penyeleksian tiap kromosom pada tahap reproduksi.
3.1.3 Reproduksi
Untuk menyelesaikan job shop scheduling problem pada local search genetic algorithm, operator reproduksi yang digunakan adalah roda roulette. Roda roulette dilakukan untuk menghasilkan suatu populasi baru
24
untuk generasi berikutnya. Dengan menggunakan operator ini diharapkan solusi terbaik dari generasi saat ini akan selalu hadir pada populasi yang baru. Sehingga demi kelangsungan hidup suatu individu, kekuatan dari individu tersebut akan bersaing dengan kekuatan dari individu yang lain pada setiap generasi. Contoh 3.3 dibawah ini menunjukkan penggunaan roda roulette untuk masalah pada contoh 3.2.
Contoh 3.3: Dari nilai fitness masing-masing kromosom pada Tabel 3.1, dapat ditentukan proporsi yang merupakan persentasi dari nilai fitness terhadap total fitness. Nilai fitness dan proporsi dari masing-masing kromosom diberikan pada Tabel 3.2. Tabel 3.2 Nilai fitness dan persentasi total fitness tiap kromosom pada populasi untuk contoh 3.3. Kromosom Nilai Fitness % Total Fitness (1,2) (2,1) (2,3) (1,3) (2,2) (1,1)
1
7,1
(2,1) (1,2) (1,3) (2,3) (1,1) (2,2)
6
42,9
(2,1) (1,2) (1,3) (2,3) (2,2) (1,1)
6
42,9
(2,1) (1,2) (2,3) (1,3) (2,2) (1,1)
1
7,1
Total
14
100
Roda roulette pada Gambar 3.1 dibentuk berdasarkan proporsi yang diperoleh pada Tabel 3.2. Reproduksi dilakukan dengan memutar roda roulette sebanyak 4 kali (sesuai dengan ukuran populasi) dengan harapan
25
kromosom dengan proporsi terbesar, yaitu kromosom kedua dan ketiga (dengan proporsi sebesar 42,9%), memiliki probabilitas terpilih yang lebih besar dibandingkan dengan kromosom pertama dan keempat (dengan proporsi sebesar 7,1%).
7,1%
42,9%
7,1%
42,9%
Gambar 3.1 roda roulette untuk Tabel 3.2.
3.1.4 Crossover
Operator crossover merupakan salah satu aspek yang penting dalam menjalankan algoritma genetik. Sudah banyak teknik operator crossover yang digunakan untuk menyelesaikan job shop scheduling problem, seperti Uniform Order Crossover (UOX) dan subsequence exchange crossover (SXX). Tetapi metode UOX masih mengakibatkan jadwal yang tidak layak, sehingga diperbaiki menjadi taskCrossover, yang
26
mempertahankan urutan tugas dari masing-masing pekerjaan serta menjaga kelayakan dari masing-masing kromosom. Pada taskCrossover, seluruh tugas dari pekerjaan yang terpilih akan diturunkan dari parent ke child. Proses pembentukan kromosom child C1 dari dua parent P1 dan P2 adalah sebagai berikut: 1. Diberikan suatu masalah dengan n pekerjaan dan m mesin. Pilih suatu bilangan i secara acak (i ∈ [1, n-1]). 2. Selanjutnya, pilih i buah pekerjaan. Pekerjaan-pekerjaan ini nantinya akan diturunkan dari parent ke child (misal dari P1 ke C1). 3. Bangun suatu mask pattern sepanjang jumlah total tugas, yaitu sebanyak n x m tugas, yang diinisialisasi dengan nol. 4. Untuk setiap posisi mask pattern yang bersesuaian dengan tugas dari pekerjaan yang dipilih pada langkah 2, ubah nilai 0 menjadi 1. 5. Dengan menjaga urutan tugas dari P1, semua tugas yang posisinya bersesuaian dengan nilai 1 pada mask pattern diturunkan (dari kiri ke kanan) ke child C1. 6. Sisa tugas pada C1 di ambil dari parent yang lain, yaitu P2. (tugas yang sudah ada di C1 tidak diambil dari P2) Dengan cara yang sama C2 dibangun dari P2 dengan membangun mask pattern yang bersesuaian dengan P2 dan sisa tugasnya diambil dari P1.
27
Contoh 3.4: Misal diberikan dua kromosom parent P1 dan P2, dan terpilih satu pekerjaan secara acak, yaitu pekerjaan 2, yang akan diturunkan dari parent ke keturunannya. Sehingga diperoleh C1 dan C2 sebagai berikut : P1: (2,1) (1,2) (1,3) (2,3) (1,1) (2,2)
P2: (2,1) (1,2) (1,3) (2,3) (2,2) (1,1)
M1:
M2:
0
0
0
0
0
0
0
0
0
↓ M1:
1
0
0
0
0
0
1
1
0
↓ 1
0
1
C1: (2,1) (2,3) (2,2) (1,2) (1,3) (1,1)
M2:
1
0
0
C2: (2,1) (2,3) (2,2) (1,2) (1,3) (1,1)
Dimana M1 adalah mask pattern dari P1. M1 diinisialisasikan dengan nol terlebih dahulu sepanjang 2x3 = 6 tugas. Untuk setiap posisi mask pattern yang bersesuain dengan tugas dari pekerjaan 2, yaitu (2,1), (2,3), dan (2,2), nilai 0 diubah menjadi 1. Kemudian C1 dibentuk dengan cara mengambil tugas yang posisinya bersesuaian dengan nilai 1 pada M1, yaitu (2,1), (2,3), dan (2,2), yang ditempatkan pada C1 dari kiri ke kanan. Sisa tugas, yaitu (1,2), (1,3), dan (1,1), diambil dari P2 secara berurutan. Sedangkan C2 dibangun dari P2 dengan menggunakan M2 sebagai mask pattern dari P2.
3.1.5 Mutasi
Pada masalah job shop scheduling problem terdapat dua operator mutasi yang akan digunakan, yaitu mutasi sederhana dan local search mutator. Operator mutasi yang akan digunakan ditentukan secara
28
sampling, yaitu akan dipilih secara acak suatu bilangan r (r ∈ [0,1]), apabila r ≤ 0,5 maka dilakukan mutasi sederhana, sebaliknya apabila r > 0,5 maka dilakukan local search mutator. Mutasi sederhana adalah operator swap mutation yang diterapkan pada masalah penjadwalan. Mutasi sederhana dilakukan dengan memilih suatu mesin secara acak. Kemudian, dua pekerjaan yang berurutan pada mesin ini dipilih secara acak. Dengan menjaga urutan tugas, posisi dari dua pekerjaan ini ditukar. Penukaran ini hanya dilakukan satu kali untuk keseluruhan jadwal. Contoh penggunaan mutasi sederhana diberikan pada contoh 3.5. Sedangkan mengenai local search mutator akan dibahas pada subbab 3.3.
Contoh 3.5: Misal diberikan suatu kromosom (2,1)(1,2)(1,3)(2,3)(1,1)(2,2), dan misal terpilih mesin 3 secara acak, dan pada mesin 3 terpilih pekerjaan 1 dan pekerjaan 2. Maka mutasi dilakukan dengan menukar posisi dari kedua tugas, (1,3) dan (2,3), tersebut. (2,1) (1,2) (1,3) (2,3) (1,1) (2,2)
(2,1) (1,2) (2,3) (1,3) (1,1) (2,2)
29
3.2
Task Assignment Scheme (TAS)
Task Assignment Scheme (TAS), menempatkan pekerjaan ke mesin dengan menjaga hal-hal berikut: o Memastikan tidak ada pre-emption (menginterupsi pemrosesan dari suatu pekerjaan untuk memproses pekerjaan lain) o Tidak ada tugas dari pekerjaan yang sama sedang dikerjakan oleh mesin lain o Meminimumkan waktu kosong mesin Langkah-langkah dari TAS adalah sebagai berikut: 1. Untuk k = 1 sampai nxm, lakukan: 2. Ambil tk sebagai gen (tugas) dari suatu kromosom. (dimana k = 1, 2, …, nxm) 3. Periksa kendala urutan dari tugas, dan periksa bahwa tidak ada tugas yang mengandung pekerjaan yang sama sedang diproses. Kemudian, tempatkan tk ke suatu mesin yang diberikan. 4. Jika masing-masing gen pada kromosom telah ditempatkan pada suatu mesin, maka telah diperoleh suatu jadwal. Jika tidak, kembali ke langkah 1 dan tempatkan tugas yang belum ditempatkan berikutnya ke suatu mesin.
30
3.3
Tahap Local Search
Untuk menyelesaikan job shop scheduling problem dengan local search genetic algorithm, digunakan suatu local search mutator yang bertujuan untuk meningkatkan jadwal yang diperoleh. Local search mutator merupakan suatu proses mutasi dengan menerapkan teknik pencarian local search. Pada local search mutator, untuk setiap kromosom pada populasi, posisi dari dua tugas yang berurutan pada mesin yang sama akan ditukar. Dari seluruh hasil penukaran, satu kromosom terbaik yang diperoleh akan diperiksa. Jika kromosom yang baru memberikan hasil yang lebih baik dari kromosom yang lama, maka kromosom diganti dan proses diulangi sekali lagi. Tetapi jika kromosom yang baru tidak lebih baik dari kromosom yang lama, maka kromosom tidak diganti dan proses berhenti. Langkah yang diikuti di dalam tahap local search mutator adalah sebagai berikut: 1. Tentukan secara acak suatu bilangan r (r ∈ [ 0,1]). 2. Jika r ≤ 0.5, lakukan mutasi sederhana seperti yang dijelaskan pada sub-subbab 3.1.5 3. Jika r lebih besar dari 0.5 lanjutkan ke langkah 4 4. Untuk mesin i = 1 sampai m dan untuk pekerjaan j = 1 sampai n, lakukan: 5. Tentukan makespan terbaik yang diperoleh dengan menukar dua tugas berurutan tj dan tj+1 (di mana j = 1, 2, ..., n) pada mesin mi
31
6. Jika penukaran mengakibatkan makespan yang lebih buruk dibandingkan dengan makespan sebelum dilakukan penukaran, batalkan penukaran, dan proses berhenti, jika tidak ulangi dari langkah 5 sekali lagi (jika pengulangan kedua, proses berhenti)
3.4 Algoritma Genetik untuk Job Shop Scheduling Problem
Berdasarkan penjelasan pada subbab 3.1 hingga subbab 3.3, maka diperoleh suatu algoritma genetik untuk job shop scheduling problem sebagai berikut:
begin Baca data (urutan pekerjaan dan waktu proses); Tentukan parameter algoritma genetik; Bangun populasi awal secara acak dengan ukuran popSize; for gen = 1 hingga maxGen do Ubah tiap kromosom menjadi layak dengan menggunakan TAS; Hitung nilai fitness tiap kromosom pada populasi; Bangun populasi baru dengan reproduksi; Terapkan crossover dan mutasi (atau local search mutator); end for; end;
BAB IV IMPLEMENTASI DAN BEBERAPA HASIL PERCOBAAN
4.1
Implementasi
Algoritma genetik untuk menyelesaikan job shop scheduling problem yang dijelaskan pada Bab III, diimplementasikan dengan menggunakan compiler MATLAB 6.0. Kinerja dari algoritma ini dalam menyelesaikan job shop scheduling problem diuji dengan menyelesaikan masalah uji yang biasa digunakan [OR]. Akan dibandingkan juga kinerja program apabila operator yang digunakan hanya crossover, crossover dengan mutasi sederhana, dan crossover dengan local search mutator. Masukan dari program tersebut adalah urutan pemrosesan tiap pekerjaan, waktu proses tiap pekerjaan, dan empat parameter dari algoritma genetik, yaitu ukuran populasi, batas generasi maksimum, probabilitas crossover, serta probabilitas mutasi. Ukuran populasi diasumsikan genap, agar kromosom-kromosom tepat berpasangan ketika dilakukan operator crossover. Pencarian solusi akan dilakukan sebanyak batas generasi maksimum yang ditentukan. Pelaksanaan operator crossover dan mutasi bergantung pada pemilihan suatu bilangan yang diperoleh secara acak. Jika bilangan tersebut memenuhi kriteria dari probabilitas crossover atau probabilitas mutasi, maka
32
33
crossover atau mutasi akan dijalankan. Tetapi apabila tidak memenuhi kriteria tersebut, maka proses crossover atau mutasi tidak dilakukan sama sekali. Program akan berhenti apabila batas generasi maksimum yang ditentukan telah tercapai. Berikut adalah fungsi-fungsi utama yang digunakan pada program beserta dengan penjelasannya : Main: Merupakan fungsi utama dari local search genetic algorithm. Fungsi ini akan memanggil beberapa fungsi yang lain. Di dalam fungsi ini pula, akan dihitung nilai fitness dan dijalankan operator reproduksi. POP: Fungsi untuk membangun solusi awal yang memenuhi kendala urutan dengan melakukan permutasi dari tiap pekerjaan untuk sembarang mesin. TAS: Fungsi untuk mengubah kromosom yang tidak layak menjadi layak. Makespan: Fungsi untuk membangun Gantt-Chart, sehingga menghasilkan besaran makespan untuk tiap kromosom pada populasi. CO: Fungsi untuk menjalankan operator crossover.
34
SimpleMut: Fungsi untuk menjalankan operator mutasi sederhana. LSGA: Fungsi untuk menjalankan operator local search mutator.
4.2
Hasil Percobaan
Di dalam subbab ini akan diberikan beberapa hasil percobaan dalam menjalankan program hasil implementasi. Program tersebut dijalankan pada Personal Computer (PC) dengan prosesor Intel Pentium III 500 MHz, memori 128 Mb, dan sistem operasi Microsoft Windows 2000 Professional Edition. Contoh pemanggilan program untuk masalah dari contoh 2.1, diberikan pada contoh 4.1. Sedangkan pada contoh 4.2 diberikan solusi yang diperoleh, beserta grafik makespan terhadap generasi untuk masalah berukuran 6x6 yang diambil dari [OV 04].
Contoh 4.1 : Diberikan suatu masalah yang terdiri dari 2 pekerjaan dan 3 mesin. Urutan pekerjaan dan waktu yang dibutuhkan untuk menyelesaikan pekerjaan, diberikan pada Tabel 2.1. Dengan ukuran populasi 4, batas generasi maksimum 5, probabilitas crossover 0,95 dan probabilitas mutasi 0,15, jadwal
35
yang diperoleh adalah: (1,2) (2,1) (1,3) (2,3) (2,2) (1,1) dengan makespan sebesar 14. Gambar 4.1 dan Gambar 4.2 merupakan tampilan program pada saat memasukan data dan solusi keluaran yang diperoleh.
Gambar 4.1 Data masukan untuk contoh 4.1.
36
Gambar 4.2 Solusi yang diperoleh untuk contoh 4.1
Contoh 4.2 : Diberikan suatu masalah yang terdiri dari 6 pekerjaan dan 6 mesin. Urutan pekerjaan dan waktu yang dibutuhkan untuk menyelesaikan pekerjaan, diberikan pada Tabel 4.1, dengan P menyatakan pekerjaan, m menyatakan mesin, dan t menyatakan waktu. Solusi keluaran yang diperoleh dengan ukuran populasi 4, batas generasi maksimum 100, probabilitas crossover 0,95 dan probabilitas mutasi 0,15, diberikan pada Gambar 4.3. Tetapi makespan yang diperoleh tidak
37
optimal yaitu sebesar 59, sedangkan makespan dari solusi terbaik untuk masalah ini adalah 55 [OV 04]. Grafik dari makespan terhadap generasi untuk masalah ini diberikan pada Gambar 4.4.
Tabel 4.1 Urutan pekerjaan dan waktu proses untuk contoh 4.2 Pekerjaan
m,t
m,t
m,t
m,t
m,t
m,t
P1
3,1
1,3
2,6
4,7
6,3
5,6
P2
2,8
3,5
5,10
6,10
1,10
4,4
P3
3,5
4,4
6,8
1,9
2,1
5,7
P4
2,5
1,5
3,5
4,3
5,8
6,9
P5
3,9
2,3
5,5
6,4
1,3
4,1
P6
2,3
4,3
6,9
1,10
5,4
3,1
Gambar 4.3 Solusi yang diperoleh untuk contoh4.2
38
64 63.5 63
makespan
62.5 62 61.5 61 60.5 60 59.5 59
0
10
20
30
40
50
60
70
80
90
100
Generasi
Gambar 4.4 Grafik makespan terhadap generasi untuk contoh 4.2
Algoritma ini telah diuji untuk menyelesaikan masalah uji yang diperoleh dari data benchmark [OR] dengan ukuran masalah 10 x 5 (yaitu, 10 pekerjaan dan 5 mesin), 15 x 5, dan 20 x 5 (urutan pekerjaan dan waktu proses diberikan pada Lampiran). Tingkat keberhasilan program untuk setiap ukuran masalah dilihat berdasarkan besar makespan yang diperoleh, dibandingkan dengan makespan solusi terbaik yang diperoleh dari data benchmark [OR]. Ukuran populasi, batas generasi maksimum, probabilitas crossover, dan probabilitas mutasi untuk setiap ukuran masalah ditetapkan sama, yaitu 4, 100, 0,95, dan 0,15. Hasil yang diperoleh dari tiap ukuran masalah dapat dilihat pada Tabel 4.2, dimana kolom masalah uji menyatakan nama file dari masalah yang digunakan, BKS (Best Known Solution)
39
menyatakan makespan solusi terbaik yang diperoleh dari data benchmark [OR], LSGA menyatakan makespan dari solusi dengan menggunakan local search genetic algorithm, dan R.error menyatakan error relatif dari solusi yang diperoleh terhadap solusi terbaik dari masalah. Tabel 4.2 Hasil Percobaan untuk tiap ukuran masalah Masalah Uji
Banyaknya pekerjaan
Banyaknya mesin
BKS
LSGA
R.error
la01
10
5
666
675
1,3
la07
15
5
890
1046
17,5
la11
20
5
1222
1222
0
Pada Tabel 4.2 terlihat bahwa pada masalah dengan 10 pekerjaan dan 5 mesin, memiliki error relatif sebesar 1,3%. Sedangkan pada masalah dengan 15 pekerjaan dan 5 mesin memiliki error relatif sebesar 17,5%, dan masalah dengan 20 pekerjaan dan 5 mesin memiliki error relatif sebesar 0%. Hal ini terjadi karena sifat probabilistik yang dimiliki oleh metode algoritma genetik. Sehingga, ukuran masalah tidak merupakan faktor utama yang mempengaruhi besarnya error relatif. Gambar 4.5 menunjukkan perbandingan grafik makespan terhadap generasi dari solusi yang diperoleh antara hanya menggunakan operator crossover, menggunakan operator crossover dan mutasi sederhana, dan dengan menggunakan operator crossover dan local search mutator. Masalah yang diuji menggunakan data masalah la01, yaitu suatu masalah dengan 10 pekerjaan dan 5 mesin.
40
Gambar 4.5 Grafik makespan terhadap generasi untuk data masalah la01 Keterangan :
+ : grafik makespan terhadap generasi yang hanya menggunakan crossover : grafik makespan terhadap generasi yang menggunakan crossover dan mutasi sederhana
x : grafik makespan terhadap generasi yang menggunakan crossover dan local search mutator
Berdasarkan Gambar 4.4, terlihat bahwa jadwal yang diperoleh dengan menggunakan operator crossover dan local search mutator, akan lebih cepat menuju ke suatu solusi optimal dibandingkan dengan jadwal yang diperoleh dengan hanya menggunakan operator crossover, dan dengan menggunakan operator crossover dan mutasi sederhana.
BAB V KESIMPULAN
Untuk menyelesaikan job shop scheduling problem, digunakan suatu algoritma genetik yang menjaga urutan dari tiap pekerjaan, sehingga setiap solusi yang diperoleh adalah layak. Operator crossover yang digunakan melakukan suatu proses evolusi dengan menjaga kelayakan dari solusi-solusi baru yang dihasilkan. Mutasi dilakukan jika kromosom yang baru memberikan makespan yang lebih baik. Kedua operator crossover dan mutasi tidak harus selalu dilakukan, bergantung pada parameter yang ditentukan. Berdasarkan hasil percobaan untuk beberapa ukuran masalah yang diperoleh dari data benchmark [OR], terlihat bahwa local search genetic algorithm memperoleh suatu jadwal dengan makespan yang optimal dan yang memiliki error relatif kurang dari 20 persen. Pada beberapa hasil percobaan terlihat pula bahwa jadwal yang diperoleh dengan menggunakan operator crossover dan local search mutator, pada setiap generasi akan lebih cepat konvergen dibandingkan dengan jadwal yang diperoleh dengan hanya menggunakan operator crossover, dan dengan menggunakan operator crossover dan mutasi sederhana.
41
