## PENJADWALAN JOB UNTUK MEMINIMASI MAKESPAN MENGGUNAKAN METODE JOB SPLITTING DAN METODE BRANCH AND BOUND
Rahmi Maulidya, Sumiharni Batubara, Rio Ronald H.B
Laboratorium Sistem Produksi, Jurusan Teknik Industri,
Fakultas Teknologi Industri, Universitas Trisakti Email : rmauli@yahoo.com , rio.butarbutar@gmail.com

## ABSTRAK
Pada lingkungan flexible flowshop dengan mesin identik paralel, setiap job mengambil rute yangsamamelewati  aliran  proses  seperti  flowshop  dengan  jumlah  mesin  lebih  dari  satu.Kasus penjadwalan  pada  produksi  tower  telekomunikasi  memiliki  karakteristik  flexible  flowshop  dengan mesin  identik  paralel.Produk  terdiri  dari  variasi  part  yang  banyak  dan  beragam.Perbedaan  dalam penentuan  kelompok  pekerjaan  memberikan  dampak  yang  besar  terhadap  waktu  penyelesaian.Satu jobtidak  dapat  diproses  pada  dua  buah  mesin  secara  bersamaan,  tetapi  apabila  job  tersebut merupakan  bagian  dari  sebuah  produk,  maka  job  dapat  dipecah  menjadi  beberapa  sub  job  dan diproses terpisah pada mesin berbeda. Pemecahan job atau yang disebut metode job splitting menjadi salah  satu  cara  untuk  meminimasi  makespan  disamping  metode  branch  and  bound  yang  terbukti sesuai  untuk  karakteristik  flexible  flowshop.Hasil  perhitungan  masing-masing  metode  memberikan dampak terhadap efisiensi waktu fabrikasi.
Kata Kunci: penjadwalan,flexible flowshop,  job splitting, branchand bound

## 1. PENDAHULUAN
Ketepatan  jadwal  produksi  merupakan faktor  kunci  bagiindustri  manufaktur supaya  produk  dapat  sampai  tepat  waktu pada konsumen.Penjadwalan produksi adalah proses pengorganisasian, pemilihan dan penentuan waktu menggunakan sumber daya yang ada untuk menghasilkan output  yang  diharapkan  dengan  waktu yang  diinginkan  (Morton  dan  Pentico, 1993). Penjadwalan memiliki tujuan meningkatkan produktivitas mesin, mengurangi  waktu  mesin  menganggur, mengurangi  keterlambatan,  meminimasi ongkos  produksi  dan  memenuhi  due date(Baker, 1974).
Jenis  penjadwalan  diantaranya  adalah Flexible  Flow  Shop  (FFS),  dimana  setiap job  mengambil  rute  yangsamamelewati aliran  proses  seperti  flowshop,  akan  tetapi dalam  prosesnya  akan  terdapat  jumlah mesin  yang  lebih  dari  satu  tipe  dan  hanya digunakan dalam satu job saja. Keuntungan  dalam  menggunakan  aliran proses  ini  adalah  semakin  singkatnya pekerjaan,  karena  menggunakan  mesin lebih  dari  satu  (Bedworth  dan  Bailey, 1987).Penelitian  mengenai  flexible  flow
shop  (FFS)mulai  dari  Ignall  dan  Schrange (1965)lalu  Lomicki  (1965)menghasilkan kriteria  awal  flexible  flow  shop.  Penelitian Hidri  dan  Haouari  (2011)  menghasilkan pengembangan  terhadap  kriteria  flexible flow shop dimana terdapat njob dikerjakan pada  k  machine  centeryang  paralel,  waktu setiap  mesin  pada  stage  awal  adalah  nol, setiap  job  diproses  pada  setiap  machine center dan tidak terdapat job sisipan.
Ruiz  dan  Vazquez-Rodriguez  (2010) meninjau  225  literatur  Hybrid  (Flexible) Flow Shop Scheduling Problem, mereview cara  memecahkan  permasalahan  FFS antara  lainexact  algorithm(branch  and bound),  heuristic(dispatching  rules),  dan metaheuristics(tabu search, genetic algorithm,  ant  colony,  artificial  immune system, dan Neural Networks)dan menemukan  bahwametode  terbaik  untuk menyelesaikan masalah adalah branch and bound.Metode
branch
and boundmenggunakan kriteria minimasi
makespan denganlower boundyang
merupakan  hasil  iterasi  dan  parsial sequence dari pencabangan (branching).Metode branch and
bounduntuk  memecahkan  masalah  FFS
awalnya  diteliti  dalamBrah  (1988)  lalu dikembangkandalam  Brah  dan  Hunsucker (1991).
Dalam  menjadwalkan  n  jobs  pada  m mesin  paralel,  secara  umum  terdapat hipotesis  bahwa  satu  jobtidak  dapat diproses  pada  dua  buah  mesin  secara bersamaan,  tetapi  apabila  job  tersebut merupakan  bagian  dari  sebuah  produk, maka  job  dapat  dipecah  menjadi  beberapa sub  job  dan  diproses  terpisah  pada  mesin berbeda.Penelitian  mengenai  job  splitting jarang  dilakukan,  sebab  banyak  penelitian hanya  memfokuskan  bahwa  setiap  job hanya dapat diproses pada satu buah mesin (Lawler  dkk,  1991).Metode  job  splitting dalam Xing dan Zhang (2000)
menghasilkan  2  buah  lemma  tentang    job splitting.  Teori  pertama  adalah  apabila terdapat  sebuahmesin  m  yang  tidak  dapat menyelesaikan  job  J,  maka  job  tersebut dapat  di  split  dengan  cara  membagi  job tersebut  kepada  mesin  lainnya  sama  rata, hasilnya  adalah  waktu  penyelesaian  job yang  merata  pada  setiap  mesin.  Teori kedua  adalah  setelah  setiap  job  dibagi sama  rata,  maka  setiap  sublot  yang  telah dibagi harus dikerjakan atau diproses pada setiap  mesin  dan  tidak  boleh  terjadi interupsi  atau  job  sisipan.  Namun  cara  ini hanya  berlaku  bila  karakteristik  mesin yang  dipakai  sama  dan  seluruh  job  dapat dikerjakan pada setiap mesin.
Pada makalah ini dilakukan penjadwalan job untuk meminimasi makespan  dengan  menggunakan  metode job  splitting  dan  metode  branch  and bound.

