National Conference : Design and Application of Technology 2004
Penentuan Ukuran Lot dan Urutan Job dalam Penjadwalan Flow Shop dengan Algoritma Genetika
V
"c.-ani I-Iartati l , Didi Teguh pribadi 2 dan HaryoIlo J '
[email protected] 2
[email protected] .1
[email protected]
ABSTRAK Algoritma Genetika lIIerupakan metoda p encarian (searching) terstruktur lIIenggunakan analogi evolusi alallliah . Solusi-solusi yang baik akan dikolllbinasikan dengan Izarapan memperoleh solusi yung lebill baik. Seba/ikllya. solusi yang jelek alulIl digantikan dengan solusi baru y ang relatif lebill baik (Hukum Darwin). Proses pengkolllbinasian solusi dilakukan mellggunakan operator genetika. A Igoritma Gelletlka telah bal/yak digunakan dalam berbagai masalah pengoptimasian kombinasi. seperti Traveling Saleslllal/ Problem (TSP). Quadratic Assignment Problem (QAP). Job Shop Sequencing dan lain-lain. Dalal1l p el/elitian ini akan dikemukakan pelldekatan untuk memecahkan dua lIIasalah yang salil/g berhubungan. yaitu lot sizing (penentuan ukuran lot) dan sequencing (penentuan urutan job) secQl'a bersalllaall dengan menggUllakan Algorilma Genetika. Setelah dilakukan penelitial/ dengan alat bantu Visual Basic 6.0 dalal1l menyelesaikan masalah A Igoritma Genetika ini. l1Iaka dapat lerlihat bahwa hasil akhir dari penjadwalall ulltuk melldapatkan nilai makespan illi lebih optimulll. Hal ini disebabkan karena Algoritllla Genetika dapat menyelesaikan dua perlllasalahan sekaligus secara bersalllaan. semelltara metoda lIIatelllatis dall Izeuristik yang ada pada QSB-3 tidak dapat melakukal/flya. Kata KUl/ci: Algoritllla Gelletika. Pelljadwalan. Lot-sizing (penentuan ukural/ lot). Sequencing (pelleutuan urutan job).
1. PENDAHULUAN Dalam dunia Illanufaktur masalab pcnjadwalan Illemcgang peranan yang sangat penting, tcrutama agar dapal menghasilkan produksi yang tepat waktu dan tidak mengalami keterlambatan. Proses penjadwalan yang baik akan mcmperianear proses produksi dan akan meningkatkan efisiensi dan efektifitas baik uang maupun waktu . Penerapan Algoritma Genetika sebagai salah satu metoda artificial intelegellce dalam masalah penjadwalan dimaksudkan untuk Illenyelesaikan masalah yang besar dan kompleks. Persoalan penjadwalan bersifat non polinomial, sehingga model matematis mehjadi sangat tcrbatas kemampuannya dalam menyelesaikan persoalan penjadwalan tersebut, maka dikembangkan suatu teknik yang iebih efektif dan efisien scpcrli artificial intelegellce.
1.1.
I'ERUI\1USAN MASALAH
Pada penjadwalan, salah satu kJitcria yang digunakan adalah makespan, dimana makespan ini dipengaruhi oleh beberapa faktor, diantaranya adalah ukuran lot dan urutan job. Dengan demikian maka perlu dilakukan penelitian yang menggabungkan penentuan ukuran lot dan urutan job dengan penjadwalan, maka pada penelilian ini akan dipeeahkan masalah penentuan ukueran lot (lot sizing) dan urutan job (s equencing) dalam penjadwalan flow shop dengan Algoritma Genetika. 1.2. TlIJlIAN PENELITIAN
Dari pcnclitian ini diharapkan dapat diperoleh pengetahuan ten tang: I. Altcrnatifpenyclesaianl11asalah penjadwaian, terutailla untuk persoalan dengan ukuran besar. 2. Mcmpcrolch urutan pckcljaan bcscrta ukuran lot dengan lIIakespall yang minimum. (hasilnya akan discrtai dengan software program). 3. Mengetahui sejauh mana keefektifan operator genetika yang terdiri dari operator reproduksi, crossover dan mutasi sebagai pengganti dari permutasi job untuk dapat menghasilkan keanekaragaman urutan pekerjaan. Dengan eara membandingkan hasil yang diperoleh dari metoda algoritm
77
National Conference: Design and Application of Technology 2004
1.3.
Pf.J','IIlATASAN J\1ASALAH
Oala5an d<1ri pcncJilian ini ad<1lah scbagai bcrikut: I. Dala yang digunakan bersirat dctcrl1linistik dari hasil pCl11bangkit bilangan random. 2. . Model ini dilclapkan pad a masalah sistcl11 procluksi yang bcrsifatflow shop. J. i'cnclilian dilaknkan pada II-job c1allll/-l1\csin. 4. Pada wakln yang bcrs<1l1\aall, sCliap I11csin hallya mal11pll mCl11proscs I lipc job. Tidak ada oller/oopillg. 5. Tidak <1da pClllbcrhcnliall opcrasi yang scdang bCljalan. (1. l'ckcrjaall dil11nlai pad<1 s<1all=O, dan sclurnh job siap dil1roscs. 7. Mcsin sclaln Icrscdi<1 clanlidak pcrnah Illcngal<1l11i kcnls<1kan. ~. Obick yang clignllakan alan (lIkural\ killclja pcnj<1dwalall) <1dalah l11inimasi II/(lk CSP(l II , yailll waklu yang dibnlllhkan lInlnk I11cnyclcsaikan scluruh job yang dijadwaikan.
2. TERMINOLOGI YANG DIGUNAKAN i\claplIl\ tcrl1\inoiogi natural (biologi) yang digunakan clalal1l algoritma genetika adalah sebagai berikut: Tabcl I. Tcrminologi Gcnctika Natllr,,! chroillosome gene allele locus genotypc phcnolype fitncss fUllction
AIl(oritma Gcnetika string featurc, character feature value string position struclure deeodc structurc fUlIgsi tujuall
• Siring; Illcwakili lIrlllanjoh (.\·cqll('IICillg) dall lIkuran lol. • "'('(fIll/'(' cha/'acler (gellcs); IlIcwakili job yang acla. • lJkllr<111 pOjllllasi; <1dalah jllllliah string yang ada clalalll sllalll gcncr:Jsi. • Filllcs,\' /illlclioll; yang dihilllng di silli adal<1h jllllll:Jh //lakes/i(lll y<1ng dihasilbn dari sllalll lIrlllan job yang ada
No. I.
2. 3. . 4. 5. G.
Urlltall .lot> (String) 2 3 5 4 1 452 1 3 5 1 :I 2 4 532 I 4 3 2 14 5 5 4 2 3 1 Minimum Maksill1ulll SUI1l:of fitncss /I. vcragc
Makcsp:ln
580
GOO 570 G20 580 GIO
= 570 = G20 = 35GO = 593 D
Dari cotlloh tcrscblll di atas dapat tcrlihal bahwa: • JlImlah populasi adalah 6; • JlIllllah job adalah 5 job; • Pcrhilllngalll//(/kcspil/l ad<1lah filncss yang clihasilkan; • (icncrasi kc-n adalah ilcrasi yang kc-n;
78
National Conference: Design and Application of Technology 2004
• Pemilihall parents dilakukan secara random untuk mengawinkan dua string yang ada schingga dihasilkan tumllan yang mempunyai u["utanjob yang bam. Data krol11osom (sll"ing) yang ada dalam satu gcncrasi (iterasi) ditentukan pad a saat enlly data. Data-data yang diperlukan adalah: • waktu proses (waktu yang dibutuhkan untllk mcngcrjakan 1 (satu) unit suatu tipe job pada sebuah Illcsin) • waktu set-up (set-lip dilakukan setiap tipe job yang l1lasuk mesin b~lubah) • jum!ah populasi • jUll11ah gcnerasi • peluang crossover • peiuang mutasi • ukmanlot
., ,.
3. LANGKAH-LANGKAH ALGORlTMA GENETlKA
job
Secara ul11um algoritma genetika yang dikembangkan terdiri dari 4 langkah yaitu (gambar 3.1.): 1. . Inisialisasi; pellcntuan populasi awal secara acak sebagai langkah awal pencarian (searching). 2. Evaluasi fW1gsi kesesuaian (fitness junction); nilai kesesuaian setiap node dihitung berdasarkan tujuan yang ingin dicapai. 3. Operasi gcnetika; alternatif solusi bam diciptakan menggunakan operator genetika tertentu.
4. Ulangi langkah 2 dan 3 hingga l11aksimul11 generasi (stopping rule) tercapai.
Berdasarkan deskripsi di atas, algoritma genetika menggunakan fungsi tujuan dalam pellentuan arah
pengembangan ketumnan. Hanya gen-gcn "baik" yang ditumnkan pada generasi berikutnya dan
dikol11binasikan untuk memperolch populasi baru.
Pengembangan algoritma genetika yang dilakukan dalam penelitian ini meliputi:
1. Penentuan representasi string, yaitu menentukan informasi apa saja yang akan dimasukkan ke dalam string. 2. Pemilihan operator genetika, yaitu memilih jcnis pengkombinasi string yang sesuai dengan permasalahan pcnjadwalnn. 3. Pcncntuan fungsi sua ian, ynitll mencntukan kriteria evaluasi penjadwalan yang digunakan.
4. ALGORlTMA GENETIKA DALAM MENENTUKAN UKURAN LOT DAN URUTANJOn Pengembangan algoritl1la genctika yang dikemukakan dalam penelitian ini adalah pendckatan bam dalam
mcmecaltkan dua masalah yang saling berhubungan yaitu ukuran lot (lot sizing) dan umtan job/proses
(seqllel/cing) di Illana keduanya secara berhubungan akan menggunakan algoritma genetika.
Oi bawah ini nkan ditunjukkan proscdur peudekatan tersebut:
I. Ukuran lot awal dibagi l1lcnjadi beberapa ukuran lot yang Icbih kecil. 2. Tentukan tipe identifikasi baru (alele) wltuk seliap job yang bam dibentuk untuk mendapatkan gambaran kromosolll. J. Gunakan algoritma genctika untuk Illclllbual populasi secm·a random. 4. Jika ·setelah predelinisi generasi, pada saat populasi berkumpul terdapat kelompok tipe job yang sarna, l11aka gabungkan kelompok yang memiliki tipe job yang sama terscbut untuk mendapat gambaran kromosol11 yang bam, lalu kembali ke langkah J. 5. Jika pada saat populasi berkumpul, dan tidak ada kelompok yang memiliki job yang sarna, maka stop. Untuk lebill jelasnya diberikan contoh penjadwalanjlow shop dengan ukuran 5 tipe job, beserta jumlah unit (demal/d) liap lipe jobnya. Tipe Job I 2 3
4 5
78
Total Unit
46 35 27 33 52
79
National Conference: Design and Application of TecHnology 2004
l)cllgall <1rliall, Icrdapat 46 lInil yang llarliS dibuat pada lipe job 1, 35 unit pada lipe job 2 dan selcrusnya.
Mesin hanls di set up kelika lipe job yang lllasuk mesin tersebul berubah, dan waktu set up lergantung pada
lipc job yang tcrakhir diproses.
KCllluciian seliap unil yang hanls dibllat pada scliap job harus dipecah dan dilentl.lkan \lrulan job yang
I11cllliliki 1/1 Ilk C.I"PIl II minil11um. Scbagai conloh. kila Icnlukan lot size = 20, maka sctclah banyak.nya unil kila
pecah nll' llIlrullo/ size ladi. kila akan i1H::ndapatkan gal1lbaran krOIllOSOl11 awal sebagai beriklll:
t\ III-Ics
Tipe .101>
- - --- I 2 3 4 5
Ullliran Lol 20 20 6 20 15 20
I 2 2 3 3 4 4 5 5 5
(,
7 8
9 10 II
12
7
20 13 20 20 12
KCl11l1dian krOillOSOl1l awal Icrsebut di alas akan diproses dC!lgan algoritma genelika. Dan scbagai conloll,
didapaillasil struklur scperli bcrikut ini:
gCl/u/r/lC : ( 7-2-6-12-4-5-8-3-10-11-9-1 )
Ilhcl/nlj ,/)(' : {(3,7) (1 ,20) (3,20) (5 , 12) (2,20) (2,15) (4,20) (1 ,6) (5,20) (5,20) (4 , 13) (1 ,20)}
SCliap pasangan di phel/otype menyatakan lipe job dan jumlah unilnya . Gen-gcn yang digarisbawahi dapal
disallibn lllenj;l(li sil/gle gcn scpcrli bcrikul:
)d/('I/()/)'/J(' : {(.1.7) (1.20) (3.20) (5,12) (2,35) ('1.20) (Ul) (5,40) (4.13) (1.20)}
gCllo/l'/}('
: ( 1-2 - 3-4-5-()-7-H-~-IO)
Ilasil yang didap;ll dari pcnggabungall Icrseblll adalah panj;lng krOlllosolll bcrkurang dari 12 Il1cnjadi 10.
l Jnluk scl;lIljulnya. pada pCllclilian ini abn dilakubn pcrhilllng;ln dcngan peillbalas-pclllbalas dan aSlllllsi
;lSlIlllSi scbagai beriklll:
1. Pcncl il ian d ilakllkan pacla 5 Illcsin dan 5, 6, 8 lipe job. 2. Rallge lolai unilliap lipl' job yang harlls dibllal [20,50] 3. RlIllge waklu proscs [0.0 I , 1.0] dan Range waktu set up [0.1 ,2.0] 4. Probabililas Cross over = I , dengan operator OX (order crossover) 5. Inilialukllran lot (lot size) = 20, 15,20 6. JUllllall I'0Plllasi = 4 7. Cienerasi =, 300, pad a sl'tiap 50 gencrasi didapat pOPlilasi lerbaik (sementara) . 8. Job yang tdah dikerjakan pad a mesin peliama akan masuk mesin kedua jika jumlahnya tclah sal1la dengan uklll'an lotnya.
5. KESII\1PULAN i);lri pcnclili<1n yang tclah dilakukan, dapal diambil kesilllpulan sebagai berikut: • Urulnn Job dan Ukuran Lot untuk pcrsoalan Pcnjadwalan flow Shop. 5 Mesin dengan 5, 6, dan 8 tipe Job ynllg lcrbnik, adalah scbagai berikul : Tabel 3. Ilasill'crhillingan Mak('spnll Tcrbilik Untuk Scliap Pcrsoalan , Mal(cs 1all Pcrsoalall
-5 Mcsin - 5 Tirc Job ~_~~~I~...:~IlJ>c Job S M~sil\ -. l\ Tipe .lob
No Split
Split=10
Split = 15
203.61 234.48 341.1 R
165.25 224.1)) 342.0(i
171.28 219.80 D7.77
Split
= 20
193.94 222.56 328.4 7
80
NatiOnal Gonterence: Design and Application of Technology 2004
TalJel 4. Hasil Perhitungan Makespall Terbaik Dellgan Splitillg Menggunakan Algoritma Gelletik
ya.
Ida
Persoalan
Ukuran Lot
5 Mcsin - 5 Tipe Job
10
5 Mcsin - G Tipc Job
15
5 Mcsin - 8 Tipe Job
20
ng
ita
Urulan Job (t, I0) (4,3) (5,10) (3,10) (4,10) (5,10) (2,20) (1,10) (3,7) (5,32) (I IG)(2,15HI,IOH3,IO~ (4,20) (G,15) (4,15) (5,18) (3,3G) (4,1) (I,IG) (2,30) (G,29) (3,15) (5,30) (4,25) (2,23) (1,30) (1,59) (5,14) (8,23) (7,5) (3,3) (8,20) (G,20) (4,29) (8,40) (5,20) (G,58) (2,33) (7,20) (4,20) (3,40) (1,20) (5,20)
Makcspan IG5.25
21980
328.47
• Ukuran kinclja penjadwalan yaitu minimasi makespan, yang dihasilkan dengan menggunakan Algoritma Genetika menunjukkan hasil yang lebih baik dari Metoda Johnson's. Selain itu, Algoritma Genetika menetapkan suatu pcndekatan lmtuk menggabungkan ukuran lot dan urutan job menjadi satu proses solusi, scdangkan pada Metoda 10lUlson's hal itu tidak dapat dilakukan. Tabel 4. Hasil Perhitungan Makespall Terbaik Menggunakan Metoda Johnson's
)h,
Jat
51
Pcrsoalan 5 Mesin - 5 TijlC Job 5 Mesin - G Tipe Job 5 Mesin - 8 Tipe Job
Urulan JolJ 2-5-1-3-4 G-3-5-4-2-1 1-8-G-7-3-4-2-5
Makcspan 20G.57 222.22 339.GO
• Pendekalan yang berbasis Algoritma Genctika, dalam l11cmecahkan masalah penetuan ukuran lot dan' urutan job ini terlihat lebih baik, ketika struktur kromosom secara dinamis diubah dengan cara menggabungkan rangkaian tipe job yang sama menjadi bentuk yang lebih efisien. • Kelebihan lain dari Algoritma Genetika yaitu dapat mcmperoleh hasil yang optimum (sub optimal) dengan menggunakan r/ln ti/lle yang kecil, yang mana hal ini tidak dapat dilakukall oleh mctoda penjadwalan sccara matcmatis dali heuristik, dan inilah salah satu kelebihan Algoritma Gcnetika yallg mCl1lpakan salah satu bagiall dari Artificial Illtelegellce, yang lebih dikenal sebagai mctoda pencariall (searching /IIethod).
6. DAFTAR PUSTAKA
IlJ
I. Chuen Lung Chen, Ranga V. Neppalli, Nasser Aljaber, Genetic Algorithms Applied to The ContinlioliS Flow Shop Problem, Computers indo Engng vol. 30 no. 4, hal. 919-929, 1996. 2. Riyaz Sikora, A Genetic Algorithms for Integrating Lot Sizing and Sequencing ini Scheduling a Capacitated Flow Line, Computers indo Engng vol. 30 no. 4, hal. 1061-1071, 1996. 3. In Lec, Riyaz Sikora, Michael J. Shaw, Joint Lot Sizing and Sequencing With Gelletic Algorithllls for Scheduling: evolving the chromosollle strUCl/Ire, In Gcnetic Algoritluns Proc. Of the fifth int. conf. (GA93) (editcd by S. Forrest), pp. 383-389. Morgan Kaufmarm, San Mateo, CA, 1993. 4. Spencer 13. Smith, Computer Based Productioll and InventOlY COlltrol, Prentice Hall IntI., Inc. USA, 1989.
pc
o
81
