## PENERAPAN ALGORITMA ANT COLONY OPTIMIZATION (ACO)
PADA JOB SHOP SCHEDULING PROBLEM (JSSP) DI PT. SIEMENS INDONESIA (CILEGON FACTORY)
Widyawati Universitas Banten Jaya Serang, Banten widyawati@unbaja.ac.id

## ABSTRACT
Fabrication process is often disrupted by non–deterministic job, this create a problem in the Pre-Fabrication department schedule because often the manufacture of raw material for non- deterministic  job  should  given  priority.  This  problem  also  affected  by  the  existing  system which  is  not  yet  fully  developed  to  solve  the  problem  of  optimize  rescheduling  master  line (seen  from  total  makespan  time).  Ant  Colony  Optimization  (ACO)  variant  Ant  System  (AS) was proposed to solve Job Shop Scheduling Problem (JSSP) with the objective to propose the best  schedule  that  give  shortest  makespan. The  algorithm  tested  to  perform  scheduling  of  5 projects (consist of 10 parts) as the initial job, and another 2 projects (consist of 4 parts) as the non-deterministic job. For the initial job, makespan was 287 days and after the arrival of non-deterministic job, makespan was 362 days compare  with the actual manufacturing time (7 project consist of 14 parts) which is ± 511 days.
Keywords:  Ant  Colony  Optimization  (ACO),  Job  Shop  Scheduling  Problem  (JSSP), Makespan Time, Non – Deterministic, Scheduling, Re – Scheduling

## PENDAHULUAN
PT.  Siemens  Indonesia  Cilegon  Factory  (PTSI-CF) merupakan  perusahaan yang bergerak dibidang fabrikasi komponen turbin dan produk industri logam presisi tinggi.  Perusahaan  tersebut  berjalan  berdasarkan  konsep job  by  order (produk  yang diproduksi  atas  surat  pesanan  pelanggan).  Kendala  yang  seringkali  dihadapi  adalah adanya pekerjaan  yang tidak bisa diramalkan  ( non-deterministic ) sehingga  membuat jadwal  produksi  yang  telah  direncanakan  perlu  dilakukan  perubahan.  Dan non deterministic menyebabkan waktu penyelesaian ( makespan time ) lebih panjang.
Ada  tiga  pendekatan  untuk  penjadwalan  ulang,  yaitu:  dengan  menjadwalkan kembali dari awal, melakukan perubahan terhadap jadwal saat perubahan terjadi, atau menunda  beberapa  operasi  yang  telah  dikerjakan  pada  jadwal  lama  dan  melakukan
penjadwalan  ulang  terhadap  sisa  operasi  yang  belum  dikerjakan.  Penelitzian  ini bertujuan  untuk  mencari  penjadwalan  dengan makespan  time yang  paling  minimum menggunakan algoritma Ant Colony Optimization (ACO) berjenis Ant System (AS).

## Metode
Metode  penelitian  ini  dilakukan  dengan  beberapa  tahap  seperti  studi  literatur, pengumpulan data, pengolahan data, dan analisis hasil.
Diagram Alir , berikut ini merupakan tahapan yang dilakukan dalam penelitian:

## Gambar 1 Diagram Alir Penelitian

## Pengumpulan Data
Sumber data yang digunakan didalam penelitian ini merupakan data sekunder yang diperoleh dari sumber yang sudah ada yaitu berupa dokumen perusahaan. Data yang  digunakan  adalah  data  sekunder,  yaitu  berupa  data  jumlah  project  pada  tahun 2015, rute project , dan waktu proses setiap project .

## Pengolahan Data
Adapun  teknik  pengolahan  data  yang  dilakukan  yaitu  dengan  menerapkan algoritma Ant  Colony  Optimization (ACO)  berjenis Ant  System (AS).  Berikut  ini merupakan tahapan secara umum dalam melakukan proses pengolahan data:

## Gambar 2 Tahapan Pengolahan Data