## 2. TINJAUAN PUSTAKA
Rabadi,  et  al  (2007)  menjabarkan  bahwa branch  &  bound  dibagi  ke  dalam  tiga bagian yaitu , branching strategy, menghitung  lower  bound,  dan  searching strategy. Pada makalah ini, metode branch and  bound  yang  diusulkan  memiliki kriteria  untuk  meminimasi  makespan dengan menggunakan lower bound
(B_la˙zewicz
dkk, 2007) untuk
menghasilkan  urutan  job  paling  optimal
sehingga  pengerjaan  dapat  dilakukan dengan  efisien.  Berdasarkan  literatur tersebut,  urutan  job  yang  dihasilkan  tidak simultan,  artinya  hanya  memperhatikan job  yang  dikerjakan  saja,  dan  tidak berhubungan dengan mesin yang mengerjakan.
Sehingga
setelah mendapatkan  urutan  job  tersebut,  maka perlu  dilakukan  penjadwalan  pada  tiap mesin.  Lower  bound  yang  digunakan (B_la˙zewicz dkk, 2007)adalah :
= + ∑ + { ∈ } ∈ (1) Notasi yang digunakan adalah : Q n = waktu penyelesaian job n
∑ + { ∈ } ∈ = Jumlah waktu proses  pada  job  n  ditambah  dengan  waktu minimum job n+1 (job pada proses berikutnya).
Dan  pada  proses  terakhir  lower  bound yang digunakan adalah :
= + ∑ ∈ (2)
Lower  bound  pada  proses  terakhir  adalah tidak ditambahkan dengan waktu minimum  job  proses  berikutnya.  Setelah menentukan lower bound, tahap berikutnya adalah menentukan B max.
= { ; ; } (3)
Hasil  dari  B max kemudian  dibandingkan untuk  seluruh  parsial  sequence,  sehingga B max yang terkecil dari seluruh job merupakan  job  yang  akan  dijadwalkan. Setelah  mendapatkan  urutan  job,  tahap berikutnya  adalah  menjadwalkan  secara manual job ke dalam mesin.

## 3. METODOLOGI PENELITIAN
Dalam  makalah  ini  diusulkan  dua  buah metode  untuk  membantu  meminimasi makespan,  metode  pertama  menggunakan teori job splitting dan metode kedua adalah menggunakan  metode  branch  and  bound. Setelah  itu  kedua  metode  dibandingkan, sehingga diperoleh hasil penjadwalan yang paling optimal.
3.1. Metode Job Splitting
• Penentuan  ukuran  job;  penentuan ukuran job berdasarkan ukuran profil
• Perhitungan kapasitas mesin; kapasitas mesin dihitung berdasarkan banyaknya unit  yang dapat dikerjakan pada mesin tersebut dalam kurun waktu tertentu.
• Perhitungan berat profil; fungsi menghitung  berat  profil  adalah  untuk menentukan  berapa  kali  pengangkutan menggunakan material handling
• Perancangan  metode  job  splitting; metode  job  splitting  membagi  satu buah  job  menjadi  beberapa  job  yang dapat  dikerjakan  pada  seluruh  mesin.
Pembagian  tersebut  dilakukan  agar banyaknya  unit  yang  dikerjakan  sama untuk seluruh mesin.
• Pengalokasian  job  ke  setiap  mesin; seluruh  job  yang  akan  dikerjakan kemudian dibagi rata ke seluruh mesin, sehingga mesin satu dan mesin lainnya memiliki jumlah unit yang sama untuk dikerjakan.
• Penjadwalan; setelah mengetahui berapa banyak unit yang akan dikerjakan, kemudian jadwalkan setiap unit kepada setiap mesin.

