## PENJADWALAN FLOW SHOP MESIN PARALEL MENGGUNAKAN METODE LONGEST PROCESSING TIME DAN CROSS ENTROPY - GENETIC ALGORITHM
PADA PEMBUATAN PRODUK STEEL BRIDGE B-60
Yusraini Muharni 1) , Ade Irman Saeful M 2) , Tania Ero Rubyanti 3)
1,2) Program Studi Teknik Industri, Fakultas Teknik, Universitas Sultan Ageng Tirtayasa, Banten
3) Laboratorium Sistem Produksi, Program Studi Teknik Industri, Fakultas Teknik, Universitas Sultan Ageng Tirtayasa, Banten e-mail: yusraini@untirta.ac.id; irman@untirta.ac.id; taniaero.te@gmail.com

## ABSTRAK
Sistem  produksi  di  sebuah  perusahaan  fabrikasi  seingkali  mengalami  permasalahan  salah satunya  adalah  ketika  perusahaan  tidak  mampu  mengirim  order  kepada  customer  di  waktu yang  telah  ditentukan.  Hal  ini  dapat  menyebabkan  perusahaan  harus  menanggung  biaya pinalti.  Masalah  ini  dapat  diatasi  apabila  dilakukannya  penjadwalan  produksi  dengan  baik. Pentingnya  penjadwalan  produksi  adalah  untuk  mengelola  dengan  tepat  sumber  daya  yang ada  agar  terciptanya  efektivitas  dan  efisiensi  dalam  penggunaan  sumber  daya.  Salah  satu usaha  yang  dilakukan  untuk  tercapainya  penjadwalan  yang  optimal  adalah  dengan meminimalkan makespan. Produk Steel Bridge B-60 merupakan salah satu dari jenis jembatan Truss  Bridge  yang  diproduksi  oleh  Perusahan  Fabrikasi  Baja  Struktur  Kontruksi  yang berlokasi di Cilegon.  Perusahan tersebut  memiliki sistem produksi make to order dengan alur produksi  flow  shop dan  susunan  mesin  paralel.  Penelitian  ini dilakukan dengan  menerapkan pendekatan  heuristic  metode  LPT  (Longest  Processing  Time)  dan  pendekatan  metaheuristic dengan menggunakan metode Cross Entropy yang dikombinasikan dengan Genetic Algorithm yang  dikenal  dengan  sebutan  CEGA  (Cross  Entropy  Genetic  Algortihm).  Algoritma metaheuristic  diterjemahkan  ke  dalam  Bahasa  pemograman  Matlab.  Hasil  perbandingan kedua metode menunjukkan bahwa kedua metode usulan yaitu LPT dan CEGA lebih baik dari metode eksisting dan memiliki efisiensi sebesar 7.94%.
Kata  kunci :  Penjadwalan  Flow  Shop,  Mesin  Paralel,  Longest  Processing  Time,  Cross Entropy, Genetic Algorithm.

## ABSTRACT
The  production  system  in  a  fabrication company often experiences problems, one of which is when  the  company  is  unable  to deliver  product  to  the  customer  at a  specified time.  This can cause  the  company  to  bear  the  cost  of  penalties.  This  problem  can  be  overcome  if  the production  schedule  is  arranged  properly.  The  importance  of  production  scheduling  is  to accurately manage existing resources in order to create effectiveness and efficiency in the use of resources. One of the efforts made to achieve optimal scheduling is to minimize makespan. Steel Bridge B-60 is one of the Truss Bridge bridges produced by the Construction Structural Steel Fabrication Company located in Cilegon. The company has a make to order production system with flow shop production lines and parallel machine arrangements. This research was carried out by applying the heuristic approach of the LPT (Longest Processing Time) method and  the  metaheuristic  approach  using  the  Cross  Entropy  method  combined  with  the  Genetic Algorithm known as CEGA (Cross Entropy Genetic Algortihm). The metaheuristic algorithm is translated  into  the  Matlab  programming  language. The  results  of the  comparison  of  the  two methods indicate that the two proposed methods, namely LPT and CEGA, are better than the existing method and have an efficiency of 7.94%.
Keywords : Flow Shop Scheduling, Paralel Machine, Longest Processing Time, Cross Entropy, Genetic Algorithm.

## PENDAHULUAN
Sistem  produksi  di  sebuah  perusahaan  fabrikasi  seingkali  mengalami  permasalahan salah satunya adalah ketika perusahaan tidak mampu mengirim order kepada customer di waktu  yang  telah  ditentukan.  Hal  ini  dapat  menyebabkan  perusahaan  harus  menanggung biaya pinalti. Salah satu penyebab keterlambatan pengiriman kepada customer yaitu belum optimalnya  perencanaan  produksi  yang  dibuat  khususnya  dalam  pengalokasian  sumber
Penjadwalan Flow Shop Mesin Paralel Menggunakan Metode Longest Processing Time dan Cross Entropy- Genetic Algorithm pada Pembuatan Produk Steel Bridge B-60 Yusraini Muharni, Ade Irman Saeful M, Tania Ero Rubyanti
daya. Pentingnya penjadwalan produksi adalah untuk mengelola dengan tepat sumber daya agar terciptanya efektivitas dan efisiensi penggunaan sumber daya. Salah satu usaha yang dilakukan  untuk  tercapainya  penjadwalan  yang  optimal  adalah  dengan  meminimalkan makespan  1  .