## Metode Ant Colony Optimization
Algoritma  semut  atau  Ant  Colony  Optimization  (ACO)  merupakan  algoritma pencarian  berdasarkan  probabilistik,  di  mana  probabilistik  yang  digunakan merupakan  probabilistik  dengan  bobot  sehingga  butir  pencarian  dengan  bobot  yang lebih besar akan berakibat memiliki kemungkinan terpilih lebih besar pula (Anamisa & Djunaidy, 2014).
Model  yang digunakan untuk menotasikan  masalah penjadwalan  jobshop pada n-job dan m-mesin adalah (Zukhri & Alhakim, 2004):
𝑛 𝑚 ⁄ 𝐺 ⁄ 𝐶 ⁄ 𝑚𝑎𝑥 (1)
Yang  mana  n  mendefinisikan  banyaknya  job  yang  akan  diproses,  m  menunjukkan banyaknya mesin yang dimiliki, C max merupakan minimum makespantime dari suatu produksi  dan  G  berisikan  aturan  urutan  proses  mesin  untuk  setiap  job  dan  waktu prosesnya. Proses mesin dimodelkan dalam bentuk matrik T , semisal untuk T dengan n=2 dan m=3 adalah sebagai berikut:

## 𝑇 = [ 𝑀1 𝑀2 𝑀3 𝑀4 𝑀5
𝑀6 ] (2)
Sedangkan untuk merepresentasikan waktu proses setiap operasi dimodelkan dengan matrik P:
𝑃 = [ 𝑡(𝑂 11 ) ⋯ 𝑡(𝑂 1𝑚 ) 𝑡(𝑂 21 ) ⋯ ⋯ ⋯ ⋯ ⋯ 𝑡(𝑂 2𝑚 ) ⋯ ⋯ 𝑡(𝑂 𝑛1 ) ⋯ 𝑡(𝑂 𝑛𝑚 )] (3)
Untuk  merepresentasikan  permasalahan jobshop pada  algoritma  semut  digunakan graph sebagai  model  yang  akan  mempermudah  dalam  pencarian  minimum  waktu penyelesaian.  Model graph dari  2/3/G/Cmax job  shop dapat  digambarkan  pada gambar 3 dibawah ini:
Gambar 3 Representasi 2/3/G/Cmax job shop pada graph
Setiap  node  dalam  graph  merupakan  representasi  dari  job  operasi  pada  matrik  T, jumlah node dirumuskan dengan:
𝑁𝑜𝑑𝑒𝑠 = (𝑛 ∗ 𝑚) + 1 (4)
Sedangkan untuk banyaknya garis dinotasikan sebagai berikut:
𝐺𝑎𝑟𝑖𝑠 = |𝑂| ∗ (|𝑂| − 1)2 + 𝑁 (5) |𝑂| = 𝑛 ∗ 𝑚

## (6)
Dalam graph diatas setiap node memiliki batasan node yang dapat dikunjungi karena terdapat beberapa garis satu arah maka suatu node tidak memiliki hak untuk melalui jalur  yang  berlawanan  arah  dengan  tanda  arah  panah  tersebut.  Dengan  demikian setiap operasi penentuan mesin harus terlebih dahulu memeriksa batasan mesin yang boleh  dilalui.Selain  itu  pemilihan  node  tujuan  yang  layak  dilalui  difilter  dengan batasan  operasi  yang  harus  terurut.Misalkan  jika  job  1  operasi  ke-2  hanya  boleh dipilih  sebagai  node  tujuan  jika  job  1  operasi  ke-1  telah  dipilih  atau  dilalui  oleh semut.
Berikut ini merupakan flowchart penerapan algoritma ACO:
Gambar 4 Tahapan Pengolahan Data

