## PENJADWALAN FLOWSHOP MENGGUNAKAN ALGORITMA NAWAZ ENSCORE HAM
Ilyas Masudin 1 , Dana Marsetya Utama 2 dan Febrianto Susastro 3
Abstract: This  article  attempts  to  schedule  flow  shop  production  using  Nawaz Enscore Ham (NEH) to schedule jobs machining. The objective of this paper is to minimize total makespan which could reduce total production costs. This paper is based  on  the  case  study  where  NEH  is  applied  in  scheduling  jobs  in  machines and  then  compared  with  the  existing  machine’s  scheduling.  The  algorit hm  of NEH  is  also  used  to  reduce  idle  time  of  machines  so  that  the  utility  or performances  of  the  machine are  maintained.    The  results  of  NEH  simulation indicate that by applying NEH algorithm to scheduling machines for 10 jobs and 5 machines can reduce 2.5 per cent or 118 minutes of completing time of jobs. It also decreases total idle time of machines about 582 minutes compared with the existing scheduling.
Keywords: scheduling, Nawaz Enscore Ham, flow shop, completing time

## PENDAHULUAN
Penjadwalan flowshop merupakan  suatu  pergerakan  unit-unit  yang  terus- menerus melalui suatu  rangkaian  stasiun-stasiun  kerja yang  disusun  berdasarkan produk (Baker, 1974). Susunan suatu proses produksi jenis flowshop dapat diterapkan dengan  tepat  untuk  produk-produk  dengan  desain  yang  stabil  dan  diproduksi  secara banyak (volume produk), sehingga investasi dengan tujuan khusus (special purpose) yang dapat secepatnya kembali.
PT. Temprina Media Grafika Cabang Malang adalah sebuah perusahaan yang bergerak di bidang percetakan yang mencetak koran Jawa Pos. Selain memproduksi koran  Jawa  Pos,  perusahaan  ini  juga  memproduksi  berbagai  macam  cetakan  mulai dari  buku  paket,  buku  Lembar  Kerja  Siswa  (LKS),  tabloid,  brosur,  dan  lain-lain. Perusahaan  menyadari  bahwa  penyelesaian  produk  yang  tepat  waktu  dapat mempengaruhi  kepuasan  pelanggan  dan  dapat  meningkatkan  permintaan  produksi. Dengan  melihat  pada  data sales order bulan  Juni  2013,  terdapat  30%  produk  yang mengalami  keterlambatan  penyelesaian  pekerjaan,  sehingga  perusahaan  akan mengalami kerugian dalam biaya pengerjaan dan terkena biaya keterlamabatan.
Untuk  memberikan  kepuasan  pelanggan  dengan  penyelesaian  pesanan  yang tepat waktu dibutuhkan cara atau metode dengan melalui beberapa proses yang juga dapat  memimalkan  biaya  pengerjaan.  Salah  satu  cara  yang  dapat  dilakukan perusahaan  adalah  dengan  melakukan penjadwalan  produksi  yang  sistematis. Terdapat banyak metode penjadwalan flowshop dengan tujuan meminimumkan waktu penyelesaian  pekerjaan  (makespan).  Salah  satu  dari  metode  penjadwalan flowshop
1 Jurusan Teknik Industri, Universitas Muhammadiyah malang Jl. Raya Tlogomas 246 Malang 65144 Email: masudin@umm.ac.id
2 Jurusan Teknik Industri, Universitas Muhammadiyah malang Jl. Raya Tlogomas 246 Malang 65144
3 Jurusan Teknik Industri, Universitas Muhammadiyah malang Jl. Raya Tlogomas 246 Malang 65144
Naskah diterima: 28 April 2014, direvisi: 18 Juni 2014, disetujui: 10 Juli 2014
adalah  metode  penjadwalan Nawaz  Enscore  Ham (NEH).  Metode Nawaz  Enscore Ham (NEH) merupakan incremental construction algorithms yang telah mendapatkan penghargaan sebagai metode heuristic terbaik dalam permutation flow shop problem (FPSP)  (Taillard,  1989),  sehingga  diharapkan  mampu  memberikan  suatu  bantuan berupa alat atau metode dalam menyelesaikan permasalahan di perusahaan mengenai keterlambatan pengerjaan pekerjaan yang dapat mempengaruhi biaya pengerjaan.
Penjadwalan  adalah  pengurutan  pembuatan/pengerjaan  produk  secara menyeluruh  pada  beberapa  buah  mesin.  Dengan demikian  masalah sequencing senantiansa  melibatkan  pengerjaan  sejumlah  komponen  yang  sering  disebut  dengan istilah job. Job sendiri  masih  merupakan  komposisi  dari  sejumlah  elemen-elemen dasar yang disebut aktivitas atau operasi. Tiap aktivitas atau operasi ini membutuhkan alokasi daya tertentu yang sering disebut dengan waktu proses (Ginting, 2009).
Penjadwalan merupakan alat ukur bagi perencanaan agregat. Pesanan-pesanan aktual  pada  tahap  ini  ditugaskan  pertama  kalinya  pada  sumber  daya  tertentu, kemudian dilakukan  pengurutan  kerja  pada  tiap-tiap  pusat  pemrosesan  sehingga dicapai optimisasi utilitas kapasitas yang ada. Pada penjadwalan ini permintaan akan produk-produk yang tertentu (jenis dan jumlah) dari jadwal produksi akan ditugaskan pada pusat-pusat pemrosesan.
Pengertian  penjadwalan  secara  umum  dapat  diartikan  seperti “ schedulling  is the  allocation  of  resources  overtime  to  perform  of  risk”, yang  artinya  penjadwalan adalah  pengalokasian  sumber  daya  yang  terbatas  untuk  mengerjakan  sejumlah pekerjaan (Baker,  1974).  Permasalahan  muncul  apabila  pada  tahap  operasi  tertentu beberapa atau  seluruh  pekerjaan  itu membutuhkan  stasiun  kerja  yang  sama.  Dengan dilakukannya pengukuran pekerjaan ini unit-unit produksi dapat dimanfaatkan secara optimum.  Pemanfaatan  ini  antara  lain  dilakukan  dengan  jalan  meningkatkan  utilitas unit-unit  produksi  melalui  usaha  mereduksi  waktu  menganggur  (idle)  dari  unit-unit yang  bersangkutan.  Pemanfaatan  lainnya  dapat  juga  dilakukan  dengan  cara meminimumkan work  in  process (WIP)  melalui  reduksi  terhadap  waktu  rata-rata pekerjaan yang menunggu dalam baris antrian pada unit-unit produksi (Conway, dkk., 2001).
Metode Nawaz Enscore Ham  (NEH) ini  dikembangkan  oleh  Muhammad Nawaz,  E. Emory  Enscore  Jr,  dan  Inyong  Ham  pada  tahun 1983.  “ In  a  general flowshop,  where  all  the  jobs  must  past  through  all  the  machines  in  the  same  order, certain  heuristic  algorithms  propose  that  the  jobs  with  higher  total  process  time should  be  given  higher  priority  than  the  jobs  with  less  total  process  time” yang artinya dalam penjadwalan flowshop secara umum, dimana semua job harus melewati semua mesin pada order yang sama.  Algoritma heuristic ini mengusulkan bahwa job dengan total waktu proses yang lebih besar seharusnya diberikan prioritas yang lebih besar dari pada job dengan total waktu proses yang lebih kecil (Nawaz, dkk., 1983).
NEH  merupakan  salah  satu  algoritma  yang  bersifat constructive  heurisitc. Algoritma NEH mengasumsikan job yang memiliki total waktu proses untuk semua mesin  yang  lebih  besar  harus didahulukan  dibanding job dengan  total  waktu  proses yang lebih kecil. NEH menginisialisasikan urutan job secara descending berdasarkan total  waktu  proses  tiap  jobnya. Kemudian dilakukan  proses partial  squence,  yaitu menentukan urutan terbaik dari setiap posisi job yang mungkin.
Beberapa  penelitian  penjadwalan produksi flowshop menggunakan algoritma NEH antara lain oleh Satriawan (2010). Metode penjadwalan yang digunakan dalam penelitian  ini  adalah  algoritma  genetika  dan  algoritma Nawaz Enscore Ham (NEH) untuk  menentukan  solusi  optimum  global.  Penelitian  lain  pada  penjadwalan flexible flowshop dengan kriteria minimasi mean tardiness dilakukan oleh Supriyanto (2008)
Masudin, dkk./Penjadwalan Flowshop Menggunakan .…… /JITI, 13 (1), Jun 2014, pp. (54-59)
dengan  mengembangkan Nawas Enscore Ham pada fleksibel  flowshop. Dalam penelitian ini prioritas yang digunakan menggunakan dispatching rules yaitu earliest due date (EDD), first come first served (FCFS), dan Nawaz  Enscore  Ham (NEH). Penggunaan  ketiga  prioritas  ini  didasarkan  aturan  prioritas  (priority  rule) yang memberikan panduan mengurutkan pekerjaan yang harus dilakukan.
Dari  permasalahan  yang  terjadi  dan  dari tinjauan  literatur yang  dilakukan, artikel ini mencoba memecahkan permasalahan penjadwalan mesin flowshop dengan menggunakan  metode  NEH  dengan  tujuan  untuk  mengurangi makespan dan  total biaya produksi sebagai konsekuensi dari penjadwalan mesin.

