## Penjadwalan Produksi Flow Shop untuk Meminimalkan Makespan dengan Metode Pour,
Pemrograman Dinamis dan Branch and Bound di CV. Bonjor Jaya

## Dwi Agustina Kurniawati
Jurusan Teknik Industri UIN Sunan Kalijaga Jln. Laksda Adisucipto, Daerah Istimewa Yogyakarta 55281
dwi.kurniawati@uin-suka.ac.id

## (Makalah: Diterima Agustus 2018, direvisi Mei 2019, dipublikasikan Juli 2019)
Intisari—  Penjadwalan  didefinisikan  sebagai  proses  pengalokasian  sumber  untuk  memilih  sekumpulan  tugas  dalam  jangka  waktu tertentu.  CV.  Bonjor  Jaya  menerapkan  penjadwalan  dengan  sistem  First  Come  First  Serve  (FCFS).  Penelitian  ini  bertujuan  untuk mencari  kombinasi  urutan  pengerjaan  produk  yang  memiliki  nilai  makespan  minimum  dengan  menggunakan  metode  Pour, Pemrograman Dinamis dan Branch and Bound. Metode Pour menghasilkan kombinasi urutan 3-4-2-1 dengan nilai makespan sebesar 89814.59 detik. Metode Pemrograman Dinamis menghasilkan kombinasi urutan 3-1-2-4 dengan nilai makespan sebesar 90012.03 detik. Metode  Branch  and  Bound  menghasilkan  kombinasi  urutan  3-4-2-1  dan  3-2-4-1  dengan  nilai  makespan  sebesar  89814.59  detik. Berdasarkan  nilai  makespan  yang  diperoleh  maka  metode  Pour  dan  Branch  and  Bound  adalah  metode  yang  paling  tepat  untuk diterapkan di CV. Bonjor Jaya dengan selisih nilai makespan 484.39 lebih cepat daripada metode penjadwalan yang diterapakan oleh perusahaan.
Kata kunci —Branch and Bound, makespan, Pemrograman Dinamis, Penjadwalan, Pour
Abstract—Scheduling is defined as the process of allocating resources to select a set of tasks within a certain period. CV. Bonjor Jaya implements scheduling with the First Come First Serve (FCFS) system. This study aims to find the sequence combination of products that  have  a  minimum  makespan  value  using  the  Pour  method,  Dynamic  Programming  and  Branch  and  Bound.  The  Pour  method produces  a  combination  of  3-4-2-1  with  an  makespan  value  of  89814.59  seconds.  Dynamic  Programming  Method  produces  a combination of 3-1-2-4 sequence with an  makespan value of 90012.03 seconds. The Branch and Bound method produces a sequence combination of 3-4-2-1 and 3-2-4-1 with an makespan value of 89814.59 seconds. Based on the makespan value obtained, the Pour and Branch and Bound methods are the most appropriate method to be applied in the CV. Bonjor Jaya with the difference in makespan value 484.39 faster than the scheduling method applied by the company.
Keywords — Branch and Bound, makespan, Dynamic Programming, Scheduling, Pour

