STUDI APLIKASI METODE ARTIFICIAL IMMUNE SYSTEM DALAM PENJADWALAN FLOW SHOP

Studi Aplikasi Metode Artificial ... Rosnani Ginting, T.U. Hidayat S. Ginting

STUDI APLIKASI METODE ARTIFICIAL IMMUNE SYSTEM DALAM PENJADWALAN FLOW SHOP Rosnani Ginting, T.U.Hidayat S.Ginting Departemen Teknik Industri dan Departemen Teknik Mesin Fakultas Teknik, Universitas Sumatera Utara Abstrak: Artificial Immune System (AIS) merupakan suatu sistem komputasi yang diinsiprasikan oleh teori imunologi, yang mengamati fungsi, prinsip, dan mekanisme sistem kekebalan tubuh vertebrata yang diaplikasikan dalam pemecahan masalah. Aplikasi Artificial Immune System dalam masalah penjadwalan menggunakan sebagian proses dari sistem kekebalan tubuh yaitu proses pembentukan antibodi dengan nilai affinity tinggi untuk membentuk urutan job dengan nilai makespan rendah. Antibodi yang memiliki kualitas baik akan mengalami proses kloning dan pematangan affinity (affinity maturation). Hasil penjadwalan adalah urutan job yang direpresentasikan oleh antibodi dengan nilai affinity paling tinggi. Key Words: artificial immune system, penjadwalan, flow shop

PENDAHULUAN Penjadwalan flow shop merupakan model penjadwalan di mana job-job yang akan diproses seluruhnya mengalir pada arah/jalur produk yang sama. Dengan perkataan lain, job-job memiliki routing kerja sama. Masalah penjadwalan sering kali muncul jika terdapat n job yang akan diproses pada m buah mesin, yang harus ditetapkan mana yang harus dikerjakan terlebih dahulu dan bagaimana mengalokasikan job pada mesin sehingga diperoleh suatu proses produksi yang terjadwal. Penjadwalan flow shop sering kali diselesaikan dengan mengembangkan permutasi urutan job yang akan diurutkan. Job bersifat independent, secara serempak tersedia pada waktu nol, dan urutan mesin dari semua pekerjaan sama. Masing-masing job memiliki waktu proses pada masing-masing mesin. Preemption tidak diizinkan. Tujuan penjadwalan pada umumnya adalah menemukan suatu urutan job yang bertujuan untuk me-minimisasi makespan. Beberapa metode telah diperkenalkan seperti metode Johnson, metode Campbell, Dudek and Smith (CDS), metode Nawaz, Enscore, and Ham (NEH algorithm), Genetic Algoritma, dan sebagainya. Dalam penelitian ini, digunakan suatu metode pengembangan dari evolutionary algorithm, yaitu metode Artificial Immune System yang mengambil ide dari mekanisme sistem kekebalan tubuh vertebrata yang diaplikasikan dalam masalah penjadwalan flow shop. Sistem Kekebalan Tubuh Sistem kekebalan berfungsi untuk melindungi tubuh terhadap masuknya benda

asing yang dapat mengganggu kestabilan kondisi tubuh. Sistem kekebalan terdiri dari sel, molekul, dan organ yang membangun suatu mekanisme identifikasi yang mampu merasakan dan memberantas sel-sel asing yang menginfeksi tubuh. Sasaran utama sistem kekebalan adalah antigen yang datang dari luar tubuh. Bagian dari sistem kekebalan yang berperan dalam pembentukan sel kekebalan (antibodi) adalah sel darah putih (lymphocite) yang terdiri dari 2 jenis yaitu sel B dan sel T, Phagocyte, APC (antigen presenting cells yaitu sel tubuh yang dapat menghadirkan antigen dalam bentuk yang dapat dikenali oleh sel B dan sel T) dan MHC (major histocompatibility complex) yaitu molekul yang mengeluarkan protein sebagai tanda suatu antigen sehingga sel B atau sel T mudah mengenali antigen tersebut. Sistem kekebalan tubuh terdiri dari dua proses yaitu pemilihan clone dan proses pematangan affinity (affinity maturation). A. Prinsip Pemilihan Clone Prinsip pemilihan clone adalah algoritma yang digunakan oleh sistem kekebalan untuk menguraikan bagian mendasar untuk stimulasi antigen. Pada prinsip ini ditekankan bahwa hanya sel yang dapat mengenali antigen yang dipilih untuk melawan antigen yang tidak dapat mengenali. Pemilihan clone berlaku baik untuk T cell maupun untuk B cell. B lymphocytes bereaksi dengan memproduksi antibodi. Masing-masing sel mengeluarkan hanya satu macam antibodi yang spesifik untuk antigen tersebut. Dengan mengikat diri pada receptor immunoglobulin, dan dengan isyarat kedua dari 15

