APLIKASI METODE METAHEURISTIK UNTUK KASUS SEQUENCING PADA MIXED MODEL ASSEMBLY LINE

Prosiding Seminar Nasional Manajemen Teknologi XXI Program Studi MMT-ITS, Surabaya 19 Juli 2014

APLIKASI METODE METAHEURISTIK UNTUK KASUS SEQUENCING PADA MIXED MODEL ASSEMBLY LINE Abduh Sayid Albana1), Gülgün Alpan-Gaujal2), dan Yannick Frein2) 1) Program Studi Magister Teknik Industri, Institut Teknologi Sepuluh Nopember, Jl. Arif Rahman Hakim Gedung Program Pascasarjana ITS Kampus ITS Sukolilo, Surabaya, 60111, Indonesia e-mail: [email protected]* 2) Univ. Grenoble Alpes, G-SCOP, F-38000 Grenoble, France CNRS, G-SCOP, F-38000 Grenoble, France

ABSTRAK Sekarang ini variasi produk semakin meningkat. Hal ini menyebabkan Manager produksi semakin sulit dalam memenuhi permintaan konsumen. Manager produksi harus melakukan eficienfy dengan line balancing dan menetukan urutan produksi (sequencing) secara tepat, sehingga dapat meminimasi biaya produksi. Pekerja dan mesin produksi haruslah fleksibel untuk mengurangi biaya dan waktu setup, sehingga berbagai jenis produk dapat diproduksi dengan urutan produksi campuran pada line produksi yang sama. Tipe assembli line seperti ini disebut sebagai Mixed Model Assembly Line (MMAL). Ada dua jenis problem utama dalam MMAL: Line Balancing dan Product Sequencing. Pada artikel ini, peneilitian dilakukan pada kasus product sequencing dengan meminimasi total work overload. Telah ada penelitian terdahulu yang menyelesaikan kasus yang sama dengan menggunakan Mixed Integer Linear Programming (MILP). MILP membutuhkan waktu komputasi yang cukup lama dan kurang cocok untuk pengambilan keputusan secara cepat. Sehingga, pada penelitian ini akan digunakan metode metaheuristik, yaitu Algoritma Genetik (GA), untuk menyelesaikan kasus tersebut. Percobaan akan dilakukan dengan menggukana kasus kecil dan kasus besar. Kasus kecil merupakan kasus akademik yang digunakan untuk memvalidasi metode metaheuristik yang diusulkan. Sedangkan, kasus besar akan digunakan untuk melihat performansi dari metode metaheuristik yang diusulkan. Data pada kasus besar merupakan data produksi harian ada salah satu perusahaan manufaktur truk di Perancis. Hasil yang diperoleh oleh algoritma genetika akan dibandingkan dengan hasil yang diperoleh oleh MILP. Analisa dilakukan dengan membandingkan kecepatan waktu komputasi dan kedekatakan dengan hasil yang diperoleh oleh MILP. Kata kunci : Mixed Model Assembly Line, Sequencing Problem, Metaheuristik

PENDAHULUAN Pada masa ini, permintaan kostumer terhadap produk spesific meningkat. Hal ini mengharuskan perusahaan manufaktur untuk memproduksi bermacam-macam jenis produk. Tingginya variasi produk menyebabkan manajemen produksi semakin sulit. Penggunaan pekerja dan mesin yang fleksibel adalah solusi umum sehingga berbagai macam jenis produk ISBN : 978-602-70604-0-1 A-23-1