## I. P ENDAHULUAN
Industri adalah bidang yang menggunakan ketrampilan, ketekunan  kerja  dan  penggunan  alat-alat  di  bidang pengolahan  hasil-hasil  bumi,  dan  distribusi  sebagai dasarnya. Salah satu tujuan pada dunia industri ialah untuk membuat  produk  yang  sesuai  dengan  pesanan  atau permintaan  dari  konsumen.  Salah  satu  permintaan konsumen  ialah  dalam  hal  ketepatan  waktu.  Penjadwalan terhadap  produksi  ialah  salah  satu  solusi  terkait  ketepatan waktu,  agar  bisa  memutuskan  pekerjaan  yang  mana  yang akan dilakukan untuk para konsumen. Dengan penjadwalan yang  baik  maka  perusahaan  dapat  mengatasi  masalah- masalah  dalam  jadwal  produksi  dan  mampu  memproduksi produknya dengan optimal dengan waktu yang minimum.
Menurut  Baker  dan  Trietsch  [1],  penjadwalan didefinisikan  sebagai  proses  pengalokasian  sumber  untuk memilih  sekumpulan  tugas  dalam  jangka  waktu  tertentu. Ada  2  jenis  persoalan  penjadwalan  dalam  penjadwalan produksi, yaitu penjadwalan flow shop dan penjadwalan job shop .  Kriteria  penjadwalan  yang  berdasarkan  waktu  ini dapat  dibedakan  atas  minimasi makespan dan  pemenuhan due date [2]. Dalam penjadwalan, salah satu acara menekan waktu  produksi  adalah  dengan  meminimasi makespan . Menurut  Ginting  (2009), makespan adalah  total  waktu penyelesaian pekerjaan pekerjaan mulai dari urutan pertama yang  dikerjakan  pada  mesin  atau work  center pertama sampai  kepada  urutan  pekerjaan  terakhir  pada  mesin  atau work center terakhir.
CV. Bonjor Jaya merupakan perusahaan yang bergerak di bidang pengecoran logam. CV. Bonjor Jaya bertempat di Klaten  dan  mempunyai  2  area  pabrik.  Produk  yang dihasilkan oleh CV. Bonjor Jaya adalah semua produk  dengan  bahan  baku Ferro  Casting (FC), Ferro Casting  Dactile (FCD)  dan  alumunium,  dengan  produk utamanya yaitu Pulley V-Belt berbagai ukuran dari 2 inch – 45 inch dan ukuran belt A, B, C, dan D. Selain Pulley V-Belt , perusahaan  juga  memproduksi  sesuai  pesanan  customer dengan bentuk, model dan ukuran yang dipesan.
Penjadwalan produksi yang diterapkan oleh CV. Bonjor Jaya  secara  umum  masih  berubah-ubah  dan  tidak  tetap dikarenakan  prioritas  produk  yang  dikerjakan  adalah  yang masuk  terlebih  dahulu  dengan  metode First  Come  First Serve (FCFS).  Dampak  yang  dihasilkan  adalah  ketika penjadwalan  yang  dilakukan  kurang  tepat  maka  besarnya makespan dalam sistem produksi tersebut akan meningkat. Besarnya makespan mengakibatkan  waktu  produksi semakin  bertambah  sehingga  waktu  yang  dimiliki perusahaan  untuk  memproduksi  produk  yang  lain  menjadi sedikit.  Penjadwalan  mesin  dalam  menghitung makespan menjadi  pilihan  bagi  peneliti  untuk  dapat  menekan  waktu produksi.
Penelitian yang dilakukan Irsyad [3] menunjukan bahwa Algoritma Heuristik Pour lebih baik dari metode First Come First  Serve (FCFS)  dan  EDD  karena  memiliki  nilai makespan terkecil dan performansi yang lebih baik. Pour [4] mengusulkan  metode  heuristik  baru  yang  dinamakan Algoritma Pour untuk  menentukan penjadwalan flow shop n job m  mesin.  Dalam  penelitian  tersebut  menunjukan bahwa Algoritma Pour memiliki performansi  yang  terbaik jika dibandingkan dengan algoritma Campbell, Dudek, and Smith (CDS), Palmer , dan Nawaz Enscore Ham (NEH) yang digunakan oleh Hamman [5] dan Karim [6].
Pada  proses  produksi  di  CV.  Bonjor  Jaya  melibatkan banyak  mesin  dan  stasiun  kerja,  dan  menurut  Sipper  dan Bulfin  (1998)  dalam  Widyawanti  dan  Abusini  [7] penjadwalan  lebih  dari  3  mesin  yang  baik  adalah menggunakan metode Branch and Bound .
Menurut  Baker  dan  Trietsch  [1]  di  bukunya  yang berjudul Principles  of  Sequencing  and  Scheduling , Pemrograman Dinamis  adalah  salah  satu metode penjadwalan  optimasi  umum  teknik  pembuatan  keputusan yang berurutan.
Penjadwalan  produksi  yang  tepat  dapat  meminimalkan makespan sehingga  waktu  produksi  yang  tersedia  dapat dialihkan  untuk  menyelesaikan  produk  yang  lain. Berdasarkan  gambaran  di  atas  maka  penelitian  ini mengangkat  tema  penjadwalan  produksi flow  shop untuk meminimalkan makespan dengan  metode Pour ,  metode Pemrograman  Dinamis  dan  metode Branch  and  Bound di CV.  Bonjor  Jaya.  Penggunaan  lebih  dari  satu  metode dimaksudkan  agar  hasil  kombinasi  urutan job dapat  lebih bervariasi sehingga nilai makespan yang dipilih dapat lebih minimal.

## II. T INJAUAN P USTAKA
Menurut  Ginting  [2],  penjadwalan  adalah  pengurutan pembuatan atau pengerjaan produk secara menyeluruh yang dikerjakan  pada  beberapa  buah  mesin  yang  melibatkan pengerjaan sejumlah komponen yang sering disebut dengan istilah ‘ job ’.
Tujuan dari aktivitas penjadwalan adalah sebagai berikut [2]:
1. Meningkatkan penggunaan sumberdaya atau mengurangi  waktu  tunggunya,  sehingga  total  waktu proses  dapat  berkurang,  dan  produktivitas  dapat meningkat.
2. Mengurangi  persediaan  barang  setengah  jadi  atau mengurangi sejumlah pekerjaan yang menunggu dalam antrian ketika sumber daya yang ada masih mengerjakan tugas  yang  lain.  Teori  Baker  mengatakan,  jika  aliran kerja  suatu  jadwal  konstan,  maka  antrian  yang mengurangi  rata-rata  waktu  alir  akan  mengurangi  rata- rata persediaan barang jadi.
3. Mengurangi  beberapa  keterlambatan  pada  pekerjaan yang  mempunyai  batas  waktu  penyelesaian  sehingga akan meminimasi penalty cost (biaya keterlambatan).
4. Membantu pengambilan keputusan mengenai perencanaan  kapasitas  pabrik  dan  jenis  kapasitas  yang dibutuhkan  sehingga  penambahan  biaya  yang  mahal dapat dihindarkan