Jurnal Sistem Teknik Industri Volume 7, No. 2 April 2006

sel T-Helper, antigen menstimulasi B cell untuk berkembang biak dan matang pada sel plasma. Gambar berikut ini memperlihatkan prinsip pemilihan clone. B. Affinity Maturation Affinity maturation merupakan proses mutasi dan pemilihan keturunan yang dapat mengenali antigen dengan lebih baik. Ada dua mekanisme dasar affinity maturation yaitu hypermutation dan perbaikan receptor. Mutasi terjadi pada daerah gen pada molekul antibodi. Mutasi menyebabkan perubahan sel secara struktur. Biasanya sel yang berubah mengakibatkan penambahan afinitas pada antibodi. Proses mutasi pada lymphocite disebut somatic hypermutation. Somatic hypermutation berbanding terbalik dengan affinitas sel, semakin tinggi afinitas yang dimiliki sel receptor dengan antigen, semakin rendah ratarata mutasi dan sebaliknya. Dengan strategi ini, sistem kekebalan menjaga sel keturunan afinitas dan juga memastikan mutasi besar untuk yang afinitas rendah sehingga diperoleh afinitas yang lebih baik. Berkaitan dengan pengacakan proses mutasi somatic, sejumlah gen hasil mutasi menjadi tidak berfungsi atau anti-self yang berbahaya. Sel tersebut dieliminasi oleh suatu proses kematian yang diprogramkan. Tetapi semua sel dengan afinitas rendah dan anti-self specifas tidak dihapus, proses ini dikenal dengan pengeditan receptor: B-Cells menghapus sel receptor dan mengembangkan sel receptor baru. Proses editing sel ini dapat menghasilkan receptor dengan afinitas yang lebih baik atau lebih buruk. Mutasi baik untuk mendapatkan hasil yang baik, sedangkan pengeditan dapat menyelamatkan sistem kekebalan dari hasil yang tidak memuaskan. C. Artificial Immune System AIS merupakan sistem komputasi yang diinsiprasikan oleh teori imunologi, mengamati fungsi, prinsip dan mekanisme kekebalan yang diaplikasikan dalam pemecahan masalah [8]. Aplikasi dari AIS mencakup pengamanan dan jaringan komputerisasi, deteksi kesalahan dan penyimpangan, optimisasi, analisis data dan penjadwalan. Forrest dkk. telah menggunakan rcontiguous bit rule dan membandingkan masalah pengamanan sistem komputer dan memperkenalkan algoritma pemilihan negatif [10]. Dasgupta dan Forrest memperkenalkan 16