## 3.2. Metode Branch and Bound
1. Pencabangan (Branching)
Pencabangan  dilakukan  berdasarkan job yang akan
dijadwalkan.
Pencabangan  ini  memiliki  tujuan untuk  mengetahui  node  yang  akan mengalami  pencabangan  selanjutnya (sub-branching) dengan nilai maksimum  diantara  node-node  yang ada.
2. Penentuan iterasi dan parsial sequence
Jumlah  maksimum  iterasi  (n)  sesuai dengan jumlah job yang akan dijadwalkan.  Tujuan  dari  parsial sequence  adalah  untuk  mengetahui penjadwalan  yang  dijadikan  acuan dalam  proses  perhitungan  dengan algoritma Branch and Bound.
3. Penentuan  batas  bawah  (lower bound)
Penentuan batas bawah pada
algoritma  Branch    and  Bound  yang biasa  disebut  bounding  adalah  untuk
mengetahui  batas  bawah  setiap  job yang  akan  dianggap  sebagai  job terakhir yang akan dijadwalkan.
Sehingga  dengan  perbandingan  batas bawah ini dapat lebih mengoptimalkan hasil yang diperoleh.
4. Penentuan B Max
Bmax  adalah  nilai  batas  bawah  yang paling  maksimum  dari  setiap  batas bawah  yang berada pada suatu parsial sequence.  Notasi  yang  digunakan adalah : q m =  Waktu  penyelesaian  pada mesin m P = Parsial sequence b m = Lower bound pada mesin m
B max = Nilai maksimum dari b m t jm =  Waktu  proses  job  j  pada mesin m T jm = Total waktu job j pada mesin m
Berikut  ini  adalah  tahapan  pada  algoritma Branch  and  Bound  (Ruiz  danVázquez- Rodriguez, 2010):
1. Menentukan iterasi n, set n=1. Maksimum  iterasi  =  jumlah  job  yang akan dijadwalkan.
2. Menetukan parsial sequence (p=1)
3. Menentukan  waktu  penyelesaian  job  1 di mesin 1
4. Menentukan  waktu  penyelesaian  job  1 di  mesin  2  dengan  menjumlahkan waktu  penyelesaian  job  1  di  mesin  1 dengan  waku  penyelesaian  job  1  di mesin 2
5. Menentukan nilai minimum dari waktu penyelesaian mesin 2 untuk setiap job
6. Menentukan jumlah waktu
penyelesaian seluruh job pada mesin 1
7. Menentukan  batas  bawah  untuk  mesin 1  (b 1 )  yaitu  dengan  menjumlahkan hasil langkah 3, langkah 5 dan langkah 6.
8. Menentukan jumlah waktu
penyelesaian seluruh job pada mesin 2
9. Menentukan  batas  bawah  untuk  mesin 2  (b 2 )  yaitu  dengan  menjumlahkan hasil langkah 4 dan langkah 8
10. Menentukan  batas  bawah  maksimum (B max) yaitu dengan membandingkan batas bawah mesin 1 dan mesin 2
11. Lakukan  pengecekan  apakah  p  sudah maksimal.  Jika  ya,  lanjut  ke  langkah 12,  jika  tidak  maka  tentukan  p=p+1 dan kembali ke langkah 2 dengan tidak mengikutsertakan  kembali  job  1  (job sebelumnya) pada perhitungan
12. Bandingkan  nilai  B  max  dari  setiap parsial  sequence  kemudian  pilih  yang paling minimum
13. Jadwalkan  job  yang  memiliki  nilai  B max  paling  minimum  ke  dalam  urutan penjadwalan
14. Buang job yang telah dijadwalkan dari perhitungan
15. Lakukan  pengecekan  apakah  iterasi  = max  n-1.  Jika  ya  letakkan  job  yang belum terjadwalkan pada urutan terakhir.  Jika  tidak  lanjut  ke  langkah berikutnya.
16. Menentukan iterasi n=n+1 dan kembali ke langkah 1.