## A. Metode Pour
Hamid  Davoud  Pour  [4]  mengembangkan  algoritma heuristik  baru  di  dalam  menyelesaikan  penjadwalan flow shop dengan  tujuan  meminimalkan makespan ( flow  time maksimum)  yaitu  berdasarkan  pendekatan  kombinasi.  Hal ini dilakukan dengan cara mengganti setiap job dengan job lainnya  dalam  urutan  sampai  ditemukan  kombinasi urutan yang dapat memenuhi kriteria tujuan [2]. Dalam metode ini diasumsikan bahwa semua job diproses secara terpisah dan independen  untuk  setiap  mesinnya,  berikut  adalah  notasi yang digunakan [2]:
• Pij = waktu proses dari job i pada mesin j .
• Cij = rentang waktu antara saat job i pada mesin j dimulai ( t = 0) sampai job itu selesai.
• ∑Ci = sum  of  completion  time untuk job  i pada  semua mesin.
• Fmax = rentang waktu antara saat pekerjaan tersedia atau dapat dimulai sampai pekerjaan itu selesai ( makespan ). Langkah-langkah  pengerjaan  Algoritma  Heuristik  Pour [2]:
1. Memilih job 1 sebagai urutan pertama sementara dalam urutan  pengerjaan  sehingga  waktu  proses job 1  pada semua mesin dianggap nol.
2. Menempatkan job - job lain (selain job yang sudah dipilih sebagai  urutan  pertama,  yaitu  job  1)  pada  urutan berikutnya.
3. Memilih  waktu  proses  terkecil  untuk  masing-masing mesin.
4. Melakukan penambahan waktu proses ( completion time )
pada Pij dengan aturan increasing processing time , yaitu dengan  menambahkan  waktu  proses  secara  kumulatif dari yang terkecil menuju yang terbesar pada tiap Pij . 5. Menghitung sum of completion time (∑ Ci ) untuk setiap job yang ada.
6. Mengurutkan ∑ Ci dengan aturan increasing order (yaitu pengurutan yang dimulai dari yang terkecil hingga yang terbesar) untuk diletakkan pada urutan setelah job yang sudah dipilih untuk urutan pertama sementara (yaitu job 1)

## B. Metode Pemrograman Dinamis
Menurut Baker dan Trietsch [1], Pemrograman Dinamis diterapkan  pada  masalah-masalah  yang  bisa  dipisah- pisahkan  menjadi  suatu  sub  masalah  yang  saling berhubungan, dimana hasil keputusan tiap tahap dipengaruhi  oleh  keputusan  yang  diambil  pada  tahap sebelumnya. Pemrograman Dinamis adalah teknik manajemen sains yang diaplikasikan kepada persoalan yang melibatkan  keputusan  berurutan  yang  saling  berkaitan. Program ini dikembangkan oleh Richard Bellman dan G. B Dantzig  pada  tahun  1940-1950  [2].  Ide  dasar  program dinamis  ini  adalah  membagi  persoalan  menjadi  beberapa bagian yang lebih kecil sehingga memudahkan penyelesaiannya.  Dengan  kata  lain,  awalnya  program dinamis  membagi  masalah  asli  ke  dalam  sub-sub  masalah dan  kemudian  menentukan  solusi  optimal  masalah  asli dengan pemecahan rekursif sub-sub masalah [2].
Menurut Baker dan Trietsch [1], penerapan Pemrograman Dinamis dalam penjadwalan untuk meminimalkan  total tardiness ,  notasi  J  menunjukkan beberapa  set  atau  himpunan  dari job dan  notasi  p(J) menunjukkan total waktu yang dibutuhkan untuk mengolah pekerjaan  di  set  J.  Notasi  (J  -  j)  digunakan  untuk menunjukkan  nilai  set  J  tanpa  elemen  j.  Dianggap  bahwa urutan  telah  ditentukan  di  mana job di  set  J  mendahului semua job lainnya. Selanjutnya, dihitung nilai dari tardiness minimum dengan semua kemungkinan urutan penjadwalan di set J dengan job j diletakkan di posisi terakhir urutan atau bisa juga ditulis dengan gj[p(J)]. Mengingat job j di posisi terakhir, nilai G(J) adalah penjumlahan dari dua faktor, yaitu nilai  gj[p(J)] dan nilai  minimum dari job yang tersisa atau bisa juga ditulis sebagai G(J - j). G(J-j) adalah nilai optimal yang  diperoleh  dengan  memecahkan  subproblem  yang terdiri dari job di set (J - j). Berikut adalah notasi yang digunakan dalam penjadwalan  untuk  meminimasi  total tardiness dengan metode Pemtograman Dinamis [1]:
• J = beberapa set dari job – job
• p(J) = waktu proses job pada set J
• j ϵ J = job – job anggota dari J
• gj  [p(J)]  =  nilai  tardiness  minimum  dengan  semua kemungkinan  urutan penjadwalan di  set J dengan job j diletakkan di posisi terakhir urutan
• G(J-j) = nilai G(J) pada himpunan J tanpa elemen j
• G(J) = hasil penjumlahan terkecil antara gj [p(J)] dengan G(J-j)