## Hasil dan Pembahasan
Penelitian  yang  dilakukan  dalam  penerapan  algoritma Ant  Colony  Optimization (ACO)  untuk  penyelesaian Job  Shop  Scheduling    Problem (JSSP)  di  PT.  Siemens Indonesia  menggunakan  bantuan  perangkat  lunak  Matlab.  Data  yang  digunakan merupakan hasil pengolahan terhadap data scheduling produk PT. Siemens Indonesia. Data ini  menjelaskan  men gen ai Schedule bahan baku suatu project / job mulai  masuk dan  diproses  di  suatu  mesin  hingga  selesai  pada  mesin  tertentu  di  departemen Pre- Fabrication (PF) .  Schedule tersebut  diolah  dari  yang  awalnya  berbentuk monitoring board dirubah kedalam  bentuk matriks sehingga  mudah dalam proses penerapan re- schedule menggunakan  algoritma  ACO  dengan  bantuan  Matlab.  Dari  hasil pengolahan  data  didapatkan  total  waktu  penyelesaian  ( makespan  time )  yang  paling minimum.

## Seleksi Data
Tahap awal dari perancangan penelitian ini adalah tahap seleksi data, yaitu pemilihan atribut  yang  nantinya  dilakukan  proses  transformasi  data  dari  data  mentah  kedalam bentuk tabel matriks untuk diolah ke tahap selanjutnya.

## Gambar 5 Data Mentah Schedule Planning

## Transformasi Data
Transformasi  data  merupakan  tahapan  yang  akan  dilakukan  setelah  persiapan  dan seleksi  data.  Pada  tahap  ini  data  mentah  akan  disesuaikan  kedalam  format  yang
diterima  oleh  perangkat  lunak  yang  akan  membantu  melakukan  pemrosesan  data (Matlab). Ada dua tahapan yang akan dilakukan didalam tahapan ini, yaitu:
a. Transformasi Format Data
Pada  tahap  ini  data  mentah schedule  planning tersebut  dirubah  pada  bagian waktu  proses  dari  setiap  komponen  pada  masing-masing  mesin  kedalam bentuk  satuan  hari.  Gambar  3.2  ini  merupakan  gambaran  hasil  transformasi tersebut secara umum.

## Gambar 6 Hasil Transformasi Format Data
b. Transformasi Data kedalam Matriks
Tahapan  transformasi  data  kedalam  bentuk  matriks  adalah  merubah  data satuan  hari  diatas  kedalam  bentuk  matriks  dan  simbol  dengan  tujuan mempermudah  dalam  proses  pengolahan  data  dan  mempermudah  ketika melakukan  proses  pengimputan  data  menggunakan  perangkat  lunak  matlab tersebut.

## Split Data
Tahapan split  data merupakan  tahapan  dimana  data  yang  berasal  dari  transformasi matriks tersebut dikelompokan berdasarkan kelompok data yang akan diproses sesuai Schedule  planning dan  data  yang  memiliki  sifat non-deterministik (tidak  dapat diramalkan).
Sifat non-deterministik didalam  set  data  ini  diambil  dari  status purchase  order (PO) project yang  pada  awalanya  sudah  ditetapkan  terlebih  dahulu Schedule  planningny a oleh  planner.  Namun  hingga  waktu  akan  diproses  status  dari  penetapan  ( approval ) dari PO tersebut tidak berubah, oleh karena itu perlu dilakukan tindakan pengambilan keputusan  mengutamakan project yang  sudah  memiliki  status  PO  ( PO  Release ) meskipun project yang memiliki status PO not-release merupakan project yang lebih dahulu direncanakan.

## Pengolahan Data Training
Gambar 7 Data Training Project LPIC

## Tabel 1 Parameter yang Ditetapkan

## Hasil Pemrosesan Data
Adapun  kombinasi  yang  akan  dilakukan  penelitian  {α,  β,  ρ,  dan  Q}  adalah  tertera pada tabel 2 dibawah ini:

## Tabel 2 Kombinasi Parameter
Gambar 8 Total Makespan Time
Gambar 9 Diagram Hubungan Waktu Dengan Job Sebelum dan Sesudah Penambahan Job
Gambar 10 Output Waktu Rata – Rata Proses
Tabel 3 Perbandingan Hasil Makespan Time dari Berbagai Paramater

