IMPLEMENTASI SISTEM MULTIAGENT DENGAN CASE-BASED REASONING DAN REINFORCEMENT LEARNING UNTUK PENYELESAIAN JOB SHOP SCHEDULING PROBLEM

P3M STIE BANK BPD JATENG Prestasi Vol. 8 No. 2 - Desember 2011

ISSN 1411 - 1497

IMPLEMENTASI SISTEM MULTIAGENT DENGAN CASE-BASED REASONING DAN REINFORCEMENT LEARNING UNTUK PENYELESAIAN JOB SHOP SCHEDULING PROBLEM Oleh : Entot Suhartono STIE Bank BPD Jateng Abstrak Job shop scheduling adalah model permasalahan penjadwalan pekerjaan manufaktur yang bertujuan memperoleh total waktu pengerjaan (makespan) minimum. Permasalahan ini bersifat NPhard sehingga untuk tingkat kesulitan yang semakin tinggi, sangat sulit untuk menemukan solusi optimal dari sebuah kasus job shop scheduling. Solusi dari permasalahan job shop scheduling ini dapat ditemukan dengan menggunakan sebuah penjadwal (scheduler) dengan kemampuan komputasi tertentu. Perkembangan sistem komputasi dewasa ini bergerak ke arah komputasi terdistribusi sehingga sistem penjadwalan berkembang mengikutinya. Dalam penelitian ini, penulis membangun sistem multiagent untuk mengimplementasikan penjadwalan terdistribusi pada permasalahan job shop scheduling. Sistem multiagent ini memiliki kemampuan penalaran dan pembelajaran untuk dapat menentukan solusi terbaik untuk permasalahan yang berbeda secara otomatis. Sistem ini menggunakan case-based reasoning sebagai penalarannya dan reinforcement learning sebagai pembelajarannya. Setelah membangun dan menguji sistem multiagent dengan case-based reasoning dan reinforcement learning ini, penulis menyimpulkan bahwa sistem multiagent dapat menyelesaikan permasalahan job shop scheduling dan dapat belajar untuk menghasilkan solusi yang optimal untuk setiap kasus. Keyword : Multiagent, Case-Based Reasoning, Reinforcement Learning, Jobshop Scheduling Pendahuluan Job shop scheduling adalah model permasalahan yang bertujuan menghasilkan penjadwalan penggunaan sejumlah mesin dengan kemampuan proses tertentu untuk menyelesaikan pekerjaan yang terdiri dari sejumlah operasi (dengan waktu pemrosesan yang bervariasi untuk tiap operasi). Job-shop Scheduling Problem (JSP) merupakan suatu permasalahan untuk menentukan urutan operasi yang dilakukan dalam mesin yang ada dengan tujuan meminimumkan waktu proses total yang dibutuhkan. Tujuan utama dari algoritma yang digunakan pada jobshop scheduling ini adalah menghasilkan 105


ISSN 1411 - 1497

penjadwalan kerja yang meminimasi waktu yang dibutuhkan untuk menyelesaikan semua job yang ada dengan memanfaatkan sumber daya (mesin) yang tersedia (Peter Brucker, 2006). Solusi alternatif untuk meningkatkan kemampuan sistem pemrosesan tanpa perlu sering melakukan penggantian adalah dengan menggabungkan lebih dari satu unit pemrosesan. Konsep ini umumnya dikenal dengan sistem terdistribusi (distributed system). Jadi peningkatan kemampuan pemrosesan dilakukan dengan menambah jumlah unit pemrosesan dan menghubungkan unit-unit pemrosesan yang ada sebagai subsistem pemrosesan. Kelebihan utama dari solusi ini adalah skalabilitas dan adaptabilitas sistem yang tinggi. Hal ini disebabkan pendistribusian beban penjadwalan pada tiap-tiap mesin yang ada. Karena kelebihannya ini, sistem ini banyak diimplementasikan dan terus dikembangkan. Solusi yang diusulkan untuk membangun penjadwal (scheduler) untuk jobshop scheduling ini adalah sistem multiagent. Sistem multiagent adalah penerapan konsep sistem terdistribusi dengan agen-agen sebagai subsistemnya (Gerhard Weiss, 1999). Agar memperoleh perilaku sistem yang optimal, tiap agen menyimpan pengalaman yang diperolehnya, melakukan penalaran untuk menggunakan pengalaman yang disimpannya dan melakukan pembelajaran untuk mencari jadwal pemrosesan optimal bagi dirinya sendiri dengan juga mempertimbangkan mengenai pengaruhnya pada sistem secara keseluruhan. Rumusan masalah yang dibahas dalam penelitian ini adalah bagaimana menangani permasalahan jobshop scheduling dalam lingkungan terdistribusi dengan memanfaatkan sistem multiagen yang dilengkapi kemampuan penalaran dengan case-based reasoning dan kemampuan belajar dengan reinforcement learning. Tujuan dari pembahasan yang dilakukan di dalam penelitian ini adalah membangun sistem multiagen yang dapat melakukan penalaran (menggunakan case-based reasoning) dan pembelajaran (menggunakan reinforcement learning) untuk menghasilkan perilaku penjadwalan optimal dalam model permasalahan job shop scheduling. Tahapan yang dilalui dalam pelaksanaan penelitian ini adalah (1) memahami konsep jobshop scheduling; (2) memahami konsep sistem multiagent, case-based reasoning dan reinforcement learning; (3) analisis dan implementasi sistem multiagent dengan melakukan eksplorasi pada framework yang dibutuhkan, serta membuat aplikasi/software yang memodelkan implementasi sistem multiagent pada model masalah job shop scheduling; (4) evaluasi hasil implementasi, yaitu melakukan evaluasi dengan membandingkan hasil penjadwalan dari solusi yang tidak memanfaatkan penalaran dan pembelajaran. Landasan Teori Jobshop Definisi formal job shop scheduling (JS)adalah sebagai berikut: Job set