## C. Metode Branch and Bound
Algoritma Branch  and  Bound merupakan  metode pencarian  solusi  di  dalam  ruang  solusi  secara  sistematis, yang diimplementasikan ke dalam suatu pohon ruang status dinamis.  Pada  algoritma  ini,  masalah  digambarkan  dalam bentuk  diagram  pohon  dimana  masing-masing  cabang menggambarkan  urutan  parsial.  Untuk  menentukan  bagian mana  yang  menjadi  cabang,  dihitung makespan terendah ( lower bound ) dari masing-masing [8].
Adapun langkah-langkah penjadwalan produksi dengan metode Branch and Bound antara lain sebagai berikut [7]:
1. Daftarkan  semua job yang  akan  dikerjakan  dan  waktu penyelesaian di tiap-tiap mesin.
2. Menghitung Cj job terjadwal.
3. Menghitung besar nilai Aj.
4. Bandingkan  semua  nilai  Aj  dan  memilih  Aj  yang maksimum.
5. Nilai  Aj  yang  paling  maksimum  (LB)  menjadi  urutan parsial.
6. Membandingkan semua nilai batas bawah ke-i dan pilih yang minimum.
7. Job dengn nilai batas bawah ke-i terendah dijadwalkan terlebih dahulu.
8. Kemudian job tersebut dihilangkan dari daftar job yang akan dikerjakan.
9. Ulangi  langkah  di  atas  sampai  semua job tersebut dijadwalkan.
Dari  prosedur  diatas  maka  dapat  dibuat  rumus algoritmanya sebagai berikut [7]:
𝐴 1 = 𝐶 1 + ∑ 𝑡 𝑖1 + 𝑚𝑖𝑛{𝑡 𝑖2 + 𝑡 𝑖3 + 𝑡 𝑖4 }
𝐴 2 = 𝑚𝑎𝑥{[𝐶 1 + 𝑚𝑖𝑛 𝑡 𝑖1 ], 𝐶 2 } + ∑ 𝑡 𝑖2 + 𝑚𝑖𝑛{𝑡 𝑖3 + 𝑡 𝑖4 } 𝐴 3 = 𝑚𝑎𝑥{[𝐶 1 + 𝑚𝑖𝑛{𝑡 𝑖1 + 𝑡 𝑖2 }], [𝐶 2 + min 𝑡 𝑖2 ], 𝐶 𝑖3 } + ∑ 𝑡 𝑖3 + 𝑚𝑖𝑛{𝑡 𝑖4 }
𝐴 4 = 𝑚𝑎𝑥{[𝐶 1 + 𝑚𝑖𝑛{𝑡 𝑖1 + 𝑡 𝑖2 + 𝑡 𝑖3 }], [𝐶 2 + min{𝑡 𝑖2 + 𝑡 𝑖3 }], [𝐶 3 + min 𝑡 𝑖3 ], 𝐶 4 } + ∑ 𝑡 𝑖4 Kemudian menentukan batas bawah dengan nilai paling maksimum, yaitu:
𝐿𝐵 = max{𝐴 1 , 𝐴 2 , 𝐴 3 , 𝐴 4 }

## III. M ETODOLOGI P ENELITIAN
Penelitian  ini  dilakukan  di  CV.  Bonjor  Jaya  dengan objek penelitiannya adalah jenis produk yang paling banyak diproduksi saat dilakukan pengambilan data yaitu Pulley B2 7, Pulley B3 7, Pulley B4 7, dan Pulley B5 7. Tahapan awal penelitian ini adalah melakukan observasi untuk mengidentifikasi  masalah  yang  dijadikan  sebagai  bahan
penelitian dan studi pustaka tentang teori yang berhubungan dengan  permasalahan.  Setelah  itu,  dilakukan  pengambilan data  waktu  kerja  dari  masing-masing  elemen  pekerjaan dengan cara observasi langsung di lapangan. Data yang telah diperoleh di hitung dengan metode pengukuran waktu untuk mendapatkan  waktu  standard  yang  akan  digunakan  untuk dilakukan  perhitungan  dengan  metode  terpilih.    Setelah dilakukan  perhitungan  dengan  metode  terpilih  maka dilakukan  perbandingan makespan dari  masing-masing metode  penjadwalan,  yaitu makespan berdasarkan  metode yang saat ini digunakan oleh perusahaan dan 3 metode yang diusulkan  dalam  penelitian  ini,  yaitu  metode Pour, Pemrograman Dinamis dan Branch and Bound . Berdasarkan perbandingan  dari  keempat  metode  tersebut  dapat disimpulkan  metode  mana  yang  terbaik  untuk  dapat diterapkan di CV. Bonjor Jaya Klaten.

## IV. P ENGOLAHAN D ATA
Perhitungan dengan metode pengukuran waktu menghasilkan  waktu  standard  untuk  tiap  produk  sebagai berikut:
T ABEL I W AKTU S TANDARD S ETIAP W ORK C ENTER P ADA T IAP P RODUK No Jenis
Pulley
Work Center (detik)
WC 1 WC 2 WC 3 WC 4  WC 5  WC 6 WC 7 1 B2 7 919.09 21759.89  1140.07  175.53  143.18  354.48  9.88
2 B3 7 1012.26  21760.07  1185.18  225.77  187.68  351.63  14.51 3 B4 7 871.23 21793.83  1417.20  196.69  190.93  401.13  10.44 4 B5 7 962.37 21806.44  1238.49  202.97  193.82  372.23  13.06

## A. Nilai  Makespan  dari  Proses  Penjadwalan  yang Diterapkan Oleh Perusahaan
CV.  Bonjor  Jaya  dalam  melaksanakan  proses  produksi sehari-hari pada dasarnya hanya melakukan proses produksi dengan berdasarkan prinsip First Come First Serve (FCFS) sehingga  belum  memiliki  ketetapan  dalam  penjadwalan. Contohnya  saja  ketika  sedang  berlangsung  pelaksanaan penelitian urutan pengerjaan produknya adalah B5 7, B2 7, B3 7, B4 7 sehingga urutannya menjadi 4-1-2-3. Hasil dari perhitungan  makespan  dapat  dilihat  pada  table  sebagai berikut:
T ABEL II M AKESPAN U NTUK W ORK C ENTER 1-4 UNTUK URUTAN 4-1-2-3
Posisi deret (i) Urutan job (ti,1) detik (ti,2) detik  tnew(i),2 detik  (ti,3) detik  tnew(i),3 detik  t(i),4 detik  tnew(i),4 detik 1 4 962.37 21806.44 22768.81 1238.49 24007.30 202.97 24210.27 2 1 919.09 21759.89 21759.89 1140.07 21661.47 175.53 21634.04 3 2 1012.26 21760.07 21760.07 1185.18 21805.18 225.77 21855.41 4 3 871.23 21793.83 21793.83 1417.20 22025.84 196.69 21996.76 T ABEL III P ERHITUNGAN M AKESPAN U NTUK W ORK C ENTER 5-7 UNTUK URUTAN 4-1-2-3
Posisi deret (i) Urutan job t(i),5 detik tnew(i),5 detik t(i),6 detik tnew(i),6 detik  t(i),7 detik tnew(i),7 detik 1 4 193.82 24404.09 372.23 24776.32 13.06 24789.38 2 1 143.18 21583.40 354.48 21565.64 9.88 21562.46 3 2 187.68 21899.92 351.63 21897.06 14.51 21901.70 4 3 190.93 22000.01 401.13 22049.51 10.44 22045.44 Total Makespan 90298.98
Dari  tabel  di  atas  diperoleh  nilai makespan dengan metode First Come First Serve (FCFS) dengan urutan job 4- 1-2-3 yaitu 90298.98 detik.

