## PENJADWALAN PESANAN MENGGUNAKAN ALGORITMA GENETIKA UNTUK TIPE PRODUKSI HYBRID AND FLEXIBLE FLOWSHOP PADA INDUSTRI KEMASAN KARTON
Nora Azmi 1) , Irawadi Jamaran 2) , Yandra Arkeman 3) , Djumali Mangunwidjaja 4)
1) Staf pengajar Jurusan Teknik Industri, Fakultas Teknologi Industri, Universitas Trisakti, Mahasiswa Program Doktor Teknologi Industri Pertanian, IPB
2), 3), 4) Staf pengajar Program Studi Teknologi Industri Pertanian, Fakultas Pascasarjana, IPB

## ABSTRACT
This  research  was  intended  to  produce  an  order  (job)  scheduling  model  at  Carton Packaging  Industries  (CPI)  that  is  useful  for  giving  information  about  the  time  delivery  to customers.  The  proposed model  is  quite  complicated  because  of  the  characteristic  of  Make  to Order (MTO) varies production process greatly between each order. The job’s schedule for CPI is prepared for production process that consists of 5 stages where in each stage uses different type of machinery. Not all jobs can be processed by all machines at a given production stage. Every job flow through 5 stage in the same order, but not all stages have to visited by all jobs. Stages  may  be  skipped  for  a  particular  job.  This  condition  makes  CPI  is  classified  as  Hybrid and flexible flowshop for machine eligibility (HFFME). HFFME is complicated and is difficult to  calculate  by  using  conventional  heuristic  model.  This  research  used  genetic  algorithm  for solving the complex problem of HFFME and the resulting model called the Genetic Algorithm for hybrid and flexible flowshop with machine eligibility (GA-HFFME). This model is developed to minimized makespan, the objective of scheduling. The experiment was conducted towards 11 orders and it was found that the GA-HFFME is effective to solve that problem.
Keywords  : hybrid and flexible flowshop, machine eligibility, genetics algorithm

## 1. PENDAHULUAN 1
Industri  kemasan  karton  (IKK)  adalah salah satu industri pendukung yang penting bagi  berbagai  jenis  produk  manufaktur, termasuk  produk-produk  agroindustri  dan pangan. Hal ini disebabkan karena kemasan karton  merupakan  kemasan  yang  cukup aman  untuk  digunakan,  termasuk  bagi produk pangan dan agroindustri. Disamping itu kemasan karton bersifat mudah diuraikan sehingga tidak merusak lingkungan,  dapat  didaur  ulang  sebagai bahan baku untuk kemasan berikutnya, dan dapat digunakan sebagai sumber energi atau kompos  (Coles,  McDowell  dan  Kirwan, 2003).
Sebagian  besar  IKK  skala  kecil  dan menengah  beroperasi  berdasarkan  pesanan ( make-to-order /MTO).  Hal  ini  disebabkan kenyataan bahwa kemasan karton seringkali merupakan  pesanan  yang  dirancang  secara khusus  untuk  konsumen  tertentu  sebagai
Korespondensi :
1 Nora Azmi E-mail : noraazmi@yahoo.com
identitas  atau  pemberi  informasi  tentang perusahaan  kepada  konsumen.  Produksi berdasarkan pesanan (MTO)  membuat IKK menghadapi  beberapa  masalah.    Salah  satu masalah  yang  dihadapi  adalah  sulitnya memberikan  informasi  waktu  penyelesaian yang akurat kepada konsumen terutama jika ada beberapa pesanan yang harus dikerjakan  pada  periode  waktu  yang  sama. Kegagalan  dalam  mengestimasi  waktu penyelesaian  pesanan  dapat  mengakibatkan beberapa pesanan terlambat daripada waktu yang  dijanjikan  sehingga  mengakibatkan kekecewaan konsumen.
Pada  penelitian  ini  dirancang  suatu model penjadwalan pesanan sebagai metode  yang  terintegrasi  dengan  proses manajemen pemesanan ( ordering management  process )  dengan  tujuan  agar dapat  mengestimasi  waktu  penyelesaian pesanan secara lebih akurat.
Permasalahan  yang  dihadapi  dalam merancang  model  penjadwalan  ini  adalah karakteristik  proses  produksi  kemasan karton yang  memiliki banyak sekali variasi antara  satu  produk  dengan  produk  lainnya,
sehingga membutuhkan proses penjadwalan yang lebih kompleks untuk penyelesaiannya. Proses produksi pada industri kemasan karton  merupakan  tipe  seri  ( flow  shop ), dengan  jumlah  tahapan  proses  yang  lebih dari tiga tahap dimana setiap tahapan terdiri dari  beberapa  mesin  yang  tidak  identik. Setiap  tahapan  juga  tidak  harus  dilewati oleh  setiap  pesanan  (job),  sehingga    kasus penjadwalan flowshop ini bisa digolongkan ke dalam hybrid flowshop sekaligus flexible flowshop . Kasus penjadwalan hybrid flowshop  dan  flexible  flowshop  dengan jumlah  tahapan  lebih  dari  tiga  dapat digolongkan sebagai kasus
non- deterministic  polynomial yang  sulit  untuk diselesaikan ( NP-hard ) dan tidak ada suatu model  matematik  yang  mampu  untuk menghasilkan  solusi  optimal  (Wadhwa, Madaan,  Raina,  2007;  Ruiz  dan  Maroto, 2006). Ponnambalam, Aravindan dan Chandrasekaran  (2001)  menyatakan  bahwa ketika suatu masalah penjadwalan flowshop termasuk  kasus  yang NP-hard maka penyelesaiannya  hanya  bisa  dilakukan melalui pengembangan suatu teknik enumeratif. Namun ketika masalah bertambah  kompleks  (contoh  :  ketika jumlah job, jumlah stage dan jumlah mesin bertambah),  maka  area  pencarian  dengan teknik  enumeratif  akan  sangat  besar sehingga akan memakan waktu yang sangat lama  untuk  dihitung  walaupun  secara komputasional.  Pada  kondisi  ini,  harus digunakan  suatu  teknik  heuristik  yang  bisa membantu  mencari  solusi  masalah  untuk kasus-kasus  yang  kompleks  seperti  pada kasus ini.
Pada  penelitian  ini  algoritma  genetika digunakan  untuk  membantu  mencari  solusi optimal  untuk  masalah  penjadwalan    pada lantai  produksi  kemasan  karton  yang memproduksi  kotak  karton  bergelombang ( corrugated  box )  dan  karton  lipat  ( folding carton ).    Algoritma  genetika  adalah  suatu teknik pencarian metaheuristik yang menggunakan  mekanisme  seleksi  alam  dan genetika  untuk  memperoleh  solusi  optimal. Solusi  optimal  ini  pada  algoritma  genetika direpresentasikan  dalam  bentuk  kromosom terbaik (Goldberg, 1989; Boukef, Benrejeb, Borne, 2007) . Kriteria (tujuan) penjadwalan
adalah untuk meminimasi waktu penyelesaian  semua  pesanan  (meminimasi makespan ) pada lantai produksi.