## METODOLOGI PENELITIAN
Penelitian ini dilakukan PT. Temprina Media Grafia Cabang Malang, dimana data  primer  dikumpulkan  meliputi  data proses  pembuatan  produk  komersial  yang meliputi buku paket, lembar kerja siswa dan brosur sebagai data job. Beberapa data yang diperlukan anatar lain data mesin-mesin yang dipakai yang meliputi data mesin, jumlah  mesin,  spesifikasi  mesin yang  berisi  kapasitas  mesin, urutan  proses pengerjaan, dan waktu proses permesinan.
Gambar 1. Langkah penyenyelesain dengan NEH
Tahap  berikutnya  melakukan  penjadwalan  dengan  metode Nawaz  Enscore Ham, metode  ini  bertujuan  untuk  meminimalkan makespan dengan  cara mendahulukan pekerjaan yang memiliki total waktu pengerjaan terbesar, untuk lebih jelasnya dapat dijelaskan pada tahap pengerjaan metode Nawaz Enscore Ham seperti gambar 1.

## HASIL DAN PEMBAHASAN
Dalam proses menjadwalkan mesin, data utama yang diperlukan adalah waktu proses  setiap job di  setiap  mesinnya.  Data  waktu  permesinan  diperlihatkan  dalam tabel 1.
Jumlahkan waktu proses setiap job
Urutkan job terbesar hingga terkecil
Set K=1 dan K = K+1
For K = K+1 ambil job yang ada pada urutan 1 dan hasilkan k calon urutan parsial baru
Hitung setiap makespan parsial dan mesin flowtime dari calon urutan parsial baru Data waktu proses Periksa apakah K = n? Urutkan parsial baru menjadi urutan final
Tabel 1. Data waktu proses tiap job di tiap mesin
Job Mesin 1 (menit) Mesin 2 (menit) Mesin 3 (menit) Mesin 4 (menit) Mesin 5 (menit) Total Job 1 7 36 65 325 78 511 Job 2 5 28 50 250 60 393 Job 3 8 41 75 375 90 589 Job 4 16 85 155 775 185 1216 Job 5 6 30 55 275 66 432 Job 6 7 36 65 325 78 511 Job 7 7 36 65 325 78 511 Job 8 8 41 75 375 90 589 Job 9 20 104 190 950 227 1491 Job 10 16 85 155 775 185 1216
Penjadwalan mesin  menggunakan  metode Nawaz  Enscore  Ham dilakukan dengan  menggunakan  algoritma  seperti  dalam  gambar  1  untuk  mendapatkan penjadwalan mesin parsial dimana urutan pengerjaan 10 job di 5 mesin.
Tabel 2. Urutan penjadwalan dengan metode heuristic Nawaz Enscore Ham
Iterasi ke- Calon Urutan Parsial Terpilih (Rp ,00) Iterasi ke- Calon Urutan Parsial Terpilih (Rp ,00) 1 9--4 7 6-1-3-10-4-9-8-7 4--9 24.848.512 6-1-3-10-4-9-7-8 2 4-9--10 6-1-3-10-4-7-9-8 4-10--9 6-1-3-10-7-4-9-8 51.859.776 10-4--9 33.833.912 6-1-3-7-10-4-9-8 3 10-4-9-3 6-1-7-3-10-4-9-8 10-4-3-9 6-7-1-3-10-4-9-8 10-3-4-9 7-6-1-3-10-4-9-8 3-10-4-9 36.679.248 8 6-1-3-10-7-4-9-8-5 4 3-10-4-9-8 39.777.216 6-1-3-10-7-4-9-5-8 3-10-4-8-9 6-1-3-10-7-4-5-9-8 3-10-8-4-9 6-1-3-10-7-5-4-9-8 3-8-10-4-9 6-1-3-10-5-7-4-9-8 8-3-10-4-9 6-1-3-5-10-7-4-9-8 55.577.176 5 3-10-4-9-8-1 6-1-5-3-10-7-4-9-8 3-10-4-9-1-8 6-5-1-3-10-7-4-9-8 3-10-4-1-9-8 5-6-1-3-10-7-4-9-8 3-10-1-4-9-8 9 6-1-3-5-10-7-4-9-8-2 3-1-10-4-9-8 6-1-3-5-10-7-4-9-2-8 1-3-10-4-9-8 43.691.376 6-1-3-5-10-7-4-2-9-8 6 1-3-10-4-9-8-6 6-1-3-5-10-7-2-4-9-8 1-3-10-4-9-6-8 6-1-3-5-10-2-7-4-9-8 1-3-10-4-6-9-8 6-1-3-5-2-10-7-4-9-8 1-3-10-6-4-9-8 6-1-3-2-5-10-7-4-9-8 1-3-6-10-4-9-8 6-1-2-3-5-10-7-4-9-8 1-6-3-10-4-9-8 6-2-1-3-5-10-7-4-9-8 6-1-3-10-4-9-8 47.575.576 2-6-1-3-5-10-7-4-9-8 58.750.448
Tabel  2  menunjukkan  calon  parsial berdasarkan hasil iterasi penjadwalan dengan metode NEH. Hasil dari simulasi  yang  dilakukan  memperlihatkan  bahwa jumlah  iterasi  yang  dilakukan  dalam  penjadwalan  dengan  algoritma heuristic NEH adalah  sebanyak  9  iterasi dimana  pada  iterasi  yang  pertama  terpilih  calon  parsial urutan 4-9 dengan total biaya sebesar Rp 24.848.512,00, untuk iterasi kedua terpilih
calon  parsial  urutan  10-4-9  dengan  total  biaya  sebesar  sebesar  Rp  33.833.912,00, calon parsial yang terpilih untuk iterasi yang ketiga yaitu 3-10-4-9 dengan total biaya sebesar Rp 36.679.248,00, calon parsial yang terpilih untuk iterasi ke empat yaitu 3- 10-4-9-8 dengan total biaya Rp 39.777.216,00, sedangkan calon parsial yang terpilih untuk iterasi kelima yaitu 1-3-10-4-9-8 dengan total biaya sebesar Rp 43.691.376,00, pada  iterasi  ke  enam  terpilih  calon  parsial  urutan  6-1-3-10-4-9-8  dengan  total  biaya Rp 47.575.576,00, untuk  iterasi  ke  tujuh  terpilih  calon  parsial 6-1-3-10-4-7-9-8-5 dengan  total  biaya Rp 51.859.776,00,  calon  parsial  yang  terpilih  untuk  iterasi  ke delapan adalah 6-1-3-5-10-4-7-9-8 dengan total biaya sebesar Rp 55.577.176,00, dan calon  parsial  yang  terpilih  untuk  iterasi  kesembilan  adalah  2-6-1-3-5-10-4-7-9-8 dengan total biaya sebesar Rp 58.750.448,00.