## B. Penjadwalan  dan  Perhitungan  Makespan  Dengan Menggunakan Metode Pour
Penjadwalan  dengan  metode Pour adalah  dengan  cara mengganti  setiap  job  dengan  job  lainnya  dalam  urutan pengerjaan  sampai  ditemukan  kombinasi  urutan job yang memenuhi  kriteria  tujuan.  Dalam  metode  ini  diasumsikan bahwa semua job diproses secara terpisah dan independent untuk setiap mesinnya. Berdasarkan langkah-langkah yang telah  dijelaskan  di  atas,  maka  perhitungan  untuk penjadwalan dengan metode Pour adalah sebagai berikut:
T ABEL IV
P ENENTUAN U RUTAN S EMENTARA D ENGAN J OB 1 S EBAGAI U RUTAN P ERTAMA Job  WC 1 WC 2 WC 3 WC 4 WC 5 WC 6 WC 7 ΣCi 1 - - - - - - - - 2  2845.86  21760.07 1185.18  625.43  187.68 351.63  38.02  26993.86 3 871.23  43553.89 3840.87  196.69  378.61  1124.99  10.44  49976.72 4  1833.60  65360.33 2423.68  399.66  572.43 723.86  23.50  71337.06 T ABEL V P ERHITUNGAN M AKESPAN DENGAN J OB 1 S EBAGAI U RUTAN
P ERTAMA
Jo b WC 1 WC 2 WC 3 WC 4 WC 5 WC 6 WC 7 1 919.09  22678.98 23819.05  23994.59  24137.76  24492.24  24502.12 2  1931.35  44439.05 45624.23  45850.00  46037.68  46389.31  46403.82 3  2802.58  66232.87 67650.07  67846.76  68037.69  68438.82  68449.26
4  3764.95  88039.31 89277.80  89480.77  89674.59  90046.82  90059.88
Dari  tabel  5.  didapat  nilai  makespan  dengan job 1 sebagai urutan pertama adalah 90059.88 detik dengan urutan 1-2-3-4.  Setelah  dilakukan  semua  perhitungan  dengan masing-masing job sebagai  urutan  pertama,  didapat makespan paling kecil dengan job 3 sebagai urutan pertama dengan  90012.03  detik  dibandingkan job 2  sebagai  urutan pertama dengan makespan 90153.06 detik dan job 4 sebagai urutan  pertama  dengan makespan 90298.98  detik.  Saat dilakukan perhitungan penentuan urutan kedua, job 3 tidak disertakan dalam perhitungan.
Untuk penentuan urutan job kedua didapat job 4 dengan nilai  makespan  paling  kecil  yaitu  68253.54  detik dibandingkan  dengan  job  1  sebagai  urutan  kedua  dengan makespan  68266.06  detik  dan  job  2  sebagai  urutan  kedua dengan makespan 68359.23 detik.
Untuk penentuan urutan job ketiga didapat job 2 dengan nilai  makespan  46355.36  detik  lebih kecil  daripada  job  1
sebagai  urutan  kedua  dengan  nilai  makespan  46403.82 detik.
T ABEL VI
P ERHITUNGAN M AKESPAN DENGAN M ETODE P OUR U NTUK
U RUTAN 3-4-2-1 Job  WC 1 WC 2 WC 3 WC 4 WC 5 WC 6 WC 7 3 871.23  22665.06  24082.25  24278.94  24469.88  24871.00  24881.44 4  1833.60  44471.49  45709.99  45912.96  46106.77  46479.00  46492.07
2  2845.86  66231.56  67416.74  67642.51  67830.19  68181.82  68196.33
1  3764.95  87991.45  89131.53  89307.06  89450.23  89804.71  89814.59
Dari  tabel  di  atas  dengan  perhitungan  menggunakan metode  Pour  didapat  urutan  pengerjaan  yang  optimum adalah 3-4-2-1 dengan nilai makespan 89814.59 detik.