J = { j1, j2, …, jn}

Machine set

M = { m1, m2, …, mm}

106

P3M STIE BANK BPD JATENG Prestasi Vol. 8 No. 2 - Desember 2011 Operations

ISSN 1411 - 1497

O = { o1, o2, …, on}

Tiap operation punya processing time

O1 = { o11, o12, …, o1m} { 11, 12, …, 1m}

Untuk tiap O terdefinisi A, yaitu relasi biner urutan antar operasi. Jika (v, w)  A maka v harus dikerjakan sebelum W.

Tujuan utama dari algoritma yang digunakan pada JS ini adalah menghasilkan jadwal (schedule) yang meminimasi waktu (makespan) yang dibutuhkan untuk menyelesaikan semua job yang ada dengan memanfaatkan machine yang tersedia (Peter Brucker, 2006). Sistem Multi Agen Caglayan (1997) mendefinisikan agent adalah suatu entitas perangkat lunak komputer yang memungkinkan user (pengguna) untuk mendelegasikan tugas kepadanya secara mandiri (autonomously). Kemudian Brenner (1998) menambahkan bahwa agent harus bisa berjalan dalam kerangka lingkungan jaringan. Dalam perkembangan aplikasi dan penelitian tentang agent, bagaimanapun juga dalam suatu komunitas sebuah sistem tidak dapat dihindari akan dibutuhkannya lebih dari satu agent, seiring dengan semakin kompleksnya tugas yang dikerjakan oleh sistem tersebut. Diharapkan bahwa meskipun berbeda vendor dan pembuat, antara satu agent dan agent lain bisa tetap berkomunikasi dan berkoordinasi berhubungan dengan suatu pekerjaan. Paradigma pengembangan sistem dimana dalam suatu komunitas sistem terdapat beberapa agent, yang saling berinteraksi, bernegosiasi dan berkoordinasi satu sama lain dalam menjalankan pekerjaan, disebut dengan multi agent system (MAS). (Romi S. W., 2003). Case-Based Reasoning Secara singkat Case-Based reasoning (CBR) didefinisikan sebagai sebuah metodologi untuk penyelesaian masalah dengan memanfaatkan pengalaman sebelumnya [Mulyana and Hartati, 2009]. CBR merupakan sebuah paradigma utama dalam penalaran otomatis (automated reasoning) dan mesin pembelajaran (machine learning). Di dalam CBR, seseorang yang melakukan penalaran dapat menyelesaikan masalah baru dengan memperhatikan kesamaannya dengan satu atau beberapa penyelesaian dari permasalahan sebelumnya. Struktur sistem CBR dapat digambarkan sebagai kotak hitam seperti pada Gambar: 1, yang mencakup mekanisme penalaran dan aspek eksternal, meliputi :   

Spesifikasi masukan atau kasus dari suatu permasalahan Solusi yang diharapkan sebagi luaran Kasus-kasus sebelumnya yang tersimpan sebagai mekanisme penalaran.

107

referensi

pada


ISSN 1411 - 1497

Gambar 1 : Arsitektur sebuah sistem CBR [Main dkk, 2001] Secara singkat, tahap-tahap penyelesaian masalah berbasis CBR adalah sebagai berikut : [Mantaras dkk, 2006]     

Pengambilan kembali kasus-kasus yang sesuai dari memori (hal ini membutuhkan pemberian indeks terhadap kasus-kasus dengan menyesuaikan fitur-fiturnya). Pemilihan sekelompok kasus-kasus yang terbaik. Memilih atau menentukan penyelesaian. Evaluasi terhadap penyelesaian (hal ini dimaksudkan untuk meyakinkan agar tidak mengulang penyelesaian yang salah) Penyimpanan penyelesaian kasus terbaru dalam penyimpan kasus/memori.

Sesuai dengan tahap-tahap tersebut, Aamodt dan Plaza [Aamodt dan Plaza, 1994] menjelaskan sebuah CBR sebagai sebuah siklus yang disingkat 4 R yaitu, Retrieve, Reuse, Revise dan Retain seperti pada Gambar-2 berikut ini :

Gambar 2 : Siklus CBR [Aamodt dan Plaza, 1994] Tahapan proses dalam CBR Pada gambar diatas dijelaskan bahwa dalam proses PBK dibutuhkan empat (4) tahap, yaitu:  RETRIEVE adalah menemukan kembali kasus yang sama atau yang paling mirip dengan kasus baru  REUSE adalah menggunakan kembali informasi dan pengetahuan dari basis kasus untuk memecahkan masalah kasus baru (proses ini disebut “tansfer solusi”), 108