aplikasi algoritma pemilihan negatif dari AIS untuk mendeteksi hal-hal baru pada data time series [5]. Dasgupta dan Forrest juga memperkenalkan penggunaan AIS dalam mendeteksi kerusakan mesin. Metode ini diinspirasikan dari algoritma pemilihan negatif yang memungkinkan untuk membedakan sel-sel sendiri dan yang bukan. Pada studinya sel sendiri didefinisikan untuk operasi pemotongan yang normal dan sel yang bukan sendiri adalah deviasi atau penyimpangan dari variasi kelonggaran dari kekuatan potong. De castro dan Timmis memperkenalkan penggunaan AIS dalam pengenalan pola (pattern recognition). De castro dan Von Zuben mengaplikasikan algoritma pemilihan clone untuk menyelesaikan masalah optimasi multimodal, penugasan pattern recognotion dan masalah perjalanan salesman. Hart dkk menggunakan pendekatan AIS untuk menyelesaikan masalah penjadwalan job shop [10]. Kriteria penjadwalan yang digunakan adalah minimisasi maximum tardiness. Masingmasing solusi adalah antibodi. Sejumlah kelompok yang terdiri dari sejumlah string dibangun dan masing-masing string adalah bagian dari solusi untuk masalah penjadwalan job shop. Costa dkk. memperkenalkan pendekatan immune untuk minimisasi makespan pada prosesor paralel. Penggunaan AIS dalam Penjadwalan Mekanisme penggunaan sistem kekebalan yang efisien membuat AIS dapat digunakan dalam masalah penjadwalan. Pendekatan AIS telah digunakan dalam menyelesaikan masalah penjadwalan job shop. Masing-masing solusi (jadwal lengkap) adalah antibodi. String-string dari penggabungan antibodi disusun. Ribuan clone dari individu terbaik digenerasikan. Clone dimutasi dan clone terbaik dipilih sebagai solusi. Representasi penjadwalan tidak berbeda dengan Genetic Algorithm. Algoritma AIS dan Algoritma Genetik memiliki kesamaan karena merupakan turunan dari proses evolutionary. IV. Algoritma dan Parameter Optimisasi Metode AIS A. Algoritma Jadwal yang mungkin direpresentasikan oleh integer-valued string dari n job. Elemen n dari string adalah job yang akan diurutkan. Oleh karena itu string disusun dari permutasi elemen n job. String-string tersebut diterima sebagai antibodi pada Artificial Immune System. Algoritma diteruskan untuk mencari solusi


dengan evolusi antibodi. Evolusi didasarkan pada dua prinsip dasar dari sistem kekebalan yaitu pemilihan clone dan affinity maturation [7].

nilai Cmax yang tinggi mungkin tidak memiliki clone dalam kelompok clone, sementara antibodi dengan Cmax yang lebih rendah mungkin memiliki sejumlah clone [8].

B. Algoritma Proses Pemilihan Clone Nilai affinity dari masing-masing jadwal dihitung sesuai dengan fungsi affinity. Doyen, dkk [8] merumuskan fungsi affinity sebagai berikut:

C. Algoritma Proses Affinity Maturation

Affinity(z) = 1/makespan (z) Di mana z adalah antibodi yang akan dihitung. Dari rumus di atas dapat diketahui bahwa nilai makespan yang paling rendah sama dengan nilai affinitas yang paling tinggi. Pada algoritma kloning antibodi dilakukan langsung proporsional dengan fungsi nilai affinitas, sama seperti sistem kekebalan tubuh. Kebalikan dengan masalah optimisasi, prosedur ini memberikan kesempatan untuk makespan (Cmax) dengan nilai yang lebih rendah untuk dipilih dan di-cloning. Untuk itu akan ada lebih banyak clone antibodi dengan nilai yang lebih rendah daripada clone dengan nilai makespan yang lebih tinggi pada populasi clone generasi selanjutnya. Pemilihan probabilitas masing-masing antibodi dihitung dengan prosedur sebagai berikut [7] dan [8]: a. Untuk masing-masing antibodi pada populasi dihitung nilai makespan. b. Cari nilai makespan maksimum (Max Cmax). c. Untuk masing-masing antibodi hitung nilai fitness dengan rumus berikut: = (Max Cmax + 1) – (makespan of antibody) d. Untuk masing-masing antibodi, cari probabilitas yang terpilih. Hitung probablitas terpilih dengan rumus berikut: = antibody all of value fitness total antibody of value fitness Dalam algoritma digunakan ukuran tetap dari populasi antibodi, juga digenerasikan sejumlah clone dengan ukuran yang sama dari populasi antibodi. Clone-clone yang digenerasikan dari masing-masing antibodi, berubah sesuai dengan pemilihan probabilitas antibodi. Diharapkan antibodi dengan pemilihan probablitas yang lebih besar akan menghasilkan clone pada kelompok clone. Karena ukuran tetap dari kelompok clone, beberapa antibodi dengan

1.

Mutasi Ada dua tahap prosedur mutasi yang digunakan [7]. Tahap pertama dilalui oleh generasi clone dengan prosedur inverse mutation. a.

Mutasi Kebalikan Untuk pengurutan s, i, dan j merupakan dua posisi pada pengurutan s. Urutan s yang lain ditentukan dengan membalikkan urutan job antara posisi i dan j. Jika nilai makespan dari urutan hasil mutasi lebih kecil dari urutan awal maka hasil mutasi ditempatkan pada urutan awal. Jika tidak, urutan akan dimutasikan lagi dengan metode mutasi penukaran pasangan. b.