## C. Penjadwalan  dan  Perhitungan  Makespan  Dengan Menggunakan Metode Pemrograman Dinamis
Perhitungan
dengan menggunakan metode Pemrograman  Dinamis  dalam  penelitian  ini  merujuk  pada metode  Pemrograman  Dinamis  pada  Baker  dan  Trietsch (2009). Pada penelitian notasi gj [p(J)] digunakan untuk nilai makespan minimum di antara semua kemungkinan  urutan  penjadwalan  di  set  J  dengan job j diletakan  di  posisi  terakhir  urutan  sehingga  notasi  yang digunakan dalam penjadwalan untuk meminimasi makespan dengan metode Pemrograman Dinamis dalam penelitian ini adalah sebagai berikut:
• J = beberapa set dari job – job
• p(J) = waktu proses job pada set J
• j ϵ J = job – job anggota dari J
• gj  [p(J)]  =  nilai  makespan  minimum  dari  berbagai kemungkinan urutan dengan job terpilih ditempatkan di urutan terakhir.
• G(J-j) = nilai G(J) pada himpunan J tanpa elemen j
• G(J) = hasil penjumlahan terkecil antara gj [p(J)] dengan G(J-j)
Langkah  pertama  yaitu  menentukan  total  waktu  proses setiap job untuk stage /tahap  1.  Dari  penjumlahan  nilai makespan setiap job dengan  G(J-j)  didapatkan  nilai  G(J). Berikut hasil dari perhitungan pada stage 1:
T ABEL VII H ASIL P ERHITUNGAN S TAGE 1 J {1} {2} {3} {4} p(J) 24502.12  24737.10  24881.44  24789.38 j ϵ J 1 2 3 4 gj[p(J)] 24502.12  24737.10  24881.44  24789.38 G(J-j) 0 0 0 0 G(J) 24502.12  24737.10  24881.44  24789.38
Pada  perhitungan stage 2,  ditentukan  6  kelompok dengan beranggotakan masing-masing 2 job . Untuk set J = {1,2} pada stage 2 jika job 1 di urutan terakhir didapatkan nilai makespan atau  g1(49239.22)  =  46355.36  dan  begitu juga  dengan  set  yang  lain.  G(J-j)  didapatkan  dari  stage sebelumnya yaitu stage 1 misalkan untuk G(J-j) pada set J = {1,2}  dengan  G(2)  sebesar  24737.10  dan  G(1)  sebesar 24502.12  dan  begitu  juga  dengan  set  yang  lain.  G(1,2) didapat  dari  penjumlahan  dengan  nilai  minimum  antara gj[p(J)]  dan  G(J-j),  begitu  juga  dengan  ke-5  set  yang  lain. Berikut hasil dari perhitungan pada stage 2:
T ABEL VIII H ASIL P ERHITUNGAN S TAGE 2 J {1,2}, {1,3}, DAN {1,4} J {1,2} {1,3} {1,4} p(J) 49239.22 49383.56 49291.50 j ϵ J 1 2 1 3 1 4 gj[p(J)] 46355.36  46403.82  46248.09  46689.19  46351.84 46505.99 G(J-j) 24737.10  24502.12  24881.44  24502.12  24789.38 24502.12 G(J) 70905.94  71129.53 71008.12 T ABEL IX H ASIL P ERHITUNGAN S TAGE 2 U NTUK J {2,3}, {2,4}, DAN {3,4} J {2,3} {2,4} {3,4} p(J) 49618.54 49526.48 49670.82 j ϵ J 2 3 2 4 3 4 gj[p(J)] 46389.9  46782.54  46493.64  46599.34  46779.02 46492.067 G(J-j) 24881.44 24737.1  24789.38 24737.1  24789.38 24881.442 G(J) 71271.34 71283.02 71373.51
Pada  perhitungan stage 3,  ditentukan  4  kelompok dengan beranggotakan masing-masing 3 job . Untuk set J = {1,2,3} pada stage 3 jika job 1 di urutan terakhir didapatkan nilai makespan minimum atau g1(74120.66) = 68008.16 dan begitu  juga  dengan  set  yang  lain.  G(J-j)  didapatkan  dari stage sebelumnya yaitu stage 2 misalkan untuk G(J-j) pada set  J  =  {1,2,3}  dengan  G(2,3)  sebesar  71271.34,  G(1,3) sebesar  71129.53  dan  G(1,2)  sebesar  70905.94  dan  begitu juga  dengan  set  yang  lain.  G(1,2,3)  didapat  dari penjumlahan dengan nilai minimum antara gj[p(J)] dan G(J- j), begitu juga dengan ke-3 set yang lain. Berikut hasil dari perhitungan pada stage 3:
T ABEL X H ASIL P ERHITUNGAN S TAGE 3 U NTUK J {1,2,3} DAN {1,2,4} J {1,2,3} {1,2,4} p(J) 74120.66 74028.60 j ϵ J 1 2 3 1 2 4 gj[p(J)] 68008.16 68149.79 68449.26  68111.91  68210.26 68266.06 G(J-j) 71271.34 71129.53 70905.94  71283.02  71008.12 70905.94 G(J) 139279.32 139172.00 T ABEL XI H ASIL P ERHITUNGAN S TAGE 3 U NTUK J {1,3,4} DAN {2,3,4} J {1,3,4} {2,3,4} p(J) 74172.94 74407.92 j ϵ J 1 3 4 2 3 4 gj[p(J)] 68054.53  68495.63 68251.96  68196.33  68539.08  68252.13 G(J-j) 71373.51  71008.12 71129.53  71373.51  71283.02  71271.34 G(J) 139381.49 139523.47
Pada  perhitungan stage 4,  ditentukan  1  kelompok dengan beranggotakan 4 job . Untuk set J = {1,2,3,4} pada stage  3  jika  job  1  di  urutan  terakhir  didapatkan  nilai makespan minimum  atau  g1(98910.04)  =  89814.59  dan begitu juga dengan anggota set yang lain. G(J-j) didapatkan dari stage sebelumnya  yaitu stage 3  misalkan untuk  G(J-j) pada set J = {1,2,3,4} dengan G(2,3,4) sebesar 139523.47, G(1,3,4)  sebesar  139381.49,  G(1,2,4)  sebesar  139172  dan G(1,2,3)  sebesar  139279.32.  G(1,2,3,4)  didapat  dari penjumlahan dengan nilai minimum antara gj[p(J)] dan G(J- j). Berikut hasil dari perhitungan pada stage 4:
T ABEL XII H ASIL P ERHITUNGAN S TAGE 4 J 1,2,3,4 p(J) 98910.04 j ϵ J 1 2 3 4 gj[p(J)] 89814.59  89956.23  90255.70  90012.03 G(J-j) 139523.47  139381.49 139172  139279.32 G(J) 229338.07  229337.72  229427.70  229291.35
Dari stage 4 pada tabel 4.45 dipilih G(J) terbesar untuk urutan job pertama  lalu  diurutkan  sampai  G(J)  terkecil sehingga  ditemukan  urutan  pengerjaan job yaitu  3-1-2-4 dengan nilai makespan sebesar 90012.03. Berikut hasil dari perhitungan makespan dengan urutan 3-1-2-4:
T ABEL XIII
P ERHITUNGAN M AKESPAN DENGAN M ETODE P EMROGRAMAN D INAMIS U NTUK U RUTAN 3-1-2-4
Job  WC 1 WC 2 WC 3 WC 4 WC 5 WC 6 WC 7 3  871.23  22665.06  24082.25  24278.94  24469.88 24871.00  24881.44 1  1790.32  44424.95  45565.02  45740.56  45883.73 46238.21  46248.09 2  2802.58  66185.02  67370.20  67595.97  67783.65 68135.28  68149.79 4  3764.95  87991.45  89229.95  89432.92  89626.73
89998.96  90012.03