dapat diproduksi dalam urutan produksi intermixed pada satu lini produksi yang sama, untuk mengurangi waktu dan biaya setup. Jenis lini produksi ini disebut sebagai Mixed Model Assembly Line (MMAL) (Boysen, dkk., 2009). Jenis lini assembly ini umumnya digunakan oleh industri otomotif dan barang konsumsi seperti: elektronik, furnitur dan pakaian. Ada dua jenis problem utama dalam MMAL: assembly line balancing dan product sequencing. Assembly line balancing adalah sebuah problem penempatan pekerjaan (task) pada suatu workstation. Objective dari problem ini adalah minimasi jumlah worksation yang dibutuhkan untuk memproduksi sebuah produk pada suatu lini produksi dengan cycle time yang telah diberikan, sebanding dengan rate produksi yang fix (Bautista dan Pereira, 2002). Product sequencing adalah problem untuk mengurutkan produk yang berbeda dalam satu lini assembly, sehingga work overload yang terjadi atau tingkat penggunaan part produksi dapat dapat diminimasi (Boysen, dkk., 2011). Work overload muncuk ketika berbagai macam jenis produk memiliki waktu proses yang berbeda-beda berada dalam satu workstation yang sama (Boysen, dkk., 2009). Work overload muncul ketika operator tidak dapat menyelesaikan tugas-tugas yang diperlukan pada produk dalam jendela waktu yang telah ditetapkan. Work overload kerja mengacu pada pekerjaan yang tersisa. Jika beberapa model intensif bekerja mengikuti satu sama lain di stasiun yang sama, work overload mungkin terjadi, dimana ini perlu dikompensasi, misalnya, dengan menambahkan pekerja tambahan. Work overloads dapat dihindari jika urutan produksi yang baik dapat ditemukan. Banyak penelitian telah dilakukan pada kedua kasus tersebut. Amen (2000), Chaves, dkk. (2009), Bautista dan Pereira (2002), dan sebagainya meneliti tentang problem assembly line balancing. Hyun, dkk. (1998), Ponnambalam, dkk. (2003), Cano- Belmán, dkk. (2010), Rahimi-Vahed, dkk. (2007a), Aroui, dkk. (2014) dan sebagainya meneliti tentang produk seqeuncing. Pada penelitian ini, permasalahan yang diteliti adalah permasalahan product seqeuncing. Pada problem product sequencing, beberapa peneliti meniliti tentang multi objectives, seperti: minimasi total utility work, minimasi total setup cost dan minimasi total variasi rate produksi (Hyun, dkk., 1998), minimasi total variasi rate produksi dan minimasi total setup cost (Ponnambalam, dkk., 2003). Peneliti lain meneliti tentang single objectives, seperti: minimasi total utility work (Cano- Belmán, dkk., (2010). Beberapa penelitian menggunakan metode eksak untuk kasus MMAL, sebagai contoh: Mixed Integer Linear Programming (Aroui, dkk., 2013), Bounded Dynamic Programming (Bautista, dkk., 1996). Beberapa penlitian lain menggunakan meta-heuristic, seperti Algoritma Genetika (Genetic Algotihm (GA)) (Hyun, dkk., 1998, Ponnambalan, dkk., 2003, Rahimi-Vahed, dkk., 2007c), Particle Swarm Optimization (PSO) (Mighorbani, dkk., 2007, Rahimi-Vahed, dkk., 2007a), Greedy Randomized Adaptive Search Procedure (GRASP) (Alpay, 2009), dan Ant Colony Optimization (ACO) (Zhu dan Zhang, 2011). Pada tahun 2013, Aroui, dkk. (2013) meniliti tentang problem product sequencing pada MMAL. Mereka memilih untuk bekerja langsung pada processing time produk untuk minimasi total work overload. Jenis pendekatan sperti ini masih jarang dikembangkan ada kebanyakan literatur (Aroui, dkk., 2013). Aroui, dkk. (2013) menggunakan kasus industri di salah satu pabrik Renault Truck Perancis sebagai kasus pada penelitiannya. Perakitan Truk merupakan salah satu jenis MMAL dengan tingkat diversifikasi produk yang tinggi dibandingkan dengan industri otomotif. Jenis kendaraan yang di produksi per hari lebih sedikit. Oleh karena itu, Aroui, dkk. (2013) memilih untuk menggunakan Mixed Integer Linear Programming (MILP) untuk kasus tersebut. Penemuan utama dari penelitian Aroui, dkk (2013) adalah hasil yang diperoleh seuqeunce dari MILP yang dihentikan setelah 2 jam perhitungan merupakan solusi ISBN : 978-602-70604-0-1 A-23-2


yang lebih baik dibandingkan dengan aktual manual prosedur pada Renaul Truck. Akan tetapi, Aroui, dkk. (2013) tidak dapat menemukan solusi optimal pada penelitian mereka. Hasil yang diperoleh oleh Aroui, dkk., (2013) memberikan hasil yang baik walaupun dengan waktu perhitungan yang lama. Akan tetapi, manager dituntut untuk dapat membuat keputusan tentang sequencing (urutan produk) secara cepat. Hal ini berkaitan dengan optimasi lini produksi harian pada perakitan Truck. Sehingga, dibutuhkan sebuah metode baru yang dapat menghasilkan nilai objektif yang setara dengan hasil yang diperoleh oleh Aroui, dkk. (2013), tetapi dengan waktu perhitungan yang cepat. Menggunakan kasus yang sama dengan penelitian Aroui, dkk. (2013), penelitian ini bertujuan untuk menemukan pendekatan yang lebih baik dalam hal waktu komputasi. Penelitian ini diharapkan tetap dapat menghasilkan hasil dengan kualitas yang sama dengan penelitian Aroui, dkk. (2013). Pada penelitian ini metode yang akan digunakan adalah Algoritma Genetika (GA). Hasil yang diperoleh akan dibandingkan berdasarkan kualitas solusi dan waktu komputasi dengan hasil MILP. DESKRIPSI MASALAH Mixed Model Assembly Line (MMAL) merupakan assembly line spesial dimana terdapat satu lini produksi yang digunakan untuk merakit beberapa jenis produk. Umumnya, jenis assembly line ini dapat ditemukan pada industri otomotif (Boysen, dkk., 2009). Ilustari dari jenis assembly line ini dapat dilihat pada Gambar 1. Produk pada MMAL bergerak menggunakan alat transportasi kontinu, umumnya menggunakan belt conveyor. Setiap produk memeliki waktu proses yang berbeda tetapi, cycle time pada setiap workstation adalah sama (konstan).

Gambar 1. Ilustrasi dari MMAL

Berdasarkan Boysen, dkk. (2009), sequencing problem dapat dikategorikan menjadi 3 macam: 1. Mixed-model sequencing: bertujuan untuk meminimasi work overload dengan menggunakan secara langsung (eksplisit) waktu operasi, waktu perpindahan pekerja, station border dan karakteristik lain dari lini produksi. 2. Car sequencing: bertujuan untuk meminimasi work overload dengan menggunakan faktor-faktor dan karakteristik dari lini produksi secara implisit. 3. Level scheduling: bertujuan untuk mencari keseimbangan antara rate penggunaan part actual dan rate penggunaan part ideal. Setiap tipe di atas memiliki subtipe yang didasarkan pada tipe lini produksi, station boundary, fungsi objektif, dll. (lebih detail lihat Boysen, dkk., 2009). Pada penelitian ini peneliti ISBN : 978-602-70604-0-1 A-23-3


meneliti tentang Mixed Model Sequencing Problem dengan fungsi objectif minimasi total work overload (MMSP-W). Untuk permasalahan yang digunakan, terdapat beberapa asumsi, yaitu: ‐ Line balancing telah dilakukan. Pekerjaan berbeda ditempatkan pada work stations yang berbeda. ‐ Produk bergerak dalam lini produksi dengan kecepatan konstan. Tidak ada buffer inventori di antara work station. ‐ Sebuah produk membutuh sejumlah pekerjaan tertentu (pekerjaan dengan waktu operasi tertentu) untuk setiap posisi. Waktu operasi dterministik. Waktu setup dan waktu yang dibutuhkan oleh operator untuk kembali ke posisi awal pada akhir pekerjaan sudah termasuk dalam total waktu operasi. Operator merupakan operaot regular yang bekerja pada setiap kendaraan mi (lihat Gambar 2). Setiap kendaraan membutuh sejumlah pekerjaan tertentu (pekerjaan dengan waktu operasi tertentu) untuk setiap posisi. Cycle time adalah waktu antara dua pekerjaan suksesif. Cycle time dinotasikan sebagai  . Delay terjadi ketika pekerjaan pada satu kendaraan tidak dapat diselesaikan dengan waktu cycle time yang telah diberikan (liat Gambar 2).

Work overload

Gambar 2. Ilustasi Delay (sumber: Aroui, dkk., 2013)

Berdasarkan Aroui, dkk. (2013), permasalahn ini diformulasikan sebagai berikut: p

n

Min r jp

(1)

p 1 j 1

Subject to: c jp  r j 1, p   d ip xij

j p

(2)

r jp  0

j p

(3)

r jp  c jp

j p

(4)

i 1

n

x

ij

1

i

(5)

ij

1

j

(6)

xij  0,1

i j

(7)

c jp , rjp  

j p

(8)

j 1 n

x i 1

ISBN : 978-602-70604-0-1 A-23-4


Di mana, : Jumlah produk n : Indeks produk i j : Indeks posisi : Indeks operator p : Cycle time  : Waktu proses yang dibutuhkan oleh produk i untuk operator p tip d ip

: Delay atau tardiness untuk operator, d ip  t ip  

xij

: Bernilai 1 jika produk i ditempatkan pada posisi j, jika tidak 0

c jp

: Delay or idle time untuk operator p untuk product pada posisi j

r jp

: Work overload operator p untuk produk pada posisi j

Fungsi objektif (1) minimasi total work overload. Konstrain (2) menggambarkan delay atau idle time dari product pada posisi j merupakan delaynya sendiri ditambah dengan tambahan overload dari posisi j 1. Konstrain (3) dan (4) mengindikasi bahwa 0, karena fungsi objektif hanya mengakomodasi delay (dan bukan idle times). Konstrain (5) menjamin bahwa hanya satu posisi yang ditempati oleh satu produk. Konstrain (6) mengindikasi bahwa hanya satu produk ditempatkan pada satu posisi dalam sequence. Dan konstrain (7)c menunjukkan bahwa vairabel yang digunakan adalah bilangan biner. PENDEKATAN METAHEURISTIK (ALGORITMA GENETIKA) Objective dari penelitian ini adalah untuk menemukan solusi yang sama yang ditemukan oleh Aroui, dkk. (2013), dengan waktu komputasi yang lebih cepat. Metaheuristik dipilih karena dapat beradaptasi dengan baik untuk kasus-kasus sulit dalam konteks industri. Metaheuristik yang didesain dengan baik umumnya dapat menghasilkan solusi yang baik dalam waktu komputasi yang cepat. Pada penelitian ini akan digunakan Algoritma Genetika (GA). Pada penelitian ini akan digunakan dua buah kasus: kasus kecil (kasus akademik) dan kasus besar (Renault Truck). Hasil yang diperoleh akan dibandingkan dengan hasil yang diperoleh dengan MILP dari Aroui, dkk. (2013). Analisa dilakukan berdasarkan kualitas solusi dan waktu komputasi. Algoritma Genetika (GA) ditemukan oleh John Holland pada tahun 1960 (Yang, 2010). Algorithma ini didasarkan pada teori seleksi alam Darwin. Ada populasi inisial yang terdiri dari beberapa kromosom. Kromosom ini merepresentasikan solusi dalam bentuk urutan produksi (vehicle sequencing). Populasi ini akan berevolusi karena operasi gentik untuk memperbaiki solusi. Ada tiga elemen dasar (operasi) pada algoritma genetika: reproduksi, crossover, dan mutasi. Element lain dari GA disebut sebagai fungsi fitness. Fungsi fitness menunjukkan kemampuan individu untuk bertahan hidup dalam populasi (Yang, 2010, Kim, dkk., 1996), dan diukur berdasarkan fungsi objektif yang akan dioptimasi (Kim, dkk., 1996). Untuk permasalahan maksimasi, fitness setara atau berbanding lurus dengan fungsi objektif (f(x)). Akan tetapi, untuk permasalahan minimasi, fitness berbanding terbalik dengan fungsi objektif (1/f(x)) (Ahmed, 2010). Santosa dan Willy merumuskan fitness seperti dalam persamaan (9). Konstanta 1 untuk menjaga agar fitness tidak menjadi ∞, ketika f(x) = 0.

ISBN : 978-602-70604-0-1 A-23-5


F  x 

1 1  f  x

(9)

Di mana, F  x  : Fitness, f  x  : Fungsi Objektif. Pada GA, terdapat beberapa parameters, seperti: jumlah kromosom dalam satu populasi, jumlah kromosom elite, probabilitas crossover, dan probabilitas mutasi. Probanilitas crossover (pc) umumnya sangat tinggi, berada diantara 0,7 sampai 1,0. Sedangkan probabiltas mutasi (pm) umumnya sangat kecil (antara 0,001 ~ 0,05). Jika pc terlalu kecil, crossover jarang terjadi, sehingga tidak efisien untuk proses evolusi. Jika probabilitas mutasi terlalu tinggi, solusi dapat “melompat-lompat” bahkan ketika sudah mendekati solusi optimal (Yang, 2010). Kromosom elite merupakan kromosom yang akan dijaga untuk generasi berikutnya tanpa termodifikasi oleh operator genetik. Tujuan dari proses elitism untuk menjaga solusi yang baik tetap berada dalam populasi. Pseudo kode untuk GA terdapat dalam Gambar 3. Dalam GA ini, terdapat beberapa perubahan karena algoritma dasar yang umum digunakan dalam GA tidak bekerja dengan baik pada kasus yang diteliti. Beberapa perubahan yang dilakukan yaitu : ‐ Crossover dan Mutasi selalu dilakukan pada tiap iterasi (pc = pm = 1). ‐ Individu anak hanya diterima jika memiliki fitness yang lebih baik dari fitness induk mereka. ‐ Mutasi dilaukan pada tiga kromosom terbaik dengan menggunakan tiga jenis mutasi (Swap, Flip dan Slide). Genetic Algorithm for MMSP-W Generate Initial sequence Calculating the objective Calculating fitness Find The best sequence while Condition not meet do Elitism Re-Calculate Objective Re-Calculating fitness Chromosome Selection & Cross Over do Fortune Wheel Selection if random number < Crossover Probability do Crossover if The child is better Replace parent. else Cancel the crossover end end Re do the Elitism Mutation if random number < Mutation Probability Mutate the Best to get Three New Routes Mutation 1 : Flip Mutation 2 : Swap Mutation 3 : Slide end end

Gambar 3. Pseudo Code GA untuk MMSP-W ISBN : 978-602-70604-0-1 A-23-6


Detail mengenai bagaimana pemilihan kandidat induk, crossover dan mutasi akan dijelaskan pada subbab berikutnya. Kromosom dan Gen Inti dari algoritma genetika adalah encoding dari fungsi optimasi sebagai array dari bit atau karakter string untuk mewakili kromosom, operasi manipulasi string dengan operator genetik, dan seleksi sesuai fitness dengan tujuan untuk menemukan solusi untuk masalah yang dihadapi (Yang, 2010). Array dari bit atau string yang dikenal sebagai gen. Dalam kasus kami, kromosom adalah urutan produk. Dan gen merupakan produk i dalam posisi j dalam urutan produksi.

Gambar 4. Representasi Kromosom dan Gen

Elitisme Individu-individu terbaik dengan fitness yang lebih tinggi harus dijaga dan diteruskan ke generasi berikutnya. Elitisme adalah suatu proses untuk memilih individu yang paling baik (dalam setiap generasi) yang akan dibawa ke generasi baru tanpa dimodifikasi oleh operator genetik (Yang, 2010). Dalam penelitian ini, digunakan 4 kromosom elite pada setiap iterasi. Pemilihan Induk & Crossover Parent atau induk adalah kromosom yang dipilih untuk melakukan proses crossover. Dan seleksi induk dilakukan berdasarkan fitness. Induk dengan fitness yang tinggi dipasangkan dengan induk dengan fitness tinggi yang lain untuk melakukan reproduksi (crossover). Kemudian induk dengan fitness rendah dipasangkan dengan induk berfitness rendah lain. Induk yang telah dipilih tidak dapat dipilih kembali (tidak ada induk yang dipilih 2 kali). Crossover adalah pertukaran materi genetik antara kromosom induk untuk menghasilkan kromosom baru (anak). Crossover dilakukan untuk semua kromosom, kecuali kromosom elite. Induk dipasangkan berdasarkan fitness. Penjelasan lebih rinci dapat dilihat pada Gambar 5. Dalam contoh ini, ada 6 induk. Induk 1 dipasangkan dengan induk 3 dalam penarikan pertama. Kemudian, dalam penarikan kedua di antara induk yang tersisa, induk 2 dipasangkan dengan induk 4 (menurut fitness). Dan terakhir, induk 5 dipasangkan dengan induk 6. Dengan skema ini, semua induk memiliki pasangan untuk melakukan proses crossover. Tidak ada induk yang dipasangkan dengan diri mereka sendiri atau melakukan crossover dua kali.

Gambar 5. Seleksi Induk dan Crossover ISBN : 978-602-70604-0-1 A-23-7


Dalam proses Crossover sendiri, hanya one point crossover yang digunakan, yaitu ketika sebuah titik potong tunggal pada kromosom kedua induk dipilih. Semua data yang melampaui titik ini pada kedua kromosom akan ditukar. Titik crossover dipilih secara acak. Secara umum, proses crossover dilakukan seperti yang diilustrasikan pada Gambar 6.

Gambar 6. Proses Crossover

Terdapat dua induk, A dan B, dan titik potong setelah gen nomor 2 (posisi 2 dipilih secara acak). Setelah operasi crossover, diperoleh 2 anak, X dan Y. Anak X mewarisi dua gen yang pertama dari induk A dan sisanya 3 gen dari induk B. (invers berlaku untuk anak Y). Tak satu pun dari anak valid karena gen diulang dua kali dan ada satu produk yang belum terdaftar. Di sini harus direvisi bagian sebelum crossover point (gen no. 2). Untuk anak X, harus direvisi dua gen pertama. Dan produk yang belum tercantum adalah produk no. 5. Terdapat dua pilihan untuk menggantikan dua gen pertama, yaitu 5-2 atau 2-5. Karena bagian ini berasal dari induk A dan induk A memiliki urutan 1-2-3-4-5 (lihat Gambar 6), ditempatkan urutan 2-5 bukan 5-2 untuk anak X. Proses yang sama dilakukan untuk anak kedua. Ketika kedua anak valid, diperiksa fitness mereka. Jika fitness anak lebih baik daripada fitness induk, maka induk terburuk diganti dengan anak, jika tidak induk tetap dalam populasi. Proses ini dilakukan untuk menjaga individu yang lebih baik tetap dalam populasi seperti dalam prosedur elitisme. Sehingga, jika fitness tidak cukup baik, dapat dikatakan bahwa anak tidak dapat bertahan dalam populasi atau mati pada iterasi berikutnya. Mutasi Mutasi adalah operator genetik yang digunakan untuk menjaga keragaman genetik dari satu generasi ke generasi berikutnya. Dalam kasus kami, Mutasi dilakukan terhadap tiga dari empat kromosom elit di setiap iterasi. Mutasi dilakukan dengan menggunakan tiga prosedur: swap, flip, dan slide. Semua proses ini (gen yang mana akan menggantikan gen yang mana) dilakukan secara acak. Dihasilkan dua nomor acak yang sesuai dengan posisi j dalam urutan (gen j dalam kromosom).

Gambar 7. Proses Mutasi

ISBN : 978-602-70604-0-1 A-23-8


Swap dilakukan dengan menukar dua gen. Sebagai contoh, kita menghasilkan dua nomor acak sesuai dengan posisi 1 dan 5. Kemudian ditukar antara produk 2 dan produk 1 (Gambar 7.a). Flip atau invers dilakukan dengan membalik urutan gen yang dipilih. Pada Gambar 7.b, dipilih secara acak posisi 4 (yang merupakan produk 3 di sini) dan posisi 2 (yang merupakan produk 5), maka kita membalikkan urutan 5-4-3 ke 3-4-5. Slide dilakukan dengan menggeser gen, misalnya, berdasarkan pilihan acak, kita geser posisi 4 ke posisi 2. Di sini kita mendapatkan produk 3 (yang berada di posisi 4) dan kemudian kita geser ke posisi 2 dari urutan. Jadi, kita mengubah urutan dari 5-4-3 menjadi 3-5-4 (Gambar 7.c). HASIL DAN PEMBAHASAN Pengujian dilakukan untuk mengevaluasi kinerja Algoritma Genetika. Pengujian dibagi menjadi dua set contoh: contoh kecil (contoh akademik) dan contoh besar (kasus nyata dari data industri). Contoh kecil yang digunakan untuk memeriksa apakah algoritma bekerja dengan benar atau tidak. Contoh besar digunakan untuk memeriksa kinerja algoritma pada kasus nyata. Sebuah contoh dikarakterisasi dengan jumlah workstation, jumlah produk untuk diurutkan dan waktu proses produk pada workstation tertentu. Contoh besar berasal dari studi kasus industri (pabrik Renault Truck di Bourg-en-Bress, Perancis). Pengujian kedua kasus dilakukan, menggunakan MATLAB, di komputer Intel Core i5 - 2,4 GHz - 4 GB RAM. Hasilnya dibandingkan dengan hasil yang diperoleh oleh Mixed Integer Linear Program (MILP) yang dikembangkan oleh Aroui, dkk. (2013), berdasarkan waktu komputasi dan kualitas hasil (efisiensi). Peru diperhatikan bahwa MILP diselesaikan menggunakan CPLEX pada komputer yang sama. Contoh kecil terdiri dari dua set data: data untuk single workstation dan data untuk multi workstation. Pada kategori single workstation terdapat 17 contoh yang diambil dari Aroui, dkk (2013), bernama WS1 sampai WS17 dengan 20 produk untuk diurutkan. Untuk setiap contoh, dilakukan 10 kali percobaan untuk melihat range solusi yang didapatkan. Tabel 1 menyajikan hasil terbaik - terburuk nilai fungsi tujuan dan waktu perhitungan untuk GA, bersama-sama dengan hasil yang diperoleh dari MILP untuk contoh yang sama. Perhitungan waktu terpanjang tidak selalu berkorelasi dengan fungsi tujuan terbaik. Solusi awal atau urutan awal dihasilkan secara acak. Tabel 1 Rekapitulasi Hasil GA untuk single workstation 20 produk

ISBN : 978-602-70604-0-1 A-23-9


Untuk set data ini, kita tidak selalu mampu menemukan hasil yang optimal. Efisiensi dihitung seperti pada Persamaan (10). Misalnya, dalam WS8, 2 dari 10 percobaan hanya mendapatkan 98% dari optimal. Untuk kasus kecil dengan 20 produk, dapat dilihat bahwa Algoritma Genetika (GA) membutuhkan lebih banyak waktu untuk mencapai optimal daripada metode CPLEX (MILP). Algoritma Genetika menggunakan lebih dari satu solusi dalam setiap iterasi. Setiap solusi perlu menghitung fungsi tujuan. Sehingga, GA membutuhkan lebih banyak waktu perhitungan dari MILP.

 Algorithm Solution  Optimal Solution    100% Efficiency  1  Optimal Solution  

(1)

Untuk masalah single workstation, diujikan juga kasus dari 43 produk. Untuk set ini kasus, MILP tidak dapat menemukan solusi optimal setelah 30 menit eksekusi. Tabel 2 menyajikan solusi terbaik ditemukan oleh MILP pada akhir 30 menit dan juga hasil GA. Untuk jenis contoh, Algoritma Genetika mendapat kualitas yang hampir sama (berdasarkan efisiensi) dengan CPLEX (MILP), tetapi dengan perhitungan yang jauh lebih cepat. Tabel 2 Rekapitulasi Hasil GA untuk single workstation 43 produk

Secara umum, Algoritma Genetika dapat mencapai hasil yang baik dalam kedua kasus dari 20 produk dan 43 produk. Untuk jumlah produk yang lebih besar (43 produk), hasil yang diperoleh oleh GA cukup menjanjikan dibandingkan dengan MILP karena trade-off antara kualitas solusi dan kecepatan perhitungan GA sangat baik. Untuk kasus multiple workstation, dilakukan tes pada 3 kasus dengan 4 workstation dan 20 produk. Tabel 3 Rekapitulasi Hasil GA untuk 4 workstation 20 produk

Untuk set kasus ini, MILP menemukan solusi optimum (lihat tabel 3.3). Performa Algoritma Genetika melampaui metode MILP dalam hal waktu perhitungan. Namun, dari segi kualitas solusi, Algoritma Genetika tidak dapat selalu menjamin untuk mendapatkan nilai optimal. Dalam kasus terburuk, GA masih dapat memberikan setidaknya 91% dari nilai optimal. Pada bagian tes yang dilakukan untuk pada Data industri Renault Trucks, terdapat 9 kasus dengan 56 ~ 61 produk dan 77 workstation, masing-masing sesuai dengan data produksi per hari.

ISBN : 978-602-70604-0-1 A-23-10


Tabel 4 Rekapitulasi Hasil GA untuk data industri

Untuk hal ini, GA memberikan hasil yang sangat baik. Perlu diperhatikan bahwa MILP dihentikan pada akhir 1 jam dan solusi terbaik yang ditemukan dicatat pada Tabel 4. MILP menemukan solusi yang hampir sama pada akhir 1 jam. Algoritma genetik dapat mencapai solusi -3% ~ 7% lebih baik daripada solusi MILP. Perhitungan waktu juga jauh lebih cepat daripada MILP. Dapat disimpulkan bahwa algoritma genetika lebih efisien daripada MILP untuk hal ini. KESIMPULAN DAN SARAN Kesimpulan dari hasil penelitian ini adalah telah berhasil diterapkan meta-heuristik untuk menyelesaikan masalah Mixed Model Assembly Line Sequencing, dalam kasus minimasi work overload. Meta-heuristik mencapai solusi dengan kualitas baik dan waktu komputasi yang lebih cepat dibandingkan dengan model MILP. Algoritma Genetika mendapatkan solusi optimal dalam hampir semua kasus kecil. Untuk contoh besar, GA memberikan hasil yang sangat baik; dalam rata-rata 5 ~ 6 menit GA mencapai solusi -3% ~ 7% lebih baik daripada solusi perhitungan 1 jam MILP. Waktu perhitungan GA juga jauh lebih cepat daripada MILP. GA lebih efisien daripada MILP dalam hal ini. GA merupakan prosedur yang baik untuk pengguna industri. GA cukup cepat dan memberikan solusi yang lebih baik daripada solusi manual saat ini. Untuk memperbaiki hasil penelitian ini, maka ada beberapa saran. 1. Penelitian ini masih dapat ditingkatkan pada beberapa aspek seperti: jenis operator, metode, dan tujuan. Seperti dilansir Aroui, dkk., (2014) dalam penelitian lebih lanjut mereka, mereka mengungkapkan bahwa ada jenis lain dari operator dalam kasus industri, misalnya, operator bekerja hanya pada kendaraan tertentu atau operator yang bekerja bersama-sama dengan operator lain. Meta-heuristik dapat diperpanjang untuk model operator seperti itu juga. 2. Dapat juga melihat Dynamic Programing sebagai alternatif metode meta-heuristik untuk menyelesaikan kasus ini. 3. Dalam hal fungsi tujuan, fungsi tujuan tunggal dapat diperluas untuk kasus multi-tujuan dengan memperhitungkan realitas industri. Misalnya, meminimalkan work overload dan meminimalkan penggunaan part rate pada saat yang sama.

ISBN : 978-602-70604-0-1 A-23-11


DAFTAR PUSTAKA Ahmed, Z., 2010. Genetic algorithm for the traveling salesman problem using sequential constructive crossover operator. J. Biometrics Bioinforma. 96–105. Alpay, Ş., 2009. GRASP with path relinking for a multiple objective sequencing problem for a mixed-model assembly line. Int. J. Prod. Res. 47, 6001–6017. Amen, M., 2000. Heuristic methods for cost-oriented assembly line balancing: A survey. Int. J. Prod. Econ. 68, 1–14. Aroui, K., Alpan, G., Frein, Y., 2014. Minimizing work overload in mixed model assembly lines: A case study from truck industry, in: International Conference on Information Systems, Logistic, and Supply Chain. Breda. Aroui, K., Alpan, G., Frein, Y., Thomazeau, J., 2013. Minimisation des retards dans le séquencement des véhicules sur une ligne d’assemblage multi modèles, in: 5èmes Journées Doctorales/Journées Nationales MACS. Bautista, J., Pereira, J., 2002. Ant algorithms for assembly line balancing. Ant Algorithms 65– 75. Boysen, N., Fliedner, M., Scholl, A., 2009. Sequencing mixed-model assembly lines: Survey, classification and model critique. Eur. J. Oper. Res. 192, 349–373. Boysen, N., Kiel, M., Scholl, A., 2011. Sequencing mixed-model assembly lines to minimise the number of work overload situations. Int. J. Prod. Res. 49, 4735–4760. Cano-Belmán, J., Ríos-Mercado, R.Z., Bautista, J., 2010. A scatter search based hyper-heuristic for sequencing a mixed-model assembly line. J. Heuristics 16, 749–770. Hyun, C.J., Kim, Y.K., Kim, Y.K., 1998. A genetic algorithm for multiple objective sequencing problems in mixed model assembly lines. Comput. Oper. Res. 25, 675–690. Ponnambalam, S.. G., Aravindan, P., Subba Rao, M., 2003. Genetic algorithms for sequencing problems in mixed model assembly lines. Comput. Ind. Eng. 45, 669–690. Rahimi-Vahed, A., Mirzaei, A.H., 2007. A hybrid multi-objective shuffled frog-leaping algorithm for a mixed-model assembly line sequencing problem. Comput. Ind. Eng. 53, 642–666. Rahimi-Vahed, A.R., Mirghorbani, S.M., Rabbani, M., 2007a. A new particle swarm algorithm for a multi-objective mixed-model assembly line sequencing problem. Soft Comput. 11, 997–1012. Rahimi-Vahed, A.R., Mirghorbani, S.M., Rabbani, M., 2007b. A hybrid multi-objective particle swarm algorithm for a mixed-model assembly line sequencing problem. Eng. Optim. 39, 877–898. Rahimi-Vahed, A.R., Rabbani, M., Tavakkoli-Moghaddam, R., Torabi, S.A., Jolai, F., 2007c. A multi-objective scatter search for a mixed-model assembly line sequencing problem. Adv. Eng. Informatics 21, 85–99.

ISBN : 978-602-70604-0-1 A-23-12


Santosa, B., Willy, P., 2011. Metoda Metaheuristik Konsep dan Implementasi. Surabaya, Guna Widya. Yang, X.S., 2010. Nature-Inspired Metaheuristic Algorithms, Second Edi. ed. Luniver Press. Zhu, Q., Zhang, J., 2011. Ant colony optimisation with elitist ant for sequencing problem in a mixed model assembly line. Int. J. Prod. Res. 49, 4605–4626.

ISBN : 978-602-70604-0-1 A-23-13

APLIKASI METODE METAHEURISTIK UNTUK KASUS SEQUENCING PADA MIXED MODEL ASSEMBLY LINE

Recommend Documents