## 2. METODE Asumsi dan Batasan Model
Proses produksi karton gelombang dan karton  lipat  dikelompokkan  menjadi    lima tahap  ( stage )  yaitu  pembuatan  karton gelombang ( corrugating ), pencetakan desain  kemasan  ( printing ),  pemotongan pola kemasan ( die cutting ), tahap penyambungan  badan  kemasan  ( finishing ) dan perlakuan tambahan ( additional treatment ).  Proses  1  ( stage  1 )  terdiri  dari dua  mesin  corrugator,  yaitu  mesin  C1  dan C2.  Proses  cetak  ( stage  2 )  terdiri  dari  tiga mesin  printing  yang  disebut  sebagai  flexo printing  1  (P1),  flexoprinting  2  (P2)  dan mesin cetak offset (P3). Stage 3 atau proses die cutting memiliki tiga mesin, yaitu mesin die cut 1 (D1), die cut 2 (D2) dan die cut 3 (D3).  Tahap  ke  4  ( stage  4 )  terdiri  dari mesin  gluing  semi  atomatis  (G1),  mesin gluing  otomatis  (G2)  dan  mesin  Stitching (S).  Mesin-mesin  yang  terdapat  pada stage 1  sampai  4  bersifat  tidak  identik  (memiliki spesifikasi  dan  kemampuan  yang  berbeda- beda), sedangkan pada stage 5 terdapat tiga unit  mesin foil  stamping yang  bersifat identik (Gambar 1).
Ciri-ciri  dan  gambaran  lantai  produksi yang  terdapat  pada  penelitian  ini  adalah sebagai berikut :
 Semua  pengerjaan job mengikuti urutan / aliran produksi yang sama
 Pada  setiap  tahapan  produksi  terdapat lebih  dari  satu  mesin  yang  tidak identik satu sama lain.
 Setiap job tidak  harus  melalui  semua tahapan ( stage ), proses produksi untuk suatu job dapat  melompati  salah  satu stage
 Tidak  semua  mesin  pada  suatu stage dapat  memproses  suatu job .    Ada mesin-mesin yang diperuntukkan khusus  untuk  memproses job dengan tipe tertentu ( eligible machine ).
 Setiap job pada  suatu  waktu  hanya boleh dikerjakan pada satu mesin.
Corrugating Machine I Corrugating Machine II Flexo Printing I Flexo Printing II Offset Printing Die cut machine I Die cut machine II Die cut machine III Semi automatic gluing machine Automatic gluing machine Stitching machine Additional Treatment (foil stamping, embossing/ debossing)
Gambar 1.  Proses Produksi Kemasan Karton Gelombang dan Karton Lipat
Selain  ciri-ciri  di  atas  juga  terdapat beberapa  asumsi  yang  digunakan  pada model penjadwalan ini, yaitu :
a. Satu  pesanan  dianggap  sebagai  satu job ,  kecuali  jika  jumlah  item  yang dipesan  sangat  banyak,  maka  pesanan bisa  dibagi  menjadi  beberapa job . Proses  pembagian  pesanan  menjadi beberapa job dilakukan  berdasarkan kesepakatan dengan konsumen.
b. Pada  saat  proses  produksi  sedang berlangsung, tidak diperkenankan adanya job sisipan
c. Waktu  proses  setiap job pada  setiap mesin bersifat deterministik.
d. Waktu transportasi tidak diperhitungkan dan dianggap merupakan bagian dari waktu setup.
e. Waktu setup setiap mesin dihitung dan digabungkan  ke  dalam  waktu  proses setiap mesin.
f. Waktu  proses  setiap  tahapan  tidak tergantung  kepada  urutan job ( job independent setup)
Adanya  kondisi  dimana  setiap  job tidak  harus  melalui  semua  tahapan  (dapat melompati  salah  satu  atau  lebih  tahapan) membuat  proses  produksi  kemasan  karton ini  dapat  disebut  sebagai  flexible  flowshop (Kurz  dan  Askin,  2003).  Kondisi  dimana pada  setiap  stage  terdapat  lebih  dari  satu mesin  dan  terdapat  mesin-mesin  tertentu yang  diperuntukkan  untuk  job  tertentu memberikan  proses  produksi  kemasan karton  juga  dapat  disebut  sebagai hybrid flowshop with machine eligibility (Ruiz dan Maroto, 2006). Selanjutnya kasus
penjadwalan  pada  industri  kemasan  karton ini  disebut  sebagai Hybrid  and  Flexible Flowshop with Machine Eligibility
(HFFME).