## D. Penjadwalan  dan  Perhitungan  Makespan  Dengan Menggunakan Metode Branch and Bound
Di  dalam  algoritma Branch  and  Bound ,  terdapat  tiga buah  bagian  utama,  yaitu:  ekspresi  batas  bawah  ( Lower Bound (LB)),  strategi  pencarian  dan  pencabangan ( branching ). Di dalam prosedur ini, suatu masalah dipecah menjadi  beberapa  sub  masalah  yang  mempresentasikan pembagian  kerja  secara  parsial.  Simpul-simpul  terus bercabang  lebih  jauh  sampai  diperoleh  solusi  lengkap. Prosedur  ini  terus  diulang  sampai  pencarian  pada  pohon berakhir dan solusi optimal ditemukan.
Berdasarkan  langkah-langkah  yang  telah  dijelaskan  di atas,  maka  perhitungan  untuk  penjadwalan  dengan menggunakan  metode Branch  and  Bound adalah  sebagai berikut:
T ABEL X IV H ASIL P ERHITUNGAN W AKTU P ADA S ETIAP M ESIN Jo b TM 1 TM 2 TM 3 TM 4 TM 5 TM 6 TM 7 1 919.0 9 22678 .98 23819 .05 23994 .59 24137 .76 24492 .24 24502 .12 2 1012. 26 22772 .33 23957 .51 24183 .28 24370 .96 24722 .59 24737 .10 3 871.2 3 22665 .06 24082 .25 24278 .94 24469
.88 24871 .00 24881 .44 4 962.3 7 22768 .81 24007 .30 24210 .27 24404 .08 24776 .32 24789 .38
𝐿𝐵(1) = 𝑚𝑎𝑥 { 27489.79 90004.08
28439.51 25173.84 25076.34
25627.67
24540.14} = 90004.08
𝐿𝐵(2) = 𝑚𝑎𝑥
{
27347.98 89955.62 28436.34 25266.00 25263.24 25860.30 24770.48} = 89955.62
𝐿𝐵(3) = 𝑚𝑎𝑥
{ 25416.63 89814.59 28329.07 25390.75 25358.91 25959.22 24918.90}
= 89814.59
𝐿𝐵(4) = 𝑚𝑎𝑥
{
27347.98 89905.73 28432.82 25315.79 25290.23 25893.43 24824.21} = 89905.73
Dari percabangan di atas dipilih hasil makepan terkecil untuk  dilakukan  percabangan  kembali.  Dari  ke  empat cabang  di  atas  LB(3)  memiliki  nilai  minimum  yaitu 89814.59, sehingga cabang dikembangkan dari node 3.
Dari  ke  tiga  cabang  di  node  3  terdapat  2  cabang  yang memiliki  nilai  minimum  yang  sama  yaitu  LB(32)  dan LB(34)  yang  memiliki  nilai  yaitu  89814.59,  sehingga cabang dikembangkan dari node 32 dan node 34.
Dari  4  cabang  yang  masing-masing  di  node  32  dan  2 cabang  di  node  34  terdapat  2  cabang  yang  memiliki  nilai minimum  yang  sama  yaitu  LB(324)  dan  LB(342)  dengan nilai  yaitu  89814.59.  Urutan  pengerjaan  yang  optimum untuk  menghasilkan makespan minimum  dengan  metode Branch  and  Bound adalah  3-2-4-1  dan  3-4-2-1  dengan waktu makespan 89814.59 detik.