Mutasi Penukaran Pasangan Untuk pengurutan s, i dan j secara acak dipilih dua posisi pada urutan s. Urutan s yang lain ditentukan dengan menukar job pada posisi i dan j. Jika nilai makespan dari urutan mutasi lebih kecil daripada urutan asli, simpan hasil mutasi dan tempatkan pada urutan asli. Jika pada algoritma tidak ditemukan urutan yang lebih baik dari dua prosedur mutasi di atas, maka gunakan urutan asli. Pada langkah sebelumnya pada algoritma ini, ada banyak kemungkinan untuk menemukan urutan yang lebih baik dengan menggunakan mutasi kebalikan karena algoritma masih jauh dari solusi yang baik dan mutasi yang besar dapat menghasilkan urutan job yang lebih baik. Pada langkah selanjutnya algoritma akan menghasilkan solusi yang baik. Kemungkinan mendapatkan urutan dengan cara membuat mutasi yang besar lebih rendah, karena mutasi yang besar dapat mengakibatkan hilangnya urutan job parsial dan jauh dari optimal. Jadi, pada langkah selanjutnya lebih efisien untuk membuat mutasi yang lebih kecil. Pada algoritma ini, efisiensi dijaga dengan menggunakan mutasi penukaran pasangan ketika mutasi kebalikan tidak memberikan solusi yang lebih baik. Seperti pada penjelasan sebelumnya, algoritma dibuat untuk menghasilkan mutasi yang lebih kecil, kebalikan dengan peningkatan (pengurangan nilai makespan) pada nilai fungsi affinity. Pada sistem kekebalan vertebrata, mutasi pada molekul receptor dilakukan secara 17


bolak-balik, proporsional dengan tingkat affinity dari molekul receptor tersebut. Pendekatan pada algoritma ini sesuai dengan mekanisme tersebut. 2. Pengeditan Receptor Pada beberapa prosedur algoritma, sejumlah antibodi yang buruk dari populasi antibodi dieliminasi dan secara acak dihasilkan antibodi dengan jumlah yang sama sebagai pengganti. Hal ini juga termasuk mekanisme sistem kekebalan vertebrata yang disebut dengan receptor editing. Mekanisme ini juga dapat digunakan untuk menemukan jadwal baru, yang berarti wilayah pencarian baru pada ruang pencarian total. Menghasilkan wilayah pencarian yang baru dapat membantu algoritma terhindar dari optimasi lokal. PEMBAHASAN 1. Perhitungan Waktu Pengerjaan Per-Order Saat selesai yang dibutuhkan untuk menyelesaikan satu pekerjaan mulai dari saat tersedia pekerjaan sampai dengan pekerjaan tersebut selesai disebut completion time. Perhitungan dilakukan dengan menjumlahkan seluruh waktu yang terpakai untuk menyelesaikan satu produk ban. Kemudian dilakukan perhitungan total waktu proses yang dibutuhkan yang dapat memenuhi kuantitasorder yang dikerjakan untuk tiap komponen. Waktu Pengerjaan Per-Order =

Makespan dilakukan untuk masing-masing kedatangan order yaitu untuk order yang datang pada tanggal 2 Mei 2005 dengan due date 30 Mei 2005 (order pertama) dan order yang datang pada tanggal 16 Mei 2005 dengan due date 4 Juni 2005 (order kedua). 2.1 Perhitungan Makespan untuk Order 2 Mei 2005 dengan Due Date 30 Mei 2005 (Order Pertama) Order yang datang pada tanggal 2 Mei 2005 terdiri dari 20 job. Dengan metode Artificial Immune System akan dilakukan penjadwalan terhadap ke 20 job tersebut. Pencarian urutan pengerjaan job yang optimum dilakukan berdasarkan penelusuran generasi dengan Artificial Immune System yang akan menghasilkan generasi yang lebih baik dari tiap populasi. Berikut ini perhitungan Makespan dengan metode AIS untuk order pertama. A. Pembangkitan Jadwal Induk Susunan urutan yang mungkin dari 20 job (n = 20) adalah: nP = n! nP = 20! nP = 20x19x18x17x16x15x14x13x12x11x10x9x 8x7x6x5x4x3x2x1 18 nP = 2,43 x 10 Urutan job yang dapat disusun dari 20 job adalah sebanyak 2,43 x 1018 urutan. Dari urutanurutan job tersebut akan diambil urutan job secara acak.