## Latar Belakang
PT  XYZ  adalah  perusahaan  yang  bergerak  di  bidang  konstruksi,  perpipaan,  dan tangki.  Saat  ini  produk  dan  layanan  utamanya  adalah stocking besi  dan  baja,  fabrikasi struktur baja, konstruksi jembatan, dan alat berat. PT XYZ memiliki sistem produksi make to  order dimana  perusahaan  baru  akan  membuat  produk  ketika order datang.  Meski memiliki sistem make to order , alur produksi di perusahaan ini dilakukan secara flow shop dimana  urutan  mesin  pada  setiap job adalah  tetap.  Dalam  menjalankan  kegiatan produksinya,  PT  XYZ  memiliki  beberapa  jenis  mesin  yang  tersusun  paralel  dengan susunan jumlah yang berbeda.
Salah  satu  keterlambatan  pengiriman  terjadi  ketika  pembuatan Steel  Bridge B-60 yang merupakan salah satu dari jenis jembatan Truss Bridge . PT XYZ mempunyai priority rules dari perusahaan yaitu part Cross Grider (CG) , Top Chord (TC) , Bottom Chord (BC) , Diagonal Chord (DG) , dan Stringer (ST) dikerjakan di awal karena memiliki dimensi yang paling besar. Maka dari itu, penelitian ini memiliki beberapa batasan diantaranya penelitian penjadwalan  ini  dibatasi  hanya  pada  lima  part  yang  memiliki  urutan  pekerjaan  tetap tersebut dengan tujuan meminimumkan makespan, tidak menggunakan parameter due-date serta penjadwalan dalam penelitian ini merupakan jenis permutation scheduling . Penelitian ini juga memiliki beberapa asumsi yaitu keadaan mesin saat produksi adalah normal, tidak ada yang dalam proses maintenance atau shut down , seluruh bahan baku sudah tersedia di awal produksi dan waktu transportasi sudah termasuk waktu set-up , dan waktu set-up akan disatukan dengan waktu proses menjadi total time .
Penelitian  ini  dilakukan  dengan  pendekatan heuristic metode  LPT  ( Longest Processing  Time )  dan  pendekatan metaheuristic dengan  menggunakan  metode Cross Entropy yang dikombinasikan  dengan Genetic Algorithm menjadi CEGA ( Cross Entropy Genetic  Algortihm ).  Kedua  metode  ini  akan  dibandingkan  dengan  penjadwalan  produksi metode eksisting yang dilakukan perusahaan.

## Tujuan Penelitian
Tujuan dari penelitian ini yaitu:
1. Mengusulkan urutan pekerjaan yang lebih baik dalam proses produksi Steel Bridge B- 60.
2. Menghitung makespan sebelum  dan  sesudah  adanya  usulan flow  shop  scheduling dalam proses produksi Steel Bridge B-60.
3. Menghitung  persen  efisiensi makespan yang  membandingkan  antara metode perusahaan dengan metode usulan terbaik.

## TINJAUAN PUSTAKA Penjadwalan
Penjadwalan dapat diartikan sebagai pengalokasian sejumlah sumber daya ( resource ) untuk melakukan sejumlah tugas atau operasi dalam jangka waktu tertentu dan merupakan proses pengambilan keputusan yang peranannya sangat penting dalam industri  manufaktur dan  jasa  yaitu  mengalokasikan  sumber-sumber  daya  yang  ada  agar  tujuan  dan  sasaran perusahaan lebih optimal  2  .

## Metode Longest Processing Time
Algoritma  heuristik  ini  merupakan  salah  satu  metode  yang  bisa  digunakan  untuk pengurutan  pada  mesin  paralel  dengan  parameter makespan .  Dengan  aturan  ini,  proses dengan  waktu  operasi  yang  paling  panjang  akan  dijadwalkan  terlebih  dahulu.  Aturan  ini juga  sangat  sederhana  yaitu  dengan  cara  mengurutkan  pekerjaan  dari  yang  mempunyai waktu  proses  terbesar  hingga  yang  terkecil  (t1≥  t2≥…≥  tn).  Setelah  itu  penjadwalan dilakukan berdasarkan urutan tersebut.
Metode Cross Entropy - Genetic Algorithm (CEGA) Algoritma  CEGA Cross  Entropy  -  Genetic  Algorithm merupakan  pengembangan algoritma  yaitu  kombinasi  algoritma Cross  Entropy dan Genetic  Algorithm (CEGA). Kombinasi  algoritma  ini  bertujuan  memperluas  pencarian  solusi  pada  sampel  elit Cross Entropy (CE)  ketika  berada  di  lokal  optimal  dengan  menambahkan  mekanisme  pindah silang dan mutasi pada Genetic Algorithm (GA) yang berfungsi menghindari kemungkinan pencarian solusi terjebak di area lokal optimal, karena mekanisme GA dapat menghasilkan kromosom  baru  yang  memiliki  sifat  tetap  menjaga nature kromosom  pada  populasi awalnya  3  .