## Algoritma  Genetika  untuk  Penjadwalan
Hybrid dan flexible Flowshop Penggunaan algoritma genetika ( Genetics Algorithm /GA) untuk penjadwalan  hybrid  atau  flexible  flowshop telah cukup banyak diteliti. Jin et al (2002) meneliti kasus penjadwalan hybrid flowshop  yang  terdiri  dari  tiga  stages dimana  setiap  stages  terdiri  dari  mesin- mesin  yang  bersifat  paralel.  Penelitian  ini menggunakan kriteria makespan, dan membuat banyak eksperimen yang merubah-rubah  jumlah  mesin  pada  setiap stages dengan tujuan memperoleh penjadwalan  dapat  meminimasi  bottleneck disamping meminimasi makespan. Penjadwalan  yang  diselesaikan  dengan  GA ini membuktikan bahwa GA dapat menyelesaian  kasus  yang  cukup  kompleks seperti pada penelitian ini.  Lantai produksi yang  diteliti  berbentuk  hybrid  flowshop, namun tidak ada fleksibilitas dalam melalui urutan produksi. Penelitian penjadwalan hybrid
flowshop  lainnya  dilakukan  oleh  Ruiz  dan Maroto  (2006)  yang  menyatakan  bahwa kasus  penjadwalan  flowshop  yang  terdiri dari  dua  stages  sudah  merupakan  kasus yang  sulit  untuk  diselesaikan  secara manual.  Penelitian  Ruiz  dan  Maroto difokuskan  pada  penjadwalan  pekerjaan pada  lantai  produksi  hybrid  flowshop dengan multiple processor dan waktu set up
yang  tergantung  pada  urutan job ( sequence dependents  set  up  time /SDST).  Penelitian yang  dilakukan  pada  pabrik  keramik  ini diselesaikan  menggunakan  GA  dengan
kriteria meminimasi
makespan.
Kompleksitas kasus ini semakin bertambah dengan    karakteristik  mesin-mesin  yang tidak paralel pada setiap stages, dan adanya kendala peruntukan mesin untuk  setiap job ( machine  eligibility  constraint ).  Penelitian ini menunjukkan bahwa GA dapat memecahkan  masalah  penjadwalan  yang kompleks  ini  dengan  baik.  Di  sisi  lain kekurangan  dari  riset  ini  adalah  adanya keharusan setiap job  untuk  melewati  setiap stages,  sehingga  penjadwalan  ini  bukan termasuk kasus fleksible  flowshop. Liu  (2010)  mengembangkan  suatu algoritma  penjadwalan  flowshop  multi pesanan  ( multiple  order )  yang  terdiri  dari tiga mesin.  Ketiga mesin merupakan mesin proses per unit, mesin proses dalam bentuk lot,  dan  mesin  proses  per  batch.  Berbeda dengan  dua  penelitian  sebelumnya,  model ini  menggunakan  kriteria meminimasi  total weighted tardines sebagai tujuan penjadwalan. Kasus penjadwalan ini menjadi  semakin  kompleks  dengan  adanya kendala  kapasitas  job,  jumlah  job  yang dibatasi,  ukuran  pesanan  yang  tidak seragam,  waktu  kedatangan  job  yang random,  adanya  batas  waktu  penyelesaian pesanan  ( job  due  dates )  dan  adanya perbedaan kapasitas mesin proses perbatch. Pada  kasus  ini  penyelesaian  dilakukan dengan  menggunakan  GA  yang  juga dibandingkan  dengan  beberapa  teknik heurustik lainnya. Hasil penelitian menunjukkan bahwa pendekatan penjadwalan  menggunakan  GA  Lebih  baik dibandingkan  pendekatan  heuristik  lainnya dan dapat memperoleh solusi yang mendekati  optimal  dalam  waktu  pencarian yang dapat diterima ( reasonable ). Walaupun telah terdapat beberapa penelitian  yang  menggunakan  GA  pada kasus  hybrid  flowshop,  kasus  flexible flowshop atau kasus-kasus flowshop lainnya, namun belum ditemukan penelitian
yang  mengaplikasikan  GA  pada  kasus HFFME  seperti  yang  dilakukan  pada penelitian ini.

## Rancangan Model Penjadwalan HFFME pada Industri Kemasan Karton
Model  penjadwalan  ini  dirancang untuk  mengestimasi  waktu  penyelesaian pesanan  ( lead  time )  pada  IKK  secara  lebih akurat.  Kriteria  yang  digunakan  untuk menjadwalkan  adalah  untuk  meminimasi makespan  (F max ).  Kriteria makespan  adalah kriteria  yang  paling  umum  digunakan  pada penjadwalan flowshop . Makespan dari suatu jadwal  ( schedule )  adalah  waktu  selesainya semua  pekerjaan  yang  ditandai  oleh  waktu selesai  pekerjaan  yang  terakhir  pada  lantai produksi.  Penggunaan  kriteria  makespan akan  memungkinkan  pihak  perusahaan melihat  berapa  banyak  pesanan  (job)  yang mampu  untuk  ditangani  dalam  periode waktu  tertentu  (Raaymakers  dan  Weijters, 2003).  Penjadwalan  yang  bertujuan  untuk meminimasi  makespan  dengan  sendirinya dapat  meningkatkan  jumlah  job  yang mampu  ditangani  oleh  perusahaan  dalam periode  waktu  tertentu.  Pada  saat  yang sama  informasi  mengenai  kapan  waktu penyelesaian  setiap  pesanan  tetap  dapat diberikan kepada konsumen.
Diagram  alir  deskriptif  penjadwalan pada  lantai  produksi  HFMME  dengan menggunakan  algoritma  genetika  dapat dilihat pada Gambar 2.
Representasi  atau  pemberian  kode kromosom  ( encoding )  merupakan  tahap awal dari penyelesaian masalah penjadwalan menggunakan algoritma genetika.
Terdapat beberapa cara representasi  kromosom,  seperti binary encoding , octal  encoding , hexadecimal encoding dan permutation  (real  number) encoding .  Pada  model  ini  digunakan  real number encoding karena menurut Sivanandam  dan  Deepa  (2008)  cara representasi  kromosom  ini  paling  sesuai untuk masalah pengurutan ( sequencing ).
Start
 Jumlah stage (s)
 Jumlah dan Jenis
