PENERAPAN CASE-BASED REASONING DAN REINFORCEMENT LEARNING PADA JOB SHOP SCHEDULING DENGAN SISTEM MULTIAGENT
LAPORAN TUGAS AKHIR
Disusun sebagai syarat kelulusan tingkat sarjana
oleh : Nama : Yohanes / NIM 13504158
PROGRAM STUDI TEKNIK INFORMATIKA SEKOLAH TEKNIK ELEKTRO DAN INFORMATIKA INSTITUT TEKNOLOGI BANDUNG 2008
Lembar Pengesahan Program Studi Sarjana Informatika PENERAPAN CASE-BASED REASONING DAN REINFORCEMENT LEARNING PADA JOB SHOP SCHEDULING DENGAN SISTEM MULTIAGENT
Tugas Akhir Program Studi Sarjana Informatika ITB
Oleh Nama : Yohanes/ NIM. 13504158
Telah disetujui dan disahkan sebagai laporan tugas akhir di Bandung, pada tanggal ……………….
Pembimbing
Nur Ulfa Maulidevi S.T., M.Sc. NIP. 999023503
ii
RINGKASAN Job shop scheduling adalah model permasalahan penjadwalan pekerjaan manufaktur yang bertujuan memperoleh total waktu pengerjaan (makespan) minimum. Model permasalahan ini dapat digunakan untuk memodelkan banyak permasalahan manufaktur di dunia nyata, seperti perakitan kendaraan, pembuatan alat elektronik dan produksi makanan .dll. Permasalahan ini bersifat NP-hard 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 (formula matematika, branch and bound atau aproksimasi). Tapi seiring dengan kebutuhan komputasi yang semakin besar, penggunaan sebuah penjadwal tidak lagi efisien. Perkembangan sistem komputasi dewasa ini bergerak ke arah komputasi terdistribusi sehingga penjadwal pun berkembang mengikutinya.
Dalam
tugas
akhir
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.
Kata kunci : sistem multiagent, penalaran (reasoning), pembelajaran (learning), job shop scheduling, case-based reasoning, reinforcement learning.
iii
KATA PENGANTAR Segala kemuliaan dan hormat bagi TUHAN, Raja Alam Semesta, di dalam Tuhan Yesus -- Penebus, Sahabat dan Gembala yang Agung. Hanya karena kemurahan-Nya, penulis bisa menyelesaikan tugas akhir ini. Tugas akhir ini dibuat untuk memenuhi persyaratan kuliah Sarjana S1 Teknik Informatika, STEI ITB dan untuk memberikan kontribusi dalam pengembangan inteligensia buatan, khususnya multiagent. Penulis mengharapkan banyak masukan dari semua pihak untuk menyempurnakan tugas akhir ini. Ucapan terimakasih juga penulis sampaikan kepada pihak-pihak yang lewat hidupnya Tuhan telah menunjukkan kemurahan-Nya selama pembuatan tugas akhir: 1.
Ayah ibu dan adik-adik dari penulis yang memberikan kasih yang tulus dan berlimpah-limpah
2.
Ibu Nur Ulfa Maulidevi, selaku dosen pembimbing yang telah menuntun penulis dalam pembuatan tugas akhir ini dengan penuh kebijaksanaan kasih dan kesabaran
3.
Ibu Masayu Leylia Khodra, Ibu Ayu Purwanti dan Bapak Rinaldi Munir. dosen penguji tugas akhir penulis, yang telah memberikan banyak masukan yang sangat berguna
4.
Ko Willy dan Ko Keefvin, pembimbing rohani penulis, untuk kasih, doa dan cucuran air mata yang membukakan tingkap-tingkap berkat di langit
5.
Danniel, Bastian, Humisar, Arnold, Anderson dan Royanto, anak-anak ku yang sah dalam iman, untuk dukungan dan pembentukan yang Tuhan kerjakan melalui kalian
6.
Rekan-rekan IF 2004 yang telah memberikan semangat dan dukungan selama empat tahun yang tak akan terlupakan di Teknik Informatika ITB
7.
Rekan-rekan di PMK dan Sion yang telah menjadi keluarga dan sahabat yang tidak tergantikan bagi penulis
8.
Dosen, staff dan karyawan Teknik Informatika STEI ITB yang melakukan pengabdian dan pekerjaan yang luar biasa yang memberkati penulis
9.
Semua pihak, yang namanya tidak dapat disebutkan satu per satu, yang secara langsung dan tidak langsung telah membantu penulis dalam menyelesaikan tugas akhir ini. iv
DAFTAR ISI
DAFTAR ISI............................................................................................................ v DAFTAR TABEL .................................................................................................. vii DAFTAR GAMBAR ............................................................................................ viii DAFTAR ALGORITMA ....................................................................................... ix DAFTAR ISTILAH ................................................................................................. x BAB I PENDAHULUAN ...................................................................................... I-1 1.1
Latar Belakang ........................................................................................... I-1
1.2
Rumusan Masalah ...................................................................................... I-3
1.3
Tujuan ........................................................................................................ I-3
1.4
Metodologi ................................................................................................. I-3
1.5
Sistematika Pembahasan ............................................................................. I-4
BAB II KAJIAN TERKAIT ............................................................................... II-1 2.1
Job Shop Scheduling.................................................................................. II-1
2.2
Sistem Multiagent...................................................................................... II-5
2.3
Case-Based Reasoning .............................................................................. II-6
2.4
Reinforcement Learning ............................................................................ II-8
BAB III ANALISIS ............................................................................................ III-1 3.1
Pendahuluan ............................................................................................ III-1
3.2
Representasi Job Shop Problem ............................................................... III-1
3.3
Representasi Agen ................................................................................... III-2
3.4
Representasi Pengetahuan Agen .............................................................. III-3
3.5
Pembelajaran Agen.................................................................................. III-6
3.6
Algoritma program .................................................................................. III-9
BAB IV PERANCANGAN DAN IMPLEMENTASI ...................................... IV-14 4.1
Pendahuluan .......................................................................................... IV-14
4.2
Perancangan Kelas ................................................................................ IV-14
4.3
Implementasi ......................................................................................... IV-23
IV.3.1
Lingkungan implementasi ............................................................ IV-23
IV.3.2
Implementasi kelas ...................................................................... IV-23 v
IV.3.3
Sintaks untuk menjalankan program............................................. IV-24
IV.3.4
Spesifikasi file input .................................................................... IV-25
IV.3.5
Spesifikasi file output .................................................................. IV-27
IV.3.6
Contoh penyelesaian kasus ........................................................... IV-30
BAB V PENGUJIAN ........................................................................................... V-1 5.1
Spesifikasi pengujian ................................................................................ V-1
5.2
Tahapan pengujian ................................................................................... V-2
5.3
Hasil pengujian......................................................................................... V-3
V.3.1
Validasi hasil penjadwalan oleh sistem multiagent ............................. V-3
V.3.2
Optimalitas hasil penjadwalan ............................................................ V-7
BAB VI PENUTUP ............................................................................................ VI-1 6.1
Kesimpulan ............................................................................................. VI-1
6.2
Saran ....................................................................................................... VI-1
DAFTAR REFERENSI .......................................................................................... xi LAMPIRAN A Contoh Penyelesaian Kasus ………………………………….... A-1
vi
DAFTAR TABEL
Tabel IV-1 Daftar Jenis Kelas............................................................................. IV-14 Tabel IV-2 Daftar Tanggung Jawab Kelas .......................................................... IV-15 Tabel IV-3 Kelas jsspui ...................................................................................... IV-19 Tabel IV-4 Kelas job .......................................................................................... IV-19 Tabel IV-5 Kelas Case ....................................................................................... IV-19 Tabel IV-6 Kelas schedule .................................................................................. IV-20 Tabel IV-7 Kelas controlAgent ........................................................................... IV-21 Tabel IV-8 Kelas controlAgentBehaviour ........................................................... IV-22 Tabel IV-9 Kelas machineAgent ......................................................................... IV-22 Tabel IV-10 Kelas machineAgentBehaviour ....................................................... IV-23 Tabel IV-11 Implementasi kelas ......................................................................... IV-24 Tabel IV-12 Daftar kelas bawaan dari framework ............................................... IV-24 Tabel V-1 Daftar file input pengujian .................................................................... V-1 Tabel V-2 Hasil penjadwalan kasus 1 .................................................................... V-6 Tabel V-3 Hasil penjadwalan kasus 2 (1)............................................................... V-6 Tabel V-4 Hasil penjadwalan kasus 2 (2)............................................................... V-6 Tabel V-5 Rata-rata makespan............................................................................... V-8
vii
DAFTAR GAMBAR
Gambar II-1 Contoh visualisasi hasil penjadwalan job shop.................................... II-1 Gambar II-2 Siklus CBR [AAM94] ........................................................................ II-8 Gambar III-1 Diagram representasi pengetahuan agen .......................................... III-3 Gambar III-2 Ilustrasi basis pengetahuan yang terbentuk ...................................... III-8 Gambar III-3 Flowchart global program ............................................................. III-11 Gambar IV-1 Diagram perancangan kelas program ............................................ IV-17 Gambar IV-2 Diagram sequence perancangan program ...................................... IV-18 Gambar IV-3 Diagram kelas implementasi program. .......................................... IV-26 Gambar IV-4 Contoh file input ........................................................................... IV-27 Gambar IV-5 Contoh file output program schedule.txt........................................ IV-28 Gambar IV-6 Contoh file case base dari agen ..................................................... IV-29 Gambar IV-7 Flowchart control agent (1) .......................................................... IV-31 Gambar IV-8 Flowchart control agent (2) .......................................................... IV-32 Gambar IV-9 Flowchart machine agent 0 (1) ..................................................... IV-33 Gambar IV-10 Flowchart machine agent 0 (2) ................................................... IV-34 Gambar IV-11 Flowchart machine agent 2 (1) ................................................... IV-35 Gambar IV-12 Flowchart machine agent 2 (2) ................................................... IV-36 Gambar IV-13 Flowchart control agent (skenario 2) .......................................... IV-37 Gambar IV-14 Flowchart machine agent 0 (skenario 2) ..................................... IV-38 Gambar IV-15 Flowchart machine agent 2 (skenario 2) ..................................... IV-39 Gambar V-1 Diagram rata-rata makespan .............................................................. V-7 Gambar A - 1 Flowchart control agent (3) ........................................................... A-1 Gambar A - 2 Flowchart control agent (4) ........................................................... A-2 Gambar A - 3 Flowchart control agent (5) ........................................................... A-2 Gambar A - 4 Flowchart machine agent 0 (3)....................................................... A-3 Gambar A - 5 Flowchart machine agent 1 (1)....................................................... A-3 Gambar A - 6 Flowchart machine agent 1 (2)....................................................... A-4 Gambar A - 7 Flowchart machine agent 1 (3)....................................................... A-4 Gambar A - 8 Flowchart machine agent 2 (3)....................................................... A-5
viii
DAFTAR ALGORITMA Algoritma III-1 Earliest Due Date ...................................................................... III-5 Algoritma III-2 Minimum Slack ........................................................................ III-5 Algoritma III-3 Shortest Processing Time .......................................................... III-5 Algoritma III-4 Difference antara state ............................................................... III-6 Algoritma III-5 Assignment nilai Q ................................................................... III-7 Algoritma III-6 Fungsi penghitung learning rate ............................................... III-7 Algoritma III-7 Fungsi penghitung reward......................................................... III-7 Algoritma III-8 Fungsi penghitung global reward .............................................. III-8 Algoritma III-9 Algoritma global program ....................................................... III-10
ix
DAFTAR ISTILAH No
Istilah
1
ACL
Arti Istilah Agent Communication Language. Merupakan format pesan yang digunakan agen JADE dalam berkomunikasi Program yang dapat menerima input dari lingkungan
2
Agent
menggunakan sensor dan memberikan aksi yang sesuai melalui efektor kepada lingkungannya
3
AID
Agent Identifier. Identitas unik untuk tiap agen JADE
4
Behaviour
Perilaku terdefinisi dari sebuah agen Pengalaman yang disimpan agen sebagai pengetahuan
5
Case
(knowledge). Terdiri dari pasangan permasalahan dan solusi (problem-solution)
6
Case Based
Paradgima penalaran basis pengetahuan yang berbentuk
Reasoning
case Aturan (rules) yang digunakan oleh tiap mesin untuk
7
Dispatching Rules
8
Due date
Batas waktu pengerjaan job yang ideal
9
Experience
Pengalaman dari agen yang disimpan kedalam case
menentukan job yang akan dikerjakan selanjutnya
FIPA adalah organisasi standarisasi dari IEEE Computer 10
FIPA
Society yang mempromosikan standar teknologi berbasis agen dan interoperabilitasnya dengan teknologi lain
11
JADE
Java Agent Development. Framework dari java untuk mengembangkan sistem berbasis multiagent Definisi pekerjaan pada kasus JSSP. Memiliki atribut rute
12
Job
mesin yang harus dilalui dan waktu proses pada setiap mesin Permasalahan penjadwalan dari sekumpulan job
13
Job shop scheduling
(pekerjaan) dengan urutan dan waktu operasi tertentu dan
problem (JSSP)
sekumpulan mesin untuk memproses kumpulan job tersebut x
No
Istilah
Arti Istilah Waktu total yang dibutuhkan untuk menyelesaikan
14
Makespan
permasalahan job shop (menyelesaikan semua job sesuai urutan mesin yang didefinisikan)
Operation time / 15
processing time / optime
Waktu proses yang dibutuhkan oleh sebuah job di sebuah mesin tertentu Pembelajaran mesin yang dilakukan dengan berinteraksi
16
Reinforcement
langsung dengan lingkungan. Pembelajaran dilakukan
Learning
dengan melakukan aksi dan menerima konsekuensi (reward) dari aksi yang dilakukannya Konsekuensi dari aksi yang dilakukan oleh agen yang
17
Reward
menggunakan reinforcement learning. Digunakan untuk memutakhirkan pengetahuan yang dimiliki agen tersebut Total sisa waktu proses yang harus ditempuh oleh sebuah
18
Slack time
job pada mesin-mesin tertentu sebelum job tersebut dinyatakan selesai
19
State
Kondisi dari sistem yang menjadi identitas unik dari setiap pengalaman yang disimpan dalam case
xi