## METODE PENELITIAN
Flow Chart Metode Longest Processing Time (LPT) Berikut  ini  (Gambar  1)  merupakan flow  chart dalam  melakukan  penjadwalan dengan metode Longest Processing Time (LPT):
Mulai Mengurutkan job berdasarkan aturan LPT kedalam list S Memilih Job teratas dari list S Menjadwalkan job pada mesin k terpilih Selesai Mengeluarkan job yang telah dijadwalkan dari list S List S = 0 Ya Tidak Mengidentifikasi job order dan notasi variabel yang akan digunakan
Gambar 1. Flow Chart Metode LPT

## Flow Chart Metode CEGA
Gambar  2  merupakan flow  chart yang  menggambarkan  langkah-langkah  dalam melakukan penjadwalan dengan metode CEGA:
Penjadwalan Flow Shop Mesin Paralel Menggunakan Metode Longest Processing Time dan Cross Entropy- Genetic Algorithm pada Pembuatan Produk Steel Bridge B-60 Yusraini Muharni, Ade Irman Saeful M, Tania Ero Rubyanti
Mulai Penentuan Nilai Parameter Inisial (Input N, α ,Ρ dan Stopping Criteria) Pembangkitan Sampel Random Awal Sejumlah N Perhitungan Fungsi Tujuan ( Makespan ) Kriteria Pemberhentian Terpenuhi Selesai Ya Tidak Solusi Optimal Pemilihan Sampel Elit Pembobotan Sampel Elit Perhitungan Linear Fitness Rangking (LFR) Update Parameter Pindah Silang Penentuan Elitisme Penentuan Kromosom Induk Crossover (2-Point order cross over) Mutasi - Swap Mutation (menukar) - Flip Mutation (membalik)
- Slide Mutation (menggeser)
Gambar 2. Flow Chart Metode CEGA

## HASIL DAN PEMBAHASAN
Tabel  1  merupakan  data  waktu  total job yang  diperoleh  dari  pengolahan  data sekunder dengan menambahkan waktu setup dan proses setiap job pada setiap mesin, dan mengalikannya dengan jumlah part .

## Tabel 1. Waktu Total
Job Mesin/Job Cutting (menit) Fit-Up Machine (menit) Welding LMH (menit) Strigthening (menit) Fit-Up Fab (menit) Welding (menit) Finishing (menit) TB60-CG 89.06 131.84 419.34 155.12 284.79 288.60 76.38 TB60-TC 150.70 220.96 638.86 262.28 478.70 487.04 130.84 TB60-BC 160.56 244.12 707.76 279.16 532.80 526.60 135.08 TB60-DG 323.40 484.52 1545.00 562.24 1056.68 1058.92 274.64 TB60-ST 565.04 751.90 2431.32 975.14 1679.08 1678.08 313.40
Adapun berikut ini (Tabel 2) merupakan data jumlah stasiun dan jumlah mesin yang ada di PT. XYZ.
Tabel 2. Jumlah Mesin Tersedia No Machine Name Quantity of Machine 1 Cuting Machine 1 2 Fit-Up Machine 1 3 Welding LMH 2 4 Strigthening 1 5 Fit-Up Fab 2 6 Welding (Manual) 3 7 Finishing Station 2

## Penjadwalan Eksisting PT XYZ
Berikut ini merupakan penjadwalan eksisting perusahaan dengan urutan job 1-2-3-4- 5 yang diterjemahkan ke dalam bentuk gantt chart.