mesin pada tiap stage (m)
 Waktu proses setiap job pada setiap mesin / waktu subkontrak pembentukan populasi awal Hitung makespan  dan nilai fitness setiap kromosom pada populasi awal Seleksi kromosom Pindah silang ( Crossover ) Mutasi Apakah g=G ? Selesai Hitung nilai fitness Peluang crossover (Pc) Representasi kromosom Jumlah pesanan  / job  Jumlah Populasi  Jumlah generasi (G) Peluang mutasi (Pm) Hitung makespan dan waktu penyelesaian setiap job ya Penggantian populasi tidak
Gambar 2. Diagram Alir Deskriptif Algoritma Genetika Pada Penjadwalan HFFME
Pembentukan  populasi  awal  atau inisialisasi populasi bertujuan untuk membangkitkan  sebuah  populasi  yang terdiri dari sejumlah kromosom. Dua aspek penting  dari  inisialisasi  populasi  adalah bagaimana  cara  membangkitkan  populasi tersebut  dan  berapa  ukuran  (jumlah kromosom)  yang  terdapat  pada  populasi tersebut    (Suyanto,  2005;  Sivanandam  dan Deepa,  2008).  Pada  model  ini  inisialisasi populasi    dilakukan  secara  random,  tanpa menggunakan bantuan suatu metode heuristik. Pada beberapa penelitian mengenai  penjadwalan job pada  lantai produksi flowshop dengan algoritma genetika,  terkadang  digunakan  bantuan metode heuristik tertentu untuk mendapatkan populasi awal. Tujuan
penggunaan  metode  heuristik  ini  adalah untuk mendapatkan nilai fitness yang cukup baik pada populasi awal sehingga algoritma genetika  lebih  cepat  menemukan  solusi yang mendekati optimum. Namun kompleksnya  permasalahan  pada  model HFFME yang disebabkan jenis mesin yang tidak identik pada setiap stage ,
menyebabkan  sulit  untuk  menerapkan metode heuristik tertentu untuk mendapatkan solusi (populasi) awal. Setelah  mendapatkan  populasi  awal, langkah  selanjutnya  adalah  menghitung nilai kebugaran ( fitness ) dari setiap kromosom  yang  terdapat  pada  populasi tersebut.  Pada  algoritma  genetika,  individu (kromosom)  yang  mempunyai  nilai fitness tinggi  akan  bisa  bertahan  hidup,  sehingga tujuan  dari  algoritma  genetika  adalah memperoleh  individu  dengan  nilai fitness yang maksimal.
Nilai fitness dari  suatu  kromosom merupakan  fungsi  tujuan  dari  penjadwalan yang dilakukan. Dalam hal ini fungsi tujuan penjadwalan  adalah  untuk  meminimasi makespan (F max ). Makespan adalah  waktu penyelesaian  paling  akhir  dari  semua pesanan ( job ) pada semua mesin dan stage . Jika terdapat n pesanan dan s stage , maka : F max = max  F i,j,  (k)  (1)
Karena  tujuan  penjadwalan  adalah untuk  meminimasi makespan sementara prinsip  algoritma  genetika  adalah  untuk memaksimasi  nilai fitness (f),  maka  nilai fungsi fitness pada kasus ini menjadi : (2) Notasi yang dipergunakan pada perhitungan makespan ini  adalah  sebagai berikut :
i =   pesanan ( job ) = 1, 2, ... n j = stage = 1,..... s  (k) =   urutan job , di mana k = 1,...n e i,j,  (k) =  mesin  yang eligible untuk job i pada stage j dan urutan ke  (k)
t e(i),j,  (k) = waktu proses mesin yang eligible untuk job i  pada stage j  dan urutan ke  (k) M j
=   mesin-mesin yang terdapat pada stage j C i,j,  (k) =  waktu  selesai  proses  ( completion time ) job i  yang  berada  pada urutan  (k) di stage j tc i,j =   waktu  subkontrak job i  pada stage j j L = Stage terakhir (sebelumnya)
yang dilalui oleh job i
i L = job terakhir  (sebelumnya)  yang menggunakan mesin-mesin yang
diperuntukkan  ( eligible )  untuk job i =  Completion  time job i  yang berada pada urutan ke  (k) pada stage sebelum nya.
= Final  time  job i  yang  berada pada urutan ke  (k) pada stage j =   Waktu additional treatment job i yang berada pada urutan ke  (k)
Algoritma  untuk  perhitungan  waktu penyelesaian
pesanan ( makespan ) dikelompokkan menjadi dua, yaitu algoritma untuk menghitung waktu penyelesaian  setiap  pesanan  ( completion time )  pada  stage  1,  dan  algoritma  untuk menghitung completion  time pada  stage  2 sampai stage 4.