Jumlah Produk x Waktu Pengerjaan Tiap Proses/Order Jumlah Mesin

Misalkan untuk job 12½ x 2¼ dipesan sebanyak 100 unit. Mesin Penggilingnan mampu menghasilkan 5 unit job dalam sekali proses. Maka waktu poengerjaan job 12½ x 2¼ adalah: Waktu pengerjaan per-order = 100 x583.14 detik 1x5

= 11662.78 detik = 194.37 menit Hasil perhitungan total waktu proses untuk job 12½ x 2¼ dapat dilihat pada Tabel V.1. 2. Minimisasi Makespan dengan Metode Artificial Immune System Metode pemecahan masalah penjadwalan yang digunakan dalam penelitian ini adalah metode Artificial Immune System. Perhitungan 18

B. Proses Cloning Fitness Value dan probabilitas seleksi dihitung dengan rumus sebagai berikut: Fitness Value = (Maks Cmax + 1) – (Makespan of antibody) Probabilitas

Seleksi

=

Fitness Value of antibody Total Fitness Value of all antibody Hasil perhitungan nilai Fitness Value dan probabilitas seleksi dapat dilihat pada Tabel V.4. Proses cloning dilakukan dengan mernggunakan bilangan acak yang dibangkitkan sebanyak 20 bilangan acak pada interval 0,1 dengan program komputer dan urutan job yang memiliki bilangan acak yang berada pada inervalnya merupakan hasil generasi.


Tabel V.1. Perhitungan total waktu proses untuk job 12½ x 2¼

No 1 2 3 4 5 6 7 8 9

Stasiun Kerja Penggilingan I Pencampuran Bahan Penggilingan II Penggulungan Kawat Pembuatan Tapak Pelapisan Nylon Pemotongan Nylon Pembentukan Ban Pemasakan Ban

Waktu Baku (detik) 583.14 482.70 483.42 123.01 120.23 1334.07 156.42 203.89 399.09

Jumlah order 100 100 100 100 100 100 100 100 100

Jumlah Mesin 1 1 3 3 1 1 1 12 14

Total Waktu (menit) 194.37 160.90 53.71 34.17 200.39 317.64 260.69 28.32 9.50

Tabel V.2. Perhitungan Probabilitas Seleksi

No 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

Makespan (menit) 6862.65 7155.36 7341.34 7345.86 7417.57 7422.90 7442.24 7580.39 7586.74 7629.57 7631.50 7644.09 7651.48 7652.67 7668.46 7735.47 7744.98 7775.67 7819.71 7894.53 Jumlah

Fitness values

Probabilitas Seleksi

Probabilitas Kumulatif

Interval

1032.88 740.17 554.19 549.67 477.96 473.63 453.29 315.14 308.79 265.96 264.03 251.44 244.05 242.86 227.07 160.06 150.55 119.86 75.82 1.00 6907.43

0.15 0.11 0.08 0.07 0.07 0.07 0.05 0.04 0.04 0.04 0.04 0.04 0.04 0.04 0.03 0.02 0.02 0.02 0.01 0.00

0.15 0.26 0.34 0.42 0.49 0.55 0.62 0.67 0.71 0.75 0.79 0.82 0.86 0.89 0.93 0.95 0.97 0.99 1.00 1.00

0.01-0.15 0.16-0.26 0.27-0.34 0.35-0.42 0.43-0.49 0.50-0.55 0.56-0.62 0.63-0.67 0.68-0.71 0.72-0.75 0.76-0.79 0.80-0.82 0.83-0.86 0.87-0.89 0.90-0.93 0.94-0.95 0.96-0.97 0.98-0.99 1.00-1.00 1.00-1.00

C. Proses Mutasi Clone Proses mutasi dilakukan untuk masingmasing clone (urutan job baru yang dihasilkan dari proses kloning). Mutasi dilakukan dengan 2 cara: 1. Inverse Mutation Pada proses ini diambil secara acak sati posisi job, kemudian urutan job dibalikkan sehingga diperoleh urutan job baru. Bila klon yang dihasilkan memiliki nilai makespan yang lebih besar dari pada hasil kloning, maka klon dimutasikan kembali dengan pairwise interchange mutation.