## Gambar 3. Penjadwalan Eksisting Perusahaan
Gambar  3  merupakan gantt  chart penjadwalan  eksisting, gantt  chart tersebut  disusun berdasarkan aliran  produksi perusahaan yaitu flow shop , dimana aliran  produksi  memiliki kesamaan urutan operasi (routin g) untuk semua job , dan setiap job baru akan bisa diproses dalam  sebuah  mesin  apabila  proses  di  mesin  sebelumnya  telah  selesai.  Pemilihan  mesin dalam  kondisi  yang  tersusun  paralel  didasarkan  pada  mesin  yang  lebih  dulu available . Berdasarkan gantt chart tersebut diketahui bahwa makespan penjadwalan eksisting adalah sebesar 9117 menit.
Penjadwalan Menggunakan Metode Longest Processing Time (LPT) Berdasarkan  data total  time dan  langkah-langkah  dalam  melakukan  penjadwalan dengan  metode priority  dispatching  rules LPT  yang  telah  digambarkan  pada  metodologi penelitian, maka dapat diketahui urutan job metode longest processing time adalah 5-4-3- 2-1. Berikut ini (Gambar 4) merupakan ganttchart penjadwalan metode LPT.
Gambar 4. Gantt Chart Penjadwalan Metode Priority Dispatching Rules LPT
Berdasarkan gantt chart tersebut  diketahui  bahwa makespan penjadwalan  dengan  metode priority dispatching rules LPT adalah sebesar 8393 menit.
Penjadwalan Menggunakan Metode Cross Entropy-Genetic Algorithm (CEGA) Berikut  ini  merupakan  tahapan  melakukan  pengembangan  algoritma  CEGA dalam penjadwalan menggunakan mesin paralel: Langkah 1: Menentukan nilai parameter inisial
a. Jumlah sampel (N) = 10.
b. Rasio sampel elit (ρ), yang merupakan parameter untuk menentukan banyaknya sampel elit yang akan diambil pada suatu populasi solusi. Nilai yang umum digunakan berkisar antara 1%-10%  4  . Peneliti menggunakan ρ sebesar 3%.
Penjadwalan Flow Shop Mesin Paralel Menggunakan Metode Longest Processing Time dan Cross Entropy- Genetic Algorithm pada Pembuatan Produk Steel Bridge B-60 Yusraini Muharni, Ade Irman Saeful M, Tania Ero Rubyanti
c. Koefisien smooth (α), memiliki rentang nilai antara 0<α<1  5  . Peneliti menggunakan α sebesar 0.5.
d. Menentukan  nilai  inisial  untuk  parameter  pindah  silang.  Nilai  default  inisial  untuk parameter pindah silang (Pps) adalah 1  6  .
e. Menentukan  kriteria  pemberhentian  (β).  Kriteria  Pemberhentian  adalah  aturan  yang digunakan  untuk  menghentikan  iterasi,  dimana  β  merupakan  selisih  hasil  iterasi sekarang dan iterasi sebelumnya  7  . Peneliti menggunakan β sebesar 0.0001.
Langkah 2: Melakukan pembangkitan sampel awal. Pembangkitan sampel  awal dilakukan dengan  metode roulette  wheel untuk  membangkitkan  sampel  awal  dengan  mekanisme random . Dengan tahapan berikut:
a. Menentukan probabilitas masing-masing individu.
b. Dari  probabilitas  tersebut,  dihitung  nilai  probabilitas  masing-masing  individu  pada angka 0 sampai 1.
c. Membangkitkan bilangan random antara 0 sampai 1.
d. Menentukan individu terpilih sebagai sampel.
Tabel 3 merupakan tabel rekapitulasi pembangkitan sampel awal.
Tabel 3. Pembangkitan Sampel Awal No Bilangan Random Nilai Probabilitas Permutasi 1 0.026 0.025 12435 2 0.256 0.258 23541 3 0.342 0.342 24351 4 0.417 0.417 31425 5 0.450 0.450 31254 6 0.592 0.592 35142 7 0.657 0.658 42153 8 0.765 0.767 45123 9 0.821 0.817 51432 10 0.973 0.975 54123
Langkah 3: Menghitung nilai fungsi tujuan Z Dalam penelitian ini funsi tujuan yaitu menghitung M ( makespan ) yang  merupakan waktu yang dibutuhkan untuk menyelesaikan seluruh job mulai dari job 1 sampai ke n dikerjakan sampai  selesai.  Berikut  ini  (Tabel  4)  merupakan  rekapitulasi  hasil  perhitungan  nilai makespan untuk 10 sampel sebagai populasi.
Tabel 4. Rekapitulasi Nilai Makespan Populasi Sampel Urutan Makespan (Menit) S1 1  2  4  3  5 9120 S2 2  3  5  4  1 8705 S3 2  4  3  5  1 9031 S4 3  1  4  2  5 9117 S5 3  1  2  5  4 8794 S6 3  5  1  4  2 8554 S7 4  2  1  5  3 9429 S8 4  5  1  2  3 8717 S9 5  1  4  3  2 8393 S10 5  4  3  1  2 8393
Langkah 4: Penentuan Sampel Elit Penentuan nilai sampel elit ini didasarkan pada langkah inisialisasi parameter. sampel elit yaitu ρ x N, jumlah sampel elit dapat diketahui sebagai berikut: Sampel Elit   = 0.03 x 10 = 0.3 ≈ 1
Dari  hasil  perhitungan  nilai  sampel  elit,  maka  akan  diambil  satu  sampel  teratas  yang memiliki makespan terkecil pada sampel ke 9 dengan urutan pekerjaan yaitu 5-1-4-3-2.
Langkah 5: Pembobotan Sampel Elit
Nilai  pembobotan  sampel  elit  didasarkan  dari  perhitungan  penentuan  sampel  elit  pada langkah  sebelumnya yaitu 1,  nilai tersebut didapatkan  dari  evaluasi terhadap  nilai terbaik pada iterasi sebelumnya  8  .
Langkah 6: Perhitungan Linier Fitness Rangking (LFR) Tahap  perhitungan  nilai  LFR  ini  digunakan  untuk  pemilihan  induk  pada  proses  pindah silang.
Berdasarkan rumus Berikut ini merupakan perhitngan LFR untuk ke-10 sampel terpilih.
LFR (I(N − i + 1)) = Fmax − (Fmax − Fmin) ∗ (i − 1) (N − 1)
dengan Fmax = 1 Z(1) dan Fmin = 1 Z(N) Fmax = 1 8393 = 0.00119 Fmin = 1 9429 = 0.00106
Dari hasil makespan yang sudah di urutkan, maka LFR untuk ke 10 sampel adalah:
a. Sampel 9  = 0.000119
b. Sampel 10 = 0.000118
c. Sampel 6 = 0.000116
d. Sampel 2 = 0.000113
e. Sampel 5 = 0.000112
f. Sampel 3  = 0.000110
g. Sampel 4  = 0.000109
h. Sampel 1  = 0.000107 i. Sampel 7  = 0.000106
Langkah 7: Penentuan Pemilihan Induk Pindah Silang
Pemilihan  induk  pindah  silang  dilakukan  dengan  memilih  dua  buah  kromosom  sebagai induk  yang  akan  dipindah  silangkan  dilakukan  secara  proporsional  sesuai  dengan  nilai fitnes s-nya. Dalam penelitian ini untuk melakukan pindah silang menggunakan mekanisme roulettee wheel, yaitu dengan pemilihan induk 1 dari sampel elit dan induk 2 dari sampel keseluruhan  1  .
a. Memilih Induk 1
Dengan  cara  mengambil  sampel  dari  nilai  sampel  elit  yang  memiliki  nilai  fungsi  tujuan terbaik (nilai makespan minimum)  dari    mekanisme  elitisme  sehingga  didapatkan  sampel S9 dengan urutan job 5-1-4-3-2.
b. Memilih Induk 2
Pada proses ini akan menggunakan nilai LFR dari sampel yang sedang dievaluasi. Apabila nilai  perbandingan  antara  kumulatif  LFR  dan  total  LFR  lebih  besar  dari  nilai  acak  yang dibangkitkan, maka sampel tersebut menjadi induk 2  8  .
Sampel 10 = 0.00119-((0.00119-0.00106) x ( (2-1) (10-1) ) = 0.000118
Penjadwalan Flow Shop Mesin Paralel Menggunakan Metode Longest Processing Time dan Cross Entropy- Genetic Algorithm pada Pembuatan Produk Steel Bridge B-60 Yusraini Muharni, Ade Irman Saeful M, Tania Ero Rubyanti
Langkah 8: Update Parameter Pindah Silang Update parameter  pindah  silang  digunakan  untuk  mendapatkan  nilai  parameter  yang terbaru untuk evaluasi kriteria pemberhentian.
Pps(i) = (1-α)*( Ze 2 x Zbest) ) + (Pps*α)
Pps(i) = (1-0.5)*( 8393 2 x 8393 ) + (1*0.5)
Pps(i) = 0.75
Hasil nilai parameter terbaru yang didapat selanjutnya akan digunakan sebagai dasar untuk menentukan apakah suatu kromosom perlu dilakukan proses pindah silang atau tidak.
Langkah 9: Elitisme Langkah elitisme  bertujuan untuk  menjaga agar individu  bernilai fitness tertinggi tersebut tidak  hilang  selama  evolusi,  sample  ini  nantinya  akan  muncul  kembali  pada  populasi sampel  diiterasi  berikutnya  8  .  Sedangkan  jumlah  sampel  yang  di  lakukan  elitisme  ini sebanyak  satu  sampel,  karena  dari  hasil  perhitungan  sampel  elit  didapatkan  nilai  1. Sehingga  sampel  yang  di  elitisme  adalah  S9  dengan  urutan job 5-1-4-3-2.  Hasil  dapat dilihat pada Tabel 5.
Tabel 5. Perbandingan LFR Kumulatif dengan Nilai Acak Sampel LFR LFR Kumulatif Ket. Nilai Acak S9 0.000119 0.10581 < 0.82211 S10 0.000118 0.21033 < 0.82211 S6 0.000116 0.31356 < 0.82211 S2 0.000115 0.41549 < 0.82211 S8 0.000113 0.51614 < 0.82211 S5 0.000112 0.61549 < 0.82211 S3 0.000110 0.71356 < 0.82211 S4 0.000109 0.81033 < 0.82211 S1 0.000107 0.90581 > 0.82211 S7 0.000106 1 > 0.82211
Metode Cross Over yang digunakan dalam penelitian ini adalah 2- point order Cross Over. Adapun  hasil  dari  pembangkitan  bilangan  R  untuk  menentukan  sampel  yang  akan dilakukan Cross Over dapat dilihat pada Tabel 6.
Tabel 6. Pembangkitan Bilangan Random untuk Penentuan Cross Over Sampel R P_ps Kesimpulan S9 0.95321  0.75  Tanpa Cross Over S10 0.50262  0.75 Cross Over S6 0.44545  0.75 Cross Over S2 0.39176  0.75 Cross Over S8 0.27268  0.75 Cross Over S5 0.98569  0.75  Tanpa Cross Over S3 0.96056  0.75  Tanpa Cross Over S4 0.99422  0.75  Tanpa Cross Over S1 0.97433  0.75  Tanpa Cross Over S7 0.98121  0.75  Tanpa Cross Over
Langkah 10: Cross Over (Pindah Silang) Cross  Over (Pindah  Silang)  merupakan  tahapan  dari  algoritma  genetika  yang  akan menyilangkan  2  induk  untuk  membentuk  kromosom  baru  yang  akan  menghasilkan
individu  baru  yang  lebih  baik.  Dalam  teknik Cross  Over ini  untuk  mengetahui  sampel mana  yang  akan  mengalami Cross  Over maka  dilakukan  penmbangkitan  bilangan  acak. Jika  dalam  pembangkitan  bilangan  acak  diperoleh  bilangan random (R)  lebih  kecil  dari parameter pindah silang (P_ps) atau R < P_ps, maka akan dilakukan pindah silang terhadap kedua  kromosom  induk  tersebut,  dan  sebaliknya  1  .  Untuk  menentukan  bagian  dari sampel induk yang akan ditukar, maka dilakukan pembangkitkan dua bilangan acak untuk proses  pindah  silang  pada ceil atau  gen  induk  yang  akan  mengalami  proses Cross  Over . Nilai  acak  tersebut  kemudian  dikonversi  menjadi  nilai  bulat,  dan  digunakan  sebagai pembatas  bagian  sampel  yang akan  di  pindah antar induk  3  .  Pada Tabel  7 dapat  dilihat proses Cross Over .
Tabel 7. Proses Cross Over Induk yang di Cross Over Urutan Job Pembangkitan Bilangan Random Cell (random*n) Cell yang di Cross Over Hasil Cross Over Keterangan S9 VS S1 51432 r1 = 0.22243 1.11215=2 51  4  32 51432 Menjadi sampel S10 12435 r2 = 0.58040 2.90200=3 12  4  35 12435 Menjadi sampel S6 S9 VS S7 51432 r1 = 0.50240 2.51200=3 514  3  2 14352 Menjadi Sampel S2 42153 r1 = 0.62441 3.12205=4 421  5  3 42135 Menjadi sampel S8 Contoh Perhitungan: Sampel S9 VS S7 Bilangan random r1= 0.50240
Bilangan random r2= 0.62441 Ceil r1 = r1 x n job = 0.50240 x 5 = 2.51200 ≈ 3
Ceil r2 =  r2 x n job = 0.62441 x 5 = 3.12205 ≈ 4
Ceil r1 yang di crossover = 514|3|2
Ceil r2 yang di crossover = 421|5|3
Cara  melakukan crossover adalah  dengan  menukar  angka  yang  berada  di  dalam kurung,  lalu  untuk  mengisi  titik-titik  pada  calon  anak  1,  maka  diperiksa  operasi  pada induk1. Jika terdapat operasi pada induk 1 yang belum tercantum pada calon anak 1, maka operasi  tersebut  akan  mengisi  titik-titik.  Hal  ini  dilakukan  secara  berurutan  3  ,  sehingga sampel anakan hasil pindah silang menjadi seperti di bawah ini.
Induk 1 = 514|3|2 Induk 2 = 421|5|3 Calon anak 1 = _ _ _|5|_
Calon anak 2 = _ _ _|3| _ Anak 1    = 1 4 3 |5| 2  Menggantikan sampel S2 Anak 2    = 4 2 1 |3| 5  Menggantikan sampel S8