## Stage 1
1. Pada  stage  j=1,  urutkan  job  i  secara acak    dimana  i  =  1,....n,  sehingga diperoleh  urutan  ke  (k)  dimana  k  = 1,...n 2. Pada T=0, pilih mesin eligible
(e (i),1,  (i) )    yg  tersedia  dengan  waktu proses terkecil untuk memproses job i, stage  1  urutan  ke  1  (min  t e(i),1,  (1) ) dimana e (i),j,  (k)  M j .
3. Hitung  waktu  selesai  job  i,  stage  1
pada urutan  (1) C i,1,  (1) = 0 + min t e(i),1  (1)
Jika  tidak  ada  mesin  eligible  yang tersedia (job tidak diproses di j=1), set C i,1,  (1) = 0.
4. Cek  apakah  masih  ada  mesin  tersisa pada  stage  1  (M 1 ≠0).  Jika  masih  ada mesin tersisa, tugaskan job pada urutan berikutnya (  (k) ) untuk diproses pada t=0,  jika  tidak  tunggu  sampai  ada mesin yang selesai berproses.
5. Jika  ada  mesin  selesai  berproses, tugaskan  job  pada  urutan  berikutnya (  (k+1))  pada  mesin  tersebut,  jika  job yang  berada  pada  (k+1)  tidak  sesuai dengan  mesin  yang  tersedia,  maka penugasan  bisa  diberikan  pada  job urutan  berikutnya    (  (k+2))  dan seterusnya.
6. Hitung waktu penyelesaian  job i yang telah  ditugaskan  terhadap  satu  mesin, sehingga :
C i,1,  (k) = waktu selesai job sebelumnya pada mesin tsb + min t e(i),1,  (k)
7. Cek  apakah  i=n  dan  k=n  ?  Jika  tidak, kembali  ke  langkah  5.    Jika  ya, penempatan  job-job  pada  stage  1 selesai.