## Analisa Hasil Penerapan NEH
Metode heuristic NEH dapat  diterapkan  di perusahaan namun  metode  ini masih  memiliki  kekurangan  sehingga  belum  dapat  memberikan  hasil  yang  sangat optimal jika di praktekkan secara langsung pada lantai produksi. Hal ini dikarenakan jumlah  tardiness  yang  besar  (lihat  tabel  3)  jika  dibandingkan  dengan  metode  awal perusahaan, kasus yang berbeda metode heuristic NEH akan memberikan hasil yang berbeda pula, jadi tidak dapat dipastikan bahwa metode heuristic NEH adalah metode yang  terbaik  yang  dapat  menyelesaikan  masalah  keterlamabatan  pada perusahaan. Secara konsep metode usulan ini lebih mudah untuk dipahami, namun dari hasil yang diberikan tidak dapat diterapkan secara langsung pada perusahaan.
Tabel 3. Perbandingan metode penjadwalan Kriteria Perbandingan Penjadwalan Penjadwalan Perusahaan Penjadwalan NEH Urutan Job 1-2-3-4-5-6-7-8-9-10 2-6-1-3-5-10-7-4-9-8 Makespan 5.036 menit 4.918 menit Idle Time M1 = 4.936 menit M2 = 4.521 menit M3 = 4.076 menit M4 = 286 menit M5 = 3.899 menit M1 = 4.818 menit M2 = 4.401 menit M3 = 3.968 menit M4 = 168 menit M5 = 3.781 menit Tardiness 3.735 menit 6.159 menit Total Biaya Rp 58.888.096,00 Rp 58.750.448,00
Meskipun  dalam  hal  keterlambatan  (tardiness)  metode  NEH  memiliki  nilai keterlambatan  yang  cukup  besar,  namun  kriteria performansi lain  yang  seperti makespan dan idle  time mesin,  metode  NEH  menghasilkan  nilai  yang  lebih  baik, sehingga  saat  perbandingan  total  biaya  dari  performansi makespan, idle  time mesin dan tardiness,  metode  NEH  memberikan  total  biaya  penjadwalan  yang  lebih  kecil dibanding metode perusahaan.