2.

Pairwise Interchange Mutation Posisi job ditukar dengan posisi job lainnnya. Penentuan job yang akan ditukar adalah dengan menggunakan bilangan acak. Sesuai dengan aturan acak proses mutasi yaitu urutan yang memiliki bilangan acak nol tidak mengalami mutasi sedangkan bilangan acak 1 akan mengalami mutasi.

2.2 Perhitungan Makespan untuk Order 16 Mei 2005 dengan Due Date 4 Juni 2005 (Prder Kedua) Order yang datang pada tanggal 16 Mei 2005 (t’ = 3960 menit) terdiri dari 10 job. Pada 19


t’=3960 menit, beberapa job pada order tanggal 2 Mei 2005 telah selesai dilakukan. Sedangkan untuk job yang belum selesai adalah job 17, 10, 19, 2, 18, 16, 12, dan 8. Contoh perhitungan sisa waktu proses untuk job-job sisa ini adalah: - job 17 (produk 28 x 1,5 BC) di mesin 7: C7 sisa di m7 = C7 operasi – Cn order baru =49.39 – (3960- 3945.65) = 35.04 menit Job 17 belum selesai dikerjakan pada mesin 7. Untuk penjadwalan ulang dengan preempt repeat mode, job 17 diselesaikan pada mesin 7 terlebih dahulu kemuidan dijadwalkan ulang pada mesin 8. Job sisa yang belum selesai dikerjakan dijadwalkan kembali bersam-sama dengan jobjob pada order kedua. Prosedur metode AIS kembali digunakan untuk mencari urutan job terbaik dari order kedua. a. Pembangkitan Jadwal Induk Susunan urutan yang mungkin dari 18 job (n = 18) adalah: nP = n! nP = 18! nP = 18x17x16x15x14x13x12x11x10x9x8x7x6x 5x4x3x2x1 15 nP = 26,4 x 10 Urutan job yang dapat disusun dari 18 job adalah sebanyak 62,4 x 1015 urutan. Dari urutanurutan job tersebut akan diambil urutan job secara acak. b.

Proses Cloning Fitness Value dan probabilitas seleksi dihitung dengan rumus sebagai berikut: Fitness Value = (Maks Cmax + 1) – (Makespan of antibody) Probabilitas Seleksi = Fitness Value of antibody Total Fitness Value of all antibody

c.