## Stage 2, 3 dan 4:
1. Untuk  stage  j=2,...,s,  urutkan  job  i berdasarkan  waktu  selesai  terkecil pada  stage  sebelumnya  (C i,j-1,  (k) ) dimana  i  =  1,....n,  sehingga  diperoleh urutan ke  (k) dimana k = 1,...n
2. Untuk  job  i  yang  berada  pada  urutan pertama  (  (1))  stage  j,  pilih  mesin eligible    (e(i),j,  (1))    yg  tersedia dengan  waktu  proses  terkecil  (min t e(i),j,  (1) ) dimana e (i),j,  (1,)  M j 3. Hitung waktu selesai job i, stage j pada urutan  (1) C i,j,  (1) = C i,j-1,  (1) + min t e(i),j,  (1,) Jika  tidak  ada  mesin  eligible  yang tersedia (job tidak diproses di j=1), set C i,j,  (1) = C i,j-1,  (1) 4. Cek  apakah  masih  ada  mesin  tersisa pada  stage  j  (M j ≠0).  Jika  masih  ada mesin tersisa, tugaskan job pada urutan berikutnya  (  (k))  untuk  diproses  pada t=0,  jika  tidak  tunggu  sampai  ada mesin yang selesai berproses.
5. Jika  ada  mesin  selesai  berproses, tugaskan  job  pada  urutan  berikutnya (  (k+1))  pada  mesin  tersebut,  jika  job yang  berada  pada  (k+1)  tidak  sesuai dengan  mesin  yang  tersedia,  maka penugasan  bisa  diberikan  pada  job urutan berikutnya  (  (k+2)) dst.
6. Hitung waktu penyelesaian  job i yang telah  ditugaskan  terhadap  satu  mesin ( finish time ), shg :
C i,j,  (k) =  max  {C iL,j,  (kL) ,  C i,,j-1,  (k) }  + min t e(i),j,  (k)
7. Cek  apakah  i=n  dan  k=n  ?  Jika  tidak, kembali ke langkah 5, jika ya lanjutkan ke langkah berikutnya.
8. Cek  apakah  j=S  ?  Jika  tidak  kembali ke  langkah  1,  jika  ya,  lanjutkan  ke langkah berikutnya
9. Hitung waktu penyelesaian akhir ( final time )
F i,j,p(k) = C i,j,p(k) + ta i,p(k) 10. Tentukan makespan ( Fmax )  =  max F i,j,p(k)
Proses perlakuan tambahan ( additional treatment )  yang  merupakan stage 5  tidak melalui tahapan penjadwalan dengan menggunakan  algoritma  genetika.  Untuk mendapatkan  waktu  penyelesaian  akhir ( final time )  dari  suatu job , completion time pada stage 4  ditambahkan  dengan  waktu proses pada stage 5.
Setelah didapatkan nilai makespan dan nilai fitness untuk  setiap  kromosom  pada populasi  awal,  tahap  berikutnya  adalah seleksi  kromosom.  Seleksi  kromosom dilakukan  untuk  mendapatkan  kromosom- kromosom  unggulan  yang  memiliki  nilai fitness yang  baik  untuk  dipindah  silangkan ( cross over ). Seleksi kromosom pada model ini dilakukan dengan dua cara, yaitu teknik roda  rolet  ( roulette  wheel )  dan  seleksi turnamen ( tournament selection ).
Pada  metode  roda  rolet  kromosom orang  tua  ( parents )  yang  akan  dipindah-
silangkan dipilih berdasarkan nilai fitnessnya. Nilai fitness dari masing-masing kromosom  dibagi  dengan  total  nilai  fitness seluruh kromosom yang ada pada populasi. Setiap  kromosom  dianggap  merupakan potongan/bagian  dari  roda  rolet  dengan ukuran potongan yang proporsional dengan nilai  fitnessnya.  Suatu  nilai  target  antara angka  nol      dan      angka    satu  ditetapkan secara  acak.  Kemudian  roda  rolet  diputar sebanyak  N  kali,  dimana  N  adalah  jumlah individual  atau  kromosom  dalam  populasi. Dari setiap putaran, kromosom dengan nilai fitness    yang  berada  di  bawah  nilai  target dipilih untuk menjadi parents bagi generasi berikutnya.
Berbeda  dengan  seleksi  roda  rolet, seleksi turnamen memilih kromosom dengan cara mengadakan kompetisi/ turnamen  di  antara  individu-individu  yang menjadi  anggota  populasi.  Individu  terbaik dari  hasil  turnamen  adalah  yang  memiliki nilai  fitness  terbesar,  yang  disebut  sebagai pemenang  ( winner ).  Pemenang  diletakkan pada  kolam  kompetisi  ( mating  pool ). Turnamen  diulang  hingga  mating  pool untuk  menghasilkan  generasi  baru  penuh. Mating  pool  akan  berisi  pemenang- pemenang  turnamen  dengan  nilai  fitness tertinggi (Sivanandam dan Deepa, 2008).
Pada  proses  seleksi  kromosom  ini diterapkan prinsip elitisme. Elitisme adalah
proses  untuk  mengcopy  dan  menempatkan individu atau kromosom-kromosom terbaik pada  populasi  baru  dengan  tujuan  agar individu-individu  terbaik  ini  tidak  hilang atau rusak karena proses pindah silang atau mutasi (Sivanandam dan Deepa (2008).
Kromosom-kromosom terpilih kemudian dipindahsilangkan dengan menggunakan  teknik Partially  Matched Crossover (PMX). Langkah-langkah proses pindah  silang  dengan  teknik  PMX  adalah sebagai berikut (Rajkumar dan
Shahabudeen, 2009) : 1. Tentukan  dua  titik  secara  random untuk  membagi  parents.  Area  yang terletak antara dua titik pada kromosom  orang  tua  ( parents )  disebut area pemetaan ( mapping ).
Gambar 3. Pindah Silang dengan Metode PMX
2. Pertukarkan  area  mapping  dari  dua parent  untuk  diturunkan  kepada  anak
( child  /offspring ).  Area  mapping  dari parent pertama di copy
untuk
diturunkan pada child ke 2, sedangkan area  mapping dari parent ke  2  di copy untuk diturunkan pada child pertama.
3. Definisikan pemetaan pada area mapping antara  dua parent .    Pada contoh  kasus  ini  pemetaan  gennya adalah sebagai berikut :
4. Isi offspring dengan  gen  yang  di copy secara  langsung  dari parent secara berurutan dari kiri ke kanan.  Jika gen tersebut  sudah  terdapat  pada  area mapping yang  di copy kan  sebelumnya, lakukan pengisian gen dengan melakukan pemetaan.
Salah  satu  parameter  penting  dalam melakukan crossover adalah  nilai  peluang crossover (Pc).  Untuk  mendapatkan  hasil terbaik,  dilakukan  uji  coba  beberapa  nilai Pc.
Setelah  proses  pindah  silang  tahap berikutnya adalah mutasi kromosom. Tenik mutasi  yang  digunakan  pada  model  ini adalah shift  mutation .  Pada  teknik  shift mutation, salah satu gen dipilih secara acak dan  kemudian  dimasukkan  (di insert )  pada posisi lain secara acak juga.
Gambar 4. Shift mutation (Rajkumar dan
Shahabudeen, 2009)
Proses mutasi bertujuan untuk mengurangi  kemungkinan  solusi  yang dihasilkan  merupakan local  optimum . Proses mutasi bisa mengembalikan gen-gen yang  hilang,  tapi  sebaliknya  juga  bisa merusak gen-gen yang ada sekarang.  Pada proses  mutasi  juga  diperlukan  parameter nilai peluang mutasi (Pm).
Hasil  pindah  silang  dan  mutasi menghasilkan  kromosom  anak  ( offsprings ) yang  akan  menggantikan  populasi  pada generasi  pertama.  Kromosom  anak  yang diperoleh  dari  hasil  pindah  silang  dan mutasi kemudian dihitung nilai fitness nya. Jika kriteria penghentian sudah tercapai,  maka  proses  pencarian  dengan algoritma  genetika  dihentikan.  Kriteria penghentian  pada  model  ini  adalah  jumlah generasi maksimum. Jika kriteria penghentian belum tercapai, maka dilakukan  penggantian  populasi  generasi sebelumnya  dengan  hasil  operator  genetika (pindah  silang  dan  mutasi)  sehingga terbentuk generasi baru. Proses penjadwalan selanjutnya kembali ke
langkah sebelumnya, yaitu seleksi kromosom yang akan dipindah silangkan.
Keluaran  dari  model  ini  adalah makespan , waktu selesai proses ( final time ) untuk setiap job dan pada mesin mana saja yang  memproses  masing-masing job pada setiap stage .  Jika  konsumen  menetapkan batas  waktu  ( due  date )  terhadap  pesanan, model  pejadwalan  ini  bisa  memperlihatkan apakah perusahaan mampu memenuhi batas waktu  tersebut  atau  tidak.  Jika  tidak,  maka perusahaan  dapat  melakukan  negosiasi ulang mengenai waktu penyelesaian kepada konsumen.

## 3. HASIL  DAN PEMBAHASAN
Model  penjadwalan  HFFME  pada industri  kemasan  karton  ini  diuji  coba dengan  menggunakan  data  sebelas  pesanan kemasan.    Setiap  pesanan  dianggap merupakan  satu  job.    Data  urutan  proses produksi  kesebelas  job  beserta  waktu prosesnya  masing-masing  dapat  dilihat pada Tabel 1.
Tabel 1. Data Pesanan (Job), Urutan Proses Produksi dan Waktu Proses
No. Job Waktu Proses (jam) Add treat ment Stage I Stage 2 Stage 3 Stage IV C1 C2 P1 P2 P3 D1 D2 D3 G1 G2 S 1 1,4 1,1 23,7 49,0 13,3 10,0 9,43 4,5 1,8 2 6,8 4,3 38,7 27,0 13,8 3 1,8 1,3 25,3 50,0 16,7 12,0 10,86 7,0 3,2 4 6,6 4,2 38,7 58,0 43,3 28,0 22,29 27,0 13,8 5 24,1 14,7 39,2 10,0 8,0 8,00 52,0 27,2 6 1,7 1,3 26,2 50,5 18,3 13,0 11,57 8,3 3,8 5,0 7 7,5 4,7 39,2 76,7 48,0 36,57 52,0 27,2 8 2,1 1,5 23,7 49,0 13,3 10,0 9,43 4,5 1,8 9 3,2 2,2 26,2 50,5 18,3 13,0 4,43 8,3 3,8 10 3,1 2,1 30,3 53,0 26,7 18,0 15,14 14,5 7,2 11 14,9 9,2 30,3 26,7 18,0 15,14 7,6
Tabel  1  memperlihatkan  bahwa  ada job  yang  tidak  diproses  pada  semua tahapan,  seperti  job  2  yang  tidak  diproses pada stage 3 (proses die cutting ). Beberapa job  juga  hanya  bisa  diproses  pada  mesin tertentu  pada  setiap  stage  (contoh  :  job  5 dan  job  7  hanya  bisa  diproses  pada  mesin P1 di stage 2, sedangkan job 11 hanya bisa diproses pada mesin S pada stage 4). Selain itu  hanya  job  6  yang  mendapatkan  proses perlakuan tambahan ( additional treatment ). Penjadwalan  ini  diselesaikan  dengan menggunakan
program
penjadwalan Genetics Algorithm for Hybrid and Flexible Flowshop  with  Machine  Eligibility (GA- HFFME)  yang  dibuat  pada  sofware  matlab versi  10.  Untuk  menjalankan  operator genetika  diperlukan  input  berupa  cara
seleksi  kromosom,  operator  pindah  silang ( crossover), peluang  pindah  silang  (Pc), peluang  mutasi  (Pc),  dan  jumlah  generasi. Pada  kasus  ini  dilakukan  beberapa  kali percobaan  untuk  menghasilkan  kromosom dengan nilai makespan yang paling kecil.
Dari beberapa kali percobaan, diperoleh  hasil  penjadwalan  dengan  nilai fitness  sebesar  0,0055  dan  nilai  makespan 180,74  jam.  Hasil  ini  diperoleh  dengan menggunakan  seleksi  turnamen,  nilai  Pc sebesar  0,7,  Pm  sebesar  0,01,  jumlah populasi  20  dan  jumlah  generasi  100 (Gambar 5).
Gambar 5. Hasil Penjadwalan GA-HFFME
Gambar 6.  Waktu Selesai Setiap Pesanan (Job)
Model  ini  juga  menghasilkan  output berupa  waktu  penyelesaian  ( completion time )  setiap  job  yang  diproses  dengan algoritma  GA  sampai  stage  4,  dan  waktu penyelesaian secara keseluruhan job sampai stage  5  ( final  time ).  Pada  Gambar  6  dapat dilihat  waktu  penyelesaian  job  1  yang berada pada urutan pertama adalah 36 jam, atau  4,5  hari  jika  dalam  waktu  satu  hari hanya tersedia waktu kerja selama 1 shift (8 jam).
Lebih  jauh  model  ini  memperlihatkan mesin-mesin yang terpilih untuk mengerjakan  suatu  job  pada  setiap  stage (Gambar  7  dan  8).    Sebagai  contoh,  job  1 pada  stage  1  diproses  pada  mesin  C2 dengan waktu penyelesaian 1,074 jam, pada stage  2  diproses  pada  mesin  P2  dengan waktu penyelesaian 24,74 jam, pada stage 3 menggunakan  mesin  D3  dengan  waktu penyelesaian 34,17, dan di stage 4 diproses pada mesin G2 dengan waktu penyelesaian 36,002 jam.
Gambar 7. Mesin Terpilih dan Waktu Penyelesaian Pada Stage 1 sampai 3
Gambar 8. Mesin Terpilih dan Waktu Penyelesaian Pada Stage 2 sampai 4
Gambar 9. Grafik Nilai Fitness dan Makespan Tiap Generasi Pada Penjadwalan GA-HFFME 10 20 30 40 50 60 70 80 90 100 0 0.001 0.002 0.003 0.004 0.005 0.006 0.007 0.008 0.009 0.01 Flowshop Hybird menggunakan Algoritme Genetika Fitness terbaik:  0.0055 Min Makespan: 180.7407 Generasi F it n e s s
Gambar  9  menunjukkan  grafik  nilai fitness  dan  makespan  yang  dihasilkan  tiap generasi  oleh  algoritma GA-HFFME .  Dari grafik  dapat  dilihat  bahwa  nilai  fitness maksimum  (optimal)  sudah  mulai  tercapai pada generasi ke 30. Sebeum generasi ke 30 masih  terjadi  fluktuasi  nilai  fitness  yang disebabkan  oleh  proses  pindah  silang  dan mutasi  yang  dilakukan  oleh  operator genetika.
Sampai generasi ke-30, jumlah alternatif  solusi  (Na)  yang  telah  dievaluasi oleh algoritma genetika mencapai :
Na  =  30  generasi  x  20  alternatif solusi/generasi = 600 alternatif solusi
Jumlah  total  alternatif  solusi  dalam  ruang pencarian (Ns) adalah :
Ns  =  jumlah  permutasi  job  =  11!  = 39.916.800 alternatif solusi Pencarian  yang  dilakukan  oleh  algoritma genetika  dalam  ruang  pencarian  (Psearch) yang tersedia adalah :
Psearch  =  (Na/Ns)  x  100  %  = (600/39.916.800) x 100% = 0,0015 %
Dari  nilai  di  atas  dapat  dilihat  bahwa algoritma  genetika  bekerja  sangat  efisien, dengan melakukan pencarian sebesar 0,0015%  dari  ruang  pencarian  yang  ada, algoritma  genetika  sudah  bisa  memperoleh suatu solusi yang mendekati optimum. Penggunaan  algoritma  genetika  untuk kasus penjadwalan flowshop yang kompleks  dan  termasuk  area NP-hard seperti model
GA-HFFME ini menunjukkan  bahwa  suatu  hasil  yang optimal  bisa  diperoleh  dalam  waktu  yang singkat  dengan  proses  pencarian  yang efisien.

## 4. KESIMPULAN

## Kesimpulan
Model  penjadwalan  flowshop  untuk industri kemasan karton terdiri dari 5 stage dimana stage 1 sampai 4 terdiri dari mesin- mesin yang tidak identik dan diperuntukkan khusus untuk memproduksi kemasan tertentu.  Pesanan  yang  datang  tidak  harus melewati setiap stage, tetapi dapat melompati  stage  tertentu.  Karakteristik  ini membuat kasus ini diklasifikasikan sebagai hybrid  and  flexible  flowshop  with  machine eligibility (HFFME)  dan  model  yang
dihasilkan  disebut Genetic  Algorithm  for Hybrid  and  Flexible  Flowshop  with Machine Eligibility ( GA-HFFME ).
Model  diuji  cobakan  pada  11  pesanan dengan  karakteristik  proses  produksi  yang berbeda-beda.
Hasil
pengujian menunjukkan  bahwa  model GA-HFFME dapat memberikan solusi penjadwalan yang memuaskan.  Nilai  fitness  dan  makespan yang  mendekati  optimum  dapat  diperoleh dalam waktu running program yang singkat dan  efisien.  Efisiensi  pencarian  dengan model GA-HFFME ditunjukkan oleh eksplorasi  ruang  pencarian  yang  hanya sebesar  0,0015%  dari  seluruh  ruang pencarian yang tersedia.

## Saran
Model  penelitian  ini  dapat  dilanjutkan dengan  algoritma  genetika  yang  bersifat hybrid ,  yaitu  dengan  mengkombinasikan beberapa  operator  pindah  silang  dan operator  mutasi  untuk  mendapatkan  solusi yang  lebih  optimal.  Kompleksitas  model juga  dapat  ditambah  dengan  menambah jumlah stage dalam  proses  produksi  dan memberikan  lebih  banyak  fleksibilitas produksi melalui kemungkinan kasus subkontrak  pada  salah  satu  atau  beberapa stage .

## 5. DAFTAR PUSTAKA
[1] Boukef, H., M. Benrejeb and P. Borne. 2007.  A  Proposed  Genetic  Algorithm Coding  for  Flow-Shop  Scheduling. International  Journal  of  Computers, Communications  &  Control ,  II  (3)  :
229-240.
[2] Coles,  R.,  D.M.  Dowell  dan  M.J.
Kirwan. 2003. Food Packaging Technology .  London  :  Blackwell Publishing, CRC Press. [3] Goldberg, D. 1989. Genetic
Algorithms  in  Search,  Optimization and  Machine  Learning .  Addison- Wesley.
[4] Jin,  Z.H.,  K.  Ohno,  T.  Ito  dan  S.E. Elmaghraby.  2002.  Scheduling  hybrid flowshop  in  printed  circuit  board assembly  lines. POMS  Series  in
Technology and Operations Management , Vol. 11.
[5] Kurz,  M.E.  dan  R.G.  Askin.  2003. Comparing scheduling rules for flexible  flow  lines. Int.  J.  Production Economics 85 : 371-388.
[6] Liu,  C.H.  2010.  A  genetic  algorithm based  approach  for  scheduling  of  jobs containing  multiple  orders  in  a  three- machine flowshop. International Journal  of  Production  Research 48
(15) : 4379-4396
[7] Ponnambalam, S.G., P. Aravindan dan S. Chandrasekaran. 2001. Constructive and improvement flowshop scheduling heuristics  :  an  extensive  evaluation. Production Planning & Control 12 (4)
: 335-344.
[8] Rajkumar,  R  dan  P.  Shahabudeen. 2009.  An  improved  genetic  algorithm for  the  flowshop  scheduling  problem. International  Journal  of  Production
Research 47(1) : 233-249.
[9] Raaymakers,  W.H.M.  dan  A.J.M.M Wejters. 2003. Makespan estimation in batch process industries : A
comparioson between regression analysis and neural networks. European  Journal  of  Operational
Research 145 : 14-30.
[10] Ruiz,  R  dan  C.  Maroto.  2006.  A genetic  algorithm  for  hybrid  flowshop with  sequence  dependent  setup  times and  machine  eligibility. European
Journal  of  Operational  Research 169
: 781-800.
[11] Sivanandam,  S.N.  dan  S.N.  Deepa.
2008. Introduction to Genetic Algorithms .  Berlin : Springer-Verlag. [12] Suyanto.  2005.  Algoritma  Genetika Dalam Matlab.  Yogyakarta :  Penerbit Andi.
[13] Wadhwa,  S., J. Madaan  dan  R.  Raina. 2007.  A  Genetic  Algorithm  Based Scheduling  for  a  Flexible  System.
Global  Journal  of  Flexible  Systems Management 8(3) : 15-24.