## Gambar 11 Grafik Waktu Proses Rata-rata
Dari  hasil  menunjukan  bahwa makespan  time terkecil  sebelum job baru  datang adalah 207 hari satuan waktu, sedangkan makespan time terkecil setelah job baru datang  adalah  295  hari  satuan  waktu  untuk  data  dengan  menggunakan  nilai ketetapan  { 𝛼 ,  β,  ρ,  dan  Q}  =  {1,  2,  0.5,  100}.  Dengan  ini  menjelaskan  bahwa untuk menyelesaikan 4 job (8 komponen) dengan jumlah mesin sebanyak 5 mesin maka makespan  time terkecil  yang  dibutuhkan  adalah  selama  207  hari.  Namun apabila  kedatangan job yang  sifatnya non-deterministic maka  akan  melakukan proses re-schedull penjadwalan  yang  sudah  diramalkan,  oleh  karena  itu  akan muncul  perubahan  waktu  yang  lebih  lama  untuk  menyelesaikan  semua job termasuk jobnon-deterministic tersebut  sebesar  295  hari  (2  job non  – deterministic ).
Vol.1 No.1 tahun 2018

## Pengolahan Data Testing
Gambar 12 Data Testing Project LPIC
Tabel 4 Parameter Testing yang Ditetapkan
Gambar 13 Output Pengolahan Data Testing
Gambar 14 Diagram Hubungan Waktu Dengan Job Sebelum Dan Sesudah Penambahan Job

## Gambar 15 Output Waktu Rata – Rata Proses
Dari hasil  menunjukan  bahwa makespan time terkecil untuk pengolahan data testing sebelum job baru  datang  adalah  287  hari  satuan  waktu,  sedangkan makespan  time terkecil  setelah job baru  datang  adalah  362  hari  satuan  waktu  untuk  data  dengan menggunakan  nilai  ketetapan  { 𝛼 ,  β,  ρ,  dan  Q}  =  {2,  2,  0,99,  100}.  Dengan  ini menjelaskan bahwa untuk menyelesaikan 5 job (10 Komponen) dengan jumlah mesin sebanyak 5  mesin  maka makespan time terkecil  yang dibutuhkan adalah selama 287 hari.  Namun  apabila  kedatangan job yang  sifatnya non-deterministic (2  job)  maka akan melakukan proses re-schedull penjadwalan yang sudah diramalkan, oleh karena itu  akan  muncul  perubahan  waktu  yang  lebih  lama  untuk  menyelesaikan  semua job termasuk jobnon-deterministic tersebut sebesar 362 hari.

## Kesimpulan
Adapun  kesimpulan  yang  didapatkan  berdasarkan  pengolahan  data testing untuk penerapan Ant Colony Optimization (ACO) berjenis Ant System (AS) pada Job Shop Scheduling    Problem (JSSP)  di  PT.  Siemens  Indonesia  dengan  menggunakan parameter   terbaik{ 𝛼 ,  β,  ρ,  dan  Q}  =  {2,  2,  0,99,  100}  adanya  perbedaan  antara waktu  penyelesaian  proses  produksi actual yang  ditetapkan  oleh planner dengan waktu proses produksi yang menggunakan algoritma ACO. Waktu proses actual yang
dibutuhkan  adalah  1  bulan  atau  +/-  37  hari  untuk  penyelesaian  1  komponenoleh karena  itu  jika  mengerjakan  5 project (10  komponen)  dibutuhkan  waktu  selama  +/- 370  hari,  sedangkan  didalam  data testing dengan  jumlah   5 project (10  komponen) waktu yang dibutuhkan adalah selama 287 hari. Ketika kedatangan job yang bersifat non  –  deterministic sebanyak  2 project/job (4  komponen)  dibutuhkan  waktu  selama 362  hari  sedangkan  secara actual dibutuhkan  waktu  untuk  pengerjaan  7 project/job (14  komponen)   adalah  selama  +/-  517  hari.  Hal  ini  menunjukan  bahwa  dengan menerapkan  Algoritma ACO didalam  JSSP dapat  menghemat waktu selama +/- 155 hari.