## Langkah 11: Mutasi
Mutasi  dimaksudkan  untuk  memunculkan  individu  baru  yang  berbeda  dengan  individu yang sudah ada. Proses mutasi akan dipilih secara random dan gen pada site tersebut akan diubah  nilainya.  Jika  angka random (R)  tersebut  lebih  kecil  dari  parameter  mutasi  (Pm) maka digit gen akan diganti, dan sebaliknya  3  . Nilai parameter mutasi ditentukan dengan rumus sebagai berikut:
P m = P_ps 2 = 0.75 2 = 0.375
Setelah  didapatkan  nilai parameter  mutasi (Pm),  dan N  yang  ditetapkan  di adalah  sebesar 10  sampel,  maka  menurut  1  ,  jumlah  sampel  kromosom  yang  akan  mengalami  mutasi dapat dihitung dengan rumus:
Na = Pm x N Na = 0,375 X 10
Penjadwalan Flow Shop Mesin Paralel Menggunakan Metode Longest Processing Time dan Cross Entropy- Genetic Algorithm pada Pembuatan Produk Steel Bridge B-60 Yusraini Muharni, Ade Irman Saeful M, Tania Ero Rubyanti
Na = 3,75 ≈ 4, Maka dapat diketahui ada 4 sampel kromosom yang akan mengalami proses mutasi.
Tabel 8. Penentuan Kromosom yang Akan Dimutasi Sampel Hasil Cross Over Random Mutasi Probabilitas Mutasi (Pm) Ket. Hasil S9 51432 0.03156 0.375 R<Pm Tetap Induk S10 51432 0.00694 0.375 R<Pm Dimutasi S6 12435 0.34550 0.375 R<Pm Dimutasi S2 14352 0.94869 0.375 R>Pm Tidak Dimutasi S8 42135 0.55741 0.375 R>Pm Tidak Dimutasi S5 31254 0.79088 0.375 R>Pm Tidak Dimutasi S3 24351 0.12640 0.375 R<Pm Tidak Dimutasi S4 31425 0.91209 0.375 R>Pm Dimutasi S1 12435 0.67069 0.375 R>Pm Tidak Dimutasi S7 42153 0.56825 0.375 R>Pm Tidak Dimutasi
Pada  Tabel  8  diketahui  bahwa  kromosom  yang  akan  mengalami  mutasi  adalah sampel  S10,  S6  dan  S3.  Meskipun  sampel  S9  memiliki  bilangan random lebih  kecil daripada  nilai  probabilitas  mutasi,  namun  karena  sampel  S9  adalah  sampel  elit  maka berdasarkan teori algoritma CEGA, sampel elit harus dipertahankan keberadaannya. Tahap selanjutnya  yaitu  melakukan  mutasi  terhadap  ketiga  kromosom  tersebut.  Mutasi  yang dilakukan  ada  3  jenis  yaitu flip  mutation,  swap  mutation dan slide  mutation .  Berikut  ini merupakan  contoh  perhitungan  proses  mutasi  pada  sampel  Z2  dan  cara  penentuan penggunaan jenis mutasi.
Rand i = 0.1115 Rand j = 0.6431 I,J = ceil (n x rij) I = ceil (5 x 0.1115) = 0.557 ≈ 1 J = ceil (5 x 0.6431) = 3.215 ≈ 4 Menurut  1  ,  untuk  menentukan  jenis  mutasi  pada  kromosom,  dapat  dilakukan  dengan rumus:
k = ceil ( Rand k x 3)
Dari hasil tersebut, terdapat ketentuan hasil sebagai berikut:
k = 1 : flip mutation (membalik)
k = 2 : swap mutation (menukar) k = 3 : slide mutatio n (menggeser)
Maka pada Tabel 9 dapat dijabarkan hasil proses mutasi pada ketiga kromosom terpilih.
Tabel 9. Hasil Proses Mutasi
Langkah 12: Menghitung Nilai Fungsi Tujuan ( Makespan ) dari Populasi Baru Setelah  melakukan  proses  mutasi,  maka  akan  diperoleh  sampel  baru  berupa  urutan pekerjaan yang baru yang akan dihitung nilai makespan -nya. Adapun berikut ini (Tabel 10) merupakan hasil perhitungan nilai fungsi tujuan (makespa n) dari sample baru.
Tabel 10. Makespan dari Populasi Baru
Sampel  Urutan Pekerjan Baru Makespan (Menit) S9 51432 8393 S10 54132 8393 S3 25341 8544 S5 31254 8794 S6 13425 9117 S4 31425 9117 S1 12435 9120 S2 14352 9329 S7 42153 9429 S8 42135 9680
Berdasarkan Tabel 10 diketahui bahwa nilai makespan dengan metode CEGA didapat nilai minimumnya adalah 8393 menit dengan urutan job 5-1-4-3-2 dan 5-4-1-3-2.

