Penerapan Algoritma Genetika dalam Job Shop Scheduling Problem Haris Sriwindono Program Studi Ilmu Komputer Universitas Sanata Dharma Paingan, Maguwoharjo, Depok Sleman Yogyakarta, Telp. 0274-883037
[email protected]
Abstract The Job Shop Scheduling problem (JSP) is among the hardest combinatorial optimization problem. A common feature of these problems is there’s no efficient algorithmic solution that can solved optimality in polynomial time. If this JSP solved by genetic algorithm, hopefully it can be solved in shorter time to obtain an acceptable result. In this research we had accomplished the JSP using Genetic Algorithm and had applied precedence preservation a crossover method and an inverse mutation method. The process of selecting some chromosomes crossover-ed was done by choosing the best fitness, while the mutation selection was done randomly. The result is the increasing number of population will increase the probability of the better result, but we had to be careful with the random part while generating the initial population. Keywords : crossover, inverse mutation, preservation crossover.
1. Pendahuluan Pembuatan jadwal penggunaan mesin untuk menyelesaikan berbagai pekerjaan (Job Shop Scheduling) secara manual pada umumnya merupakan proses yang membutuhkan waktu lama karena termasuk dalam salah satu jenis masalah optimasi yang sulit (Hardest Combinatorial) [1]. Job Shop Scheduling Problem (JSSP) secara umum adalah merupakan sebuah masalah di mana terdapat beberapa mesin yang harus dipakai untuk menyelesaikan beberapa job yang terdiri dari beberapa operasi yang sudah diketahui jangka waktu penyelesaiannya. Masalah JSSP ini adalah bagaimana menyusun jadwal semua operasi dari semua job pada tiap mesin sehingga diperoleh total waktu pengerjaan yang minimal dengan beberapa persyaratan. Persyaratan yang harus dipenuhi tersebut adalah: - Setiap job diproses oleh sebuah mesin maksimal satu kali. - Pengerjaan setiap operasi dalam satu job harus berurutan. - Tidak terdapat halangan precedence di antara operasi pada job yang berbeda. - Operasi pengerjaan tidak dapat disela. - Pada satu satuan waktu sebuah mesin hanya dapat memproses sebuah operasi. Salah satu cara untuk menyelesaikan JSSP adalah dengan menggunakan Algoritma Genetika, di mana tidak seluruh kemungkinan solusi dicoba, tetapi diharapkan dapat menghasilkan solusi yang lumayan baik. Algoritma Genetika melakukan pemilihan solusi dengan cara yang mirip dengan seleksi alam (teori evolusi) yaitu individu yang dapat bertahan hidup adalah individu yang paling mampu menyesuaikan diri dengan lingkungannya. Dalam rangka beradaptasi, maka makhluk hidup baru yang lebih baik, dapat dihasilkan dengan cara perkawinan silang maupun mutasi. Sesuai dengan teori evolusi pula bahwa probabilitas terjadinya mutasi lebih kecil dari pada probabilitas terjadinya perkawinan silang.
Haris Sriwindono, Penerapan Algoritma Genetika dalam Job Scheduling Problem
Secara umum, Algoritma Genetika bermain di ruang solusi, dan akan mencari solusi terbaik dari ruang solusi tersebut (search space). Semua calon solusi yang dipilih akan dievaluasi tingkat kebaikannya dengan fungsi tertentu (fitness function) sehingga dapat diketahui calon solusi yang memegang tingkat kebaikan tertinggi. Beberapa calon solusi terbaik akan dipilih untuk dikawinkan agar dapat menghasilkan solusi baru dengan harapan nilai kebaikannya menjadi lebih tinggi dari pada orangtuanya. Juga bisa terjadi mutasi dari sebuah solusi menjadi solusi baru dengan harapan yang sama. 2. Tinjauan Pustaka 2.1. Algoritma Genétika Algoritma Genetika diawali dengan dibentuknya himpunan solusi secara random yang disebut populasi. Setiap individu dalam populasi disebut kromosom yang merepresentasikan sebuah solusi. Sebuah kromosom adalah sebuah string yang tergantung dari cara pengkodeannya. Kromosom-kromosom berkembang melalui iterasi beruntun yang disebut generations. Pada setiap generasi, kromosom dievaluasi dengan menggunakan alat tertentu (fitness function). Untuk menghasilkan generasi berikutnya (keturunan/offspring), kromosom baru dihasilkan dengan dua cara yaitu perkawinan silang antar dua kromosom pada generasi sebelumnya (crossover) atau terjadi mutasi pada sebuah kromosom dari generasi sebelumnya. Populasi baru terbentuk dengan memilih kromosomkromosom pada generasi berikutnya beserta generasi sebelumnya sesuai dengan nilai fitnessnya, dan membuang beberapa kromosom yang nilai fitnessnya buruk, untuk menjaga agar jumlah anggota populasi konstan. Setelah berjalan beberapa generasi, maka AG akan menghasilkan solusi yang mengarah pada solusi terbaik. Bila P(t) dan C(t) adalah orangtua dan keturunan pada generasi t, maka algoritma genetika berjalan sbb. (Gen, 1997): Procedure Algoritma Genetika; Begin t←0 Initialize P(t) Evaluate P(t) While Not (terminate condition) do Recombine P(t) to yield C(t) Evaluate C(t) Select P(t+1) from P(t) and C(t) t ← t+1 End End
2.2. JSSP Masalah Job Shop Scheduling adalah bagaimana menyusun semua operasi dari semua job pada tiap mesin sedemikian ingá total waktu pengerjaannya minimal. Masalah Job Shop Scheduling klasik dapat dideskripsikan sebagai berikut: “Terdapat m mesin dan n job yang akan dijadwalkan. Setiap job terdiri dari sekumpulan operasi dan setiap operasi dikerjakan pada mesin tertentu. Setiap operasi dideskripsikan dengan mesin yang sesuai dan waktu pemrosesan yang pasti” Contoh sebuah persoalan JSSP seperti terlihat pada Gambar 1, sedangkan contoh solusi yang diperoleh seperti terlihat pada Gambar 2.
39
Media Teknika Vol. 7 No. 1, Juni 2007: 38 – 44
Processing Time
Machine Sequence
Operasi
Operasi
Job
1
2
3
Job
1
2
3
j1
3
3
2
j1
m1
m2
m3
j2
1
5
3
j2
m1
m3
m2
j3
3
2
3
j3
m2
m1
m3
Gambar 1. Contoh JSSP 211
111
321
M1 M2
312
122
232
223
M3 1
133
4
7
333
10
12
Gambar 2. Machine Gantt Chart Pada gambar 2 dapat terlihat bahwa, pada mesin M1 (baris teratas) terjadi runtunan pekerjaan 211, 111,321 maksudnya adalah 211(job 2, operasi 1, mesin1), 111 (job 1, operasi 1, mesin 1) dan 321 (job 3, operasi 2, mesin 1) demikian dan seterusnya. 111
J1 J2
211
122
133
223 312
232 321
333
J3 1
4
7
10
12
Gambar 3. Job gantt chart Bila dilihat dari sisi Job, maka solusi pada gambar 2 dapat ditampilkan seperti pada gambar 3 dengan arti yang sama tetapi dengan tolok ukur Job sebagai indikator baris. Jadi, masalah JSSP ini adalah menemukan solusi (seperti pada gambar 2 atau 3 di atas) yang total waktu untuk menyelesaikannya adalah minimal. Secara visual, yang dimaksud dengan total waktu minimal adalah jumlahan kolom horisontal, di mana lebar kolom merupakan durasi waktu yang diperlukan untuk operasi. 3. Metode Penelitian Metodologi yang digunakan untuk melaksanakan penelitian ini adalah sesuai dengan metode pembuatan perangkat lunak yaitu SDLC (System Development Life Cycle) atau waterfall yaitu sbb: 3.1. Analisa Pada tahap ini dilakukan analisa terhadap kebutuhan sistem, juga analisa terhadap algoritma yang akan disusun dengan cara mempelajari literatur dan atau hasil-hasil riset sebelumnya. Pada tahap ini diharapkan dihasilkan berbagai informasi untuk
40
Haris Sriwindono, Penerapan Algoritma Genetika dalam Job Scheduling Problem
menyusun algoritma genetika yang meliputi representasi masalah, penentuan fitness function, metode crossover serta metode mutasi dan seleksi. 3.2. Perancangan Dari tahap sebelumnya yaitu analisa, maka dapat disusun perancangan rinci yang berupa algoritma yang siap untuk dikodekan menjadi program komputer. 3.3. Pengkodean Ini adalah tahap pengkodean atau pembuatan program, program dibuat dalam MatLab. 3.4. Ujicoba Setelah program berhasil dibuat, maka langkah berikutnya adalah ujicoba untuk mengetahui kehandalan dari program komputer yang telah dibuat. 3.5. Implementasi Setelah melalui tahap testing atau ujicoba maka program komputer yang dihasilkan siap untuk dipakai. 4. Hasil dan pembahasan 4.1. Representasi Kromosom Ada beberapa model representasi kromosom yang dapat digunakan dalam JSSP ini, salah satunya adalah operation based representation (OB). Prinsip dari OB adalah semua operasi pada suatu pekerjaan akan dikodekan dengan simbol yang sama, kemudian diinterpretasikan menurut urutannya dalam deretan. Sehingga untuk problem dengan aa
job, setiap job terdiri dari b operasi dan m mesin, kromosom akan terdiri dari
∑b i =1
i
gen.
Contoh kromosom untuk permasalahan yang terdiri dari 3 job, 3 mesin dan 3 operasi dapat direpresentasikan sebagai berikut : job1 operasi2 1
1
2
3
2
2
1
3
job1
job1
operasi1
operasi3
3
Gambar 4. Representasi kromosom 4.2. Pembangkitan Kromosom Pembangkitan kromosom dalam job-shop scheduling problem pada penelitian ini akan dilakukan secara random atau acak. Pada penelitian ini akan dibangkitkan satu populasi awal yang terdiri dari 10, 20 dan 30 kromosom dan semua kromosom dalam bentuk representasi OB seperti pada gambar 4. 4.3. Penentuan Fitness Function Untuk masalah job-shop scheduling ini pencarian nilai fitness dilakukan dengan menghitung total waktu pengerjaan semua job. Kromosom yang mempunyai nilai fitness terbaik adalah kromosom yang mempunyai total waktu minimum dalam mengerjakan semua job. Secara ringkas fungsi Fitness dapat ditulis sebagai berikut:
41
Media Teknika Vol. 7 No. 1, Juni 2007: 38 – 44
n
min ∑ max[cik ] i =1
(1)
i< k <m
4.4. Pemilihan kromosom orangtua Pemilihan kromosom untuk dijadikan orang tua (yang akan dikenai operasi crossover) dilakukan berdasarkan nilai fitness dari masing-masing kromosom. Orangtua yang dipilih adalah yang memiliki nilai fitness terbaik, jadi yang memiliki nilai fitness terkecil. Dengan harapan bahwa orangtua dengan fitness terbaik akan menghasilkan keturunan dengan nilai fitness tak jauh dari orangtuanya. 4.5. Proses crossover Untuk mendapatkan individu baru salah satu caranya adalah dengan melakukan perkawinan silang atau crossover. Dalam melakukan crossover melibatkan dua individu yang telah dipilih menjadi orangtua dan akan akan menghasilkan sebuah offspring. Dalam job-shop scheduling problem ini metode crossover yang akan digunakan adalah metode precedence preservation crossover (PPX) adapun langkah-langkah dari proses crossover adalah sebagai berikut: - Membangkitkan bilangan biner secara random sepanjang jumlah gen pada kromosom. - Dimulai dari bilangan biner pertama jika bernilai 1 maka gen untuk offspring diambil dari gen paling kiri parent pertama yang belum terpakai. Dan pada parent kedua dicari gen paling kiri yang sama dengan gen yang diambil dari parent pertama yang belum dipakai kemudian dicoret. - Jika bilangan biner bernilai 0 maka gen untuk offspring diambil gen paling kiri parent kedua yang belum terpakai. Dan pada parent pertama dicari gen paling kiri yang sama dengan gen yang diambil dari parent kedua yang belum terpakai kemudian dicoret. - Langkah di atas dilakukan berulang-ulang sampai gen bilangan biner yang terakhir sehingga membentuk offspring yang baru. Ilustrasi proses crossover adalah sebagai berikut : parent1
1
1
2
3
2
2
1
3
3
biner
1
0
1
1
0
0
1
0
1
parent2
2
1
1
2
3
2
3
3
1
offspring
1
2
1
3
2
2
1
3
3
Gambar 5. Proses Crossover 4.6. Proses mutasi Mutasi merupakan proses untuk menghasilkan individu baru dari sebuah kromosom melalui perubahan salah satu gen pada kromosom tersebut. Metode mutasi yang digunakan adalah metode inverse mutation. Adapun langkah-langkah dari mutasi adalah sebagai berikut : - Dipilih dua buah gen secara random dengan isi gen yang berbeda. - Kedua gen tersebut ditukarkan tempatnya.
42
Haris Sriwindono, Penerapan Algoritma Genetika dalam Job Scheduling Problem
Operasi mutasi dapat diilustrasikan sebagai gambar berikut : Parent
1
2
1
3
2
2
1
3
3
Offspring
1
3
1
2
2
2
1
3
3
Gambar 6. Proses Mutasi
4.7. Proses Pembentukan Populasi Baru. Dari hasil regenerasi (baik crossover maupun mutasi) yang menghasilkan kromosom keturunan (offspring) yang baru, langkah selanjutnya adalah menghitung fitness masing-masing offspring tersebut. Kemudian dilakukan pembandingan nilai fitness offspring dengan nilai-nilai fitness yang ada pada populasi sebelumnya. Bila ada kromosom bernilai fitness yang lebih buruk (yang berada dalam populasi) maka akan digantikan dengan offspring yang bernilai fitness lebih baik. Dengan demikian diharapkan akan diperoleh kromosom dengan nilai lebih baik pada populasi baru. 4.8. Hasil pengamatan Untuk persoalan seperti pada contoh Gambar 1, diperoleh hasil sebagai berikut: (sebuah sampel dari beberapa eksperimen, dengan jumlah iterasi 10 dan probabilitas mutasi: probabilitas crossove r=1:5) Jumlah kromosom dlm populasi percobaan ke 1 2 3 4 5 6 7 8 9 10 Jumlah Rerata frekuensi
5 11 14 14 12 14 14 16 14 11 12 132 13.2 2
10 14 12 11 11 14 14 14 12 14 11 127 12.7 3
15 12 11 14 12 12 11 12 11 12 11 118 11.8 4
20 12 11 14 14 11 11 14 11 11 12 121 12.1 5
25 14 12 11 11 12 12 11 11 11 11 116 11.6 6
Tampak bahwa dengan meningkatnya jumlah populasi awal, maka kebolehjadian mendapatkan solusi minimal semakin besar. Semakin banyak jumlah kromosom pada populasi awal, maka kecenderungan mendapatkan nilai fitness awal yang baik juga semakin besar. 5. Kesimpulan dan Saran 5.1. Dari hasil pengamatan yang diperoleh dapat diduga bahwa dengan meningkatnya jumlah kromosom pada populasi awal ternyata berpengaruh pada hasil yang diperoleh, yaitu adanya kecenderungan meningkatnya kebolehjadian mendapatkan nilai fitness terbaik. 43
Media Teknika Vol. 7 No. 1, Juni 2007: 38 – 44
5.2. Perlu diperhatikan bahwa pembangkitan kromosom awal dilakukan secara acak, sehingga tidak dapat dipastikan bahwa dengan jumlah kromosom awal yang besar akan cepat menghasilkan solusi yang baik. Selain itu pemilihan kromosom untuk dimutasi juga dilakukan secara acak. 5.3. Untuk penelitian selanjutnya dapat dicoba metode lain untuk menentukan pemilihan orangtua misalnya menggunakan Roulette Wheel, metoda pemilihan kromosom yang akan dimutasi, maupun metoda crossover-nya. 5.4. Untuk penelitian selanjutnya dapat dicoba untuk ukuran problem yang lebih besar, mungkin akan dapat diamati fenomena lain yang mungkin timbul.
Daftar Pustaka [1] Gen, M., Cheng, R., 1997, Genetic Algorithms & Engineering Design, John Wiley and Sons, Inc. [2] http://www.cs.felk.cuvt.cz/~obitko/main.html, 21 November 2006. [3] Pressman R.S., 1990, Software Engineering: A practitioner's approach, 3th Ed, McGraw Hill. [4] Prather, R. E., 1995, Discrete Mathematical Structures for Computer Science, Houghton Mifflin Company. [5] Whitten, J. L., 1994, Systems Analysis and Design Methods, 3rd Ed, IRWIN.
44
