tugas ahkirku

PENJADUALAN FLOWSHOP DENGAN ALGORITMA GENETIKA Tessa Vanina Soetanto Dosen Fakultas Teknik, Jurusan Teknik Industri Universitas Kristen Petra Danny Prabowo Soetanto Dosen Fakultas Teknik, Jurusan Teknik Industri Universitas Kristen Petra ABSTRACT This paper explains and gives an application of genetic algorithm for flowshop scheduling at “X” company to reach minimum multiple objectives of makespan, total flowtime and machine idletime. Comparison to HC heuristic algorithm (Ho and Chang, 1991) is done to show the differences of genetic algorithm. Keywords: flowshop, multiple objectives, genetic algorithm PENDAHULUAN Masalah penjadualan flowshop adalah menjadualkan proses produksi dari masingmasing n job yang mempunyai urutan proses produksi dan melalui m mesin yang sama. Sudah banyak penelitian yang dilakukan untuk mencari penyelesaian yang optimal terhadap masalah ini dan kebanyakan hanya mengacu pada satu tujuan saja yaitu meminimumkan makespan (waktu penyelesaian job terakhir yang meninggalkan sistem). Beberapa diantaranya adalah Campbell et al. (1970), Dannenbring (1977), Nawaz et al (1983), Ogbu & Smith (1990) serta Widmer & Hertz (1989). Namun tujuan yang lain seperti meminimumkan total flowtime (lamanya waktu yang dihabiskan seluruh job pada lantai produksi) atau multiple objectives yang meminimumkan makespan, total flowtime dan machine idletime (waktu idle mesin) akan lebih efektif dalam mengurangi biaya penjadualan, hal ini dikatakan oleh French (1982). Oleh karena itu Ho & Chang (1991) memberikan algoritma usulan untuk menyelesaikan masalah flowshop dengan multiple objectives dan dipergunakan untuk mengevaluasi algoritma usulan: genetika, yang dikembangkan oleh Sridhar & Rajendran (1996). Sedangkan solusi awal untuk algoritma genetika diberikan berdasarkan algoritma heuristic NEH (1983) dan algoritma heuristic RC (1991) Beberapa asumsi yang dipakai dalam penjadualan flowshop ini adalah: proses produksi dari job-job sudah diketahui secara jelas JURNAL TEKNIK INDUSTRI VOL. 1, NO. 1, DESEMBER 1999: 1 - 11 Jurusan Teknik Industri, Fakultas Teknologi Industri, Universitas Kristen Petra http://puslit.petra.ac.id/journals/industrial 2 tidak terdapat pre-emption (interupsi untuk mengerjakan produk lain ditengah-tengah pengerjaan suatu produk) setiap job memerlukan m mesin dan setiap proses memerlukan mesin yang berbeda - waktu set-up bersifat independent dan termasuk dalam waktu proses - semua job mempunyai ready tim yang sama. Metode Dalam menyelesaikan masalah penjadualan pada sistem produksi bersifat flowshop; Nawaz, Enscore, and Ham (1983) mengusulkan algoritma heuristic yaitu job dengan total waktu proses pada semua mesin lebih besar seharusnya diberi bobot yang lebih tinggi daripada job lain dengan total waktu proses yang lebih kecil, sehingga dapat diraih makespan yang minimum. Parameter – parameternya adalah sebagai berikut : = job yang sudah dijadualkan dari n job yang ada/partial schedule = kumpulan job-job yang belum dijadualkan q(,j) = waktu penyelesaian pada mesin j setelah memproses beberapa job dalam partial schedule (completion time partial schedule pada mesin j) a = salah satu job dalam  q(a,j)= completion time job a di mesin j, saat job a ditambahkan pada  Sehingga secara umum, didapatkan rumusan : q(a,j) =max [q(,j) ; q(a,j-1)] + Taj (11) Sedangkan makespan dari partial schedule a : Ma = q(a,m) (12) Namun dengan adanya perubahan pada formulasi time table yang disesuaikan dengan kondisi lantai produksi yang ada maka q(a,j) = Eaj (13) Ma = q(a,m) = Eam (14) Hasil pembahasan Di dalam menyelesaikan masalah penjadualan flowshop dengan multiple objectives, meminimumkan makespan, total flowtime dan machine idletime maka Sridhar and Rajendran (1996) menggunakan Algoritma Genetika. Algoritma Genetika adalah suatu algoritma/prosedur penelusuran yang berdasarkan pada mekanisme dari natural selection dan natural genetics yang dapat digunakan untuk memecahkan combinatorial optimization problems yang sulit. Algoritma ini PENJADUALAN FLOWSHOP DENGAN ALGORITMA GENETIKA (Tessa Vanina Soetanto) Jurusan Teknik Industri, Fakultas Teknologi Industri, Universitas Kristen Petra http://puslit.petra.ac.id/journals/industrial 5 dikembangkan oleh John Holland, rekan kerja dan muridnya dari Michigan University (1975); yang mengkombinasikan keberhasilan suatu struktur untuk bertahan hidup (survival of the fittest) dengan pengubahan informasi dari struktur tersebut secara random untuk membentuk suatu mekanisme penelusuran seperti yang dilakukan dalam proses pembentukan manusia atau mahkluk hidup (gen/sifat yang diturunkan). Dalam Algoritma Genetika dikenal adanya chromosome yaitu kandidat penyelesaian yang digambarkan dengan urutan binary digits atau integers sesuai kondisi yang dikehendaki. Chromosome terdiri dari gen-gen yang melambangkan ciri-ciri unik dari chromosome tersebut sedangkan nilai yang berkaitan dengan ciri-ciri yang dilambangkan oleh gen tertentu disebut allele. Populasi adalah sekumpulan chromosome yang akan diperbaharui pada setiap generasi. Dikenal pula adanya dua operator yang memegang peranan penting dalam Algoritma Genetika yaitu crossover operator dan mutation operator. Crossover operator adalah operator yang menggabungkan dua chromosome sehingga menghasilkan child chromosome yang mewarisi ciri-ciri dasar dari parent chromosome sedangkan mutation operator dipergunakan untuk memperkenalkan transformasi (informasi) baru pada populasi yang melibatkan perubahan chromosome secara random. Jika Algoritma Genetika diaplikasikan pada problem penjadualan maka chromosome menggambarkan urutan job, gen-gen melambangkan posisi-posisi job tersebut, sedangkan allele menggambarkan job-job yang memiliki posisi-posisi tersebut. Untuk menginitialisasi dua sub populasi digunakan makespan minimizing Algoritma Heuristic NEH (Nawaz et al, 1983) dan total flowtime minimizing Algoritma Heuristic RC (Rajendran and Chaudhuri, 1992). Crossover operator yang digunakan adalah Partially Matched Crossover (PMX) yang ditemukan oleh Goldberg and Lingle (1985), operator ini memberikan pemisah antara posisi job-job dengan garis vertikal seperti contoh berikut ini , misalnya bilangan random yang dihasilkan adalah 2 dan 4 maka garis vertikal akan diletakkan pada posisi ke-2 dan posisi ke-4 chromosome parent. P1 : 1 | 4 5 | 2 3 C1 : 4 | 1 2 | 5 3 P2 : 3 | 1 2 | 5 4 C2 : 3 | 4 5 | 2 1 Untuk membangun Child 1 (C1), maka dilihat pemisahan pada Parent 2 (P2) untuk mencari job mana yang akan ditukar dengan job pada Parent 1 (P1). Ternyata job 4 dan job 1, job 5 dan job 2 ditukar dengan Parent 1 untuk menghasilkan Child 1 dan demikian pula untuk menghasilkan Child 2 (C2). Sedangkan cara mengevaluasi chromosome yang tidak sesuai dengan fungsi tujuan dan menggantikannya dengan chromosome yang potensial menggunakan operator Delta. Apabila terdapat dua chromosome (urutan/ sequence) yaitu S1 dan S2 dengan makespan MS1 dan MS2, total flowtime FT1 dan FT2 serta machine idletime IT1 dan IT2; serta bobot kepentingannya atau bobot biaya relatif dari makespan, total flowtime, machine idletime adalah w1, w2, dan w3 ( w1+w2+w3 = 1). KESIMPULAN 1. Penjadualan flowshop menggunakan Algoritma Genetika yang bertujuan meminimumkan makespan, total flowtime dan machine idletime secara bersama-sama maka didapatkan penjadualan job : 6-5-2-1-3-7-4-8 dengan makespan 483334 detik, total flowtime 1699242 detik dan machine idletime sebesar 252390 detik. 2. Penjadualan menggunakan Algoritma Heuristic HC yang mempunyai tujuan yang sama dengan Algoritma Genetika maka didapatkan penjadualan job : 6-5-2-1-3-8-4-7 dengan makespan 480700 detik, total flowtime 1699350 detik dan machine idletime sebesar 256226 detik . DAFTAR PUSTAKA French, Simon. 1982. Sequencing and Scheduling: An Introduction to the Mathematics of Job Shop, Chichester: Ellis Horwood. Ho, J. C., and Chang, Y. L., 1991. “A new heuristic for the n-job, m-machine flowshop problem”, European Journal of Operational Research, No. 52, 194-202. Michalewicz, Zbigniew, 1992. Genetic Algorithms + Data Structures = Evolution Programs, Springer-Verlag. Nawaz, M., Enscore, E. E., and Ham, I., 1983. “A heuristic algorithm for the mmachine, n-job flowshop sequencing problem”, OMEGA, No. 11, 91-95. R. Baker, Kenneth, 1974. Introduction to Sequencing and Scheduling, New York: John Wiley & Sons. Rajendran, C., and Chaudhuri, D., 1992. “An efficient heuristic approach to the scheduling of jobs in a flowshops”, European Journal of Operational Research, No. 61, 318-325. Sridhar, J., and Rajendran, C., 1996. “Scheduling in flowshop and cellular manufacturing systems with multiple objectives – a genetic algorithmic approach”, Production Planning & Control, Vol. 7, No. 4, 374-382.