IMPLEMENTASI METODE FUZZY RULE BASE PADA KASUS JOB-SHOP DENGAN PENJADWALAN ADAPTIF

Tugas Akhir Periode Juli 2010

IMPLEMENTASI METODE FUZZY RULE BASE PADA KASUS JOB-SHOP DENGAN PENJADWALAN ADAPTIF Husnul Hakim—Ahmad Saikhu, S.Si, MT Jurusan Teknik Informatika ITS, Fakultas Teknologi Informasi, Institut Teknologi Sepuluh Nopember, Surabaya Email : [email protected] Masalah penjadwalan job-shop dapat ditangani dengan berbagai macam pendekatan yaitu dengan pendekatan analisis, heuristik, dan simulasi. Pendekatan analitis berfokus pada permodelan dan perumusan matematika untuk mengatur penjadwalan. Pendekatan secara analitis hanya terbatas untuk kasus atau permasalahan yang berukuran kecil, sehingga tidak dapat menyelesaikan kasus-kasus penjadwalan yang kompleks. Pada pendekatan heuristik, permasalahan pada penjadwalan job-shop diselesaikan dengan berfokus kepada pemilihan job-job sesuai prioritas dengan menggunakan dispatching rules. Melalui pendekatan ini diperoleh hasil penjadwalan yang lebih baik apabila dibandingkan dengan pendekatan analitis. Akan tetapi, masih tetap sulit untuk membuktikan kegunaan umum dari suatu rule disebabkan oleh karakteristik sistem yang berbedabeda. Pendekatan simulasi lebih digunakan dalam penentuan atau penilaian terhadap rule-rule. Melalui proses simulasi, setiap rule akan dinilai performanya pada suatu periode waktu tertentu. Setelah diperoleh performa dari masing-masing rule, kemudian akan diambil keputusan untuk penjadwalan. Pendekatan simulasi memiliki kekurangan untuk pengambilan keputusan secara real-time. Selain melalui pendekatan-pendekatan di atas, penjadwalan job-shop juga dapat diselesaikan melalui logika fuzzy. Dengan menggunakan logika fuzzy, diharapkan penjadwalan yang dilakukan dapat lebih bersifat adaptif. Penjadwalan dengan logika fuzzy yang digunakan dalam penyusunan tugas akhir ini digunakan untuk membangun rule yang tepat untuk menjadwalkan job-shop. Rule yang dibangun menentukan control vector yang digunakan untuk menentukan prioritas job yang paling tepat untuk digunakan di dalam sistem.

ABSTRAK Penjadwalan job-shop merupakan permasalahan yang kompleks untuk dipecahkan. Metode penjadwalan yang tepat untuk suatu jobshop akan meningkatkan kinerja atau performa jobshop tersebut. Ada banyak pendekatan yang bisa digunakan untuk menyelesaikan penjadwalan jobshop, mulai dari pendekatan analitis, heuristik, dan simulasi. Dalam tugas akhir ini, akan diimplementasikan fuzzy rule base untuk menyelesaikan penjadwalan job-shop. Logika fuzzy yang diimplementasikan, digunakan untuk memilih control vector yang tepat dalam menjadwalkan jobshop. Control vector adalah vektor yang elemenelemennya merupakan bobot dari kriteria penjadwalan (dispatching rules). Dispatching rules yang digunakan dalam tugas akhir ini adalah Normalized Urgency of Next Workstation (NUNQ) dan Normalized Processing Time (NPT). Fuzzy rule base akan menentukan kombinasi antara NPT dan NUNQ dengan bobot yang tepat untuk dijadikan sebagai aturan penjadwalan pada jobshop, sesuai dengan keadaan atau state (direpresentasikan dengan state vectors) pada jobshop. Dengan demikian, penjadwalan job-shop menjadi adaptif, karena pemilihan control vector tergantung pada state vectors. Hasil dari Tugas Akhir ini adalah rule berupa pemilihan control vector terbaik untuk setiap fuzzy subspace. Pada tiap fuzzy subspace terdapat nilai fuzzy dari state vectors. Nilai fuzzy yang dipilih dalam Tugas Akhir ini adalah K=3, yang berarti bahwa state vectors difuzzifikasi untuk tiga ukuran, yaitu kecil, sedang, dan besar. Rule yang terbentuk menunjukkan bentuk penjadwalan adaptif berdasarkan nilai fuzzy dari 4 state vectors, apakah kecil, sedang, atau besar.

2. Kata Kunci : Job-shop problem , Penjadwalan Adaptif, Fuzzy Rule Base 1.