## 4. KASUS
Dalam  makalah  ini,  perusahaan  yang memproduksi
tower
telekomunikasimemiliki
karakteristik
Flexible  Flow  Shop  dengan  mesin  paralel identik. Bahan baku utama adalah besi plat danbesi  siku(Gambar  1).  Pesanan  yang dikerjakan  adalah  20  tower  pada  lini  plat dan  lini  siku,  dan  tidak  terdapat  job sisipan.Proses produksi  pembuatan sebuah tower terdiri dari :
• Cutting; proses pemotongan atas material  baik  siku  maupun  plat  baja menjadi  ukuran  yang  diinginkan. Proses  cutting  mengikuti  pola  atau bentuk  yang  dipesan  oleh  konsumen. Ada  2  jenis  cutting  yaitu  cutting  siku dan  cutting  plate.  Untuk  cutting  siku menggunakan  mesin  cutting  shearing dan bandsaw.
• Stamping;  proses  penamaan  dari  parts yang  akan  membentuk  tower.  Pada proses  stamping  setiap  bagian  ditandai dengan  jelas  mengikuti  petunjuk  yang telah disediakan sehingga setiap bagian dapat  disusun  dengan  tepat  di  lokasi pemasangan.
• Punching/Drilling;  proses  melubangi parts mengikuti petunjuk yang diberikan oleh perusahaan. Fungsi dari lubang-lubang  ini  adalah  sebagai tempat sambungan baut/material lainnya  sehingga  tower  dapat  berdiri tegak.
• Proses Khusus; biasanya terdapat pada tower  yang  membutuhkan  penangan khusus  atas  permintaan  konsumen. Misalnya untuk tower yang membutuhkan  bentuk  kaki-kaki  yang disesuaikan  dengan  kontur,  maupun ketinggian yang disesuaikan.
• Finishing  area;  proses  packaging  yang dilakukan hanyamenempatkan part pada kontainer. Perakitan part dilakukan di lokasi tempat proyek.
Gambar 2 menunjukkan flow machine dari lini  siku,  lini  plat  dan  lini  plat  khusus untuk pembuatan tower.
Gambar 1.Bahan Baku Besi Plat (kiri) dan Besi Siku (kanan)
(a)
(b)
(c)
Gambar 2. Flow Machine lini siku (a), lini plat (b) dan Lini Plat Khusus (c)
Kapasitas  mesin  cutting  and  shearing ditentukan  berdasarkan  waktu  kerja  8  jam per  hari,  waktu  proses  pemotongan  25 detik dengan efisiensi mesin 88%.Perhitungan kapasitas mesin = 8jam x 25detik  x  88%  =  1.013,76  unit  per  hari. Tabel 1 menunjukkan data untuk lini siku, Tabel  2  menunjukkan  data  untuk  lini  plat dan  lini  plat  khusus  dan  Tabel  3 menunjukkan spesifikasi material handling. Tabel 1.Data Lini Siku Kode Mesin Mesin Jumlah mesin Waktu proses (detik) Efisiensi Kapasitas mesin (unit/hari) MC1-MC6  Cutting&shearing 6 25 88% 1013,76 MS1-MS4 Stamping 4 20 86% 1238,4 MP1-MP6 Copy punch 6 65 85% 376,62 Tabel 2.Data Lini plat (MC,MS,MP) dan Lini plat Khusus (MG,MS,MR) Kode Mesin Mesin Jumlah Mesin Waktu proses (detik) Efisiensi Kapasitas mesin (unit/hari) MC7,MC8 cutting&shearing 2 20 90% 1296 MS5,MS6 stamping 2 15 95% 1824 MP7,MP8,MP9 copy punch 3 55 94% 492,22 MG1,MG2 Gas cutting 2 126 90% 205,71 MS7 Stamping 1 22 90% 1178,18 MR1,MR2,MR3  Radial Drilling 3 360 90% 72
Tabel 3.Spesifikasi material handling Alat MH  Kapasitas Waktu Keterangan Forklift 5000 kg 12 menit loading dan unloading Warehouse – area fabrikasi Area  fabrikasi  –  gudang  barang jadi Crane 2000 kg 4 menit perpindahan tempat 3 menit loading dan unloading Mesin cutting – mesin stamping Mesin stamping – mesin holling 5. HASIL DAN PEMBAHASAN 5.1.Metode Job Splitting
Pada  metode  job  splitting,  pembagian  job berdasarkan  profile,  artinya  berdasarkan ukuran/spesifikasi dari komponen tersebut.
Sehingga  satu  buah  job  hanya  terdiri  dari satu jenis komponen yang berukuran sama. Hal  yang  sama  juga  berlaku  pada  lini  plat dan  plat  khusus.  Tabel  4  menunjukkan pembagian job pada metode job splitting.
Tabel 4.Pembagian job lini siku dengan metode job splitting Job Komponen Qty * Demand J1 L 50x50x5 6140 J2 L 60x60x6 3220 J3 L 120x120x12 400 J4 L 100x100x10 160 J5 L 40x40x4 4940 J6 L 70x70x7 560 J7 L 90x90x9 160 J8 L 80x80x8 80
Tabel 5. Waktu Pengangkutan Menggunakan Crane Siku
Tabel 6. Waktu Pengangkutan Seluruh Komponen Siku Menggunakan  forklift
Tabel 7. Hasil perhitungan metode job splitting
J1 L      50  x  50  x  5 44195.8 6140
23 92 69 161 J5 L      40  x  40  x  4 10835.8 4940 6 24 18 42 J2 L      60  x  60  x  6 28706.6 3220 15 60 45 105 J6 L      70  x  70  x  7 7290.8 560 4 16 12 28 J3 L     120  x 120  x 12 29531.2 400 15 60 45 105 J4 L      90  x  90  x  9 6216.8 160 4 16 12 28 J7 L     100  x 100  x 10 4136 160 3 12 9 21 J8 L      80  x  80  x  8 4636.8 80
3
12 9 21
Job Profile
Total berat Total Demand Jumlah Pengangkutan Waktu Pengangkutan Waktu Loading Unloading (Menit) Total Waktu MH (Menit)
J1 L      50  x  50  x  5 44195.8 9 108 J2 L      60  x  60  x  6 28706.6 6 72 J3 L     120  x 120  x 12 29531.2 6 72 J4 L      90  x  90  x  9 6216.8 2 24 J5 L      40  x  40  x  4 10835.8 3 36 J6 L      70  x  70  x  7 7290.8 2 24 J7 L     100  x 100  x 10 4136 1 12 J8 L      80  x  80  x  8 4636.8 1 12
Job
Profile Sum of Weight (Kg) Jumlah Pengangkutan Waktu Loading dan Unloading (Menit)
Waktu fabrikasi (menit) Penambahan waktu MH dari Warehouse  ke  area  raw  material (menit) Penambahan  waktu  MH  dari  Holling finished area (menit) Waktu collecting (menit) Total  waktu  penjadwalan  pada  lini (menit) Waktu kerja standar (hari)

