BAB II TINJAUAN PUSTAKA
2.1
Job Shop Scheduling Problem (JSSP) Job shop scheduling problem (JSSP) adalah permasalahan optimasi
kombinatorial. Misalkan terdapat π buah job atau pekerjaan, yaitu π½1 , π½2 , β¦ , π½π yang akan diproses pada π buah mesin, yaitu π1 , π2 , β¦ , ππ . Waktu yang diperlukan untuk operasi πππ (mengerjakan job π½π dengan menggunakan mesin ππ ) adalah π‘ππ . Setiap operasi diproses selama waktu tertentu dan oleh mesin tertentu. Setiap mesin hanya dapat menangani satu operasi, dan operasi dari pekerjaan yang sama tidak dapat diproses secara bersamaan. Tujuan dari job shop scheduling adalah bagaimana membuat jadwal yang berupa urutan pengerjaan yang optimal berdasarkan kriteria tertentu, misalkan untuk mendapatkan jadwal dengan makespan yang minimum. (Suyanto, 2010) Untuk job shop dengan π job dan π mesin, kemungkinan jadwal yang dapat dibuat sangat besar, yaitu sebanyak (π!)π buah kemungkinan. Tetapi, tidak semua kemungkinan jadwal tersebut layak digunakan atau valid. Sebuah jadwal akan dikatakan valid apabila urutan proses pengerjaan operasi-operasi dalam suatu job memenuhi routing yang ditetapkan, dan tidak ada tumpang tindih (overlap) waktu pengerjaan dari operasi-operasi yang dikerjakan pada mesin yang sama. (Suyanto, 2010)
5
6
Terdapat beberapa jenis penjadwalan job shop berdasarkan waktu kedatangan job di suatu tempat produksi, yaitu job shop statik dan job shop dinamik. Penjadwalan job shop statik merupakan model penjadwalan job shop yang paling sederhana. Pada model ini semua job diterima atau tiba di tempat produksi pada waktu yang sama. Misalkan terdapat 2 job, yaitu job 1 dan job 2 dengan 2 mesin, yaitu mesin 1 dan mesin 2. Masing-masing job memiliki urutan operasi dan waktu operasi dari mesin yang telah ditentukan. Job 1 diproses pada operasi 1 oleh mesin 2 dengan waktu 2 detik dan dilanjutkan operasi 2 oleh mesin 1 dengan waktu 3 detik. Job 2 diproses pada operasi 1 oleh mesin 1 dengan waktu 8 detik dan dilanjutkan operasi 2 oleh mesin 2 dengan waktu 5 detik. Tabel 2.1 Contoh model job shop statik ππ1 , ππ1
ππ2 , ππ2
Job 1
π2 ,2
π1 ,3
Job 2
π1 ,8
π2 ,5
Keterangan : ππ1
: Mesin operasi π1
ππ2
: Mesin operasi π2
ππ1
: Waktu operasi π1
ππ2
: Waktu operasi π2
Karena mesin yang beroperasi pada job 1 dan job 2 untuk operasi 1 berbeda, maka keduanya dapat beroperasi bersamaan. Selanjutnya pada operasi 2, job 1 diharuskan menunggu mesin 1 selesai beroperasi terlebih dahulu pada job 2,
7
sedangkan job 2 dapat langsung beroperasi pada mesin 2 ketika telah selesai beroperasi pada mesin 1. Untuk lebih jelasnya dapat dilihat pada Gambar 2.1 berikut.
Gambar 2.1 Ilustrasi model job shop statik Penjadwalan job shop dinamik merupakan pengembangan model statik. Pada model job shop dinamik waktu tiba pekerjaan di tempat produksi bervariasi. Jika waktu kedatangan job dapat diketahui sejak awal maka penjadwalan tersebut dinamakan job shop deterministik. Namun apabila waktu kedatangan yang job bervariasi dan tidak diketahui sebelumnya maka penjadwalan itu dinamakan job shop non β deterministik. Dengan demikian jadwal yang dibuat hanya melibatkan pekerjaan yang sudah diterima. Jika terdapat pekerjaan baru di tengah-tengah jadwal produksi, maka akan dilakukan penjadwalan ulang. (Saputro & Yento, 2004) Akan tetapi dalam penelitian ini hanya akan dibahas model job shop statik.
8
2.2
Formulasi masalah job shop statik Untuk permasalahan π job dan π mesin (π, π β π), solusinya diperoleh dari
urutan π Γ π proses. Masing-masing solusi diwakili oleh urutan semua operasi yang ada. Operasi yang dimaksud adalah operasi pertama sampai operasi keπ (π β€ π Γ π), π β π. Setiap proses diwakili oleh sepasang πππ dan πππ , π β {1,2, β¦ , π}. (Bouzidi & Riffi, 2014) Misalkan πΌπ β {π1 , π2 , β¦ , ππ (πβ€π Γ π) } dan π β {1,2, β¦ , π}, π β π. Bentuk solusi umum JSSP yang diperoleh dari urutan π Γ π proses dapat dilihat pada Gambar 2.2. πΌ1
πΌ2
β¦
πΌπ (πβ€π Γ π)
Gambar 2.2 Bentuk solusi umum JSSP Dalam membuat jadwal yang valid, langkah pertama yang harus dilakukan adalah data dari kasus JSSP dibuat ke dalam bentuk matriks informasi. Matriks informasi dibuat untuk mewakili informasi dari masing-masing operasi dan sebagai dasar dalam membuat penjadwalan yang memenuhi setiap batasan yang ada (valid). Matriks informasi memiliki π (π β€ π Γ π) kolom dan lima baris. Kolom mewakili jumlah total operasi yang ada pada seluruh job dan kelima baris yang dimaksud adalah : ππ
: nama atau nomor operasi di jadwal (π β {1,2, β¦ , π}, π β π).
π½ππ
: job dari operasi ππ .
πππππ : urutan dari operasi ππ dengan job yang sesuai.
9
πππ
: mesin dimana operasi ππ akan diproses.
πππ
: waktu proses dari operasi ππ . Bentuk matriks informasi dapat dilihat pada persamaan (2.1)
π1 π½π1 ππππ1 ππ1 (ππ1
π2 π½π2 ππππ2 ππ2 ππ2
β¦ β¦ β¦ β¦ β¦
ππ π½ππ πππππ πππ πππ
β¦ β¦ β¦ β¦ β¦
ππ (πβ€π Γ π) π½ππ (πβ€π Γ π) πππππ (πβ€π Γ π) πππ (πβ€π Γ π) πππ (πβ€π Γ π) )
(2.1)
Sebagai contoh permasalahan job shop scheduling dengan 2 job dan 2 mesin adalah model job shop statik yang sebelumnya telah dibahas, yaitu : π½1 = {(2,2), (1, 3)} π½2 = {(1, 8), (2,5)} π½1 adalah job pertama dengan urutan operasi diawali dengan operasi 1 pada mesin 2 dengan waktu 2 satuan waktu. Dilanjutkan ke operasi 2 pada mesin 1 dengan waku 3 satuan waktu. Sedankan π½2 adalah job kedua dengan urutan operasi diawali dengan operasi 1 pada mesin 1 dengan waktu 8 satuan waktu. Dilanjutkan ke operasi 2 pada mesin 2 dengan waku 5 satuan waktu. Sebagai langkah pertama yaitu menyatakan data ke dalam bentuk matriks informasi, seperti berikut : 1 1 1 2 (2
2 1 2 1 3
3 2 1 1 8
4 2 2 2 5)
10
Langkah kedua membuat solusi acak awal, solusi yang dihasilkan dapat berupa solusi yang valid atau tidak valid. Gambar 2.3 adalah contoh representasi solusi yang tidak valid. Dilihat dari matriks informasi, 4 dan 2 adalah operasi kedua dari π½1 dan π½2, sehingga 4 dan 2 tidak bisa mulai beroperasi sebelum 1 dan 3 selesai. Dengan demikian solusi jadwal dikatakan tidak valid, karena urutan operasi salah. 4
2
1
3
Gambar 2.3 Contoh representasi solusi Untuk dapat menghitung makespan, sebuah solusi harus valid. Solusi awal yang tidak valid diperbaiki sehingga menjadi valid, proses ini dinamakan proses koreksi. Untuk memperbaiki solusi acak yang tidak valid, digunakan matriks informasi dari kasus pada Gambar 2.4. Pertimbangkan βsolusi baruβ sebagai solusi yang valid dan βsolusi lamaβ sebagai solusi saat ini. Proses koreksi digambarkan sebagai berikut : 1.
Amati dan periksa βsolusi lamaβ prioritaskan operasi dengan urutan lebih awal dari operasi lainnya pada setiap job.
2.
Operasi yang tersedia ditambahkan ke solusi βsolusi baruβ dan dihapus dari solusi βsolusi lamaβ
3.
Ulangi 1 dan 2 sampai βsolusi lamaβ menjadi solusi βsolusi baruβ yang disusun valid.
Solusi yang valid dari Gambar 2.3 : 1
3
2
4
Gambar 2.4 Solusi baru yang valid
11
Hitung makespan dari solusi penjadwalan yang valid. Tujuannya untuk mendapatkan waktu operasi dengan makespan minimum. Makespan dari jadwal di Gambar 2.4 adalah 13, seperti yang diperlihatkan oleh GANT chart di Gambar 2.8, dimana ππ , π β {1,2} mewakili mesin dan masing-masing warna mewakili operasi dengan job yang sama. Langkah-langkah dalam membuat GANT chart dari solusi baru yang valid pada Gambar 2.4 dimulai dari operasi pertama, operasi ketiga, operasi kedua, dan operasi keempat sebagai berikut. Langkah pertama adalah penempatan operasi pertama, yaitu operasi 1 job 1 oleh mesin 2 dengan waktu 2 satuan waktu, prosesnya dapat dilhat pada Gant chart Gambar 2.5.
Gambar 2.5 Penempatan job 1 operasi 1 pada mesin 2 Langkah kedua dilakukan penempatan operasi ketiga yaitu operasi 1 job 2 oleh mesin 1 dengan waktu 8 satuan waktu.
Gambar 2.6 Penempatan job 2 operasi 1 pada mesin 1
12
Langkah ketiga dilanjutkan penempatan operasi kedua, yaitu operasi 2 job 1 oleh mesin 1 dengan waktu 3 satuan waktu. Operasi kedua dapat dimulai setelah operasi ketiga selesai beroperasi, seperti pada Gambar 2.9.
Gambar 2.7 Penempatan job 1 operasi 2 pada mesin 1 Langkah keempat penempatan operasi keempat, yaitu operasi 2 job 2 oleh mesin 2 dengan waktu 5 satuan waktu. Operasi keempat dapat langsung dimulai setelah operasi ketiga berakhir, keadaan ini disajikan dalam GANT chart Gambar 2.10.
Gambar 2.8 Penempatan job 2 operasi 2 pada mesin 2 Terdapat beberapa algoritma yang tergolong ke dalam algoritma metaheuristik untuk menyelesaikan kasus optimasi diantaranya Algoritma Genetika, Ant Colony Optimization (ACO), Particle Swarm Optimization (PSO), Bee Colony Optimization (BCO), dan Cat Swarm Optimization (CSO). Pada penelitian ini algoritma yang akan diterapkan dalam menyelesaikan kasus JSSP adalah algritma CSO.
13
2.3
Cat Swarm Optimization Cat Swarm Optimization (CSO) adalah algoritma yang diusulkan oleh Shu-
Chuan Chu dan Pei-Wei Tsai pada tahun 2006. CSO dihasilkan melalui pengamatan terhadap perilaku sekumpulan kucing dan terdiri dari dua sub-models yaitu : βseeking modeβ dan βtracing modeβ. (Chu & Tsai, 2007) Tahap pertama yang dilakukan pada proses CSO adalah menentukan berapa banyak kucing yang digunakan dalam iterasi, selanjutnya menggunakan kucing dalam CSO untuk menyelesaikan masalah. Setiap kucing memiliki posisi yang tersusun di dalam dimensi M, kecepatan untuk setiap dimensi, nilai fitness yang menunjukan penyesuaian kucing pada fungsi fitness dan bendera untuk menentukan kucing masuk berada dalam seeking mode atau tracing mode. Solusi akhir adalah satu kucing dengan posisi terbaik. CSO akan menyimpan solusi terbaik hingga akhir iterasi. (Chu & Tsai, 2007) a. Seeking Mode Mode ini menggambarkan keadaan kucing pada saat beristirahat, melihat kondisi sekitarnya mencari posisi berikutnya untuk bergerak. Seeking mode memiliki empat faktor penting yang harus diperhitungkan, yaitu : seeking memory pool (SMP), seeking range of the selected dimension (SRD), counts of dimension to change (CDC), dan self position considering (SPC). SMP digunakan untuk menentukan berapa banyak jumlah kucing tiruan yang akan dibuat, SRD atau mencari rentang dimensi terpilih, CDC menentukan dimensi yang akan berubah,
14
dan SPC mempertimbangkan apakah posisi saat ini menjadi salah satu kandidat. (Chu & Tsai, 2007) Langkah β langkah seeking mode dapat dideskripsikan dalam 5 tahap sebagai berikut (Chu & Tsai, 2007) : Langkah 1 : Bangkitkan π tiruan dari posisi kucing ke- π, dengan π = πππ. Jika nilai SPC benar, maka π = (πππ β 1), kemudian pertahankan posisi saat ini sebagai salah satu kandidat. Langkah 2 : Untuk setiap tiruan, disesuaikan dengan CDC, tambahkan atau kurangkan SRD persen dari nilai saat ini secara acak dan gantikan nilai yang sebelumnya. Langkah 3 : Hitung nilai fitness (FS) untuk semua titik kandidat. Langkah 4 : Jika semua nilai fitness tidak benar-benar sama, hitung probabilitas terpilih masing-masing titik kandidat dengan menggunakan persamaan (2.2), sebaliknya atur probabilitas terpilih untuk semua titik sama dengan 1. |πΉπβ βπΉππ |
πβ = πΉπ
πππ₯ βπΉππππ
, dimana 0 < β < π
(2.2)
Langkah 5 : secara acak pilih titik untuk bergerak dari titik-titik kandidat, dan pindahkan posisi kucing ke- π. Jika tujuan fungsi fitness adalah untuk menemukan solusi minimal, maka πΉππ = πΉππππ₯ , sebaliknya πΉππ = πΉππππ . (Chu & Tsai, 2007)
15
b. Tracing Mode Tracing mode adalah mode yang menggambarkan keadaan ketika kucing sedang mengikuti jejak targetnya. Sekali kucing memasuki tracing mode, kucing tersebut akan bergerak sesuai dengan kecepatannya untuk tiap dimensi. (Chu & Tsai, 2007) Tahapan tracing mode dapat dijabarkan dalam 3 langkah sebagai berikut (Chu & Tsai, 2007) : Langkah 1 : Perbarui nilai kecepatan untuk setiap dimensi (ππ,π ) dengan rumus πβ²π,π = ππ,π + π1 Γ π1 (ππππ π‘,π β ππ,π ), dimana d = 1,2,3,.., M
(2.3)
Langkah 2 : Periksa apakah kecepatan berada dalam rentang kecepatan maksimum. Jika kecepatan yang baru melebihi rentang, tetapkan nilai sama dengan batas. Langkah 3 : Perbarui posisi kucing ke- π dengan rumus πβ²π,π = ππ,π + πβ²π,π
(2.4)
ππππ π‘,π adalah posisi kucing yang memiliki nilai fitness terbaik, ππ,π adalah posisi kucing ke- π pada dimensi ke- π, π1 adalah konstanta dan π1 adalah nilai acak dalam rentang [0,1]. Seperti yang telah dibahas pada sebelumnya CSO terdiri dari dua sub model yaitu seeking mode dan tracing mode, untuk mengkombinasikan kedua mode dalam satu algoritma, perlu didefinisikan mixture ratio (MR). Dengan mengamati perilaku
16
kucing, dapat diketahui bahwa kucing menghabiskan sebagian besar waktunya untuk beristirahat. Selama beristirahat, kucing mengubah posisinya secara perlahan dan berhatihati, terkadang tetap pada posisi awalnya. Untuk menerapkan perilaku ini ke dalam CSO, digunakan seeking mode. Perilaku mengejar target diaplikasikan dalam tracing mode. Oleh karena itu, MR harus bernilai kecil untuk memastikan bahwa kucing menghabiskan sebagian besar waktu kucing dalam posisi seeking mode. (Chu & Tsai, 2007) Secara umum proses CSO dapat digambarkan dalam 6 langkah sebagai berikut (Chu & Tsai, 2007) : Langkah 1 : Bangkitkan π kucing dalam proses. Langkah 2 : Sebarkan kucing secara acak dalam ruang solusi berdimensi M dan pilih nilai dalam rentang kecepatan. Kemudian pilih sejumlah kucing secara sembarang dan masukkan dalam tracing mode sesuai MR, sisanya dimasukkan dalam seeking mode. Langkah 3 : Hitung nilai fitness (FS) masing-masing kucing dengan memasukkan nilai posisi kucing ke dalam fungsi fitness, yang menunjukkan kriteria tujuan, dan simpan kucing terbaik dalam memori. Perlu diingat bahwa yang perlu disimpan adalah posisi kucing terbaik (ππππ π‘ ) karena kucing terbaik sejauh ini mewakili solusi terbaik.
17
Langkah 4 : Pindahkan kucing sesuai benderanya. Jika kucing berada dalam seeking mode perlakukan sesuai proses seeking mode, sebaliknya perlakukan sesuai tracing mode. Proses masing-masing telah dijelaskan sebelumnya. Langkah 5 : Pilih lagi sejumlah kucing dan masukkan dalam tracing mode sesuai MR, sisanya masukkan ke dalam seeking mode. Langkah 6 : Perhatikan terminating condition-nya. Jika telah terpenuhi, hentikan program. Sebaliknya ulangi langkah 3 hingga 5.
18
Diagram proses algoritma Cat Swarm Optimization dapat dilihat pada Gambar 2.7
Gambar 2.9 Bagan Cat Swarm Optimization (sumber : Chu, 2006)
19
2.4
Inertia Weight (π) Parameter ini berguna untuk mengontrol keseimbangan antara kemampuan
eksplorasi global dan lokal, serta penurunan kecepatan untuk menghindari stagnasi pada optimum lokal. Jika nilai inertia weight terlalu besar akan mengakibatkan posisi kucing berubah terlalu jauh, sehingga gagal untuk menemukan solusi. Sebaliknya, jika nilai inertia weight terlalu kecil posisi kucing akan terjebak pada optimum lokal. (Suyanto, 2010) Untuk menyelesaikan permasalahan kucing yang menjauhi solusi dan terperangkap pada optimum lokal, CSO dimodifikasi dengan menambahkan parameter baru berupa nilai inertia weight (π€) yaitu, CSO dengan inertia. Pada nilai inertia weight (π€) berubah secara acak dalam tracing mode, sehingga kecepatan pada persamaan (2.3) menjadi : πβ²π,π = π€ Γ ππ,π + π1 Γ π1 (ππππ π‘,π β ππ,π ), dimana d = 1,2,3,.., M
(2.5)