Job-Shop Problem

Konsep penjadwalan job-shop adalah menentukan waktu suatu operasi mulai dikerjakan dan mengalokasikan resource untuk mengerjakan operasi tersebut. Pada saat menjadwalkan suatu operasi selain menentukan kapan operasi tersebut mulai dikerjakan juga ditentukan resource mana yang dipakai oleh operasi tersebut. Oleh karena itu,

Pendahuluan

Penjadwalan job-shop merupakan bagian penting dalam mencapai produktivitas yang baik.

1

Tugas Akhir Periode Juli 2010 pada saat menjadwalkan suatu operasi harus diperhatikan dua batasan (constraint) berikut ini. 1. Presedence Constraint. Penjadwalan untuk setiap operasi dari job yang sama harus berurutan sesuai dengan precedence constraint job tersebut. 2. Resource Constraint. Penjadwalan setiap operasi membutuhkan sebuah resource untuk mengerjakan operasi tersebut. Pada saat operasi ini mulai diproses, resource tersebut harus sedang tidak dipakai oleh operasi ini. Resource ini juga menjadi tidak dapat dipakai oleh operasi lain sampai operasi tersebut selesai. Jika penjadwalan suatu operasi melanggar constraint maka penjadwalan operasi tersebut harus dialihkan waktunya, dii mana pengalihan waktu ini menyebabkan penyelesaian job berlangsung lebih kama dan menyebabkan keterlambatan. 2.1.

memiliki waktu proses paling tinggi pada antrian akan diutamakan.

Dispatching Rules

Dispatching rules merupakan algoritmaalgoritma untuk menantukan urutan job yang akan dikerjakan terlebih dahulu dalam suatu kasus jobshop. Berikut ini adalah beberapa contoh dari dispatching rules. a.

b.

c.

EDD EDD atau Earliest Due Date merupakan rule yang mendahulukan atau memprioritaskan lebih tinggi kepada job yang memiliki due date paling dekat dengan saat ini. Rule ini efektif dalam meminimalisasi mean tardiness dari job.

e.

S/OPN S/OPN adalah slack per remaining operation. Job yang diproses lebih dahulu, adalah job dengan rasio slack paling rendah dari operasi yang selanjutnya akan dikerjakan. Rule ini efektif untuk mengontrol tardiness karena memprioritaskan job berdasarkan slack terendah dan sisa operasi yang belum dikerjakan.

f.

COVERT COVERT (Cost Over Time). Pengurutan berbanding terbalik dengan rasio dari fungsi penalti sepanjang waktu proses. COVERT baik dalam pengoptimalan tardiness.

g.

MWKR MWKR merupakan kepanjangan dari Most Work Remaining. Pada rule ini, job dipilih berdasarkan sisa operasi yang belum dilakukan pada job tersebut.

h.

FCFS First Come First Serve (FCFS) mengurutkan job berdasarkan urutan kedatangannya pada antrian workcenter. Job yang lebih datang lebih awal akan diproses terlebih dahulu.

i.

FAFS Pada First Arrival First Serve (FAFS), job yang dikerjakan lebih dahulu adalah job yang lebih awal masuk ke dalam sistem.

j.

RANDOM Prioritas pekerjaan secara random.

3.

Logika Fuzzy

Konflik

Suatu operasi yang akan dijadwalkan pada waktu tertentu, harus memenuhi constraint yang telah disebutkan pada bagian sebelumnya. Jika penjadwalan melanggar salah satu constraint, maka akan terjadi konflik dan operasi tersebut harus dialihkan ke alokasi waktu yang lain. 2.2.

d.

FIFO Merupakan kependekan dari First In First Out. Job yang mengantri terlebih dahulu, akan memiliki prioritas lebih tinggi untuk diproses. Dengan kata lain, pekerjaan diproses sesuai dengan urutan antrian. SPT Shortest Processing Time. Job yang akan diproses pada mesin akan diurutkan berdasarkan waktu prosesnya pada mesin tersebut. Job yang memiliki waktu proses paling singkat pada antrian, akann diproses lebih dahulu. Rule ini adalah salah satu yang paling banyak digunakan karena kesederhanaannya. SPT juga baik digunakan untuk meminimalisasi mean flow time. LPT LPT (Longest Processing Time) adalah kebalikan dari SPT. Job-job yang akan diproses akan diurutkan berdasarkan waktu prosesnya pada mesin tersebut. Job yang

