BAB II KAJIAN TERKAIT 2.1 Job Shop Scheduling Definisi formal formal job shop scheduling adalah sebagai berikut: Job set J = { j1 , j2 , ... jn } Machine set M = {m1 , m2 , ... mm } Operations O = {o1 , o2 , ... on } Oi = {oi1 , oi 2 ,...o im } Tiap operation punya processing time {τ i1 , τ i 2 ,...τ imi } Untuk tiap O terdefinisi A, yaitu relasi biner urutan antar operasi. Jika (v, w) ∈ A
maka v harus dikerjakan sebelum w Objektif utama dari algoritma yang digunakan pada job shop scheduling ini adalah menghasilkan jadwal (schedule) yang meminimasi waktu (makespan) yang dibutuhkan untuk menyelesaikan semua job yang ada dengan memanfaatkan machine yang tersedia [BRU06].
Contoh hasil penjadwalan dapat dilihat pada Gambar II-1. Bagian baris menyatakan mesin yang bekerja (M1, M2, M3). Sedangkan bagian kolom menyatakan pekerjaan (J1, J2, J3) yang diproses di dalam mesin tersebut pada tiap waktu. J1 J2 J3
M1
M2
M3
M4
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
Gambar II-1 Contoh visualisasi hasil penjadwalan job shop
II-1
25
26
27
28
II-2
Metode yang digunakan dalam penyelesaian job shop scheduling: 1. Formula matematika Metode ini dapat menghasilkan solusi penjadwalan yang optimal dengan cara menghitung makespan dari semua kemungkinan yang ada (brute force) dengan menurunkan pertidaksamaan dari kasus job shop scheduling. Metode ini hanya dapat digunakan untuk kasus berskala kecil karena sebagian besar masalah job shop scheduling bersifat NP (non polynomial) –hard [PIN94], artinya solusi dari permasalahan ini membutuhkan waktu komputasi yang meningkat secara nonpolynomial bersama dengan peningkatan skala masalah. Hal ini menimbulkan kebutuhan sumber daya komputasi yang besar jika metode ini diterapkan pada kasus job shop scheduling. Contoh metode : integer programming, mixed-integer programming dan dynamic programming. Contoh pencarian solusi job shop dengan integer programming:
Kasus 3 job dan 4 mesin. Memiliki 3 jenis produk : A, B dan C. Dengan spesifikasi sebagai berikut : (machine / process time) Produk A:
1 / a1 3 / a3 4 / a4
Produk B:
1 / b1 2 / b2 4 / b4
Produk C:
2 / c2 3 / c3
Spesifikasi tambahan : produk B harus selesai dalam waktu kurang dari d jam dari waktu mulai. Tentukan urutan pengerjaan untuk menghasilkan waktu penyelesaian (makespan) paling minimum.
Penyelesaian: xA1 = start time produk A pada mesin 1 xA3 = start time produk A pada mesin 3 xA4 = start time produk A pada mesin 4 xB1 = start time produk B pada mesin 1 xB2 = start time produk B pada mesin 2 xB4 = start time produk B pada mesin 4
II-3
xC2 = start time produk C pada mesin 2 xC3 = start time produk C pada mesin 3
Pertidaksamaan yang dapat diekstraksi dari masalah : Technological
A) xA1 + a1 <= xA3
Route
xA3 + a3 <= xA4 B) xB1 + b1 <= xB2 xB2 + b2 <= xB4 C) xC2 + c2 <= xC3
One product
1) xA1 + a1 <= xB1 or xB1 + b1 <= xA1
Machine at
xA1 + a1 – xB1 <= My1
a time
xB1 + b1 – xA1 <= M(1-y1)
where y1 = 0 or 1
2) xB2 + b2 – xC2 <= My2 xC2 + c2 – xB2 <= M(1-y2) 3) xA3 + a3 – xC3 <= My3 xC3 + c3 – xA3 <= M(1-y3) 4) xA4 + a4 – xB4 <= My4 xB4 + b4 – xA4 <= M(1-y4) B finished by d
xB4 + b4 <= d
All jobs completed
z >= xA4 + a4 z >= xB4 + b4 z >= xC3 + c3
Objective:
Min z
Dengan mencari nilai dari variabel - variabel (xA1, xA3, xA4, xB1, xB2, xB4, xC2, xC3) yang meminimumkan z, maka akan didapat urutan pengerjaan yang paling
optimal. 2. Branch and Bound Merepresentasikan semua sequence yang mungkin dari proses job shop scheduling dalam bentuk pohon dengan bobot untuk tiap cabang (dihitung dengan fungsi tertentu). Kemudian penelusuran (branching) dilakukan untuk mencari sequence yang memberikan bobot yang optimal. Cabang yang tidak memberikan hasil yang lebih baik tidak akan dilanjutkan penelusurannya (bounded). 3. Metode aproksimasi a) Artificial intelligence
II-4
Constraint satisfaction approach : mengurangi kemungkinan solusi yang harus ditelusuri dengan memberikan berbagai batasan (constraints) hasil analisis untuk mengarahkan penelusuran ke arah yang optimal. Contoh : constraint propagation, backtracking, variable heuristic, value heuristic Neural networks : menggunakan model jaringan saraf (node & layer) dengan pembobotan untuk merepresentasikan solusi yang ada dan menelusurinya. Contoh : Hopfield networks, back-error propagation networks b) Local search methods Mencari solusi terbaik dengan menelusuri konfigurasi (kumpulan solusi) yang ada. Pada setiap transisi antar konfigurasi, dihitung cost yang dihasilkan dari fungsi tertentu. Transisi dapat dilakukan ke tetangga (neighbour) dengan beberapa alternatif cara : memilih tetangga dengan cost transisi terkecil, memilih tetangga yang terbaik dari seluruh tetangga atau memilih tetangga terbaik dari beberapa tetangga (sample) c) Priority dispatch rules Aturan (rule) untuk memilih operasi yang akan dikerjakan pada tiap tahap pada mesin. PDR adalah metode yang banyak diterapkan di kasus-kasus dunia nyata karena sangat mudah diterapkan dan memberi hasil yang cukup memuaskan. Contoh PDR adalah : • Earliest Due Date : waktu operasi total tersingkat (Σ Ot0..i) • Shortest Processing Time: waktu proses tersingkat (Oti ) • Minimum Slack Time: waktu sisa tersingkat (Σ Ot0..i - Oti) Contoh: Job = {J1, J2} Machine = {M1,M2,M3} J1.O = {1,3,2}
J1.Ot = {5,10,12}DD = 27 PT = 5 ST = 22
J2.O = {1,2}
J2.Ot = {11,2}
DD = 13 PT = 11 ST = 2
J3.O = {1,3}
J3.Ot = {5,30}
DD = 5 PT = 35 ST = 30
Pilihan job yang dibuat oleh mesin m1 (di awal proses) : Dengan EDD: J3 karena DD tercepat adalah J3. Dengan SPT: J1 karena PT terpendek adalah J1.
II-5
Dengan MST: J2 karena ST terminimum adalah J2.
Dalam tugas akhir ini, metode yang digunakan adalah PDR karena metode ini sederhana, bersifat real-time dan memberikan hasil yang baik [HOR06].
2.2 Sistem Multiagent Sistem multiagent adalah sistem yang terdiri dari agen-agen otonom yang memiliki kemampuan yang terbatas dan beroperasi dengan pengetahuan sendiri tetapi mampu menghasilkan perilaku global yang sesuai dengan kebutuhan [VID07]. Agen-agen yang ada saling berkomunikasi dengan menggunakan high level languages.
Latar belakang munculnya pendekatan sistem multiagen (sebelumnya dikenal dengan distributed agent) adalah perkembangan model sistem komputasi dan pemrosesan yang bergerak ke arah sistem terdistribusi (dihubungkan dengan jaringan) yang bersifat realtime. Oleh karena itu, agen cerdas (intelligent agents) dituntut untuk bersifat adaptif terhadap perubahan lingkungan yang dinamis [LES95].
Sistem multiagent dipelajari dalam salah satu subdisiplin Artificiall Intelligence, yaitu Distributed Artificiall Intelligence (DAI). DAI adalah studi, konstruksi dan aplikasi dari sistem multiagen (multiagent systems) yaitu, sistem di mana beberapa agen cerdas (intelligent agents) yang saling berinteraksi untuk mencapai kumpulan tujuan (set of goals) atau menyelesaikan kumpulan tugas (set of tasks) [GER99].
Dua alasan utama perkembangan dari sistem multiagent adalah [GER99] : 1. Sistem multiagent memiliki peran yang penting pada perkembangan ilmu komputer dan penerapannya. Karakteristik sistem komputer yang berkembang saat ini adalah terdistribusi (distributed), besar (large), terbuka (open) dan heterogen (heterogenous). Untuk memenuhi itu, komputer harus bertindak lebih dari sekedar “bagian (parts)” dari sistem, melainkan “individu” atau agen dari sistem, yaitu subsistem yang bersifat otonom (dapat menjadi sistem tersendiri) dan memiliki kemampuan lebih dari pada sekedar bagian (parts).
II-6
2. Sistem multiagent memiliki kapasitas untuk berperan dalam pembangunan dan analisis model dan teori interaksi antar manusia dalam satu masyarakat. Banyak bagian dari proses interaksi manusia yang masih sedikit dipahami oleh ilmu pengetahuan. Dengan DAI, dasar aspek sosiologis dan psikologis dari interaksi antar manusia dapat dieksplorasi lebih jauh. Objek studi utama dari sistem multiagent adalah “interacting, intelligent agent” [GER99]: i. Agent : otonom, mampu menerima informasi dari lingkungan melalui sensor dan mempengaruhi lingkungan melalui afektor. ii. Intelligent: memiliki dan mengejar suatu tujuan. Melakukan tugas dengan optimal berdasarkan ukuran performansi tertentu (performance measure). Aspek inteligensia agen mencakup problem solving, planning, search, decision making dan learning. Dalam bidang computer science, intelligent berarti kemampuan untuk menyimpan, menggunakan (reasoning) dan menambah (learning) pengetahuan. iii. Interacting : dapat dipengaruhi oleh agen lain (konsekuensinya, dapat mempengaruhi agen lain) dalam mencapai tujuannya. Fokus interaksi pada DAI adalah koordinasi, yaitu mencapai atau menghindari kondisi yang diinginkan atau tidak diinginkan oleh salah satu atau sebagian agen dalam sistem.
2.3 Case-Based Reasoning Case-based reasoning (CBR) [AAM94] adalah sebuah paradigma problem solving yang memanfaatkan pengetahuan spesifik yang disimpan sebelumnya dalam bentuk kasus (case) yaitu situasi problem konkrit. CBR mencari solusi dari suatu kasus dalam domain masalah tertentu dengan mencari kasus sebelumnya (past case) yang mirip dengan kasus yang ingin diselesaikan (current case), kemudian menggunakan solusi dari past case tersebut sebagai solusi dari current case. CBR juga bersifat incremental (dapat berkembang) karena dapat memperoleh pengetahuan baru dari kasus-kasus yang berhasil diselesaikan. CBR memiliki cara kerja yang berbeda dengan metode AI lainnya yang hanya mengandalkan pengetahuan umum dari domain masalah tertentu atau melakukan asosiasi dari relasi umum antara deskriptor masalah dan kesimpulannya.
II-7
CBR pada dasarnya adalah metode penyelesaian masalah baru dengan mengingat kondisi yang pernah dialami sebelumnya dan dengan menggunakan informasi dan pengetahuan yang berhubungan dengan kondisi itu. CBR memiliki paradigma similar problems have similar solutions (masalah yang mirip memiliki solusi yang mirip juga) [GAB06]. CBR dapat diilustrasikan dengan situasi problem solving berikut: 1) Dokter – ketika sedang mendiagnosa salah seorang pasiennya, seorang dokter teringat akan pasien lain yang ia rawat beberapa waktu sebelumnya. Dokter ini teringat akan pasien yang lain karena kemiripan gejala penyakit pasiennya (bukan oleh warna rambut pasiennya). Kemudian dokter itu menggunakan data hasil diagnosa dan perawatan pasien sebelumnya untuk menentukan diagnosa dan perawatan pasien di depannya. 2) Drilling Engineer – ketika seorang drilling engineer pernah mengalami dua situasi ledakan (blow out) dramatis sebelumnya, dengan cepat akan mengingat salah satu situasi ledakan tersebut (atau keduanya) ketika kombinasi pengukuran yang dihadapi sekarang cocok dengan kombinasi pengukuran sebelum terjadi ledakan di masa lalu. Sehingga ia dapat menghindari kesalahan yang sama. 3) Konsultan finansial – ketika menghadapi kasus pengajuan kredit suatu perusahaan yang sulit diselesaikan, keputusan dibuat dengan mengingat kasus kredit macet yang melibatkan perusahaan dengan alasan pengajuan kredit yang sama. Berdasarkan pengalaman tersebut, pengajuan kredit perusahaan yang sekarang, ditolak. Secara umum, siklus proses pada CBR ditunjukkan pada Gambar II-2 adalah sebagai berikut [AAM94] : 1. RETRIEVE the most similar case(s) : ambil kasus paling mirip 2. REUSE the case(s) to attempt to solve the problem : gunakan kasus tersebut untuk menyelesaikan kasus yang ada 3. REVISE the proposed solution if necessary: lakukan revisi pada solusi jika perlu 4. RETAIN the new solution as a part of a new case : simpan kembali solusi sebagai bagian dari kasus yang baru
II-8
Gambar II-2 Siklus CBR [AAM94]
2.4 Reinforcement Learning Reinforcement learning adalah salah satu teknik atau algoritma pembelajaran yang dilakukan dengan 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 [SCH07]. Tujuan akhir dari proses yang dilakukan agen dalam reinforcement learning adalah mempelajari control policy atau aturan (aksi-state) yang memberikan kinerja atau performansi global yang optimal (memaksimalkan reward).
Pendekatan yang digunakan untuk memodelkan pembelajaran adalah Markov Decision Process (MDP) [TOM97]. MDP merupakan tuple dengan empat elemen (A, S, r, p) dimana S dan A merupakan kondisi (state) dan aksi (action) yang mungkin.
II-9
Kemudian p(s,a,s’) = [0,1] fungsi probabilitas transisi dari kondisi s menuju kondisi s’ dengan melakukan aksi a. Sedangkan r(s,a) = R adalah fungsi yang mengembalikan nilai reward yang diperoleh dari penerapan aksi a pada kondisi s pada lingkungan (environment).
Dalam pencarian solusi optimal, agen harus
membedakan reward yang diperoleh dari pencapaian atas kondisi tertentu (successor state) dan reward yang diperoleh sebagai hasil dari melakukan sebuah aksi pada kondisi tertentu. Sehingga fungsi reward dibedakan menjadi dua, V(s) = R dan Q(s,a)= R.
Tetapi jika lingkungan permasalahan tidak bisa dimodelkan secara eksplisit (setiap kondisi atau state terdefinisi ) dan struktur pemberian reward untuk tiap kondisi tidak memungkinkan, maka Q-learning adalah metode terbaik. Assignment nilai Q adalah: Q(s,a):=(1-α)Q(s,a) + α(r(s,a)+max(Q(s’,b)) [TOM97]. Di mana b adalah
aksi terbaik yang diketahui agen untuk kondisi s’. r(s,a) adalah fungsi yang mengembalikan immediate reward . Untuk jumlah himpunan kondisi (state) dan aksi (action) yang terbatas (finite), fungsi Q ini bersifat konvergen menuju suatu fungsi optimal Q*(s,a). Karena Q*(s,a) konvergen, maka akan dapat dihasilkan policy optimal π*(s) = arg max Q*(s,a), yaitu urutan pasangan kondisi-aksi dengan nilai Q tertinggi.