ISSN 1411 - 1497

 REVISE adalah merevisi atau memperbaiki solusi yang diusulkan.  RETAIN adalah menyimpan pengalaman untuk memecahkan masalah yang akan datang kedalam basis kasus. Reinforcement Learning Reinforcement Learning (RL) adalah salah satu tehnik atau algoritma pembelajaran yang berinteraksi dengan lingkungan. Agen yang menggunakan Reinforcement Learning belajar dari konsekuensi (berupa reward) tindakan (action) yang diambilnya pada suatu kondisi tertentu pada masa lampau dan eksplorasi aksi baru. Dengan kata lain, agen tersebut melakukan pembelajaran yang bersifat trial and error (Scholarpedia, 70). Reinforcement Learning merupakan salah satu paradigma baru dalam learning theory. Reinforcement Learning dibangun dari porses pemetaan (mapping) dari situasi yang ada di dalam lingkungan (states) ke bentuk aksi perilaku (behavior) agar dapat memaksimalkan reward. Agen yang bertindak sebagai learner tidak perlu diberitahukan behavior apakah yang akan sepatutnua dilakukan, atau dengan kata lain biarlah sang learner belajar sendiri dari pengalamannya. Ketika ia melakukan sesuatu yang benar berdasarkan rule yang telah ditentukan, maka ia akan mendapat reward, dan sebaliknya (A. Ridho, 2006). Tujuan akhir dari proses yang dilakukan agen dalam Reinforcement Learning adalah mempelajari control policy atau aturan yang memberikan kinerja atau performansi global yang optimal (memaksimalkan reward). Analisis Representasi job shop problem Penelitian ini mengacu pada definisi permasalahan job shop scheduling pada Operational Research (OR) Library (http://people.brunel.ac.uk/~mastjjb/ jeb/orlib/files/jobshop1.txt): Jumlah_job jumlah_mesin Job[0] <no_mesin1 waktu_operasi1> <no_mesin2 waktu_operasi2>... Job[1] <no_mesin1 waktu_operasi1> <no_mesin2 waktu_operasi2>... ... Job[jumlah_job] <no_mesin1 waktu_operasi1> <no_mesin2 waktu_operasi2>...

jumlah_job adalah jumlah job yang harus diselesaikan. jumlah_mesin adalah jumlah mesin yang tersedia untuk menyelesaikan seluruh job yang ada. Tiap job memiliki dua atribut, yaitu: a. no_mesin adalah mesin yang harus dilalui oleh job tersebut untuk dapat dinyatakan selesai. b. no_mesin adalah waktu operasi pada setiap mesin ke-no_mesin jumlah_mesin dan definisi tiap job harus konsisten. Jika di dalam urutan_mesin terdapat instan mesin yang indeks-nya berada di luar batas jumlah_mesin, maka masalah job shop scheduling tersebut tidak dapat dislesaikan. 109


ISSN 1411 - 1497

Untuk melakukan simulasi penyelesaian tiap job yang ada, maka dibuat sebuah struktur data untuk memuat informasi setiap job Job: . Mengacu pada contoh representasi permasalahan job shop scheduling di atas. Maka struktur data dari job pertama adalah Job[0] < {9 8 0 1 6 5 7 4 2 3}, {83 61 83 65 64 85 78 85 55 77}, > 0 Penghitung adalah nilai yang akan terus dimutakhirkan sesuai dengan lama proses yang telah dialami job tersebut (jadi diinisialisasi dengan 0). Representasi Agent Pendekatan sistem multiagen untuk menyelesaikan permasalahan job shop scheduling ini dilakukan dengan membuat agen, yaitu machine agent, untuk tiap mesin yang bertugas untuk mengambil keputusan (job atau operasi yang dipilih) pada tiap kondisi dan melakukan pembelajaran dari tiap keputusan yang diambil. Tugas dari machine agent hanyalah untuk mengambil keputusan dan melakukan pembelajaran, karena itu diperlukan sebuah agen lagi, yaitu control agent, yang berltugas mengatur seluruh proses pembuatan jadwal. Control agent bertugas untuk memulai dan menghentikan proses simulasi, melakukan simulasi pemberian daftar job ke setiap machine agent, melakukan pemutakhiran status tiap job dan status tiap machine agent saat simulasi dan mencatat semua aksi yang diambil seluruh machine agent disetiap waktu dalam sebuah jadwal. Representasi Pengetahuan Agent Representasi pengetahuan yang dimiliki oleh machine agent berupa sejumlah kasus Casebase = <state, solution>. Diagram ini representasi pengetahuan agen adalah sebagai berikut:

Gambar 3 : Diagram representasi pengetahuan agen Bagian state yang merupakan indentifier dari tiap kasus direpresentasikan oleh sistem yang digambarkan oleh status job dan mesin. Menurut (Riedmiller, 1999) keadaan sistem dapat dibedakan menjadi dua, yaitu: Keadaan sistem statik, yaitu spesifikasi awal dari sistem tersebut. Contoh: jumlah job, jumlah mesin, estimasi maskepan (dengan perhitungan) 2. Keadaan sistem dinamis, yaitu keadaan sistem yang berbeda dari waktu ke waktu. Keadaan sistem dinamis, menggambarkan progress sistem tersebut saat beroperasi. a. Kondisi job : due date setiap job, processing time job, slack time dari job. 1.

110

P3M STIE BANK BPD JATENG Prestasi Vol. 8 No. 2 - Desember 2011 b. c.

ISSN 1411 - 1497

Konsekuensi aksi : slack time rata-rata akibat penerapan aksi. Hubungan antara job/operasi : urutan operasi yang belum dilalui tiap job.

Pembelajaran Agen Pembelajaran dilakukan dengan reinforcement learning (metode Qlearning) dengan tujuan untuk menemukan policy, yaitu aksi (dispatching rule) yang paling tepat untuk tiap kondisi sistem secara global. Pada sistem multiagen, di mana terdapat banyak agen yang bekerja secara konkuren, maka aksi yang dipelajari oleh sistem sebenarnya adalah vektor dari aksi-aksi elementer tiap agen. Setiap agen memberikan kontribusi aksi untuk menghasilkan vektor aksi gabungan (join action vector). Jadi tujuan bersama dari tiap agen (tujuan dari pembelajaran sistem) adalah mencari joint policy yang merupakan pemetaan kondisi-aksi untuk setiap agen yang menghasilkan reward yang optimal (Gabel, 2006). Pada model permaslahan job shop scheduling ini, tujuan utama yang ingin dicapai adalah menghasilkan rangkaian cara pemilihan job yang tepat untuk tiap achine agent sehingga dapat dihasilkan jadwal kerja yang optimal. Jadwal kerja yang optimal dicapai dengan menghasilkan keterlambatan penyelesaian (tardiness) yang minimal untuk seluruh job. Implementasi penalaran case-based reasoning dan pembelajaran Reinforcement Learning, akan terbentuk suatu basis pengetahuan yang terdiri dari kumpulan case yang saling terhubung pada tiap agen. Bentuk basis pengetahuan yang terbentuk dapat diilustrasikan seperti pada Gambar 4 Ilustrasi basis pengetahuan yang terbentuk.

Gambar 4: Ilustrasi basis pengetahuan yang terbentuk

Algoritma Program Tiap agen (machine agent) mewakili tiap mesin yang bertugas untuk mengambil keputusan. Setiap mesin diberi nama/kode berupa : [0 …jumlah_mesin]. Sedangkan seluruh simulasi proses pembuatan jadwal 111


ISSN 1411 - 1497

dilakukan pada satu agen yaitu control agent. Adapun urutan kerja agen adalah sebagai berikut: 1. Control agent akan mengirimkan daftar job kepada setiap machine agent. 2. Machine agent akan memutuskan job yang dipilih berdasarkan pengetahuan yang dimilikinya dan mengirimkan keputusannya kepada control agent. 3. Control agent memutakhirkan jadwal dan status job dan machine agent dan kemudian kembali mengirimkan job kepada tiap machine agent. 4. Jika semua job sudah selesai diproses maka control agent akan menghentikan prosesnya (shutdown dirinya) dan semua machine agent. Setiap machine agent melakukan pembelajaran mesin dengan Reinforcement Learning. Tujuan pembelajaran ini adalah mencari policy atau aturan yang meminimumkan wakut total yang dibutuhkan untuk menyelesaikan seluruh job (meminimumlan waktu jadwal selesai). Algoritma program utam (main program) dijelaskan pada flowchart program pada Gambar 5, sedangkan pseudoces program dapat dilihat pada algoritma 1. 1. CB : list of cassebase <state,solution>; Ct : global time; Jumlah_mesin : jumlah machine agent; S : kondisi (state) S‟ : kondisi suksesor V : casebase 2. Repeat a. S := S‟; b. For machine agents (i…jumlah_mesin) do i. If CB = 0 or tidak ada kasus yang cukup dekat then Tambah case base dengan kondisi S dan solusi kosong; Reinisialisasi 2 kases terdekat dengan S ii. Cari V:= casebase terdekat (nearest neighbour) dari kondisi S dan CB; iii. Pilih aksi a[i]:= yang terbaik atau random; c. Terapkan joint-actions a:= {a[0], a[1],..,a[i]}; d. Berikan global reward ke semua agen; e. S‟:= kondisi suksesor akibat a; f. For machine agents (i..jumlah_mesin) do i. V‟:= casebase terdekat (nearest neighbour)dari kondisi S‟ pada CB; ii. Tentukan := 1/1 + V‟.solution.E[i].nilai_update; iii. Tentukan V.solution.E[i].nilai_Q := (1-)V.solution.E[i].nilai_Q + (r+V‟.solution.E[0].nilai_Q; iv. V.solution.E[i].nilai_update ++; 112


ISSN 1411 - 1497

v. urutkan E menaik berdasarkan nilai_Q; g. Until (semua job selesai dikerjakan) Algoritma 1 : Algoritma global program Start Control agent (CA) : Validasi masalah dan spesifikasi sistem Machine agent (MA): Load Knowledge

Deskripsi masalah job shop

Machine agent Case base

Kirim daftar job ke machine agent (MA) yang bersangkutan tidak

CA memeriksa apakah semua dafta job sudah terkirim?

ya tidak

CA: mengirim kondisi (state) sistem ke MA

MA memeriksa apakah daftar job kosong?

tidak

MA melakukan learning untuk memilih job dari daftar dan mengirimkan pilihan ke CA

CA : terima job pilihan dari semua machine agent tidak ya

CA : terapkan vektor aksi (kumpulan job pilihan). Generate reward dan kirimkan ke semua MA

ya

CA: apakah semua job pilihan telah diterima?

CA : apakah semua job sudah selesai dikerjakan?

CA : update jadwal dan kondisi sistem

ya

CA : Simpan case base. Cetak hasil jadwal

Schedule

Machine agent Case Base

END

Gambar 5: Flowchart program secara global cb adalah kumpulan case base dari tiap machine agent (tiap machine agent memiliki cb sendiri). Ct adalah global time, yang menjadi acuan waktu yang sama bagi seluruh elemen sistem. Sedangkan jumlah_mesin adalah jumlah mesin yang didefinisikan pada permasalahan job shop tersebut siklus CBR pada sistem ini adalah sebagai berikut: 1. Retain Untuk semua machine agent , ditambahkan case base dari kondisi (state) yang baru s jika CB machine agent kosong atau c tidak memiliki neighbour yang cukup dekat (dibatasi dengan nilai treshold yang dihitung dari rata-rata operation time seluruh job) pada CB. Ketika case 113


ISSN 1411 - 1497

baru dengan state s ditambahkan, maka dua case terdekat dengan case baru harus direinisialisasi karea setelah case baru ditambahkan, transisi dari kedua case tersebut akan berubah. 2. Retrieval dan Reuse Ambil V yaitu case base yang palinh dekat dengan kondisi s. Pilih aksi sebagai solusi elementer dari V. Aksi bisa dipilih secara acak (eksplorasi) atau dipilih aksi terbaik (eksploitasi, menggunakan aksi yang memiliki nilai Q terendah). Kedua kemungkinan pemilih aksi ini ditentukan dengan nilai probabilitas eksplorasi yang juga ditentukan oleh user. 3. Revise Aksi yang diperoleh dari setiap machine agent , yang memiliki daftar pekerjaan pada saat itu, digabungkan menjadi vektor aksi yang kemudian diterapkan pada sistem. Setelah menerima immediate reward dari hasil penerapan aksi tersebut, nilai immediate reward dikirim ke semua agen yng berkontribusi di dalam vektor aksi yang telah diterapkan. Setelah itu, kondisi (state) suksesor S‟ adalah kondisi sistem akibat dari penerapan vektor aksi pada sistem. Siklus dimulai dari retain karena pada awal sistem ini digunakan untuk memilih aksi, machine agent harus memiliki basis pengetahuan dulu (minimal satu case). Jika machine agent belum memiliki case sama di dalam basis pengetahuannya, maka machine agent tidak bisa memutuskan aksi yang akan digunakan.

Gambar 6: Diagram perancagan kelas program

114


ISSN 1411 - 1497

Perancangan Kelas Perancangan kelas program dapat dilihat pada Gambar 6. Kelas jsspui merupakan kelas yang hanya bertugas menghidupkan seluruh agen yang dibutuhkan sesuai dengan definisi permasakahan job shop scheduling yang diberikan oleh user. Kelas machineAgentBehaviour merupakan bagian dari kelas machineAgent sedangkan kelas controlAgentBehaviour merupakan bagian dari kelas controlAgent. Kelas dapat menggunakan atribut dan metode yang ada pada kelas machineAgent dan controlAgentBehaviour dpt menggunakan atribut dan metode yang ada pada kelas controlAgent. Implementasi Lingkungan implementasi yang digunakan pada penelitian adalah bahasa pemrograman Java dengan framework JADE. Bahasa pemrograman Java digunakan karena merupakan bahasa yang dapat menghasilkan program multiplatform. Selain itu, bahasa pemrograman Java juga menyediakan framework khusus untuk mengembangkan sistem multigane, yaitu JADE (Java Agent Development). Java SDK (SE Development Kit) yang digunakan adalah versi 1.7 dan IDE yang digunakan untuk membuat program adalah NetBeans 7.0 yang dijalankan pada sistem operasi Windows 7. Sintaks untuk menjalankan program job shop scheduling adalah sebagai berikut: java jsspui [path_dari_file_job_shop_input] [learning_exploration_rate][test_value]

Contoh: 1. C:\My Documents\NetBeansProjects\JSSP\build\classes>java jsspui D:\test1.text 2. C:\My Documents\NetBeansProjects\JSSP\build\classes>java jsspui D:\test1.text 5 3. C:\My Documents\NetBeansProjects\JSSP\build\classes>java jsspui D:\test1.text 5 1

Keterangan : 1. learning_exploration_rate Bernilai {0 … 10} 0 = tidak melakukan eksplorasi; 10 = terus melakukan eksplorasi: 2. test_value Nilai untuk mengeksekusi test agnet yang hanya menggunakan jenis DPR.0 = EDD agent, 1 = MS agent, 2 = SPT agent 3. Program harus dijalankan di folder di mana seluruh kelask JSSP berada Spesisifikasi file input yang digunakan untuk program yang dibuat penelitian ini adalah sebagai berikut : # JSS 115


ISSN 1411 - 1497

# 10 5 //[jumlah_job] [jumlah_mesin] #1 72 0 87 4 95 2 66 3 #4 3 3 35 0 48 2 39 1 #1 46 3 20 2 21 0 97 4 #0 59 3 19 4 46 1 34 2 #4 23 2 73 3 25 1 24 0 #3 28 0 45 4 5 1 78 2 #0 53 3 71 1 37 4 29 2 #4 12 2 87 3 33 1 55 0 #2 49 3 83 1 40 0 48 4 #2 65 3 17 0 90 4 27 1 //[mesin1] [optime1] [mesin2] [optime2] …

60 54 55 37 28 83 12 38 7 23 [mesinN] [optimeN]

Data yang diinput sesuai dengan spesifikasi file diketik dengan menggunakan program text editor Notepad++ seperti yang terlihat pada ilustrasi berikut ini (Gambar 7):

Gambar 7: Contoh file input Sepesifikasi file output, program akan menghasilkan 2 jenis output, yaitu: 1. Schedule.txt : dibagi menjadi dua bagian yaitu spesifikasi job yang diberikan dan hasil penjadwalan (Gambar 8). 1 0 2 1 4 7 3 - Baris pertama adalah id dari job - Baris kedua adalah urutan mesin (rute) yang harus dilalui job - Baris ketiga adalah waktu operasi job ditiap mesin. Pada contoh di atas: waktu operasi pada mesin 4 adalah 88, mesin 8 adalah 68 dan seterusnya. Total time = 34 Machine[0] 0 0 0 0 – 1 1 1 1 1 - - - - - - - - - - - - - - - - 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 - - - - - - - - - - - - Machine[1] - - - - – - - - - - 1 1 1 1 1 1 0 0 0 2 2 2 2 2 2 2 - - - - - - - - - - - - - - - - - - - - - - - - - - - - Machine[2] 1 1 1 1 1 0 0 0 0 0 0 0 2 2 2 2 2 - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

- Baris pertama adalah maskepan - Baris kedua dan seterusnya adalah tabel (baris dan kolom) jadwal pengerjaan yang dihasilkan sistem. Bagian baris (machine[1], machine[2], 116


ISSN 1411 - 1497

machine[1]) adalah mesin yang bekerja pada sistem. Sedangkan bagian kolom adalah waktu (t). Lambang „-„ berarti pada saat itu mesing sedang idle. Sedangkan lambang berupa angka tertentu adalah id dari job yang sedang diproses pada mesin tersebut.

Gambar 8: Contoh file output program schedule.txt 2. Case [n].txt : representasi pengetahuan dari tiap machine agent. Contoh file output case base dapat dilihat pada Gambar 9, adapun penjelasan dari bagian-bagian dalam file tersebut adalah: 10 0 0 0 1 2

11 15

2 0.6041666666666666 3 0.4166666666666667 0 0.0

- Baris pertama merupakan state dari case yaitu case[i].state - Baris kedua merupakan evaluation value dari tiap case[i].solution - Baris ketiga dan seterusnya adalah experience[i] = atau case[i].solution.E[j] = . Tuple E =

selalu terurut menaik berdasarkan Q

Gambar 9: Contoh file case base dari agen

117


ISSN 1411 - 1497

Pengujian Berdasarkan tujuan, pengujian program dilakukan menjadi dua, yaitu: a. Validitas hasil pendjawalan oleh sistem multiagent dengan Case-Based Reasoning dan Reinforcement Learning : menguji apakah sistem multiagent dapat menghasilkan jadwal yang valid atau dapat dilaksanakan. b. Optimalisasi hasil penjadwalan: menguji optimalitas hasil penjadwalan berdasarkan maskepan dengan membandingkan sistem multiagent lain yang tidak menggunakan learning dan reasoning. Pengujian dilakukan dengan mencoba kasus job shop scheduling yang dimasukkan dalam file-file input untuk program JSSP. Tahapan pengujian yang dilakukan untuk kedua jenis pengujian yang akan dilakukan adalah sebagai berikut: a. Validasi hasil penjadwalan oleh sistem multiagent - Menentukan dua kasus penjadwalan job shop sederhana (3 job 3 mesin dan 6 job 6 mesin) - Melakukan simulasi job shop scheduling menggunakan program yang sudah dibuat untuk memperoleh jadwal (urutan pengerjaan) - Melakukan analisis pada hasil keluaran program (jadwal) b. Optimalitas hasil penjadwalan - Memilih tiga sistem multiagent lain (yang tidak menggunakan reasoning dan learning) sebagai pembanding - Memilih 10 jenis kasus penjadwalan (6 job 6 mesin, 10 job 10 mesin, 15 job 5 mesin, 15 job 15 mesin, 20 job 5 mesin, 20 job 10 mesin, 20 job 15 mesin, 20 job 20 mesin, 30 job 10 mesin, 50 job 10 mesin). Untuk setiap jenis digunakan tiga kasus yang berbeda sehingga total kasus yang diuji 30 buah kasus. - Melakukan simulasi berulang untuk setiap kasus dan mencatat makespan paling baik (minimum) yang dapat dihasilkan oleh sistem. Sistem multiagent tanpa reasoning dan learning menghasilkan makespan yang sama setiap iterasi (perulangan). Makespan yang dihasilkan sistem multiagent dengan reasoning dan learning akan terus berubah seiring dengan pembelajaran yang dilakukan. - Melakukan anilisis terhadap rata-rata makespan yang dihasilkan setiap sistem untuk setiap jenis kasus (berdasarkan 10 jenis kasus yang diuji) Validasi Hasil pendjadwalan oleh Sistem Multiagent Hasil pengujian dari program JSSP diawali dengan validasi hasil penjadwalan oleh sistem multiagent adalah sebagai berikut (lihat hasil penjadwalan kasus 1 pada tabel 1):

118


ISSN 1411 - 1497

Kasus I : 3 job 3 mesin (3x3.txt) # JSS #3 3 #0 4 2 7 1 3 #2 5 0 5 1 6 #2 5 1 6 0 9

Hasil penjadwalan kasus 1 menunjukkan bahwa program dapat menghasilkan penjadwalan yang valid, dimana: - Setiap t, hanya ada sebuah job yang diproses di sebuah mesin. Untuk setiap t, tidak ada mesin yang mengerjakan job yang sama. - Job0 : operasi1 dikerjakan pada t=0 s.d t=3, operasi2 dikerjakan pada t=10 s.d t=16 dan operasi3 dikerjakan pada t=22 s.d t=24 Job1 : operasi1 dikerjakan pada t=0 s.d t=4, operasi2 dikerjakan pada t=5 s.d t=9 dan operasi3 dikerjakan pada t=10 s.d t=15 Job2 : operasi1 dikerjakan pada t=5 s.d t=9, operasi2 dikerjakan pada t=16 s.d t=21 dan operasi3 dikerjakan pada t=22 s.d t=30 - Semua operasi pada setiap job telah dikerjakan Kasus II : 6 job 6 mesin (6x6.txt) # JSS #6 6 #2 1 0 3 1 6 3 7 5 3 4 6 # 1 8 2 5 4 10 5 10 0 10 3 4 #2 5 3 4 5 8 0 9 1 1 4 7 #1 5 0 5 2 5 3 3 4 8 5 9 #2 9 1 3 4 5 5 4 0 3 3 1 # 1 3 3 3 5 9 0 10 4 4 2 1 Hasil penjadwalan kasus 2(1) (tabel 2) dan kasus 2(2) (tabel 3) menunjukkan bahwa program dapat menghasilkan penjadwalan yang valid, dimana: - Setiap t, hanya ada sebuah job yang diproses di sebuah mesin. Untuk setiap t, tidak ada mesin yang mengerjakan job yang sama. - Job0 : operasi1 dikerjakan pada t=0 s.d t=3, operasi2 dikerjakan pada t=10 s.d t=16 dan operasi3 dikerjakan pada t=22 s.d t=24 Job1 : operasi1 dikerjakan pada t=0 s.d t=4, operasi2 dikerjakan pada t=5 s.d t=9 dan operasi3 dikerjakan pada t=10 s.d t=15 Job2 : operasi1 dikerjakan pada t=5 s.d t=9, operasi2 dikerjakan pada t=16 s.d t=21 dan operasi3 dikerjakan pada t=22 s.d t=30 - Semua operasi pada setiap job telah dikerjakan

119


ISSN 1411 - 1497

Tabel 1 Hasil penjadwalan kasus 1 Total time = 34 Time Machine[0] Machine[1] Machine[2]

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 0000–11111 – – – – – – – – – – – – 2 2 2 2 2 2 2 2 2 – –––––––––– 1 1 1 1 1 1 2 2 2 2 2 2 0 0 0 – – – – – – – 11111222220 0 0 0 0 0 0 – – – – – – – – – – – – – – –

Tabel 2 Hasil penjadwalan kasus 2(1) Total time = 70 Time Machine[0] Machine[1] Machine[2] Machine[3] Machine[4] Machine[5]

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 --------333 3 3 0 0 0 5 5 5 5 5 5 5 5 5 5 - 2 2 2 2 2 2 2 2 2 55533333111 1 1 1 1 1 4 4 4 0 0 0 0 0 0 - - - - - - - - - - 44444444402 2 2 2 2 3 3 3 3 3 1 1 1 1 1 - - - - - - - - - - ---555----- - - - - 2 2 2 2 - 3 3 3 - - 0 0 0 0 0 0 0 - - - ----------- - - - - - - - - 4 4 4 4 3 3 3 3 3 3 3 3 3 5 5 5 5 ------55555 5 5 5 5 - - - - 2 2 2 2 2 2 2 2 4 4 4 4 - 3 3 3 3

Tabel 3 Hasil penjadwalan kasus 2(2) Total time = 70 Time Machine[0] Machine[1] Machine[2] Machine[3] Machine[4] Machine[5]

36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 4 4 4 - - - - - - - - - - - - - - - - - 1 1 1 1 1 1 1 1 1 1 - - - - 2 - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 5 - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 4 - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 2 2 2 2 2 2 2 - - - - - - - - - - - - 3 3 3 3 3 0 0 0 - - 1 1 1 1 1 1 1 1 1 1 - - - - - - - - - - - - - - -

Optimalitas Hasil Penjadwalan Rata-rata makespan untuk setiap kasus dapat dilihat pada Tabel 4 Rata-rata makespan. Hasil pengujian tersebut dapat dilihat bahwa sistem multiagent dapat menghasilkan rata-rata makespan yang lebih kecil dibandingkan dengan ketiga sistem yang lainnya. Tabel 4: Rata-rata makespan EDD MS SPT Multi

6x6 76.3 73.3 81.67 69.67

10x10 1304.7 1355.7 1208 1110.7

15x15 2040.3 2108.3 1834 1726

15x5 110.67 1169.3 1007 967

20x5 1371 1420.7 1314.3 1258

20x10 1792.3 1875.3 1673 1587.3

20x15 1675.7 1586.3 1553.3 1350.7

20x20 2122.7 2125.3 2000.3 1792.3

30x10 2241 2340.7 2062 2010

50x10 2848.3 4077.3 3624 3518.7

Pada Tabel 4: Rata-rata makespan, dapat dilihat bahwa seiring dengan meningkatnya kompleksitas kasus (meningkatnya rata-rata makespan) selisih makespan daris sistem multiagent dan sistem yang lainnya juga semakin besar. Berdasarkan Tabel 4: Rata-rata makespan dapat dilihat bahwa pada kasus dengan mesin terbanyak, sistem multiagent yang menggunakan Case-Based Reasoning 120


ISSN 1411 - 1497

dan Reinforcement Learning menunjukkan hasil yang lebih signifikan dibandingkan dengan sistem multiagent tanpa reasoning dan learning. Kesimpulan Berdasarkan hasil analisis dan pengujian yang telah dilakukan, maka dapat dbuat kesimpulan adalah sebagai berikut: 1) Sistem multiagent dapat digunakan untuk menyelesaikan permasalahan job shop Scheduling; 2) Penalaran menggunakan case-based reasoning dan pembelajaran menggunakan reinforcement learning dapat mengekstraksi aturan (policy) penggunaan dispatch rules untuk tiap kasus job shop scheduling; 3) Sistem multiagent dengan kemampuan penalaran (reasoning) dan dengan kemampuan belajar (learning) memberikan hasil penjadwalan yang lebih baik dibanding dengan sistem multiagent lain yang hanya menggunakan satu dispatch rules (tanpa kemampuan reasoning dan learning); 4) Sistem multiagent memberikan hasil yang lebih signifikan untuk kasus yang lebih kompleks (terdiri dari banyak job dan banyak mesin). Daftar Pustaka Aamodt, Agnar, and Enric Plaza. AICom - Artificial Communications, IOS Press, Vol. 7: 1, pp. 39-59. 1994