Himpunan fuzzy lahir karena banyaknya fenomena yang bersifat samar atau serba tidak tepat ditinjau dari cara berpikir manusia. Pada kenyataannya, tidak ada suatu kondisi atau pernyataan yang tepat 100% benar atau 100% salah. Menurut Prof. Lotfi. A. Zadeh, true atau false dalam logika boolean tidak dapat merepresentasikan pernyataan ‘abu-abu’ atau samar

2

Tugas Akhir Periode Juli 2010 di antara pernyataan true dan false seperti yang terjadi di dunia nyata. Untuk mengatasi masalah di atas, maka lahirlah logika fuzzy. Logika fuzzy memberikan nilai spesifik pada setiap nilai di antara pernyataan true atau false dengan menentukan fungsi keanggotaan (membership function) bagi tiap nilai input dari proses fuzzy dan derajat keanggotaaan (degree of membership). Input diberi milai derajat sesuai fungsi keanggotaan antara nilai 0 sampai 1, sehingga memungkinkan bagi suatu persamaan memiliki nilai true dan false secara bersamaan. 3.1.

yaitu pemotongan, pembengkokan, permesinan dan pengelasan. Tugas akhir ini akan menyelesaikan permasalahan job-shop dalam pengurutan job ketika akan dikerjakan pada suatu workcenter dengan mempertimbangkan waktu proses tiap job di setiap workcenter yang dilalui. Selain itu juga dipertimbangkan jumlah antrian di tiap workcenter. Setelah diketahui keadaan sistem yaitu waktu proses di setiap workcenter dan jumlah antrian di setiap workcenter dapat ditentukan urutan pengerjaan dari tiap job di setiap workcenter melalui penentuan prioritas.

Fungsi Keanggotaan

Fungsi keanggotaan adalah suatu kurva yang menunjukkan pemetaan titik-titk input data ke dalam nilai keanggotaannya (derajat keanggotaannya) yang memiliki interval antara 0 dan 1. Salah satu cara yang dapat digunakan untuk mendapatkan nilai keanggotaan adalah dengan melalui pendekatan fungsi. Fungsi-fungsi keanggotaan yang dapat digunakan dalam merepresentasikan logika fuzzy antara lain : a. Representasi Linear b. Representasi Kurva Segitiga c. Representasi Kurva Trapesium d. Representasi Kurva Bentuk Bahu e. Representasi Kurva-S 3.2.

4.2.

Performa yang dinilai pada job-shop dalam tugas akhir ini adalah flow-time. Untuk itulah perlu ditentukan decision criteria yang tepat yang dapat mengoptimalkan nilai dari flow-time. Flow-time adalah total waktu dari suatu job selama berada di dalam sistem. Flow-time dirumuskan dalam persamaan 1. 𝑓𝑙𝑜𝑤 − 𝑡𝑖𝑚𝑒 = 𝑡𝑜𝑡𝑎𝑙 𝑝𝑟𝑜𝑐𝑒𝑠𝑠𝑖𝑛𝑔 𝑡𝑖𝑚𝑒 + 𝑤𝑎𝑖𝑡𝑖𝑛𝑔 𝑡𝑖𝑚𝑒 + 𝑡𝑜𝑡𝑎𝑙 𝑡𝑟𝑎𝑛𝑠𝑝𝑜𝑟𝑡𝑎𝑡𝑖𝑜𝑛 𝑡𝑖𝑚𝑒 + 𝑠𝑒𝑡 − 𝑢𝑝 𝑎𝑛𝑑 𝑙𝑜𝑎𝑑/𝑢𝑛𝑙𝑜𝑎𝑑 𝑡𝑖𝑚𝑒. (1)

Fuzzy Rule Base

Waktu proses operasi dan waktu transportasi bersifat deterministik, sedangkan waktu set-up diabaikan dalam sistem pada tugas akhir ini. Oleh karena itu, untuk meminimaliasi flow-time maka waiting time dari job pada queue harus diminimaliasi . Untuk mencapai waiting time minimal ini, digunakan dua macam kriteria penjadwalan, yaitu Normalized Urgency of Next Workcenter (NUNQ), dan Normalized Processing Time (NPT). Normalized berarti nilai dari kriteria ditransformasi ke suatu range dari 0 sampai 1. a. NUNQ merepresentasikan jumlah antrian dari workcenter. b. NPT merepresentasikan processing time dari job pada setiap workcenter.

Fuzzy rule base merupakan inti dari logika fuzzy. Fuzzy rule base berisi pernyataan-pernyataan logika fuzzy yang berbentuk pernyataan-pernyataan IF-THEN. Bentuk umum dari fuzzy rule base adalah : B”