## 5.2. Metode Branch and Bound
Tahapan  pada  metode  branch  and bound  kurang  lebih  sama  seperti  metode job  splitting.  Pertama  adalah  pembagian
Tabel 8. Pembagian job pada lini siku untuk metode
Job  splitting  membagi  berdasarkan jumlah  mesin  pada  proses  berikutnya  dan setiap  selesai  memproses  komponen  maka seluruh  komponen  digabungkan  terlebih dahulu kemudian lanjut ke proses berikutnya, sedangkan pada metode Branch  and  Bound  pembagian/ job  dilakukan  terlebih  dahulu,  sehingga satu buah job tersebut diproses secara utuh berdasarkanjumlah  unit  pada  satu  buah mesin. Cara ini tidak memerlukan
Maulidya, dkk) Jurnal Teknik Industri ISSN: 1411
Lini Siku Lini Plat 3923 2447,5 Penambahan waktu MH dari Warehouse  ke  area  raw  material 360 48 Penambahan  waktu  MH  dari  Holling- 360 48 Waktu collecting (menit) 1305 448 Total  waktu  penjadwalan  pada  lini 5948 2991,5 Waktu kerja standar (hari) 12,39 6,23

## Branch and Bound
Tahapan  pada  metode  branch  and bound  kurang  lebih  sama  seperti  metode job  splitting.  Pertama  adalah  pembagian
job  berdasarkan  komponen.  Jumlah  unit yang dibagi berdasarkan
kemampuan/kapasitas produksi mesin. Satu buah job hanya dapat dipro satu buah mesin.
Tabel 8. Pembagian job pada lini siku untuk metode branch and bound
membagi  berdasarkan
jumlah  mesin  pada  proses  berikutnya  dan setiap  selesai  memproses  komponen  maka seluruh  komponen  digabungkan  terlebih dahulu kemudian lanjut ke proses berikutnya, sedangkan pada metode pembagian/klasifikasi n  terlebih  dahulu,  sehingga satu buah job tersebut diproses secara utuh berdasarkanjumlah  unit  pada  satu  buah mesin. Cara ini tidak memerlukan
penggabungan  setelah  melakukan  satu tahapan  proses.Hal  ini  dapat  dilihat  pada Tabel 8.
Branching  adalah  sebuah  me untuk  mengetahui  job-job akan  dijadwalkan,  penentuan yang digunakan berdasarkan literatur yang terdapat  pada  (B_la˙zewicz  et  al.  2007) yang  menyatakan  bahwa  lower  bound dihitung  untuk  menyelesaikan  permutasi parsial  dengan  mempertimbangkan  sisa
Lini Plat Khusus 1543 24 24 32 1591 3,31 job  berdasarkan  komponen.  Jumlah  unit yang dibagi berdasarkan
kemampuan/kapasitas produksi mesin.
Satu buah job hanya dapat diproduksi oleh