Intelligence

Monfroy, Eric, 2001, Constraint Programming: Introduction, Universite de Nantes. Gabel, Thomas & Martin Riedmiller. Multi-agent Case-Based. 2006. Champandard, A.J., 2002, Reinforcement Learning: Plain and Simple, http://reinforcement learning.aidepot.com/Main.html, Sutton, R. S. and A. G. Barto, 1998, Reinforcement Learning : An ntroduction, London. MIT Press. M, Pinedo, Introduction to Scheduling – Algorithms, 1994. Johan K. W., Adrianto H. dan Marsolim, Perancangan Dan Implementasi Papan Jadwal Perkuliahan Berdasarkan Sistem Penjadwalan Otomatis, Jurnal Teknik Elektro - TESLA Vol. 8 No. 2, 75 – 95 (Oktober 2006) Mauridhi Hery P; Agus Kurniawan, Supervised Neural Networks dan Aplikasinya, Graha Ilmu, Yogyakarta, 2006. Horng, Horg-Chyi. Comparing Steady-state Performance of Dispatching Rulepairs in Open Shops. International Journal of Applied Science and Engineering. 2006. Lesser and Victor R, Multiagent Systems: An Emerging Subdiscipline of AI. Vidal, Jose. Fundamentals of Multiagent Systems. 2007 Gerhard Weiss, Multiagent Systems: A Modern Approach to Distributed Modern Approach to Artificial Intelligence. The MIT Press, 2007.

121


ISSN 1411 - 1497

Bayegan, Elisabeth, and Nytrø,Oystein, and Grimsmo, Anders, “Ontologies for Knowledge Representation in a Computer-Based Patient Record”, Journal from Department of Computer and Information Science Departmen. 2007. Sri Mulyana dan Sri Hartati, Tinjauan Singkat Perkembangan Case–Based Reasoning, ISSN: 1979-2328, Seminar Nasional Informatika UPN Yogyakarta, 2009, Main, J.; Dillon, T.S.; Shiu, S., A Tutorial on Case-Based Reasoning : Soft Computing in Case-Based Reasoning (Eds), Sprenger-Verlag, London, pp. 1-28. 2001. Mitchell, Tom M. Machine Learning. McGraw-Hill. 1997. Scholarpedia. http://www.scholarpedia.org/article/Reinforcement_learning. 2007. Riedmiller, Simone & Martin Riedmiller. A Neural Reinforcement Learning Approach to Learn Local Dispatching Policies in Production Scheduling. 1999.

122

IMPLEMENTASI SISTEM MULTIAGENT DENGAN CASE-BASED REASONING DAN REINFORCEMENT LEARNING UNTUK PENYELESAIAN JOB SHOP SCHEDULING PROBLEM

Recommend Documents