“If 𝑥1 is𝐴11 and 𝑥2 is𝐴12 . .. and... 𝐴1𝑛 then y is

𝐴11 dan B adalah himpunan fuzzy, sedangkan 𝑥 = (𝑥1 , 𝑥2 , … , 𝑥𝑛 ) adalah input dari variabel fuzzy. Pad subbab 2.3.5 akan dijelaskan lebih lanjut mengenai fuzzy rule base, terutama implementasinya dalam menyelesaikan masalah penjadwalan pada job-shop. 4.

Implementasi Fuzzy Rule Base Pada Penjadwalan Job-Shop

4.1.

Deskripsi Sistem Job-Shop

Penjadwalan

Untuk melakukan normalisasi pada jumlah antrian dan processing time, digunakan persamaan 2. 𝑁𝑒𝑤 𝑥𝑖 =

𝑂𝑙𝑑 𝑥 𝑖 −𝑀𝑖𝑛 (𝑋) 𝑀𝑎𝑥 𝑋 −𝑀𝑖𝑛 (𝑋)

(2)

Sistem job-shop yang digunakan pada tugas akhir ini adalah sistem job-shop yang terdiri dari empat workcenter (pemotongan, pembengkokan, permesinan, dan pengelasan). Tiap workcenter memiliki tiga mesin untuk memproses job. Tiap job akan diproses melalui urutan yang telah ditentukan,

Dengan : 𝑁𝑒𝑤 𝑥𝑖 : Nilai hasil normalisasi. 𝑂𝑙𝑑 𝑥𝑖 : Nilai yang akan dinormalisasi

3

Tugas Akhir Periode Juli 2010 𝑀𝑎𝑥 𝑋 𝑀𝑖𝑛(𝑋)

dengan menghitung ketepatan dari rule untuk setiap state vectors.

: Nilai maksimum dari data. : Nilai minimum dari data.

a.

Kriteria penjadwalan NUNQ dan NPT akan digunakan dalam menentukan prioritas dari jobshop dengan penggunaan control vector.

4.3.

Bobot dari kriteria yang digunakan, ditentukan melalui sebuah control vector (w1,w2) yang menunjukkan bobot dari NUNQ dan NPT. Control vector yang digunakan dalam tugas akhir ini ditunjukkan pada tabel 1. Tabel 1 Control Vector c1 0 -1

c2 1 -1

c3 0 1

c4 1 1

Priority Index merupakan indeks yang menunjukkan nilai prioritas dari job untuk diproses pada suatu workcenter. Priority index suatu job k pada workcenter s dirumuskan dengan persamaan 3. 𝑃𝑟𝑖𝑜𝑟𝑖𝑡𝑦 𝑘, 𝑠 =

𝑤𝑖 𝑠 𝑥𝐶𝑟𝑖𝑡𝑒𝑟𝑖𝑜𝑛𝑖 (𝑘, 𝑠) 𝑖

(3) Priority index menentukan urutan pengerjaan job pada suatu workcenter. Job yang memiliki priority index lebih tinggi akan dikerjakan lebih dahulu, dan sebaliknya. Fuzzy rule yang akan dibangun pada tugas akhir ini adalah menentukan control vector mana yang paling tepat untuk digunakan sesuai dengan keadaan dari sistem jobshop. Keadaan sistem ini direpresentasikan dalam sebuah state vector yang berisi nilai-nilai state variables. 4.4.

Knowledge Acquisition Decision Making Phase

Phase

dan

memfuzifikasi

dan

Terdapat dua tahapan dalam penerapan logika fuzzy untuk penjadwalan job-shop yaitu : Knowledge Acquisition Phase dan Decision Making Phase 1.)

states