## V. H ASIL DAN P EMBAHASAN
Penjadwalan yang baik adalah penjadwalan yang dapat meningkatkan  produktivitas  dengan  cara  meningkatkan sumber  daya  atau  mengurangi  waktu  tunggunya  sehingga waktu proses dapat berkurang.
Pada  CV.  Bonjor  Jaya,  mereka  menggunakan penjadwalan dengan sistem First Come First Serve (FCFS) dimana produk dikerjakan sesuai dengan waktu kedatangannya. Urutan job pada perusahaan dengan urutan B5 7, B2 7, B3 7 lalu B4 7 sehingga urutannya adalah 4-1- 2-3. Dari urutan ini diperoleh makespan sebesar 90298.98. Dengan perhitungan penjadwalan menggunakan metode Pour didapatkan urutan B4 7, B5 7, B3 7, lalu B2 7 sehingga urutannya adalah 3-4-2-1. Nilai makespan yang didapatkan dengan  menggunakan  urutan  tersebut  adalah 89814.59 detik.
Urutan  yang  didapatkan  dengan  perhitungan  metode Pemrograman Dinamis adalah B4 7, B2 7, B3 7, lalu B5 7 sehingga  urutannya  adalah  3-1-2-4.  Nilai makespan yang didapatkan  dengan  menggunakan  metode  tersebut  adalah 90012.03 detik.
Dengan  menggunakan  metode Branch  and  Bound didapatkan  2  urutan  yaitu  3-4-2-1  dan  3-2-4-1.  Nilai
makespan yang  didapatkan  dengan  menggunakan  metode tersebut adalah 89814.59 detik.
Berdasarkan  hasil  perhitungan  di  atas,  metode penjadwalan  dengan  nilai makespan paling  kecil  adalah metode Pour dan Branch  and  Bound dengan  makespan 89814.59 detik.

## VI. K ESIMPULAN
Berdasarkan  pembahasan  di  atas  maka  dapat  diambil beberapa kesimpulan mengenai penelitian ini yaitu sebagai berikut:
1. Dengan  menghitung  tipe  penjadwalan  yang  diterapkan perusahaan,  mereka  menerapkan  penjadwalan  dengan urutan  4-1-2-3.  Dengan  menghitung  menggunakan metode Pour didapatkan urutan pengerjaan job 3-4-2-1. Dengan menghitung menggunakan metode Pemrograman  Dinamis  didapatkan  urutan  pengerjaan job 3-1-2-4. Dengan menghitung menggunakan metode Branch and Bound didapatkan urutan pengerjaan job 3- 4-2-1 dan 3-2-4-1
2. Dengan urutan penjadwalan yang diterapkan perusahaan yaitu  4-1-2-3  didapatkan  nilai makespan sebesar
90298.98 detik. Dengan urutan penjadwalan dari metode Pour  yaitu  3-4-2-1  didapatkan  nilai makespan sebesar 89814.59 detik. Dengan urutan penjadwalan dari metode Pemrograman  Dinamis  yaitu  3-1-2-4  didapatkan  nilai makespan sebesar  90012.03  detik.  Dengan  urutan penjadwalan dari metode Branch and Bound yaitu 3-4- 2-1  dan  3-2-4-1  didapatkan  nilai makespan sebesar
89814.59 detik.
3. Dari perhitungan yang dilakukan menggunakan metode- metode  terpilih  terdapat  nilai makespan minimal  ada pada  metode  Pour  dan Branch  and Bound sebesar 89814.59 dengan urutan job 3-4-2-1 dan 3-2-4-1. Nilai
Pada  penelitian  yang  dilakukan  masih  ada  kekurangan yang dapat disempurnakan kedepannya. Adapun saran yang dapat diberikan adalah sebagai berikut:
1. Hasil  dari  penelitian  ini  hanya  bisa  diterapkan  untuk objek  penelitian  ini  saja,  sehingga  dengan  adanya penelitian  ini  perusahaan  bisa  menjadwalkan  untuk produk-produk yang lain.
2. Penggunaan  metode  penjadwalan  lain  yang  metode perhitungannya  lebih  kompleks  agar  didapatkan  hasil yang lebih baik.

## R EFERENSI
[1]. Baker,  K.  R.  dan  Trietsch,  D.  2009. Principles  of  Sequencing  and Scheduling . New York: John Wiley and Sons Ltd.
[2]. Ginting, R. 2009. Penjadwalan Mesin . Yogyakarta: Graha Ilmu.
[3]. Irsyad, A. L. 2015. Penjadwaln Flow Shop N Job M Mesin Dengan Metode First Come First Served (FCFS), Earliest Due Date (EDD),
Dan  Algoritma  Heuristik  Pour .  Skripsi.  Universitas  Islam  Negeri Sunan Kalijaga. Yogyakarta.
[4]. Pour, H. D. 2001. A New Heuristic for n-Job m-Machine Problem . Production Planning Control, Vol. 12, No. 7, 648-653.
[5]. Hamman,  M.  K.  2015. Penjadwalan  Produksi  Flow  Shop  Untuk Meminimalkan Makespan  Dengan  Metode  Campbell,  Dudek,  And Smith  (CDS),  Metode  Palmer,  Metode  Dannenbring,  Dan  Metode Ignall-Scharge  (Studi  Kasus  Di  CV.  Bonjor  Jaya  Klaten). Skripsi. Universitas Islam Negeri Sunan Kalijaga Yogyakarta.
[6]. Karim,  M.  S.  2015. Penjadwalan  Produksi  Flow  Shop  Dengan Metode Ignall-Scharge Dan Algoritma Nawaz Enscore And Ham Di CV.  Bestone  Indonesia . Skripsi.  Universitas  Islam  Negeri  Sunan Kalijaga. Yogyakarta.
[7]. Widyawati, S. dan Abusini, S. 2015. Penjadwalan Produksi Untuk Meminimumkan Makespan Pada Flow Shop Menggunakan Metode Branch  And  Bound  (Studi  Kasus  CV.  Dian’s  Print) .  Jurnal Mahasiswa Matematika, Vol. 3, No. 1, Februari 2015, Hal. 65-68.
[8]. Mangngenre,  S.,  Rapi,  A.  dan  Flannery,  W.  2013. Penjadwalan Produksi Dengan Metode Branch and Bound Pada PT. XYZ. Jurnal Teknik  Industri,  Fakultas Teknik,  Universitas  Hasanuddin, Makassar.