## KESIMPULAN
Dalam artikel ini dibahas penerpan metode NEH dalam menjadwalkan 10 job pada  5  mesin  dengan  tujuan  mengurangi  waktu makespan atau  penyelesaian jobs. Dari  hasil  simulasi  didaptkan  bahwa  nilai makespan penjadwalan  dengan  metode NEH  memberikan  nilai makespan yang  lebih  kecil  dari  metode  perusahaan  yang menggunakan  prinsip  penjadwalan  mesin  dengan  basis first  come  first  service (FCFS).
Meskipun hasil simulasi menunjukan tidak berkurangnya nilai tardiness atau keterlambatan,  akan  tetapi  terdapat  pengurangan  total  biaya  dengan  diterapkannya penjadwalan  dengan  metode  NEH  sebesar  Rp  137.648,00,  sedangkan  dari  utilitas mesin didapatkan pengurangan waktu idle mesin sebesar 582 menit.

## Daftar Pustaka
Ginting, Rosnani. 2009. Penjadwalan Mesin. Yogyakarta: PT. Graha ilmu. Baker, K.R. 1974. Introduction to Sequencing and Scheduling. Canada: John Wiley & Sons, Inc. Conway,  R.  W.; Maxel,  W.L.; and  Miller,  L.W. 2001. Theory of  Scheduling. New York, USA: Andison Wesley Publishing Company Inc.
Taillard, E, 1989. Benchmarks Basic Scheduling Problems. OWRP/21 Dec 1989. Satriawan,  Nedi. 2010. Penjadwalan  Produksi  Flow  Shop  Menggunakan  Algoritma
Genetika  dan  NEH. Skripsi  S1. Bandung: Program  Studi  Ilmu  Komputer, Fakultas Pendidikan  Matematika  dan  Ilmu  Pengetahuan  Alam,  Universitas Pendidikan Indonesia.
Supriyanto. 2008. Penjadwalan Pekerjaan Pada Fleksible Flowshop Dengan Kriteria Minimasi Mean Tardiness Di CV. Dimas Rotan Sukoharjo. Skripsi S1. Surakarta: Universitas Negeri Sebelas Maret.
Nawaz,  Muhammad;  Enscore,  E.  Emory  Jr.;  dan  Ham,  Inyong.  1983.  A  Heuristic Algorithm  for  m-Machine,  n-Job  Flow-shop  Sequencing  Problem. Journal
Omega. Vol. 11, No. 1, pp. 91-95.