Pada tahap ini, states variables yang menggambarkan karakteristik dari sistem (dalam hal ini job-shop). States variables yang dipilih dalam tugas akhir ini terdiri dari 4 variabel, yaitu : 𝑥1 : NPT maksimum dari antrian 𝑥2 : NUNQ maksimum dari antrian 𝑥3 : NPT minimum dari antrian 𝑥4 : panjang antrian yang dinormaliasasi. 𝑥1 merupakan representasi dari NPT maksimum pada antrian job. Hal ini berarti dari p-replikasi yang dilakukan, masing-masing total waktu proses di tiap workcenter dinormalisasi. Setelah dilakukan normalisasi kemudian dipilih nilai NPT yang paling tinggi dari keempat workcenter sebagai 𝑥1 . Hal ini berlaku pula untuk menentukan 𝑥3 , hanya saja pada 𝑥3 , bukan nilai yang paling tinggi pada NPT tiap workcenter yang dipilih, melainkan yang memiliki nilai paling rendah. Variabel 𝑥2 menunjukkan keadaan maksimum pada antrian di tiap workcenter. Jumlah antrian rata-rata dari tiap workcenter pada setiap replikasi terlebih dahulu dicatat. Setelah itu, lakukan normalisasi pada tiap workcenter. Dari asil normalisasi ini kemudian dipilih nilai yang paling maksimum sebagai x2 dari tiap replikasi. Variabel terakhir dalam state variables adalah x4 yang merupakan panjang antrian yang dinormalisasi. Panjang antrian diperoleh dengan menjumlahkan banyaknya antrian dari tiap workcenter kemudian dinormalisasi. States variables ini kemudian akan difuzzifikasi berdasarkan fungsi keanggotaan yang dipilih. Nilai fuzifikasi dari state variables direpresentasikan dengan bilangan fuzzy, 𝐴𝑘𝑖 . Fungsi keanggotaan yang digunakan adalah fungsi keanggotaan yang digunakan dalam implementasi tugas akhir ini adalah fungsi keanggotaan yang ditunjukkan pada gambar 1.

Priority Index

c w1 w2

Memilih variables

Knowledge Acquisition Phase

Tahap pengumpulan data dan tahap pembangunan rule pada knowledge acquisition phase terdiri dari 3 langkah, yaitu : 1) Memilih dan memfuzifikasi states variables. 2) mengumpulan data performa dari tiap state vector berdasarkan rule dan control vector. 3) Membangun rule base

Gambar 1. Fungsi Keanggotaan

4

Tugas Akhir Periode Juli 2010 Dengan fungsi keanggotaan pada gambar 1, maka state variables dapat difuzifikasi ke dalam tiga kategori yaitu kecil, sedang dan besar. b.

𝛽 𝑐 𝐴𝐾𝑖 𝑗 …𝑣 =

Mengumpulkan data sampel

(5) c=1, 2, ..., q;

Data sampel berisi nilai states variables dan performa (dalam hal ini flow time) . State vectors dinotasikan dengan xp = { x1p, x2p, . . . , xmp } , p=1,2,...,n. Dimana m adalah banyaknya state variables dan n adalah banyaknya data sampel. Nilai performa dari control vector c pada state xp , 𝑋 disimbolkan dengan 𝑃𝑉𝑐 𝑝 , c = 1, 2, ... , q, di mana q adalah jumlah dari kontrol vektor yang mungkin. Performa diperoleh dengan menghitung flow time berdasarkan prioritas yang dihitung berdasarkan control vector c. c.

c.

Step 3. Menghitung DS (Degree of Suitability) untuk menila kekuatan relatif dari suatu control vector c dibandingkan dengan control vector lainnya pada state xp. Semakin besar nilai DS menggambarkan semakin cocok/tepatnya penggunaan control vector c untuk state xp.

𝐷𝑆 𝑐 𝐴𝐾𝑖 𝑗 …𝑣 =

Membangun Rule Base

𝛽𝑖 𝑗 ..𝑣 =

𝑥𝑝

2.)

𝑥𝑝 𝑥𝑝 𝑃𝑉𝑤𝑜𝑟𝑠𝑡 −𝑃𝑉𝑏𝑒𝑠𝑡

𝑡 𝐴𝐾𝑖 𝑗 …𝑣 𝑞

Decison Making Phase

Decision making phase adalah proses menilai rule untuk state vector yang diberikan dan menentukan rule mana yang paling tepat untuk state tersebut. Prosedur dalam mengambil keputusan pada tahap ini adalah sebagai berikut. a. Step 1. Menghitung nilai Degree of Appropriateness (DA) yang mengindikasikan kecocokan dan efektivitas dari control vecto c, c= 1,2,...,q pada current state x.

𝑥𝑝

𝑃𝑉𝑤𝑜𝑟𝑠𝑡 −𝑃𝑉𝑐

𝑞 𝑡=1 𝛽

(7)

Prosedur pembangunan rule base terdiri dari 3 langkah sebagai berikut. a. Step 1. Performa yang diukur adalah meanflow time. Oleh karena itu, semakin kecil nilai performa menunjukkan performa itu 𝑥 semakin baik. Degree of Effectiveness 𝐷𝐸𝑐 𝑝 untuk setiap control vector c pada state xp didefiniskan sebagai berikut : 𝑥