Mutasi Sequence Hasil Proses Kloning Proses mutasi dilakukan untuk masingmasing clone (urutan job baru yang dihasilkan dari proses kloning. Mutasi dilakukan dengan 2 cara. Dari hasil mutasi tersebut dapat dilihat urutan job yang memiliki nilai makes pan yang terendah adalah urutab pertama yaitu: 20

4-5-12-14-13-17-8-16-10-15-18-2-3-7-1-16-119 atau 2-16-26-25-29-8-28-22-27-30-10-19-12-17-1823-12 Dengan nilai makespan sebesar 4870.99menit. 2.3 Pemenuhan Due-Date Order dengan Metode Artificial Immune System Due date merupakan batas waktu penyerahan produk oleh produsen, yang ditetapkan oleh konsumen. Dari hasil teknik penelusuran dengan AIS disimpulkan penjadwalan untuk ke-20 produk ban sebagai order yang datang pada 2 Mei 2005 dapat diselesaikan pada waktu 6801.22 menit atau pada tanggal 26 Mei 2005 dan order yang datang pada 16 Mei 2005 dapat selesai pada 4870.99 menit atau pada tanggal 31 Mei 2005. dapat disimpulkan seluruh job dapat diselesaikan pada tanggal 31 Mei 2005 atau pada 9180 menit. Untuk menguji apakah hasil ini dapat memenuhi due date tiap order dilakukan analisa pemenuhan untuk tiap order yang dapat dilihat pada tabel berikut: Tabel V.3. Pemenuhan Due Date 30 Mei 2005 Waktu Kode Selesai Produk job Order (menit) 13 24 x 2.00 609.81 4 22 x 1.75 790.80 14 26 x 2.00 945.41 9 16 x 2.125 1666.69 15 26 x 1 3/8 1899.72 1 12½ x 2¼ 2172.39 7 24 x 1.75 2933.05 6 20 x 2.125 3229.85 3 27 x 1¼ 3366.83 20 2.75 x 17 3456.62 11 24 x 1.90 3765.31 5 20 x 1.75 3897.73 17 28 x 1.5 BC 4571.32 10 26 x 1.90 4814.52 19 2.5 x 17 4895.39 2 16 x 1.75 5491.13 16 28 x 1.5 BS 5777.84 18 13 x 300 6556.98 12 20 x 2.00 6635.81 8 24 x 1 3/8 6801.22

Order 2 Mei – Waktu Selesai Order 4 Mei 2005 4 Mei 2005 6 Mei 2005 9 Mei 2005 9 Mei 2005 10 Mei 2005 11 Mei 2005 12 Mei 2005 13 Mei 2005 13 Mei 2005 13 Mei 2005 14 Mei 2005 15 Mei 2005 17 Mei 2005 17 Mei 2005 19 Mei 2005 20 Mei 2005 23 Mei 2005 26 Mei 2005 26 Mei 2005

KESIMPULAN Semua clone dari kumpulan clone yang merupakan tiruan dari antibodi dengan tingkat


afinitas yang baik dihasilkan proses mutasi. Ada dua fase proses mutasi: pertama mutasi kebalikan. Jika proses ini tidak menghasilkan solusi yang baik maka metode mutasi peukaran pasangan dilakukan. Setelah mutasi kedua, jika masih belum ada perbaikan maka urutan asli digunakan tanpa perubahan. Pada beberapa prosedur algoritma, mekanisme pengeditan receptor dari sistem kekebalan digunakan: jadwal yang buruk dieliminasi dan jadwal yang baru dihasilkan sebagai pengganti. Kumpulan clone diterima sebagai populasi antibodi untuk generasi selanjutnya setelah proses cloning dan mutasi. Clone yang dihasilkan dari proses mutasi ditugaskan sebagai antibodi untuk generasi selanjutnya. Pada generasi berikutnya clone akan dibuat dari antibodi ini. DAFTAR PUSTAKA Baker, K.R., Introduction to Sequencing and Scheduling, John Willey & Sons Inc., New York, 1974. Costa, A.M., Vargas, P.A., Von Zuben, F.J., and França, P.M. (2002). Makespan minimization on parallel processors: An immune based approach,In the proc. of the special sessions on artificial immune systems in the 2002 Congress on Evolutionary Computation, IEEE World Congress on Computational Intelligence, Honolulu, Hawaii, pp: 115-123 Dasgupta, D., and Forrest, S. (1999). Artificial immune systems in industrial applications, Proceedings of the Second International Conference on Intelligent Processing and Manufacturing Materials (IPMM), Honolulu, July 10-15.

Dasgupta, D., and Forrest, S. (1996). Novelty detection in time series data using ideas from immunology. Proceedings of the ISCA’96, RENO, Nevada, June 19-21. De Castro, L. N. dan F. J. Von Zuben, Artificial Immune System, Part I Basic Theory and Application, Technical Report, TR-DCA 01/99, 1999. De Castro, L. N. dan F. J. Von Zuben, Artificial Immune System, Part II A Survey Of Applications, Technical Report, TR-DCA 02/00, 2000. Doyen, Alper, Orhan Engin dan Coskun Ozkan, A New Artificial Immune System Approach to Solve Permutation Flow Shop Scheduling Problems, IJCI Proceeding of Intl. Vol.1, No.1, July 2003. Engin, Orhan dan Alper Doyen, A New Approach to Solve Hybrid Flow Shop Scheduling Problems by Artificial Immune System, Future Generation Computer System 20, pp. 1083-1095, 2004. Forrest, S., Perelson, A., Allen, L., and Cherukuri, R. (1994). Self-nonself discrimination in a computer. Proceedings of the IEEE Symposium on Research in Security and Privacy, IEEE Computer Society Pres, Los Alamitos, CA, 202-212. Hart, E., Ross, P., and Nelson, J. (1998). Producing Robust Schedules Via an Artificial Immune System. Proceedings of ICEC’98, pp.464-469.

21

STUDI APLIKASI METODE ARTIFICIAL IMMUNE SYSTEM DALAM PENJADWALAN FLOW SHOP

Recommend Documents