iii

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)

1

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

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 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

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.

6

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

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.

Gambar 2.1.a Gambar 2.1.d

Gambar 2.1.b Gambar 2.1.e

Gambar 2.1.c Gambar 2.1.f

Gambar 2.1 Gantt-Chart dari jadwal (1,2)(2,1)(1,3)(2,3)(1,1)(2,2)

m3 m2 m1

12 waktu

m3 m2 m1

3 waktu

m3 m2 m1

4 waktu

m3 m2 m1

13 waktu

m3 m2 m1

7 waktu

m3 m2 m1

14 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.

Gambar 2.2 Gantt-Chart dari jadwal (2,1) (1,2) (2,3) (1,3) (2,2) (1,1)

Ket :

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.

m3

m2

m1

19 waktu

P1 P2

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 kromosom-

kromosom 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.

27,1%

34,3%

20,0%

18,6%

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, karakteristik-

karakteristik 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 gen-

gen 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 1 0 0 1 0

2.4 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.

20

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 masing-

masing 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.

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) 19 1 (2,1) (1,2) (1,3) (2,3) (1,1) (2,2) 14 6 (2,1) (1,2) (1,3) (2,3) (2,2) (1,1) 14 6 (2,1) (1,2) (2,3) (1,3) (2,2) (1,1) 19 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% 42,9%

7,1%

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: 0 0 0 0 0 0 M2: 0 0 0 0 0 0

↓ ↓

M1: 1 0 0 1 0 1 M2: 1 0 0 1 1 0

C1: (2,1) (2,3) (2,2) (1,2) (1,3) (1,1) 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;

32

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

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

0 10 20 30 40 50 60 70 80 90 10059

59.5

60

60.5

61

61.5

62

62.5

63

63.5

64

mak

espa

n

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 Banyaknya Banyaknya BKS LSGA R.error

Uji pekerjaan mesin

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

: grafik makespan terhadap generasi yang hanya menggunakan crossover : grafik makespan terhadap generasi yang menggunakan crossover dan mutasi sederhana : grafik makespan terhadap generasi yang menggunakan crossover dan local search mutator

+

x

Keterangan :

Gambar 4.5 Grafik makespan terhadap generasi untuk data masalah la01

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.

41

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.