BAB I PENDAHULUAN 1.1 Latar Belakang
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). Misalnya diberikan n jumlah job (pekerjaan), i = 1, 2, 3 .. n dan sejumlah m mesin (machine) M1, M2, M3, .. Mm. Job I terdiri dari ni operasi Oi1, Oi2, .. Oini . Pekerjaan tersebut harus diproses dengan urutan tertentu. Setiap operasi Oij memiliki atribut waktu pemrosesan pij, yang berarti operasi Oij harus diproses di sebuah mesin selama pij. Objektif utama dari algoritma yang digunakan pada jobshop scheduling ini adalah menghasilkan penjadwalan kerja yang meminimasi waktu yang dibutuhkan untuk menyelesaikan semua job yang ada dengan memanfaatkan sumber daya (mesin) yang tersedia [BRU06].
Salah satu contoh permasalahan jobshop scheduling adalah proses pembuatan roti isi (sandwich). Misalkan ada 3 jenis sandwich berdasarkan isi roti nya : 1. Tipe I : keju – daging - mayonaise 2. Tipe II : mayonaise – daging - keju 3. Tipe III
: daging – keju - mayonaise
Untuk memproses sandwich tersedia tiga mesin yaitu mesin untuk meletakkan keju, daging dan mayonaise. Mesin keju membutuhkan waktu proses 10 detik, mesin daging membutuhkan waktu proses 8 detik dan mesin mayonaise membutuhkan waktu proses 12 detik. Tiap mesin hanya bisa memproses sebuah sandwich dalam satu waktu (tidak bisa diinterupsi). Jika ada banyak sandwich dengan jenis berbeda yang akan diproses, maka dibutuhkan penjadwalan urutan pengerjaan yang optimal agar waktu penyelesaian permasalahan yang dibutuhkan minimal.
I-1
I-2
Kebutuhan akan kemampuan sistem pemrosesan (processing power) dalam segala bidang kehidupan manusia terus meningkat. Keadaan ini mendorong manusia untuk meningkatkan kemampuan sistem pemrosesan yang ada dengan berbagai cara. Solusi yang pertama kali berkembang adalah dengan meningkatkan kemampuan (kapasitas, kecepatan, efisiensi energi .dll) unit utama dari sistem pemrosesan (processing unit) yang ada. Kelebihan dari solusi ini adalah tidak memerlukan usaha (effort) untuk koordinasi dan komunikasi. Dengan solusi ini, unit yang lama diganti dengan unit baru yang memiliki kemampuan proses lebih tinggi. Konsekuensi dari solusi ini adalah pemborosan karena unit yang lama tidak dapat digunakan lagi.
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.
Dalam tugas akhir ini, 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 [GER99]. 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.
Setiap agen menyimpan pengetahuan (yang didapat dari pengalaman) dan menggunakannya kembali menggunakan paradigma penalaran case-based reasoning. Pada case-based reasoning, pengetahuan (knowledge) tiap agen direpresentasikan
I-3
dalam bentuk kasus-solusi (case-solutions). Setiap agen memiliki, menyimpan dan memproses pengetahuannya masing-masing (distributed knowledge). Dengan paradigma ini, agen akan belajar untuk mengambil solusi yang tepat berdasarkan deskripsi kondisi (kasus) yang dihadapinya.
Setiap agen juga melakukan
pembelajaran
yang
untuk
menambah
pengetahuan
dimilikinya.
Algoritma
pembelajaran yang digunakan adalah reinforcement learning yaitu pembelajaran yang dilakukan dengan
berinteraksi dengan
lingkungan.
Pembelajaran dilakukan
berdasarkan konsekuensi yang diterima agen akibat aksi yang dilakukannya. Aksi yang diambil dapat berdasarkan pengetahuannya atau eksplorasi pilihan baru. Agen melakukan trial and error untuk mendapatkan jadwal memaksimalkan akumulasi reward tiap-tiap waktu.
1.2 Rumusan Masalah Rumusan masalah yang dibahas dalam tugas akhir adalah bagaimana menangani permasalahan
jobshop
scheduling
dalam
lingkungan
terdistribusi
dengan
memanfaatkan sistem multiagent yang dilengkapi kemampuan penalaran dengan case-based reasoning dan kemampuan belajar dengan reinforcement learning.
1.3 Tujuan Tujuan dari pembahasan yang dilakukan di dalam tugas akhir ini adalah membangun sistem multiagent yang melakukan penalaran (menggunakan case-based reasoning) dan pembelajaran (menggunakan reinforcement learning) untuk menghasilkan perilaku penjadwalan optimal dalam model permasalahan job shop scheduling.
1.4 Metodologi Tahapan yang dilalui dalam pelaksanaan tugas akhir ini adalah sebagai berikut : 1. Memahami konsep jobshop scheduling 2. Memahami
konsep
sistem
multiagent,
case-based
reinforcement learning 3. Analisis dan implementasi sistem multiagent i. Melakukan eksplorasi pada framework yang dibutuhkan
reasoning
dan
I-4
ii. Membuat aplikasi/software yang memodelkan implementasi sistem multiagent pada model masalah job shop scheduling 4. Evaluasi hasil implementasi i. Melakukan evaluasi dengan membandingkan hasil penjadwalan dari solusi yang tidak memanfaatkan penalaran dan pembelajaran ii. Pembuatan laporan hasil evaluasi
1.5 Sistematika Pembahasan BAB I PENDAHULUAN berisi tentang latar belakang dari topik tugas akhir ini, fokus atau rumusan masalah yang, tujuan yang akan dicapai dan metode yang akan digunakan untuk mencapai tujuan itu.
BAB II KAJIAN TERKAIT berisi tentang penjelasan permasalahan job shop scheduling secara umum, penjelasan konsep sistem multiagent,
penjelasan case-
based reasoning dan penjelasan konsep reinforcement learning.
BAB III ANALISIS berisi tentang penerapan teori yang dibahas dalam bab kajian terkait untuk menyelesaikan permasalahan job shop scheduling. Pembahasan yang dilakukan adalah representasi permasalahan job shop scheduling dan representasi agen-agen pada sistem multiagent. Berikutnya akan dibahas mengenai pengetahuan agen dan proses pembelajaran yang dilakukannya (dalam lingkup job shop scheduling). Bab ini diakhiri dengan pembahasan algoritma global dari program ini.
BAB IV PERANCANGAN DAN IMPLEMENTASI berisi tentang perancangan dan implementasi perangkat lunak (program simulasi) sebagai realisasi dari hasil analisis pada bab sebelumnya. Bagian perancangan menjelaskan kelas-kelas yang digunakan berikut atribut dan operasi (method) dari setiap kelas dalam bentuk diagram (berbasis UML) dan tabel-tabel. Bagian implementasi menjelaskan pengembangan dan penggunaan program (input, output dan tampilan).
I-5
BAB V PENGUJIAN berisi tentang spesifikasi dan hasil pengujian perangkat lunak untuk menyelesaikan kasus-kasus job shop scheduling dan analisis singkat dari hasil pengujian yang dilakukan.
BAB VI PENUTUP berisi tentang kesimpulan dan saran mengenai tugas akhir ini.