## branch and bound
penggabungan  setelah  melakukan  satu Hal  ini  dapat  dilihat  pada
adalah  sebuah  metode job  mana  saja  yang akan  dijadwalkan,  penentuan  lower  bound yang digunakan berdasarkan literatur yang
B_la˙zewicz  et  al.  2007) yang  menyatakan  bahwa  lower  bound dihitung  untuk  menyelesaikan  permutasi mempertimbangkan  sisa
pekerjaan  pada  setiap  mesin,  dimana jumlah branch yang terdapat pada permutasi  sama  dengan  jumlah  job  yang
akan dikerjakan. Setelah melakukan branching hasilnya adalah partial sequence tersebut di iterasi.
Tabel 9. Partial Sequence untuk iterasi 1
Iterasi  yang  dihasilkan  pada  metode  ini  adalah  urutan-urutan  job  yang  dapat  meminimasi makespan seperti terlihat pada Tabel 10.
Tabel 10. Urutan Job pada Metode Branch and Bound
Penggunaan MH crane dan MH forklift juga  dipakai  dalam  metode  ini,  seperti terlihat  pada  tabel  11  untuk  Material Handling  Crane  pada  Lini  Siku.  Pada metode  branch  and  bound  menghasilkan
waktu  pengerjaan  sebesar  11,04  hari  atau efisiensi  sebesar    20,5%    untuk  lini  siku, 5,8  hari  atau  efisiensi  sebesar  10,8  % untuk  lini  plat  dan  3,6  hari  atau  efisiensi sebesar 12,13 % untuk lini plat khusus.
Parsial Sequence q1 q2 q3 b1 b2 b3 B Max 234
1 426 767 1875 7066 6076 18838 18838 18 2 426 767 1875 6640 5735 17730 17730 3 426 767 1875 6214 5394 16622 16622 4 426 767 1875 5788 5053 15514 15514 5 426 767 1875 5362 4712 14406 14406 6 427 769 1879 4937 4373 13302 13302 7 447 805 1967 4530 4067 12280 12280 8 447 805 1967 4083 3709 11118 11118 9 448 806 1970 3637 3352 9959 9959 10 167 300 733 2908 2488 7558 7558 11 67 120 293 2641 2175 6685 6685 12 515 927 2265 3022 2929 8484 8484 13 515 927 2265 2507 2517 7146 7146 14 515 927 2265 1992 2105 5808 5808 15 515 927 2265 1477 1693 4470 4470 16 233 420 1027 680 774 1894 1894 17 67 120 293 281 287 553 553 18 33 60 147 180 174 234 234 B Max Parsial Sequence J33,J30,J27,J15,J16,J13 J33,J30,J27,J15,J16,J13 J33,J30,J27,J15,J16,J13 Urutan Job
J8,J7,J6,J5D,J5A,J4,J5C,J3,J2C,J2A,J5A,J2B,J1E,J2A,J1B,J1D,J1A,J1C J8,J7,J4,J6,J5A,J5D,J5B,J5C,J7,J2B,J2C,J2A,J3,J1F,J1D,J1B,J1C,J1A J35,JJ34,J26,J42,J41,J39,J32,J31,J37,J29,J40,J38,J36,J28,J14,J23,J22,J24,J 21,J19,J17,J12,J25,J20,J9,J18,J10,J11 J35,JJ34,J26,J42,J41,J39,J32,J31,J37,J29,J40,J38,J36,J28,J14,J23,J22,J24,J 21,J19,J17,J12,J25,J20,J9,J18,J10,J11
J35,JJ34,J26,J42,J41,J39,J32,J31,J37,J29,J40,J38,J36,J28,J14,J23,J22,J24,J
21,J19,J17,J12,J25,J20,J9,J18,J10,J11
Lini Proses J8,J7,J6,J5D,J5A,J4,J5C,J3,J5B,J2C,J2B,J2A,J1F,J1E,J1D,J1C,J1B,J1A Plat khusus Gas Cutting Stamping Radial Drilling Cutting Stamping Copy Punch Siku Plat Cutting Stamping Holling
Di  dalam  metode  Branch  And  Bound, urutan  job  hasil  iterasi  digunakan  pada proses  paling  awal  yaitu  proses  cutting. Setelah  selesai  proses  cutting,  urutan  job berubah  disesuaikan  dengan  job  mana yang selesai terlebih dahulu. Urutan-urutan
job dapat berbeda baik pada proses cutting, stamping,dan  holling.  Waktu  saat  selesai pada  proses  holling  merupakan  waktu yang  menjadi  acuan  berapa  lama  proses produksi berlangsung.
Tabel 11. Tabel Waktu MH Crane pada Lini Siku
Tabel 12. Hasil perhitungan metode Branch and Bound
Lini Siku Lini Plat Lini Plat Khusus Waktu fabrikasi (menit) 4581 2681 1701 Penambahan waktu MH dari Warehouse  ke  area  raw  material (menit) 360 48 24 Penambahan  waktu  MH  dari  Holling- finished area (menit) 360 48 24 Total  waktu  penjadwalan  pada  lini (menit) 5301 2777 1749 Waktu kerja standar (hari) 11,04 5,79 3,64
Setelah melakukan perhitungan dengan menggunakan  metode  job  splitting  dan metode branch and bound, maka diperoleh perbandingan  hasil  penjadwalan.  Hal  ini
dapat  dilihat  pada  Tabel  13  untuk  hasil perhitungan  penjadwalan  dan  pada  tabel 13 memperlihatkan efisiensi hasil penjadwalan terhadap sistem awal. Tabel 13.Hasil Perhitungan Penjadwalan (dalam satuan menit) Lini Metode Segmentasi  Metode Job Splitting Metode Branch and Bound Siku 7061 5948 5301 Plat 3548 2991,5 2777 Plat Khusus 1984 1591 1767
J1A 1023 7365.96667 4 16 12 28 J1B 1023 7365.96667 4 16 12 28 J1C 1023 7365.96667 4 16 12 28 J1D 1023 7365.96667 4 16 12 28 J1E 1023 7365.96667 4 16 12 28 J1F 1025 7378.97 4 16 12 28 J2A 1073 1073.33333 1 4 3 7 J2B 1073 1073.33333 1 4 3 7 J2C 1074 1077 1 4 3 7 J3 400 29531.2 15 60 45 105 J4 160 4136 3 12 9 21 J5A 1235 2708.95 2 8 6 14 J5B 1235 7176.65 4 16 12 28 J5C 1235 1822.7 1 4 3 7 J5D 1235 7382.8 4 16 12 28 J6 560 7290.8 4 16 12 28 J7 160 4136 3 12 9 21 J8 80 4636.8 3 12 9
21
Waktu Loading
Unloading (Menit) Total Waktu MH (Menit) Berat (Kg) Jumlah Pengangkutan Waktu Pengangkutan (Menit)
Job Jumlah
Unit
Penjadwalan awal menggunakan sistem  segmentasi  menghasilkan  waktu yang  lebih  panjang  daripada  penjadwalan menggunakan  metode  job  splitting  atau metode  branch  and  bound.  Kelemahan penjadwalan  awal  adalah  pengaturan  job dengan sistem segmentasi yang mengakibatkan terjadinya pemborosan waktu di dalam pemakaian MH crane.Berdasarkan  tabel  14,  efisiensi terbesar  adalah  dengan  menggunakan metode  branch  and  bound.  Namun,  untuk
dapat  menggunakan  metode  branch  and boundperusahaan perlu menempatkan
salah satu operator untuk
mengkoordinasikan  pada  lantai  produksi. Ruang  gerak  operator  tersebut  dinamakan collecting area. Fungsinya adalah mengumpulkan  seluruh  job  yang  telah diproses  untuk  diproses  kemudian  pada mesin  yang  terpilih.  Gambar  3  berikut  ini adalah  tampilan  flow  machine  yang  telah ditambahkan collecting area.
Tabel 14 Efisiensi Hasil Penjadwalan
Gambar 3. Flow Machine Lini Siku dengan collecting area.
Penggunaan  metode  job  splitting  dan metode  branch  and  boundpada  makalah ini untuk meminimasi makespan.
Padakedua  metode,  pembagian  job  yang digunakan adalah dengan
mengklasifikasikan  job  sesuai  dengan ukuran profil. Penggunaan material handlingcrane  dan  forklift  juga  memiliki pengaruh  yang  signifikan  terhadap  waktu penjadwalan. Sebab terdapat waktu pengangkutan  yang  disesuaikan  dengan berat  setiap  job,  semakin  berat  job tersebut, maka semakin banyak pengangkutan  yang  dilakukan  dan  ini berpengaruh besar terhadap waktu penyelesaian. Berdasarkan hasil
perhitungan mendapatkan  hasil  bahwa  metode  job
splitting  memberikan  efisiensi  yang  lebih besar  dibandingkan  metode  branch  and bound. Job splitting menghasilkan efisiensi  15,8  %  untuk  lini  siku,  15,7  % untuk lini plat dan 19,80 % untuk lini plat khusus.  Sedangkan  metode  branch  and bound menghasilkan efisiensi 24,9% untuk lini siku, 21,7% untuk lini plat dan 10,9% untuk  lini  plat  khusus.  Pada  lini  plat khusus,  penggunaan    metode  job  splitting menghasilkan  efisiensi  yang  lebih  baik sebab  jumlah  unit  yang  dikerjakan  pada satu mesin sama satu dengan yang lainnya, dan  di  dalam  lini  ini,  waktu  setup  mesin dan waktu collectingnya rendah. Sehingga, waktu fabrikasi menjadi lebih cepat.
Siku Plat Plat Khusus Lini Job Splitting Branch and bound Efisiensi dengan Metode
15.80% 19.80%
10.90%
24.90% 15.70% 21.70%