𝑚𝑎𝑥 𝑡 {𝛽 𝑡 𝐴𝐾 𝑖 𝑗 …𝑣 }

dengan :

“Jika xp = 𝑨𝑲 𝒊 𝒋…𝒗 maka gunakan control vector c”

𝐷𝐸𝑐 𝑝 =

𝛽 𝑐 𝐴𝐾 𝑖 𝑗 …𝑣 −𝛽 𝑖 𝑗 ..𝑣

(6)

Dari data sampel yang terdiri dari state vectrors (yang elemen-elemennya merupakan state variables) dan nilai performa, kemudian state vector xp difuzifikasi menjadi “ jika x1p = 𝐴𝐾𝑖 , x2p = 𝐴𝑗𝐾 ,..., xmp = 𝐴𝐾𝑣 , maka xp dikatakan memiliki nilai 𝐴𝐾𝑖 𝑗 …𝑣 . Dengan demikian, rule base yang dibangun akan berupa :

, untuk c=1,2,...q . (4)

b.

𝑥

𝑥1𝑝 𝜇𝑗𝐾 𝑥2𝑝 … 𝜇𝑣𝐾 (𝑥𝑚𝑝 )𝐷𝐸𝑐 𝑝

𝐾 𝑛 𝑝=1 𝜇𝑖

𝐷𝐴𝐾𝑐

Dengan : 𝑥𝑝 𝑃𝑉𝑤𝑜𝑟𝑠𝑡 = performa paling buruk di antara semua control vector pada state xp. 𝑥𝑝 𝑃𝑉𝑏𝑒𝑠𝑡 = performa paling buruk di antara semua control vector pada state xp. 𝑥 𝐷𝐸𝑐 𝑝 memiliki nilai di antara 0 dan 1. Nilai 1 menunjukkan nilai efektivitas dari control vector paling baik sedangkan 0 paling buruk. Step 2. Menghitung cumulative score yang merupakan nilai kumulatif dari semua control vector c pada setiap fuzzy subspace 𝐴𝐾𝑖 𝑗 …𝑣 dengan :

= 𝑖

b.

𝜇𝑖𝐾 𝑥1 𝜇𝑗𝐾 𝑥2 … 𝜇𝑣𝐾 𝑥𝑚 𝐷𝑆(𝑐| 𝐴𝐾𝑖 𝑗 …𝑣 )

… 𝑗

𝑣

(8) Step 2 menentukan control vector yang paling tepat untuk K. 𝑐 ∗ 𝐾 = 𝑎𝑟𝑔𝑚𝑎𝑥𝑡 {𝐷𝐴𝐾𝑡 } (9)

c.

5

Step 3. Jika 𝐷𝐴𝐾𝑐 untuk 𝑐 ∗ yang dipilih nilainya kurang dari threshold T, gunakan control vector yang telah digunakan sesuai

Tugas Akhir Periode Juli 2010 dengan tahap knowledge-acquisition phase. Jika tidak, maka control vector c* adalah control vector yang tepat untuk current state. 5.

scores diperoleh dengan mengalikan state variables yang difuzifikasi, dengan nilai degree of effectiveness untuk setiap subspace. Diagram alir proses ini ditunjukkan pada gambar 3. Mulai

Desain dan Implementasi Sistem

Dataset yang akan diproses untuk membangun rule base diperoleh melalui proses perhitungan terhadap bilangan acak yang dibankitkan berdasarkan data rata-rata dari proses simulasi. Selanjutnya tiap job diurutkan dengan menerapkan prioritas untuk tiap job menggunakan control vector sehingga diperoleh performa dari tiap control vector. 5.1.

Input : Matriks deg_ef, statevect

Fuzzifikasi State Vectors

Pembangunan Rule Hitung Cumulative Scores

Ada tiga step dalam membangun rule yaitu penghitungan degree of effecitveness dari performa tiap control vector, perhitungan cumulative score yang merupakan nilai dari tiap control vektor untuk tiap fuzzy subspace, dan menghitung degree of suitable untuk menentukan control vector yang tepat untuk suatu state dan kemudian merumuskannya dalam rule.

Output : Matriks CT

Selesai

Mulai

Gambar 3. Diagram Alir Cumulative Scores Step terakhir dalam pembangunan rule adalah menghitung degree of suitability, dengan diagram alir seperti pada gambar 4.

Input : Dataset performa control vector

Pilih Performa Terbaik dan Performa Terburuk

Mulai

