JOB SHOP
SCHEDULING PROBLEM
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)
BAB I
PENDAHULUAN
1.1
Latar
Belakang Masalah
Penjadwalan
merupakan suatu proses pengaturan sumber daya untuk menyelesaikan tugas-tugas
dengan melibatkan pekerjaan, sumber daya, dan waktu. Pekerjaan diproses pada setiap sumber daya
dengan urutan tertentu selama waktu tertentu.
Tujuan dari masalah penjadwalan antara lain: meminimumkan waktu
penyelesaian semua tugas (makespan),
meminimumkan keterlambatan pengerjaan, meminimumkan waktu tunggu pada mesin,
meminimumkan biaya, dan lain-lain.
Masalah
penjadwalan merupakan salah satu aspek penting pada lingkungan industri.
Misalkan suatu percetakan akan memproduksi brosur, koran, dan majalah dengan
menggunakan 3 sumber daya, yaitu mesin cetak, mesin potong, dan mesin
jilid. Misal brosur hanya melalui mesin
cetak, sementara koran setelah dicetak perlu dipotong, sedangkan majalah
setelah dicetak, dijilid, lalu dipotong.
Pada beberapa masalah penjadwalan, pekerjaan memiliki batas waktu, sehingga mempengaruhi prioritas
pemrosesan. Salah satu solusi untuk
menyelesaikan masalah percetakan tersebut, dapat dimulai dengan menempatkan
majalah pada mesin cetak, karena majalah memiliki urutan proses yang
terpanjang. Setelah majalah dicetak,
proses untuk majalah dilanjutkan dengan menempatkan majalah pada mesin jilid,
sementara akan ditentukan apakah brosur atau koran yang akan ditempatkan pada
mesin cetak. Penempatan brosur pada
mesin cetak akan lebih baik dari pada koran, karena jika koran yang ditempatkan
terlebih dahulu pada mesin cetak, maka kemungkinan koran dan majalah akan tiba
di mesin potong pada waktu yang bersamaan.
Setelah brosur dicetak maka pemrosesan brosur selesai, dan koran dapat
ditempatkan pada mesin cetak, sementara majalah ditempatkan pada mesin
potong. Proses dari majalah selesai
setelah pemotongan, dan sebagai proses terakhir, koran ditempatkan pada mesin
potong. Masalah percetakan tersebut
hanya menggunakan tiga sumber daya untuk menyelesaikan tiga pekerjaan, jika
suatu masalah dengan pekerjaan dan sumber daya yang lebih banyak, maka
pemrosesan akan menjadi lebih kompleks.
Job shop scheduling problem merupakan salah
satu masalah penjadwalan yang memiliki kendala urutan pemrosesan tugas, dan
setiap tugas harus melalui setiap mesin tepat satu kali. Terdapat dua jenis metode yang biasa
digunakan untuk menyelesaikan masalah job
shop scheduling problem. Metode
eksak, seperti pemrograman linier dan pemrograman non-linier, dapat digunakan
untuk ukuran job shop scheduling problem
yang kecil. Sedangkan untuk ukuran
masalah yang besar, digunakan suatu pendekatan secara aproksimasi, seperti local search, simulated annealing, genetic
algorithm, tabu search, dan ant colony optimization. Hal ini
disebabkan karena untuk ukuran masalah yang besar, kompleksitasnya akan semakin
besar.
Pada
skripsi ini, pendekatan yang digunakan adalah algoritma genetik, dengan
menerapkan teknik local search. Algoritma genetik ditemukan oleh John Holland
pada tahun 1960. Algoritma ini
menerapkan suatu proses evolusi biologi.
Banyak percobaan dalam menyelesaikan job
shop scheduling problem dengan menggunakan metode algoritma genetik, tetapi
masih terdapat beberapa percobaan yang menghasilkan solusi yang tidak
layak. Pada metode dalam skripsi ini,
ketidaklayakan dari solusi dapat dihindari dengan menggunakan suatu skema yang
menjaga urutan pemrosesan tugas. Kualitas dari solusi akan diuji dengan
menggunakan beberapa masalah uji yang biasa dipakai untuk menyelesaikan job shop scheduling problem.
Terdapat tiga operator dasar yang
digunakan pada algoritma genetik, yaitu reproduksi, crossover, dan mutasi.
Reproduksi digunakan untuk menyeleksi solusi-solusi yang akan diproses, crossover digunakan untuk memperoleh
solusi-solusi melalui proses perkawinan, dan mutasi digunakan untuk mengubah
kualitas dari suatu solusi. Pada skripsi
ini, akan digunakan suatu operator crossover
yang sederhana dan efisien, yang memastikan bahwa setiap solusi baru yang
dihasilkan akan selalu layak. Pada tahap
mutasi, akan digunakan suatu operator yang mengarah pada suatu proses pencarian
local search, dengan harapan akan
meningkatkan kualitas dari solusi.
1.2 Perumusan
Masalah
Apakah job shop scheduling problem dapat
diselesaikan dengan menggunakan algoritma genetik, dan apakah pemilihan antara
menggunakan mutasi sederhana dengan local
search mutator akan mempengaruhi kinerja dari algoritma.
1.3
Tujuan
Penulisan
Penulisan skripsi ini bertujuan
untuk melihat kemampuan dari local search
genetic algorithm dalam menyelesaikan job
shop scheduling problem dengan menggunakan suatu masalah uji yang biasa
dipakai untuk menguji kinerja dari suatu program untuk menyelesaikan job shop scheduling problem. Selain itu, akan dilihat juga perbandingan
kinerja dari local search genetic
algorithm antara hanya menggunakan crossover,
menggunakan crossover dan mutasi sederhana, dan dengan menggunakan crossover
dan local search mutator.
1.4
Pembatasan Masalah
Job shop scheduling problem yang akan
dibahas adalah job shop scheduling problem dengan tujuan meminimumkan makespan. Sedangkan untuk pengujian, masalah uji yang
digunakan dibatasi hanya untuk 3 masalah.
1.5
Sistematika Penulisan
Sistematika
pembahasan skripsi ini adalah sebagai berikut: Bab I membahas tentang latar
belakang, tujuan dari skripsi, batasan masalah, dan sistematika penulisan; Bab
II membahas definisi dan teori dasar dari masalah penjadwalan, job shop scheduling problem, algoritma
genetik, dan local search; Bab III
membahas tentang local search genetic
algorithm dalam menyelesaikan job shop scheduling problem; Bab IV
membahas implementasi algoritma dan beberapa hasil eksperimen; dan terakhir Bab
V membahas kesimpulan yang berdasarkan pada hasil eksperimen.
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 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.
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.
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.
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
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
12
|
|
waktu
|
|
|
m3
|
|
|
|
|
|
|
|
|
|
m2
|
|
|
|
|
|
|
|
|
|
m1
|
|
|
|
|
|
|
|
|
|
|
|
|
3
|
|
|
|
waktu
|
|
Gambar 2.1.a Gambar 2.1.d
|
m3
|
|
|
|
|
|
|
|
|
|
m2
|
|
|
|
|
|
|
|
|
|
m1
|
|
|
|
|
|
|
|
|
|
|
|
|
|
4
|
|
|
waktu
|
|
|
m3
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
m2
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
m1
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
13
|
waktu
|
|
Gambar 2.1.b Gambar 2.1.e
|
m3
|
|
|
|
|
|
|
|
|
|
|
|
m2
|
|
|
|
|
|
|
|
|
|
|
|
m1
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
7
|
|
waktu
|
|
|
m3
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
m2
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
m1
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
14
|
waktu
|
|
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)
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 waktu
|
|
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.
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
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, 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.
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.
Gambar
2.3 roda roulette untuk Tabel 2.2.
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.
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 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.
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.
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.
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)
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
|
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 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 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%).
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 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]).
[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.
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 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.
[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)
3.2
Task
Assignment Scheme (TAS)
Task
Assignment Scheme (TAS), menempatkan pekerjaan ke mesin dengan menjaga
hal-hal berikut:
- Memastikan
tidak ada pre-emption
(menginterupsi pemrosesan dari suatu pekerjaan untuk memproses pekerjaan
lain)
- Tidak
ada tugas dari pekerjaan yang sama sedang dikerjakan oleh mesin lain
- 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.
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:
- Tentukan
secara acak suatu bilangan r (r [ 0,1]).
- Jika
r
0.5,
lakukan mutasi sederhana seperti yang dijelaskan pada sub-subbab 3.1.5 - Jika
r lebih besar dari 0.5 lanjutkan ke langkah 4
- Untuk
mesin i = 1 sampai m dan untuk pekerjaan j = 1 sampai n, lakukan:
- Tentukan
makespan terbaik yang diperoleh dengan menukar dua tugas berurutan tj dan tj+1 (di mana j = 1, 2, ..., n) pada mesin mi
- 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 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 :
v 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.
v POP:
Fungsi untuk
membangun solusi awal yang memenuhi kendala urutan dengan melakukan permutasi
dari tiap pekerjaan untuk sembarang mesin.
v TAS:
Fungsi untuk
mengubah kromosom yang tidak layak menjadi layak.
v Makespan:
Fungsi untuk
membangun Gantt-Chart, sehingga
menghasilkan besaran makespan untuk
tiap kromosom pada populasi.
v CO:
Fungsi untuk
menjalankan operator crossover.
v SimpleMut:
Fungsi untuk
menjalankan operator mutasi sederhana.
v 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 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.
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 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
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) 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.
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.
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.
0 komentar:
Post a Comment