## Penjadwalan Metode CEGA menggunakan MATLAB
Berikut  ini  merupakan pseudocode untuk  studi  kasus  dalam  penelitian  ini  sebagai panduan dalam menerjemahkan ke dalam bahasa pemrograman pada MATLAB.
a. Pseudocode Berikut  ini  merupakan pseudocode untuk  studi  kasus  penjadwalan  mesin  paralel menggunakan algoritma CEGA  sebagai panduan  dalam  menerjemahkan ke  dalam  bahasa pemrograman pada MATLAB (Gambar 5).
Gambar 5. Program Menggunakan Software MATLAB
Dalam  penjadwalan  metode  CEGA  menggunakan  MATLAB  dilakukan  iterasi sebanyak  3  kali  dengan  mengubah  parameter  nilai  koefisien smooth rendah  (0.1),sedang (0.5) dan tinggi (0.9). Dari hasil run dengan software matlab (Gambar 6), didapatkan nilai
Determine Initial Parameter Generate Initial Random Population Calculate Objective Function
(Makespan)
For  i to N
If Stopping Criteria is achieve Then stop If Stopping Criteria not achieve Select elite sample jumlahSampelElit = rho * N Weighting elite sample Calculate Linier Ftiness Rangking Fmax = 1/min(i); Fmin = 1/max(i); LFR(i) = Fmax - ((Fmax - Fmin) * ((i-1)/(jumlahSampel-1)));
Crossover Update Parameter
Pps(i)=(1-α)*u+(Pps*α) Elitism Sample Select parents for crossover process i1 = Parents If LFR Kumulatif > R, then parents Crossover Process i = i+1 i1 = No Crossover If R<Pps, then Cross Over Mutation Process Select Ceil = R * N i1 = No Mutation If R < Pm = Mutation Calculate K = Ceil (R *3) If K = 1, then Flip Mutation If K = 2, then Swap Mutation If K = 3, then Slide Mutation Calculate New Objective Function
Penjadwalan Flow Shop Mesin Paralel Menggunakan Metode Longest Processing Time dan Cross Entropy- Genetic Algorithm pada Pembuatan Produk Steel Bridge B-60 Yusraini Muharni, Ade Irman Saeful M, Tania Ero Rubyanti
minimum makespan dari ketiga iterasi tersebut adalah 8393 menit. Lalu dilakukan running yang  kedua  agar  bilangan random pada  setiap  nilai  acak  berubah,  tetap  dihasilkan  nilai minimum makespan adalah  sebesar  8393  menit,  maka  dapat  disimpulkan  bahwa  hasil sudah  konvergen  dan  tidak  ada makespan yang  lebih  minimum  lagi,  sehingga stopping criteria telah  terpenuhi.  Adapun  berikut  ini    (Gambar  6)  merupakan  grafik  hasil running program Ke- 1 dengan 3 iterasi.
Gambar 6. Hasil Running Program Menggunakan Software MATLAB
Dari Gambar 7 hasil running program pada software Matlab,  diketahui  bahwa  nilai minimum  dari  penjadwalan  produksi  dengan  metode  CEGA  diperoleh  nilai  8393  pada ketiga  iterasi.  Berikut  ini  merupakan gantt  chart penjadwalan  dengan makespan terkecil yaitu sampale S9 dengan urutan job 5-1-4-3-2 dan sampel S10 dengan urutan 5-4-1-3-2.
Gambar 7. Gantt Chart Penjadwalan Produksi Sampel 9 (kiri) dan Sampel 10 (kanan)