## 6. KESIMPULAN
Penentuan job berdasarkan kesamaan  ukuran  memberikan  dampak yang berbeda terhadap penjadwalan. Penjadwalan branch and bound
menghasilkan  efisiensi  yang  lebih  baik pada  lini  siku  dan  lini  plat.  Sedangkan metode job splitting menghasilkan efisiensi  lebih  tinggi  pada  lini  plat  khusus sebab  jumlah  unit  yang  dikerjakan  pada satu mesin sama dengan yang lainnya, dan di  dalam  lini  ini,  waktu  setup  mesin  dan waktu  collectingnya  rendah.  Sehingga, waktu fabrikasi menjadi lebih cepat. Pada  metode  ini  harus  ada  operator  untuk mengkordinasikan  transfer  komponen  dari satu  proses  ke  proses  berikutnya.  Sebab, metode ini membagi satu buah job menjadi sub-sub  job  sesuai  dengan  jumlah  mesin paralel  pada  proses  selanjutnya.  Fungsi dari  operator  tersebut  adalah  membagi sub-sub  job  tersebut  untuk  ditempatkan pada mesin yang akan mengerjakan.

## 7. DAFTAR PUSTAKA
B_la˙zewicz,  Jacek,et  al.  2007.  Handbook on  Scheduling:  From  Theory  to Applications.  Springer-Verlag  Berlin Heidelberg.
Baker,
K.R., 1974.Introduction
to
Sequencing  and  Scheduling,  New
York, John Wiley & Sons Inc.
Bedworth, David D. dan Bailey, James E.,
1987.Integrated  Production  Control System: Management, Analysis, Design,  2 nd edition,  John  Wiley  and
Sons, New York.
Brah,  S.A.,  1988.  Scheduling  in  a  Flow
Shop  With  Multiple  Processors.  PhD Thesis. University of Houston. TX.
Brah, S.A., dan Hunsucker,J.L.,1991.Branch and bound algorithm for the flow shop with multiple processors, European Journal
of  Operational  Research  51  (1),  p.88- 99.
Rabadi, Ghaith, Anagnostopoulos, Georgio C.,dan Mollaghasemi, Mansooreh, 2007. A Heuristic
Algorithm for The Just In Time Single Machine  Scheduling  Problem  with Setups:  A  comparison  with  simulated annealing,  International  Journal  of Advanced  Manufacturing  Technology
32, 3-4, p.326-335. Hidri, Lotfi dan Haouari,Mohamed,2011.Bounding strategies  for  the  hybrid  flow  shop scheduling problem, Applied Mathematics and Computation 217. Ignall, E., dan Schrage,L.E., 1965.Application  of  the  branch-and- bound  technique  to  some  flow-shop scheduling problems, Operation Research 13, p.400-412.
Lawler,  E.L.,  Lenstra,  J.K.,  Kan,A.H.G.
Rinnooy dan D.B.
Shmoys,
1993.Sequencing and scheduling:
algorithms  and  complexity,  in:  S. Grave, A.H.G. Rinnooy Kan, P. Zipkin (Eds.),  Logistics  of  Production  and Inventory, North-Holland, Amsterdam, p.445{522}.
Lomnicki,Z.A.,  1965.A  branch-and-bound algorithm  for  the  exact  solution  of  the three-machine  scheduling  problem, Operation  ResearchQuart  16,  p.89-
100.
Morthon,  Thomas  E.,  danPentico,  David W., 1993. Heuristics Scheduling Systems: With Application in
Manufacturing  and  Service.  John Wiley and Sons. New York
Ruiz,  Rubén,  dan  Vázquez-Rodríguez, José  Antonio,  2010.  The  hybrid  flow shop  scheduling  problem,  European Journal of Operational Research205.
Xing, Wenxun, dan Zhang,Jiawei,2000.Parallel machine scheduling with splitting jobs, Discrete Applied Mathematics 103.