Input : Cumulative Scores

Hitung Bii

Hitung Degree of Effectiveness Hitung Nilai MaksimalCumulati ve Score untuk suatu state di antara semua control vector

Output : Matriks deg_ef

Hitung Degree Of Suitable

Konstruksi Rule Berdasarkan Degree Of Suitable

Output : suit_score, rules

Selesai

Selesai

Gambar 2. Diagram Alir Degree of Effectiveness Gambar 4. Diagram Alir Perhitungan Degree of Suitability

Setelah menghitung degree of effectiveness, kemudian dihitung cumulative scores. Cumulative

6

Tugas Akhir Periode Juli 2010

5.2.

𝑥1 𝑥2 𝑥3 𝑥4

Decision Making

Tahap decision making phase adalah tahap pengambilan keputusan untuk menentukan control vector apa yang paling tepat untuk suatu current state. Diagram alir tahapan ini ditunjukkan pada gambar 5.

: NPT maksimum dari antrian : NUNQ maksimum dari antrian : NPT minimum dari antrian : panjang antrian yang dinormaliasasi.

Tabel 1. Dataset Skenario 1 p

x1

x2

x3

x4

PVC1

PVC2

PVC3

PVC4

1

0.00

0.00

0.26

0.00

38.38

38.68

39.80

39.76

2

0.55

0.59

1.00

0.70

42.85

43.20

44.78

44.48

3

0.14

0.45

0.44

0.28

39.91

40.22

41.22

41.50

4

0.19

0.41

0.58

0.43

40.90

41.23

42.82

42.52

5

0.00

0.00

0.26

0.06

39.14

38.92

39.44

40.03

6

0.42

0.55

0.67

0.55

41.37

41.68

43.43

43.11

7

0.01

0.18

0.33

0.21

39.68

40.03

41.51

41.24

8

0.08

0.09

0.14

0.09

38.78

39.07

40.52

40.22

9

0.00

1.00

1.00

1.00

44.89

45.20

46.81

46.45

10

0.27

0.41

0.54

0.53

41.30

41.61

43.21

42.90

Mulai

Input : Degree of Suitable, Current State

Hitung Degree Of Appropriateness :

DA cK  Threshold

TIDAK

?

YA Gunakan control vector C* Tampilkan Pesan Output Matriks DA, Decision

Performa (flow-time) dari tiap control vector disimpan dalam kolom-kolom PVC1,PVC2, PVC3 dan PVC4. Dengan melakukan uji coba pada skenario 1diperoleh rule yang menunjukkan hasil yang sama untuk setiap subspace, yaitu bahwa untuk setiap subspace, control vector yang digunakan adalah control vector 1 (0,-1). Berikut ini rule yang dihasilkan pada skenario 1.

Selesai

Gambar 5. Diagram Alir Decision Making Phase 6.

Uji Coba dan Evaluasi

“Jika x1 kecil, x2 kecil, x3 sedang, x4 besar gunakan control vector ke-1 “

Uji coba dilakukan untuk menilai performa (flow-time) pada job-shop. Uji coba dilakukan pada job-shop dengan distribusi waktu pengerjaan pada mesin sesuai distribusi pada mesin pemotong, pembengkok, permesinan, dan pengelasan yaitu dengan distribusi : 1. Skenario 1 dengan TRIANGULAR (0.9, 1, 1.1) 2. Skenario 2 dengan distribusi NORMAL (1, 0.001). Data hasil pembangkitan bilangan acak tersebut kemudian dinormalisasi, dan dihitung prioritas dari masing-masing job pada tiap workcenter menggunakan control vector. Dataset yang diperoleh ditunjukkan pada Tabel 1. Pada skenario 1 ini, dilakukan 10 kali replikasi (direpresentasikan dengan p). States variables yang menggambarkan keadaan waktu proses job di tiap mesin dan jumlah antrian direpresentasikan dalam variabel x1, x2, x3,dan x4. Dimana :

.... “Jika Jika x1 kecil, x2 kecil, x3 sedang, x4 besar gunakan control vector ke-1” Untuk skenario uji coba kedua, distribusi yang digunakan adalah distribusi NORMAL (1,0.001). Tabel 2 merupakan dataset untuk input pada skenario uji coba 2. Rule yang dihasilkan pada skenario uji coba kedua adalah sebagai berikut : “Jika x1 sedang, x2 besar, x3 sedang, x4 besar gunakan control vector ke-2” ... “Jika x1 besar, x2 besar, x3 besar, x4 besar gunakan control vector ke-1”