## Perbandingan Penjadwalan Metode Eksisting, LPT dan CEGA
Berikut  ini  merupakan  tabel  perbandingan  penjadwalan  metode eksisting ,  metode LPT, dan metode CEGA.
Tabel 11. Perbandingan Penjadwalan Metode Eksisting , LPT dan CEGA
No Metode Urutan Job Makespan (Menit) Efisiensi 1 Eksisting 1-2-3-4-5 9117 2 LPT 5-4-3-2-1 8393 7,94% 3 CEGA 5-1-4-3-2 8393 7,94% 4 CEGA 5-4-1-3-2 8393 7,94%

## Contoh Perhitungan:
Efisiensi = Makespan Perusahaan − Makespan Metode LPT Makespan Perusahaan 𝑥100%
Efisiensi = 9117−8393 9117 x 100% =  7,94%
Berdasarkan  Tabel  11  diketahui  bahwa  walaupun  hasil  urutan job berbeda  namun hasil penjadwalan metode LPT dan CEGA menghasilkan nilai efisiensi yang sama apabila dibandingkan  dengan  metode eksisting perusahaan  yaitu  sebesar  7,94%.  Karena  metode usulan mempunyai makespan yang sama, maka perlu dilakukan analisa lebih lanjut untuk memilih  metode  usulan  terbaik  yaitu  dengan  cara  membandingkan idle  time mesin,
berdasarkan gantt chart ketiga metode tersebut, dapat dilihat bahwa metode LPT memiliki idle time mesin yang paling sedikit hanya terjadi saat menunggu job awal yang dikerjakan di  mesin  tersebut,  Maka  berdasarkan  kondisi  tersebut,  peneliti  mengusulkan  urutan job dengan metode LPT yaitu 5-4-3-2-1 sebagai metode usulan terbaik.

