PENERAPAN ALGORITMA CODEQ UNTUK MENYELESAIKAN PERMASALAHAN JOB SHOP SCHEDULING Mohammad Bisyrul Jawwad, Yudha Prasetyawan, Budi Santosa Jurusan Teknik Industri Institut Teknologi Sepuluh Nopember (ITS) Surabaya Kampus ITS Sukolilo Surabaya 60111 Email:
[email protected] ;
[email protected] ;
[email protected] ABSTRAK Job shop scheduling merupakan suatu permasalahan dalam bidang penjadwalan, dimana setiap pekerjaan terdiri dari sejumlah operasi yang harus dilakukan di suatu mesin tertentu selama durasi waktu tertentu. Ketika suatu operasi akan diproses di suatu mesin, ada kemungkinan operasi tersebut mengantri terlebih dahulu karena mesin tersebut sedang dipakai oleh operasi lain. Permasalahan ini akan menjadi rumit ketika pekerjaan yang diselesaikan dalam jumlah yang cukup besar, untuk itu diperlukan metoda pencarian yang efektif. Dalam penelitian ini diusulkan algoritma CODEQ. CODEQ adalah suatu algoritma baru yang merupakan gabungan dari chaotic search, opposition-based learning, differential evolution, dan quantum mechanism. Algoritma yang diusulkan diimplementasikan pada 30 set problem yang ada dalam OR-Library. Hasil yang diperoleh menunjukkan bahwa algoritma yang diusulkan memberikan hasil makespan yang sama untuk kasus ukuran kecil (< 15 x 5), sedangkan untuk kasus ukuran besar (> 10 x 10)makespane yang dihasilkan lebih besar. Lebih jauh, algoritma ini akan membutuhkan waktu yang cukup lama dengan semakin banyaknya jumlah operasi Kata kunci: job shop scheduling, CODEQ, ABSTRACT Job shop scheduling is a problem in scheduling, where every job consist of a number of operation that must be done in a certain machine in some duration of time. When an operation will be performed in a machine, it is possible that queue will occure because that machine is being used by other operation. This problem will be difficult when there are so many jobs that must be finished, so it is needed to find an effective searching method. In this research given CODEQ algorithm as a suggestion. CODEQ is a new algorithm made from combination of chaotic search, opposition-based learning, differential evolution, dan quantum mechanism. The suggested algorithm is implemented at 30 set of problems in OR-Library. The result shows that the suggested algorithm give a same makespan result for small size case (< 15 x 5), otherwise the makespan result for big size case (> 10 x 10) is bigger. Furthermore, this algorithm is needed long enough time along with the number of operation. Key words: Job shop scheduling, CODEQ meminimumkan biaya produksi dan mampu mengurangi keterlambatan. Konsep penjadwalan job shop adalah menentukan waktu suatu operasi mulai dikerjakan dan mengalokasikan resource untuk mengerjakan operasi tersebut. Pada saat menjadwalkan suatu operasi selain menentukan kapan operasi tersebut mulai dikerjakan juga ditentukan resource mana yang dipakai. Oleh karena itu, pada saat menjadwalkan suatu operasi perlu
1. Pendahuluan Masalah penjadwalan job shop merupakan penjadwalan yang melibatkan suatu tugas pada seperangkat kerja pada stasiun-kerja (mesin) secara berurutan, saat mengoptimalkan satu atau lebih sasaran tanpa melanggar batasan yang ditetapkan (Guo et al, 2006) dalam (Ginting,2007) . Tujuan dari job shop adalah meminimumkan waktu proses total yang dibutuhkan untuk menyelesaikan pekerjaan, sehingga diharapkan mampu 1
diperhatikan dua constraint berikut(Gamma, 2006):
Dalam penyelesaian job shop scheduling sudah ada beberapa metoda atau pendekatan metaheuristik yang diajukan sebagai alternatif pemecahan masalah untuk mendapatkan waktu total produksi minimum, rata-rata waktu menyelesaikan pekerjaan, rata-rata waktu tunggu, rata-rata keterlambatan, mean machine utilization, dan yang lainnya. Beberapa diantaranya adalah dengan menggunakan tabu search (Betrianis dan Aryawan, 2003), genetic algorithm (Fachrudin ,2010), Hybrid Cross Entropy – Genetic Algorithm (Budiman,2010), Hybrid immune simulated annealing algorithm (zhang dan Wu, 2007), Ant Colony Optimization (Xing. et al, 2008) , dan lain-lain. Jika permasalahan job shop scheduling ini menggunakan exact optimization seperti integer programming, akan diperlukan waktu komputasi yang sangat lama terutama untuk problem berukuran besar (jika jumlah pekerjaan yang akan diselesaikan cukup banyak dan menggunakan mesin yang cukup banyak pula). Seiring dengan berkembangnya metoda optimasi ditemukan beberapa pendekatan baru dalam menyelesaikan permasalahan optimasi yaitu Harmony Search, Differential Evolution, Chaotic Search, Opposition Based Learning, dan metoda baru lain, beberapa peneliti berinovasi dengan menggabungkan beberapa metoda tersebut untuk mencari metoda optimasi baru yang lebih baik dan langkah inovasi tersebut disebut dengan Hybrid. Salah satu inovasi dari penggabungan metoda tersebut yaitu metoda CODEQ yang merupakan gabungan dari beberapa langkah metoda Chaotic search, Opposition – based leraning, Differential Evolution, dan Quatum mechanic (Omran and Salman, 2009). Algoritma CODEQ dipilih sebagai metode yang akan digunakan dalam penelitian ini karena performansi dari metoda CODEQ telah diteliti dan dibandingkan dengan pendekatan optimasi lain yaitu DE (Differential Evolution) dan PSO (Particle Swarm Optimization) menggunakan 11 fungsi, hasilnya menunjukkan bahwa metoda CODEQ memberikan hasil yang lebih baik dari kedua metoda tersebut, dan selain karena performansinya, CODEQ juga tidak membutuhkan parameter dari user seperti yang dibutuhkan pada metoda lain (Omran and Salman, 2009). Aplikasi dari metoda ini belum banyak ditemukan pada masalah optimasi kombinatorial untuk variabel diskrit
1. Precedence constraint; penjadwalan untuk setiap operasi dari job yang sama harus berurutan sesuai dengan Precedence constraint job tersebut. Sebagai contoh, masalah job shop yang ditunjukkan oleh gambar 2.1 memiliki beberapa Precedence constraint. Salah satunya adalah pada operasi O11, O12, O13, dan O15 yang berada pada pekerjaan yang sama yaitu J1. Oleh karena itu, operasi O15 harus dijadwalkan setelah operasi O11, O12, dan O13 selesai diproses. Namun, operasi O15 dan O22 berada pada pekerjaan yang berbeda, maka urutan penjadwalan kedua operasi ini tidak menjadi masalah.
Gambar 1.1: Precedence Constraint Job
2. Resource constraint; penjadwalan setiap operasi membutuhkan sebuah resource untuk mengerjakan operasi tersebut. Pada saat operasi ini mulai diproses resource tersebut harus sedang tidak dipakai operasi lain. Resource ini juga menjadi tidak dapat dipakai oleh operasi lain sampai operasi tersebut selesai. Jika penjadwalan suatu operasi melanggar salah satu constraint, maka penjadwalan operasi tersebut harus dialihkan waktunya, dimana pengalihan waktu ini bisa membuat proses penyelesaian pekerjaan dapat berlangsung lebih lama dan bahkan membuat proses mengalami keterlambatan. Permasalahan ini tidaklah menjadi rumit jika pekerjaan yang diselesaikan hanya sedikit, namun ketika ada sejumlah m machine (pekerjaan) (mesin) berbeda dan n job berbeda untuk dijadwalkan. Setiap pekerjaan terdiri dari sejumlah operasi yang harus dilakukan di suatu mesin tertentu selama durasi waktu tertentu. Ketika suatu operasi akan diproses di suatu mesin, ada kemungkinan operasi tersebut mengantri terlebih dahulu karena mesin tersebut sedang dipakai oleh operasi lain. 2
seperti permasalahan job shop scheduling. Salah satu penelitian yang dilakukan dengan metoda ini yaitu penelitian tentang aplikasi metoda CODEQ pada Capacited Vehicle Routing Problem (C-VRP). Pada penelitian sebelumnya sudah pernah dilakukan optimasi penjadwalan job shop dengan menggunakan Algoritma Defferential Evolution dengan merepresentasikan vektor permutasi sebagai urutan pekerjaan (Dini, 2009). Seperti dijelaskan pada paragraph sebelumnya bahwa metoda CODEQ ini merupakan pengembangan dari Defferential Evolution dan langkah kedua metoda ini pun tidak jauh berbeda, sehingga dari sini dijelaskan bahwa metoda CODEQ bisa digunakan untuk menyelesaikan permasalahan job shop scheduling. Diharapkan dari penelitian ini menjadi untuk menyelesaikan permasalahan job shop scheduling dengan waktu yang optimal.
awal (xi) selanjutnya individu tersebut diurutkan berdasarkan kegiatan pendahulu pada masing-masing pekerjaan kemudian dicari nilai total waktu operasinya dengan menggunkan tabel waktu. 3) Mutasi mencari vektor baru (mutan). Dengan cara memilih tiga individu(xi, xi1, xi2) secara random sebagai induk, dengan ketentuan xi ≠ xi1 ≠ xi2. Selanjutnya dicari nilai mutan (υi ) .
2. Metodologi Secara umum, langkah-langkah penerapan algoritma CODEQ untuk permasalahan Job Shop Scheduling hampir sama untuk permasalahan yang lain. Hanya saja perlu beberapa penyesuaian agar permasalahan yang ada pada set data bisa diolah menggunakan algoritma CODEQ, penyesuaian yang dimaksud adalah dengan memberikan indeks pada urutan masing-masing operasi, lebih lengkapnya sebagai berikut: 1) Input data Data yang digunakan meliputi data urutan operasi mesin dan data waktu masingmasing operasi . kedua data selanjutnya dipisah agar lebih mudah dalam pengolahan. Matriks data urutan pekerjaan akan diberikan indeks sebanyak jumlah operasi untuk semua mesin. Jadi bila ada 2 pekerjaan dan masing-masing pekerjaan mempunyai 3 operasi berbeda, maka indeks yang terbentuk sejumlah 2 x 3 = 6. 2) Inisialisasi Pada tahap ini dibangkitkan sampel awal secara random (bisa digunakan metoda lain yang lebih bagus). Pembangkitan pada penelitian ini dengan cara random permutasi sebanyak indeks yang sudah ditentukan pada tahap pertama. Dari sini akan diperoleh beberapa individu solusi
. Nilai u adalah bilangan yang dibangkitkan secara random pada rentang waktu 0 sampai satu. Selanjutnya mutan yang terbentuk diurutkan berdasarkan kegiatan pendahulu, lalu dihitung nilai waktu operasinya seperti pada tahap inisialisasi. 4) Crossover Membandingkan total nilai waktu operasi (makespan) mutan υi dengan total nilai waktu operasi (makespan) pada solusi awal xi , apabila nilai mutan lebih bagus maka individu mutan akan menggantikan individu awal, sebaliknya bila lebih jelek tetap menggunakan individu awal untuk proses selanjutnya. 5) Penentuan nilai W Menentukan nilai W sebagai perbandingan selanjutnya, nilai w ini bentuknya sama seperti individu awal dan mutan, yaitu berbentuk matriks urutan operasi yang diperoleh dengan cara: LB: Batas bawah permasalahan, yang dalam permasalahan ini adalah total waktu operasi pada individu yang paling kecil
1
𝑣𝑖 𝑡 = 𝑥𝑖 + (𝑥𝑖1 − 𝑥𝑖2)ln ( )….(2.1) 𝑢
Persamaan tersebut diturunkan dari persamaan Quantum Mechanic yaitu : 𝑙 2
1 𝑢
𝑥 𝑡 + 1 = 𝑔 ± ln ( )………….(2.2) Diasumsikan bahwa g induk yang akan dicari mutannya (g = x i), sedangkan 𝐿
𝐿 2
sebagai perbedaan vektor ( 2 = ( xi1 − xi2))
3
Ub: Batas atas permasalahan yang dalam hal ini adalah total waktu operasi yang paling tinggi Xb: nilai individu yang paling jelek pada setiap itersi Xg: nilai individu yang paling baik pada setiap iterasi c(t):bilangan variable chaotic
Untuk membuktikan bahwa algoritma usulan mampu digunkan untuk menyelesaikan permaslahan job shop scheduling, dari algoritma yang dibuat akan dibandingkan dengan metode enumerasi, yaitu dengan menghitung semua kemungkinan yang ada lalu diambil solusi (makespan) yang paling optimal. Selain itu dibandingkan pula dengan hasil dari Quantum Genetic Algorithm (Gu et al 2009), berikut perbandingan untuk ketiga metode yang diujikan pada data sederhana dari Gu et al:
𝑤 𝑡 = 𝐿𝐵 + 𝑈𝐵 − 𝑟 ∗ 𝑥𝑏 𝑡 𝑟 ≤ 0,5 .(2.3) 𝑥𝑔 𝑡 + 𝑥𝑖1 𝑡 − 𝑥𝑖2 𝑡 ∗ 2𝑐 𝑡 − 1 𝑟 > 0,5
x1(t) dan x2(t) merupakan vektor yang dipilih secara random dengan i1 ≠ i2 ≠ i. dan c adalah variable chaotic yang diperoleh dari persamaan berikut: 𝑥(𝑡)
𝑥(𝑡 + 1) =
𝑝 1−𝑥(𝑡) 1−𝑝
𝑥 𝑡 ∈ (0, 𝑝) 𝑥 𝑡 ∈ (𝑝, 1)
Tabel 3.1 Contoh Problem item
job
operation time
j1 j2 j3 j1 j2 j3
Machine Sequence
(2.4)
Notasi x diganti dengan notasi c 𝑐 𝑡−1
𝑐 𝑡 =
𝑝 1−𝑐 𝑡−1 1−𝑝
𝑐 𝑡 − 1 ∈ 0, 𝑝 𝑐 𝑡 − 1 ∈ 𝑝, 1
No 1 2 3
.(2.5)
Dari vektor W yang sudah didapatkan seperti langkah sebelumnya, di urutkan berdasarkan kegiatan pendahulu dan dicari total waktu operasinya sebagaimana tahap kedua dan ketiga. 6) Perbandingan nilai xi dan nilai W Membandingkan nilai total waktu dari xi dengan w, apabila total waktu individu w lebih baik akan digunakan sebagai solusi pada iterasi ini, sebaliknya apabila lebih jelek maka yang menjadi solusi tetap dari xi. 7) Mengecek kriteria pemberhentian Apabila kriteria pemberhentian iterasi telah tercapai maka proses komputasi dihentikan, apabila belum tercapai maka kembali ketahap ketiga dengan menggunakan individu hasil perbandingan antara xi dan w sebagai bahan pada tahap ketiga. 8) Penampilan solusi akhir Setelah kriteria pemberhentian sudah dilalui selanjutnya adalah memilih nilai total waktu terbaik diantara sekian individu yang ada pada tahap ini.
operation sequence 1 2 3 3 3 2 1 5 3 3 2 3 m1 m2 m3 m1 m3 m2 m3 m1 m2
Tabel 3.2 Hasil Perbandingan Metode makespan Quantum Genetic Algorithm 11 Enumerasi 11 CODEQ 11
mesin1 j2 j1 mesin2 j3 mesin3
j3 j1 j2
11 j2 j3
j1
Gambar 3.1 Makespan CODEQ
Algoritma yang diusulkan diujikan pada 30 set data dari OR Library. Dari masing– masing data, untuk data dengan ukuran sama seperti antara la01 sampai la05 terdapat perbedaan pada masing-masing kasus, yaitu dalam hal urutan operasi dan waktu permesinan. Perhitungan dilakukan dengan bantuan software MATLAB 7.10 yang dijalankan pada sistem operasi Windows XP. Sedangkan untuk spesifikasi hardware yang digunakan adalah komputer dengan spesifikasi prosesor intel (R) Core (TM) 2 Duo 2.1 GHz dengan RAM berkapasitas 2 GB. Hal yang diperbandingkan adalah total makespan saja adapun waktu tidak dibandingkan karena dalam melakukan komputasi selain faktor algoritma, waktu komputasi juga dipengaruhi oleh spesifikasi computer yang digunakan. . Untuk persolan kode ft06 dengan jumlah pekerjaan 6 dan jumlah mesin 6, akan
3. Hasil Komputasi 4
dibandingkan dengan metode Simulated Annealing (SA) yang dilakukan oleh (Van Laarhoven,1992) dan (Steinhofel ,1999) dalam (Chao et al,2006), Particle Swam Optimization oleh (Lin et al,2010), Genetic Algorithm oleh (Goncalves et al ,2005), dan Artificial Imune System yang dilakukan oleh (Ge at al ,2008) dalam (Lin et al ,2010).
Hasil pengujian untuk permasalahan 15 pekerjaan dengan 5 mesin dibandingkan dengan metode GA, IA, PSO dan MA. Tabel 3.6 Hasil Eksperimen untuk Kasus 15 x 5
Tabel 3.3 Hasil Eksperimen untuk kasus 6 x 6
Hasil pengujian terhadap permasalahan dengan 20 pekerjaan dan 5 dibandingkan dengan GA, IA, PSO dan MA.
Untuk kasus la01sampai la05 dengan ukuran 10 pekerjaan dan 5 mesin akan dibandingkan dengan GA, PSO IA dan Memetic Algorithm (MA) yang telah dilakukan oleh (Yang et al ,2008),
Tabel 3.7 Hasil Eksperimen untuk Kasus 20 x 5
Tabel 3.4 Hasil Eksperimen untuk Kasus 10 x 5
4. Analisis dan Pembahasan Analisis yang dilakukan meliputi uji validasi, uji permasalahan, dan uji performansi dari algoritma CODEQ. 4.1 Analisis Uji Validasi Dengan membandingkan hasil dari algoritma usulan dengan algoritma yang sudah dilakukan penilitian sebelumnya, yaitu Quantum Genetic Algorithm dan dengan metode enumerasi, hal ini menunjukan bahwa algoritma yang diusulkan yaitu CODEQ dikatakan valid dalam penyelesaian permasalahan Job Shop Scheduling. Sehingga algoritma ini dinyatakan bisa menyelesaikan permasalahan Job Shop Scheduling, terlepas dari hasil yang akan dicapai ketika nanti algoritma ini akan diterapkan untuk kasus dengan ukuran yang berbeda dan lebih besar.
Pada pengujian set data dengan ukuran 10 pekerjaan dan 10 mesin akan digunakan pembanding yang berbeda. Untuk kasus dengan kode orb01 sampai orb10 digunakan pembanding dari metode TSSA dan GA sedangkan untuk kasus dengan kode la16 sampai la20 menggunakan pembanding dari metode GA, IA, PSO dan MA. Perbedaan dalam penggunaan pembanding ini disebabkan karena keterbatasan data referensi yang ditemukan oleh penulis tentang penggunaan metode tersebut pada permasalahan Job Shop Scheduling. Tabel 3.5 Hasil Eksperimen untuk kasus 10 x 10
4.2 Analisis Uji Permasalahan Analisis Hasil Data Uji Kecil (6 x 6 dan 10 x 5) Dari percobaan yang dilakukan terhadap data ukuran 6 pekerjaan dan 6 mesin, algoritma ini menghasilkan nilai makespan yang sama ketika dibandingkan dengan metode lain, yaitu Artificial Imune, Simulated Annealing, Genetic Algorithm, Memetic Algorithm.
5
Untuk data ukuran 10 pekerjaan dan 5 mesin yang menjadi pembanding adalah algoritma Artificial Imune , Particel Swam Optimization, Genetic Algorithm, Memetic Algorithm. Algoritma ini memberikan solusi yang cukup baik, terutama untuk permasalahan la02 dan la05 diperoleh makespan yang sama, sedangkan untuk permasalahan yang lain perbedaan yang ditimbulkan tidak terlalu besar. Hasil bagus yang diperoleh ini tidak terlepas dari metode penyaringan atau seleksi yang dimiliki oleh algoritma ini yaitu pada tahap crossover dan tahap seleksi. Kedua tahap penyaringan ini membuat algoritma ini lebih cepat dalam menemukan solusi yang optimal. Selain itu, Jumlah pembangkitan sampel awal yang beragam juga mempengaruhi hasil yang akan diperoleh, semakin banyak sampel awal akan membuat solusi optimal lebih cepat muncul.
Untuk data ukuran 20 pekerjaan dan 5 mesin hasil yang diberikan oleh algoritma ini lebih buruk dibanding seluruh metode yang digunakan sebagai pembanding, terutama untuk permasalahan kode la12 perbedaan yang ditimbulkan mencapai 13%. Jadi secara keseluruhan algoritma CODEQ ini memberikan solusi yang cukup baik untuk ukuran data kecil namun untuk data ukuran besar algoritma ini lebih buruk. Kondisi ini disebabkan beberapa hal sebagai berikut: 1) Dari replikasi yang dilakukan, hasil yang diperoleh mengalami fluktuasi antara satu dengan yang lainya, hal ini dikarenakan bilangan random yang dibangkitkan saat melakukan tahapan mutasi dan tahapan penentuan nilai w jika bilangan random yang dibangkitkan mendukung untuk membuat makespan pekerjaan kecil maka akan dihasilkan makespan yang kecil pula, begitu juga sebaliknya. 2) Hal yang sama juga terjadi ketika tahap inisialisasi dimana pembangkitan individu awal juga dibangkitan dengan cara random permutasi. Maka untuk perbaikan pembangkitan awal bisa dilakukan dengan metode yang lebih baik, yang mendukung pencapaian solusi optimal. 3) Jumlah penyaringan 2 kali untuk setiap iterasi yang dimiliki metode ini tidak menjadi jaminan akan membuat iterasi lebih cepat optimal, karena apabila individu yang dihasilkan dari mutasi maupun dari penentuan individu w lebih jelek maka individu pada iterasi tersebut tidak menjadi lebih baik dibanding iterasi sebelumnya. 4) Jumlah operasi yang semakin besar akan membuat kemungkinan untuk membentuk individu awal semakin besar. Dan membuat pembentukan solusi optimal menjadi lebih lama.
Analisis Hasil Data Uji Besar (10 x10, 15 x 5 & 20 x 5) Untuk data ukuran 10 pekerjaan dan 10 mesin algoritma ini memberikan hasil yang kurang memuaskan secara keseluruhan ketika dibandingkan dengan TSSA. Terutama untuk kode orb10, persentase perbedaan yang dihasilkan mencapai 6,886%, sedangkan untuk permasalahan yang lain perbedaan yang ditimbulkan antara 0,25% sampai 2 % . Jika hasil ini dibandingkan dengan makespane dari algoritma GA, algoritma ini memberikan hasil yang sedikit lebih baik. Untuk data ukuran 15 pekerjaan dan 5 mesin yang digunakan sebagai pembanding adalah algoritma GA, IA, PSO, dan MA. Algoritma CODEQ ini memberikan hasil makespan yang cukup baik, untuk permasalahan kode la06 dan la08 algoritma ini memberikan hasil yang sama dengan algoritma lain, sedangkan untuk permasalahan yang lain perbedaan yang dihasilkan dari perbandingan metode ini tidak terlalu besar. Hal yang membuat algoritma ini kompetitif untuk persoalan ukuran ini karena jumlah total operasi yang akan di olah pada tahap inisialisasi tidak sebanyak yang ada pada kasus ukuran 10 x 10, sehingga kemungkinan kombinasi data yang akan dibangkitkan menjadi berkurang, jika semakin sedikit kemungkinan solusi yang bisa di bangkitkan diawal, akan membuat solusi optimal cepat dicapai.
4.3 Analisis Uji Performansi Pada tahap inisialisasi, sampel awal dibangkitkan secara random permutasi dari jumlah total operasi, jumlah operasi yang semakin besar akan memberikan kemungkinan untuk membentuk individu awal dengan kemungkinan berbeda juga semakin besar, jadi yang berpengaruh terhadap pencarian hasil dalam hal ini adalah jumlah total operasi. 6
Adapun jumlah mesin dan jumlah pekerjaan kedunya memberikan kontribusi pada penentuan jumlah total operasi (operasi total yan\\\g diperoleh dengan mengalikan jumlah mesin dengan jumlah pekerjaan, misal 6 pekerjaan dengan 5 mesin maka akan menghasilkan 30 operasi).
muncul kembali, misalnya dengan menentukan sampel elit. Agar kemungkinan algoritma menemukan solusi optimal semakin besar, maka digunakan jumlah pembangkitan sampel awal, misal n2 atau n3 dan dengan jumlah iterasi yang besar pula bila memungkinkan. Melihat bahwa metode ini adalah metode yang relatif baru, untuk penelitian selanjutnya bisa digunakan untuk permasalahan yang lain, seperti untuk flow shop, (No Wait Job Shop Scheduling) NWJSS, (Resources Counstrain Project Scheduling Problem) RCPSP, dsb. 6. Daftar Pustaka Betrianis & Aryawan, P.T. 2003. Penerapan Algoritma Tabu Search dalam Penjadwalan Job Shop. Departemen Teknik Industri, Fakultas Teknik, Universitas Indonesia, Jakarta Budiman, A. 2010, Pendekatan Cross Entropy-Genetic Algorithm untuk Permasalahan Penjadwalan Job shop tanpa Waktu Tunggu Pada Banyak Mesin. Institut Teknologi Sepuluh Nopember, Surabaya. Chao, Y.Z.; Li P.G.; Rao, Y.Q.; Guan, Z.L.2006. Avery fast TS/SA algorithm for the job shop scheduling problem. School of Mechanical Science & Engineering, Huazhong University of Science & Technology, Wuhan, China Dini, M. 2009. Optimasi Penjadwalan Job Shop dengan Metode Algoritma Defferential Evolution untuk Meminimumkan Total Biaya Lembur pada Kegiatan Pemuatan Barang Kontainer Ekspor, Universitas Indonesia, Jakarta. Fachrudin, A. 2010. Penerapan Algoritma Genetika untuk Masalah Penjadwalan Job Shop pada Lingkungan Industri Pakaian. Institut Teknologi Sepuluh Nopember, Surabaya Gamma. 2006. Implementasi Model Penjadwalan Job-Shop dalam Masalah Penjadwalan Kereta Api Jalur Tunggal dengan Pendekatan Constraint Programming. Institut Teknologi Bandung, Bandung Ginting, R. 2007. Sistem Produksi, Graha Ilmu, Yogyakarta Giri, Y. 2010. Penggunaan Metoda Codeq Untuk Menyelesaikan permasalahan Capacited Vehicle Routing Problem, Institut Teknologi Sepuluh Nopember. Surabaya
Gambar 4.1 Hubungan Performansi CODEQ dengan Jumlah Total Operasi
semakin besar jumlah operasi maka akan membuat jumlah kemungkinan untuk membentuk individu awal secara random permutasi semakin besar, dan hal ini akan mempengaruhi solusi optimal yang akan dihasilkan semakin sulit. Jadi, seharusnya sampel awal yang dibangkitkan pada tahap inisialisasi berjumlah sebanding dengan jumlah total operasi atau sejumlah tertentu yang bisa merepresentasikan jumlah total operasi, misal n2 ,dsb. 5. Kesimpulan dan Saran Dari hasil eksperimen maupun analisis yang telah dilakukan, maka dapat diambil kesimpulan bahwa Algoritma CODEQ bisa digunakan untuk menyelesaikan permasalahan penjadwalan job shop. Solusi yang dihasilkan menghasilkan sama baik dibanding metode pembanding untuk problem dengan skala 6 pekerjaan x 6 mesin , sedangkan untuk kasus dengan skala 10 pekerjaan x 10 mesin dan 20 pekerjaan x 5 mesin menghasilkan makespan yang lebih besar dibanding solusi yang sudah ada. Semakin besar jumlah operasi akan membuat algoritma CODEQ semakin lama menentukan nilai optimal. Sedangkan saran yang bisa diberikan untuk penelitian selanjutnya adalah dengan memodifikasi algoritma CODEQ terutama pada saat pembangkitan sampel awal supaya sampel yang sebelumnya sudah muncul tidak 7
Gu, J.; Gu, M.; Ca, C., Gu, X. 2009. A novel competitive co-evolutionary quantum genetic algorithm for stochastic job shop scheduling problem. Research Institute of Automation, East China University of Science and Technology, Shanghai, China Http://people.brunel.ac.uk/mastjjb/jeb/orlib/jo bshopinfo.html , (diakses pada 22 maret 2011) Laguna, M; Barnes, J; Glover, F. 1991. Journal of International Manufacturing: 2 vol 63. Lin, T.L.; Horng, S.J.; Kao, T.W.; Chen, Y.H.; Run, R.S. 2010. An efficient job-shop scheduling algorithm based on particle swarm optimization. Department of Electrical Engineering, National Taiwan University of Science and Technology, Taipei, Taiwan Pinedo, M & Chao, X. 1999. Operations Scheduling with Applications in Manufacturing and Services. McGrawHill, Singapore. Omran, G.H. & Salman, M.A. 2009. Constrained optimization using CODEQ. Departmen of Computer Sciene. Gulf
University for Science and Technology, Kuwait Sempena, S. 2008. Algoritma Genetik Hibrida dalam Penyelesaian Job-Shop Scheduling Problem. Jurusan Teknik Informatika ITB, Bandung Xing, L.N.; Chen, W.Y.; Wang, P; Zhao, Q.S.; Xiong, A.J. 2010, Knowledge-Based Ant Colony Optimization for Flexible Job shop Scheduling Problems. Department of Management Science and Engineering, College of Information System and Management, National University of Defense Technology, Changsha , China. Yang, J.H.; Sun, L.; Lee, H.P.; Qian, Y.; Liang, Y. 2008. Clonal Selection Based Memetic Algorithm for Job Shop Scheduling Problem. Institute of Electric and Information Engineering, Beihua University, Jilin , P. R. China Zhang, R. & Wu, C. 2007. A Hybrid immune simulated annealing algorithm for the job shop scheduling problem, Department of Automation, Tsinghua University, Beijing , PR China.
8