7

Tugas Akhir Periode Juli 2010 Dari uji coba yang telah dilakukan dan setelah menganalisis hasil pengujian terhadap implementasi fuzzy rule base pada kasus job-shop dengan penjadwalan adaptif, dapat diambil beberapa kesimpulan antara lain:

Tabel 2. Dataset Skenario 2 p

x1

x2

x3

x4

PVC1

PVC2

PVC3

PVC4

1

0,24

1,00

1,00

0,37

44,80

44,81

44,85

44,84

2

0,08

0,40

0,45

0,17

41,22

41,23

41,26

41,26

3

0,25

1,00

1,00

1,00

55,67

55,68

55,73

55,72

4

0,11

0,31

0,31

0,29

43,43

43,44

43,48

43,48

5

0,35

0,60

0,58

0,53

47,63

47,64

47,68

47,64

6

0,37

0,80

0,93

0,77

51,94

51,94

52,00

51,99

7

0,04

0,40

0,38

0,15

37,25

37,25

37,29

37,28

8

0,00

0,00

0,00

0,00

38,29

38,29

38,33

38,32

9

0,23

1,00

0,89

0,85

56,25

56,24

56,29

56,28

a. b.

c.

8.

Kemudian setelah terbentuk rule base dilakukan perbandingan performa terhadap kedua skenario uji coba. Hasil performa flow-time untuk kedua skenario ditunjukkan pada gambar 6.

Flow Time

Flow Time

60,00 Triangula r

40,00 20,00

Normal

b.

20

c.

0,00 0

10 State Vectors Ke-

Saran

Saran untuk pengembangan lebih lanjut dari tugas akhir ini antara lain : a.

80,00

Fuzzy rule base dapat diimplementasikan untuk kasus job-shop. Penggunaan distribusi yang berbeda, yaitu TRIANGULAR dan NORMAL untuk waktu proses suatu entitas pada workcenter mempengaruhi flow-time dari job-shop. Pada saat dilakukan uji coba, rule yang menunjuk control vector 1 yaitu (0,-1) sebagai control vector untuk suatu subspace lebih dominan dibandingkan dengan control vector lainnya. Ini menunjukkan bahwa untuk jobshop dengan karakteristik seperti yang diujicobakan, NPT lebih banyak digunakan dibandingkan dengan penggunaan kombinasi antara NUNQ-NPT yang diwakilkan oleh control vector lainnya.

Penggunaan simulasi bu1.kan hanya untuk dasar dalam pembangkitan bilangan acak, tetapi benar-benar dilakukan untuk menilai performa dari control vector. Dengan demikian, penghitungan prioritas juga dapat langsung dilakukan dengan simulasi tanpa harus dihitung berdasarkan bilangan acak yang dibangkitkan. Gunakan kombinasi control vector selain control vector yang digunakan pada tugas akhir ini. Untuk kriteria performa selain flow-time dapat digunakan dispatching rules yang lain selain NUNQ dan NPT.

Gambar 6. Perbandingan Flow Time 9. Gambar 5.3 menunjukkan perbedaan flowtime pada job-shop pada skenario 1 dan skenario 2. Garis berwarna biru menunjukkan flow-time pada skenario 1 sedangkan garis berwarna biru menunjukkan flow-time pada skenario 2. Flow-time pada skenario 1 lebih rendah daripada skenario 2. Hal ini berarti, bahwa lamanya suatu job berada di dalam sistem, lebih sedikit atau lebih cepat jika dibandingkan dengan skenario 1. Atau dengan kata lain, implementasi fuzzy rule base untuk job-shop menghasilkan performa yang lebih baik pada distribusi TRIANGULAR(0.9,1,1.1) dibandingkan dengan pada distrubusi NORMAL (1,0.001). 7.

Daftar Pustaka

[1] Key K. Lee. Agustus, 2008. Fuzzy Rule Generation for Adaptive Scheduling in a Dynamic Manufacturing Environment. [2] Gamma. Algoritma Penjadwalan Produksi Pada Lingkungan Mesin Job Shop Dengan Minimalisasi Rataan Waktu Tunggu. [3] Eva Yustvita Rahmayani. 2008. Sistem Inferensi Fuzzy Untuk Menentukan Tingkat Risiko Penyakit Geriatri. [4] Institut Teknologi Bandung. 2008. Penjadwalan Produksi Flow-Shop dan JobShop. [5] http://www.ai.indra-ehm.net/ . Diakses pada 22 Maret 2010

Kesimpulan

8