## Daftar Pustaka
Al  Salami,  N.  M.  (2009).  Ant  Colony  Optimization  Algorithm. UbiCC  Journal,  Volume  4, Number 3 , 823-826.
Anamisa,  D.  R.,  &  Djunaidy,  A.  (2014).  Penyelesaian  Penjadwalan  Mata  Kuliah Menggunakan  Hibridisasi  Algoritma  Genetika  dan  Algoritma  Koloni  Semut. JUTI, Volume 12, Nomor 1 , 15-20.
Aprilius, W., Augustino, L., & M. H., O. Y. (2013). Implementasi Algoritma MAX-MIN Ant System  pada  Penjadwalan  Mata  Kuliah. ULTIMATICS,  Vol.  V,  No.  2,  ISSN  2085- 4552 , 48-53. Ariesta,  Y.  (2012). Penerapan  Ant  Colony  System  Pada  Vehicle  Routing  Problem  Untuk Menentukan  Rute  Distribusi  Terpendek. Jakarta:  Jurusan  Teknik  Industri,  Fakultas Teknologi Industri, Universitas Trisakti.
Astuti,  M.  (2013). Studi  Penjadwalan  Job  Shop  untuk  Meminimalkan  Waktu  Keseluruhan Menggunakan Pendekatan Algoritma Artificial Immune System. Yogyakarta: Volume V, Nomor 1.
Çalis,  B.,  &  Bulkan,  S.  (2013).  A  research  survey:  review  of  AI  solution  strategies  of  job shop scheduling problem. Journal of Intelligent Manufacturing (DOI 10.1007/s10845- 013-0837-8) . Dorigo, M. (1996). The Ant System: Optimization by a Colony Of Cooperating Agents. IEEE Transactions on Systems, Man, and Cybernetics–Part B, Vol.26, No.1, 1996, pp.1-13 , 1-26.
Dorigo,  M.,  Di  Caro,  G.,  &  Gambardella,  L.  (1999). Ant  Algorithms  for  Discrete Optimization.
Flórez, E., Gómez, W., & Bautista, M. (2013). An  Ant Colony Optimization  Algorithm For Job  Shop  Scheduling  Problem. International  Journal  of  Artificial  Intelligence  & Applications (IJAIA), Vol. 4, No. 4 , 53-66.
Jones, A., & Rabelo, L. (1998). Survey of Job Shop Scheduling Techniques.
Laksono,  A.  (2009). Algoritma  Ant  Colony  Optimization  (ACO)  Untuk  Menyelesaikan Traveling  Salesman  Problem  (TSP). Semarang:  Program  Studi  Matematika  Jurusan Matematika, Fakultas MIPA, Universitas Diponegoro.
Omkumar,  M.,  &  Shahabudeen,  P.  (n.d.).  Ant  Colony  Optimization  for  Multilevel Assembly  Job  Shop  Scheduling. The  International  Journal  of  Applied Management and Technology, Vol 6, Num 1 (IJAMT) , 127-152.
Rajendran, C., & Ziegler, H. (2004). Ant-colony algorithms for permutation flowshop scheduling  to  minimize  makespan/total  flowtime  of  jobs. European  Journal  of Operational Research 155 (2004), Elsevier , 426-438.
Ventresca,  M.,  &  Ombuki,  B.  (2004). Ant  Colony  Optimization  for  Job  Shop Scheduling  Problem. St.  Catharines,  Ontario,  Canada  L2S  3A1:  Brock University, Department of Computer Science.
Zhang, S., Wong, T., Zhang, L., & Wan, S. (n.d.). A two-stage approach based on Ant Colony  Optimization  Algorithm  for  Integrated  Process  Planning  and Scheduling. Proceedings of the 41st International Conference on Computers & Industrial  Engineering (pp.  804-809).  Pokfulam  Road,  Hong  Kong:  The University of Hong Kong.
Zukhri,  Z.,  &  Alhakim,  S.  (2004).  Algoritma  Semut  Pada  Penjadwalan  Produksi  Job Shop. Media Informatika, Vol. 2, No. 2, ISSN: 0854-4743 , 75-81.