## KESIMPULAN
Berikut ini merupakan kesimpulan penelitian penjadwalan yang telah dilakukan:
1. Usulan urutan pekerjaan yang lebih baik adalah 5-4-3-2-1.
2. Makespan eksisting sebelum dilakukan usulan flow shop scheduling adalah 9117 menit dan makespan setelah  dilakukan  usulan flow  shop  scheduling adalah  8393  menit dengan metode LPT dan CEGA.
3. Persen  efisiensi makespan adalah  sebesar  7,94%  baik  itu  menggunakan  metode  LPT maupun CEGA.

## DAFTAR PUSTAKA
[1]. Widodo,  Dian  Setiya.,  2015.  Penjadwalan  Flow  Shop  Dengan  Pendekatan  Cross Entropy-Genetic  Algorithm  Untuk  Menurunkan  Makespan  Pada  Pembuatan  Roda Gigi. Jurnal Teknik Industri HEURISTIC . Vol 12 No 2.
[2]. K. R. Baker and D. Trietsch., 2013. Principles Of Sequencing And Scheduling : John Wiley & Sons.
[3]. Widodo,  D.S.,  Santoso,  P.  B.,  dan  Siswanto,  E.,  2014.  Pendekatan  Algoritma  Cross Entropy  Genetic  Algorithm  Untuk  Menurunkan  Makespan  Pada  Penjadwalan  Flow Shop. Journal of Engineering and Management in Industrial System Vol. 2.
[4]. Kroese,  Dirk  P.,  2009. Cross-Entropy  Method,  Brisbane:  Mathematics  Department , Univerisity of Queensland.
[5]. De  Boer.,  Pieter-Tjerk.,  Kroese  Dirk  P.,  Mannor  S.,  and  Rubinstein  R.Y.,  2003, A tutorial on the Cross-Entropy Method, Haifa: Department of Industrial Engineering , Technion – Israel Institute of Technology.
[6]. Budiman  M.A.,  2010, Pendekatan  Cross  Entropy-Genetic  Algorithm  Untuk Permasalahan  Penjadwalan  Job  Shop  Tanpa  Waktu  Tunggu  Pada  Banyak  Mesin . Surabaya : Institut Teknologi Sepuluh Nopember.
[7]. Basori,  Sayid  dan  Suparno.,  2009. Pendekatan  Cross  Entropy  Untuk  Minimasi Bikriteria  Makespan  Dan  Total  Tardiness  Pada  Penjadwalan  Produksi  Flowshop Dengan Mesin Paralel . Surabaya: Institut Teknologi Sepuluh Nopember.
[8]. Nurkhalida, L., dan Santosa, B., 2012. Pendekatan Cross Entropy-Genetic Algorithm Pada  Permasalahan  Multi  Objective  Job  shop  Scheduling .  Surabaya:  Institut Teknologi Sepuluh Nopember.