Penjadwalan Produksi Untuk Meminimalkan Waktu Produksi Dengan Menggunakan Metode Branch And Bound
Nunung Indra Lesmana
Jurusan Teknk Industri, Fakultas Teknik, Universitas Muhammadiyah Malang Jl. Raya Tlogomas 246 Malang Surel: indra.nunung@gmail.com

## Abstract
Scheduling  is  the  process  of  organizing,  selecting  and  timing  of  the  use  of  existing resources to produce output as expected within the expected time too. Problems faced by the company is determining the minimal production scheduling, as in the case of the production of the company in March, May and August 2015, delays occurred up to three business days, or approximately 14% compared to normal production time per month. The  results  of  this  study  indicate  if  using  methods  Branch  and  Bound,  the  more processing time than the method the company trimmed. for example, in February 2016 when  using  the  method  of  the  company,  the  turnaround  time  is  obtained  10584.385 minutes,  whereas  if  the  company  uses  Branch  and  Bound  method  can  be  reduced completion  time  of  789.66  minutes  so  that  it  becomes  9794.719  minutes,  or  1.8  days faster than using companies.
Key words :  production  scheduling,  flow  shop,  branch  and  bound, makespan.

## Abstrak
Penjadwalan  merupakan  proses  pengorganisasian,  pemilihan,  dan  penentuan  waktu penggunaan sumber daya yang ada untuk menghasilkan output seperti yang diharapkan dalam  waktu  yang  diharapkan  juga.  Permasalahan  yang  dihadapi  oleh  perusahaan adalah menentukan penjadwalan produksi yang minimal, seperti dalam kasus produksi perusahaan  di  bulan  maret,  mei,  dan  agustus  2015,  keterlambatan  terjadi  sampai dengan tiga hari kerja atau sekitar 14 % dibandingkan dengan waktu normal produksi per bulan. Hasil dari penelitian ini menunjukkan jika menggunakan metode Branch and Bound  maka  waktu  pengerjaan  lebih  singkat  daripada  menggunakan  metode perusahaan. misalnya pada bulan Februari 2016 jika menggunakan metode perusahaan maka  waktu  penyelesaian  yang  didapat  adalah  10.584,385  menit,  sedangkan  jika menggunakan  metode  Branch  and  Bound  waktu  penyelesaian  bisa  diperkecil  sebesar 789,66  menit  sehingga  menjadi  9.794,719  menit,  atau  1,8  hari  lebih  cepat  dibanding dengan menggunakan metode perusahaan.
Kata kunci : penjadwalan produksi, flow shop, branch and bound, makespan.

## 1. Pendahuluan
Penjadwalan merupakan alat ukur bagi perencanaan agregat. Pesanan-pesanan actual pada tahap ini ditugaskan pertama kalinya pada sumber daya tertentu, kemudian dilakukan pengurutan kerja pada tiap-tiap pusat pemrosesan sehingga dicapai optimasi utilitas kapasitas yang ada. Pada penjadwalan ini permintaan akan produk-produk yang tertentu (jenis dan jumlah) dari MPS akan ditugaskan pada pusat-pusat pemrosesan[1].
Menurut  Haming  and  Nurnajamuddin  [2]  penjadwalan  adalah  pengalokasian sumber daya dari waktu ke waktu untuk menunjang pelaksanaan dan penyelesaian suatu aktivitas pengerjaan spesifik. Penentuan alokasi sumber daya perusahaan (sumber daya manusia, sumber daya kapasitas dan peralatan produksi atau mesin-mesin, dan waktu) ditunjukkan  untuk  mewujudkan  sasaran  penggunaan  sumber  daya  secara  efektif  dan

## ISSN 1978-1431 print / ISSN 2527-4112 online
efisien, sekaligus menghasilkan keluaran (output) yang tepat jumlah, tepat waktu, dan tepat kualitas [3-5].
Masalah utama yang dihadapi oleh perusahaan adalah menentukan penjadwalan produksi yang minimal. Tujuan penulisan makalah ini adalah untuk menguraikan salah satu metode dalam meminimalkan waktu penjadwal produksi untuk jenis produk Maxi, Matras, dan Twin. Perusahaan menggunakan metode FIFO dalam proses produksinya, yang artinya job yang dikerjakan terlebih dahulu adalah job yang pertama datang[6-9]. Dengan begitu, penyelesaian job akan membutuhkan waktu yang lama. Seperti dalam kasus produksi dibulan maret, mei, dan agustus 2015 keterlambatan terjadi satu sampai tiga  hari  kerja  atau  sekitar  14  %  dari  waktu  normal  selama  satu  bulan.    Atas  dasar permasalahan tersebut perusahaan memerlukan sebuah metode penjadwalan yang baik untuk  sistem  operasinya.  Berdasarkan  pada  permasalahan  di  atas  dan  juga  pada penelitian-penelitian sebelumnya perlu dilakukan suatu penjadwalan produksi agar bisa meminimalkan waktu penyelesaian produksi, sehingga perusahaan dapat memproduksi produk sesuai dengan waktu yang ditentukan, sehingga mesin dapat digunakan dengan optimal. Pada  penelitian  ini,  metode  penjadwalan  produksi  yang  digunakan  adalah branch and bound.

## 2. Metode Penelitian Langkah-Langkah Penelitian

## 1. Membuat Jadwal Produksi Metode Perusahaan (FIFO)
Memilih  pekerjaan  berdasarkan  yang  datang  dahulu,  itu  yang  diproses[10]. Dengan  menggunakan  aturan  ini,  proses  pekerjaan  tersebut  tiba  pada  fasilitas  yang bersangkutan[3].
2. Membuat Jadwal Produksi Dengan Metode Usulan
Metode  Branch  and  Bound  merupakan  salah  satu  metode  yang  baik  untuk digunakan  dalam  menyelesaikan  masalah  kombinasi  dengan  menggunakan  strategi pengurangan  jumlah  perhitungan  yang  dilakukan,  dalam  metode  ini  terdapat  dua prosedur  dasar  yaitu branching (percabangan)  dan bounding (pembatasan). Branching adalah proses pembagian atau percabangan satu masalah yang besar atau rumit menjadi dua atau lebih sub masalah yang lebih kecil atau sederhana, sedangkan bounding adalah proses  menghitung  batas  bawah  solusi  optimal  dari  sub  masalah  yang  diperoleh  dari percabangan. [11].
Dalam menyelesaikan masalah penjadwalan pada system produksi yang bersifat flow shop, menggunakan pendekatan Algoritma Branch and Bound untuk aliran produksi flow  shop yang  dikembangkan  oleh Ignall  and  Scharge,  dan  Lomnicki.  Adapun perhitungan untuk tiga mesin adalah sebagai berikut [12]:
Memilih job yang terlebih dahulu dikerjakan,kemudian menghitung lower bound di mesin 1 (b1), lower bound di mesin 2 (b2), dan lower bound di mesin 3 (b3)
𝑏1 = 𝑞1 +   ∑ 𝑡𝑗1 𝑗𝜖𝜎 + min 𝑗𝜖𝜎 {𝑡𝑗2 + 𝑡𝑗3} (1)
Kemudian menghitung b untuk mesin ke dua
𝑏2 = 𝑞2 +   ∑ 𝑡𝑗2 + max 𝑗𝜖𝜎 {𝑡𝑗3} 𝑗𝜖𝜎 (2) Yang terakhir menghitung untuk mesin ke tiga 𝑏3 = 𝑞3 +   ∑ 𝑡𝑗3 𝑗𝜖𝜎 (3) Kemudian menentukan nilai B 𝐵 =   max{𝑏1, 𝑏2, 𝑏3} (4)
Lakukan langkah yang sama untuk menghitung urutan pengerjaan yang berbeda dan pilih B terkecil, atau jika perhitungan penjadwalan dengan menggunakan m mesin maka dapat memakai rumus
𝑏𝑖 = 𝑞𝑖 +   ∑ 𝑡𝐽𝑖 +   min 𝐽∈𝜎 {∑ 𝑡𝐽𝑖 𝑚 𝑖=𝑖+1 } 𝐽∈𝜎 (5) 𝐵𝐾 = max 𝑖 {𝑏𝑖} (6) 𝑀 = min 𝐾 {𝐵𝐾} (7)
Dimana : bi = lower bound, adalah hasil perhitungan dari nilai batas bawah pada mesin i. qi = jumlah completion time yang terakhir pada mesin i. σ  = job yang belum dijadwalkan. tij = waktu proses job j pada mesin i. m = banyaknya tahapan pengerjaan di mesin. n  = banyaknya job BK = max lower bound untuk partial sequencing ke-K
M = min lower bound dari job j.

## 3. Hasil dan Pembahasan

## 3.1 Penjadwalan Awal Perusahaan
Pada penelitian ini solusi awal metode yang diterapkan pada perusahaan untuk urutan pekerjaan adalah dengan subjektifitas, dan urutannya adalah job 1-2-3-4-5-6 yang terdiri dari Maxi ukuran 120 x 200 cm (J1), Maxi ukuran 160 x 200 cm (J2), Maxi ukuran 180 x 200 cm (J3), dan Twin ukuran 160 x 200 cm (J6). Untuk lebih jelasnya dapat dilihat pada tabel 1:

## Tabel 1
Urutan Pengerjaan dengan Metode   Perusahaan Urutan Ke-
Job Urutan Ke-
Job
Urutan Ke-
Job
Urutan Ke- Job Urutan Ke- Job Urutan Ke- Job
1
J1.1 9 J2.1 17 J3.1 25 J4.2
33 J5.2 41 J6.3
2 J1.2
10
J2.2 18 J3.2 26 J4.3
34 J5.3 42 J6.4
3 J1.3
11
J2.3 19 J3.3 27 J4.4
35 J5.4 43 J6.5
4 J1.4
12
J2.4 20 J3.4 28 J4.5
36 J5.5 44 J6.6
5 J1.5
13
J2.5 21 J3.5 29 J4.6 37 J5.6
45 J6.7
6 J1.6
14
J2.6 22 J3.6 30 J4.7 38 J5.7 46 J6.8 7 J1.7 15 J2.7 23 J3.7 31 J4.8 39 J6.1 8 J1.8 16 J2.8 24 J4.1 32 J5.1
40
J6.2
Dari tabel 2 dapat disimpulkan bahwa dengan menggunakan metode FIFO (Firs In Firs Out) makespan yang dihasilkan sebesar 10584,,39 menit.

## 3.2 Penjadwalan Dengan Metode Branch and Bound
Berikut  perhitungan  penjadwalan  dengan  menggunakan  Metode Branch  and Bound, pada perhitungan metode Branch and Bound ini menggunakan bantuan program Microsoft Excel dan hasil perhitungannya adalah sebagai berikut : Iterasi 1

## ISSN 1978-1431 print / ISSN 2527-4112 online
Tabel 2 a Perhitungan Makespan dengan metode perusahaan (menit)
Job Batch Mulai Selesai M1 M2 M3 M4 M5 M6 M7 M1 M2 M3 M4 M5 M6 M7 J1 J1.1 0,00 52,35 128,10 128,10 128,10 128,10 333,60 52,35 128,10 128,10 128,10 128,10 333,60 613,60 J1.2 52,35 128,10 203,85 203,85 203,85 203,85 613,60 104,70 203,85 203,85 203,85 203,85 409,35 893,60 J1.3 104,70 203,85 279,60 279,60 279,60 279,60 893,60 157,05 279,60 279,60 279,60 279,60 485,10 1173,60 J1.4 157,05 279,60 355,35 355,35 355,35 485,10 1173,60 209,40 355,35 355,35 355,35 355,35 690,60 1453,60 J1.5 209,40 355,35 431,10 431,10 431,10 690,60 1453,60 261,75 431,10 431,10 431,10 431,10 896,10 1733,60 J1.6 261,75 431,10 506,85 506,85 506,85 896,10 1733,60 314,10 506,85 506,85 506,85 506,85 1101,60 2013,60 J1.7 314,10 506,85 582,60 582,60 582,60 1101,60 2013,60 366,45 582,60 582,60 582,60 582,60 1307,10 2293,60 J1.8 366,45 582,60 655,32 655,32 655,32 1307,10 2293,60 416,71 655,32 655,32 655,32 655,32 1504,38 2562,40 J2 J2.1 416,71 655,32 754,32 754,32 754,32 1504,38 2562,40 490,81 754,32 754,32 754,32 754,32 1706,38 2852,40 J2.2 490,81 754,32 853,32 853,32 853,32 1706,38 2852,40 564,91 853,32 853,32 853,32 853,32 1908,38 3142,40 J2.3 564,91 853,32 952,32 952,32 952,32 1908,38 3142,40 639,01 952,32 952,32 952,32 952,32 2110,38 3432,40 J2.4 639,01 952,32 1051,32 1051,32 1051,32 2110,38 3432,40 713,11 1051,32 1051,32 1051,32 1051,32 2312,38 3722,40 J2.5 713,11 1051,32 1150,32 1150,32 1150,32 2312,38 3722,40 787,21 1150,32 1150,32 1150,32 1150,32 2514,38 4012,40 J2.6 787,21 1150,32 1249,32 1249,32 1249,32 2514,38 4012,40 861,31 1249,32 1249,32 1249,32 1249,32 2716,38 4302,40 J2.7 861,31 1249,32 1348,32 1348,32 1348,32 2716,38 4302,40 935,41 1348,32 1348,32 1348,32 1348,32 2918,38 4592,40 J2.8 935,41 1348,32 1401,78 1401,78 1401,78 2918,38 4592,40 975,42 1401,78 1401,78 1401,78 1401,78 3027,46 4749,00 J3 J3.1 975,42 1076,02 1401,78 1401,78 1401,78 3027,46 4749,00 1076,02 1201,27 1401,78 1401,78 1401,78 3228,96 5044,00 J3.2 1076,02 1201,27 1401,78 1401,78 1401,78 3228,96 5044,00 1176,62 1326,52 1401,78 1401,78 1401,78 3430,46 5339,00 J3.3 1176,62 1326,52 1451,77 1451,77 1451,77 3430,46 5339,00 1277,22 1451,77 1451,77 1451,77 1451,77 3631,96 5634,00 J3.4 1277,22 1451,77 1577,02 1577,02 1577,02 3631,96 5634,00 1377,82 1577,02 1577,02 1577,02 1577,02 3833,46 5929,00 J3.5 1377,82 1577,02 1702,27 1702,27 1702,27 3833,46 5929,00 1478,42 1702,27 1702,27 1702,27 1702,27 4034,96 6224,00 J3.6 1478,42 1702,27 1827,52 1827,52 1827,52 4034,96 6224,00 1579,02 1827,52 1827,52 1827,52 1827,52 4236,46 6519,00 J3.7 1579,02 1827,52 1935,24 1935,24 1935,24 4236,46 6519,00 1665,54 1935,24 1935,24 1935,24 1935,24 4409,75 6772,70 J4 J4.1 1665,54 1935,24 2032,74 2366,24 2619,24 4409,75 6772,70 1739,64 2032,74 2366,24 2619,24 2872,24 4409,75 6772,70 J4.2 1739,64 2032,74 2366,24 2699,74 2952,74 4409,75 6772,70 1813,74 2130,24 2699,74 2952,74 3205,74 4409,75 6772,70 J4.3 1813,74 2130,24 2699,74 3033,24 3286,24 4409,75 6772,70 1887,84 2227,74 3033,24 3286,24 3539,24 4409,75 6772,70 J4.4 1887,84 2227,74 3033,24 3366,74 3619,74 4409,75 6772,70 1961,94 2325,24 3366,74 3619,74 3872,74 4409,75 6772,70 J4.5 1961,94 2325,24 3366,74 3700,24 3953,24 4409,75 6772,70 2036,04 2422,74 3700,24 3953,24 4206,24 4409,75 6772,70 J4.6 2036,04 2422,74 3700,24 4033,74 4286,74 4539,74 6772,70 2110,14 2520,24 4033,74 4286,74 4539,74 4539,74 6772,70 J4.7 2110,14 2520,24 4033,74 4367,24 4620,24 4873,24 6772,70 2184,24 2617,74 4367,24 4620,24 4873,24 4873,24 6772,70 J4.8 2184,24 2617,74 4367,24 4493,97 4590,11 4686,25 6772,70 2212,39 2654,79 4493,97 4590,11 4686,25 4686,25 6772,70 J5 J5.1 2212,39 2654,79 4493,97 4877,47 5130,47 5383,47 6772,70 2312,99 2780,04 4877,47 5130,47 5383,47 5383,47 6772,70 J5.2 2312,99 2780,04 4877,47 5260,97 5513,97 5766,97 6772,70 2413,59 2905,29 5260,97 5513,97 5766,97 5766,97 6772,70 J5.3 2413,59 2905,29 5260,97 5644,47 5897,47 6150,47 6772,70 2514,19 3030,54 5644,47 5897,47 6150,47 6150,47 6772,70 J5.4 2514,19 3030,54 5644,47 6027,97 6280,97 6533,97 6772,70 2614,79 3155,79 6027,97 6280,97 6533,97 6533,97 6772,70 J5.5 2614,79 3155,79 6027,97 6411,47 6664,47 6917,47 6917,47 2715,39 3281,04 6411,47 6664,47 6917,47 6917,47 6917,47 J5.6 2715,39 3281,04 6411,47 6794,97 7047,97 7300,97 7300,97 2815,99 3406,29 6794,97 7047,97 7300,97 7300,97 7300,97 J5.7 2815,99 2908,55 6794,97 7147,79 7380,55 7613,31 7613,31 2908,55 3023,78 7147,79 7380,55 7613,31 7613,31 7613,31
Tabel 2 b (Lanjutan)
Job Batch Mulai Selesai M1 M2 M3 M4 M5 M6 M7 M1 M2 M3 M4 M5 M6 M7 J6 J6.1 2908,55 3057,05 7147,79 7481,29 7734,29 7987,29 8194,79 3057,05 3256,55 7481,29 7734,29 7987,29 8194,79 8484,79 J6.2 3057,05 3256,55 7481,29 7814,79 8067,79 8320,79 8528,29 3205,55 3456,05 7814,79 8067,79 8320,79 8528,29 8818,29 J6.3 3205,55 3456,05 7814,79 8148,29 8401,29 8654,29 8861,79 3354,05 3655,55 8148,29 8401,29 8654,29 8861,79 9151,79 J6.4 3354,05 3655,55 8148,29 8481,79 8734,79 8987,79 9195,29 3502,55 3855,05 8481,79 8734,79 8987,79 9195,29 9485,29 J6.5 3502,55 3855,05 8481,79 8815,29 9068,29 9321,29 9528,79 3651,05 4054,55 8815,29 9068,29 9321,29 9528,79 9818,79 J6.6 3651,05 4054,55 8815,29 9148,79 9401,79 9654,79 9862,29 3799,55 4254,05 9148,79 9401,79 9654,79 9862,29 10152,29 J6.7 3799,55 4254,05 9148,79 9482,29 9735,29 9988,29 10195,79 3948,05 4453,55 9482,29 9735,29 9988,29 10195,79 10485,79 J6.8 3948,05 4453,55 9482,29 9735,29 9988,29 10195,79 10485,79 3998,54 4521,38 9595,68 9821,31 10074,31 10266,34 10584,39
Menentukan q apabila job 1.1 dikerjakan terlebih dahulu : q1 = t11 = 52,35 menit q2 = t11 + t12 = 52,35 + 75,75 = 128,1 menit q3 = t11 + t12 + t13 = 52,35 + 75,75 + 0 = 128,1  menit q4 = t11 + t12 + t13 + t14 = 52,35 + 75,75+ 0 + 0 = 128,1 menit q5 = t11 + t12 + t13 + t14 + t15 = 52,35 + 75,75 + 0 + 0 + 0 = 128,1 menit q6 = t11 + t12 + t13 + t14 + t15 + t16= 52,35 + 75,75 + 0 + 0 + 0 + 205,5 = 333,6   menit q7 = t11 + t12 + t13 + t14 + t15 + t16 + t17= 52,35 + 75,75 +  0  +  0  + 0 +   205,5  +  280 = 613,6 menit
Menghitung nilai bi pada job 1.1
𝑏1 = 𝑞1 +   ∑ 𝑡𝑗1
𝑗 尷 𝜎 + min 𝑗𝜖𝜎 {𝑡𝑗2 + 𝑡𝑗3 +  𝑡𝑗4 + 𝑡𝑗5 +  𝑡𝑗6 +  𝑡𝑗7}
b1 = 52,35 + (3946,19) + 319,14 = 4317,68 menit 𝑏2 = 𝑞2 +   ∑ 𝑡𝑗2
𝑗𝜖𝜎 + min 𝑗𝜖𝜎 {𝑡𝑗3 +  𝑡𝑗4 + 𝑡𝑗5 +  𝑡𝑗6 +  𝑡𝑗7}
b2 = 128,1 + ( 5183,51 ) + 265,68 = 5577,29 menit 𝑏3 = 𝑞3 +   ∑ 𝑡𝑗3
𝑗𝜖𝜎
+ min 𝑗𝜖𝜎 { 𝑡𝑗4 + 𝑡𝑗5 +  𝑡𝑗6 +  𝑡𝑗7}
b3 = 128,1  + ( 7562,94 ) + 192,28 = 7883,32 menit
𝑏4 = 𝑞4 +   ∑ 𝑡𝑗4
𝑗𝜖𝜎
+ min 𝑗𝜖𝜎 { 𝑡𝑗5 +  𝑡𝑗6 +  𝑡𝑗7}
b4 = 128,1  + ( 5474,92) + 96,14 = 5699,16 menit 𝑏5 = 𝑞5 +   ∑ 𝑡𝑗5
𝑗𝜖𝜎 + min 𝑗𝜖𝜎 {  𝑡𝑗6 +  𝑡𝑗7}
b5 = 128,1  + (5474,92) + 0 = 5603,02 menit 𝑏6 = 𝑞6 +   ∑ 𝑡𝑗6
𝑗𝜖𝜎 + min 𝑗𝜖𝜎 {𝑡𝑗7}
b6 = 333,6 + ( 5858,70) + 0 = 6192,30 menit
𝑏7 = 𝑞7 +   ∑ 𝑡𝑗7
𝑗𝜖𝜎 b7 = 613,6 + ( 8287,70) = 8901,70 menit

## ISSN 1978-1431 print / ISSN 2527-4112 online
Dari Partial Sequence di atas didapat nilai B dari seluruh job nilai yang terkecil adalah job ke 2.8. Sehingga job ke 2.8 dikerjakan terlebih dahulu. Kemudian menentukan q untuk menentukan urutan berikutnya.
Iterasi 2 Apabila Job 1.1 dikerjakan setelah Job 2.8 M1 M2 M3 M4 M5 M6 M7 Job 2.8 Job 1.1
Gambar 1 Gantt Chart Iterasi 1
Dari Gambar 1 didapat nilai q untuk Job 1.1 yakni: q1= 92,36 menit q2= 169,22 menit q3= 169,22 menit q4= 169,22 menit q5= 169,22 menit q6= 374,72 menit q7= 655 menit Menghitung bi dari job 1.1 𝑏1 = 𝑞1 +   ∑ 𝑡𝑗1 𝑗𝜖𝜎 + min 𝑗𝜖𝜎 {𝑡𝑗2 + 𝑡𝑗3 +  𝑡𝑗4 + 𝑡𝑗5 +  𝑡𝑗6 +  𝑡𝑗7}
b1 = 92,36 + (3906) + 356,06 = 4354,59 menit
𝑏2 = 𝑞2 +   ∑ 𝑡𝑗2
𝑗𝜖𝜎 + min 𝑗𝜖𝜎 {𝑡𝑗3 +  𝑡𝑗4 + 𝑡𝑗5 +  𝑡𝑗6 +  𝑡𝑗7}
b2 = 169,22 + ( 5130,045 ) + 319,01 = 5618,27 menit 𝑏3 = 𝑞3 +   ∑ 𝑡𝑗3
𝑗𝜖𝜎 + min 𝑗𝜖𝜎 { 𝑡𝑗4 + 𝑡𝑗5 +  𝑡𝑗6 +  𝑡𝑗7}
b3 = 169,22 + ( 7562,94 ) + 192,28 = 7883,32 menit
𝑏4 = 𝑞4 +   ∑ 𝑡𝑗4
𝑗𝜖𝜎 + min 𝑗𝜖𝜎 { 𝑡𝑗5 +  𝑡𝑗6 +  𝑡𝑗7}
b4 = 169,22 + (5474,92) + 96,14 = 7828,30 menit
𝑏5 = 𝑞5 +   ∑ 𝑡𝑗5
𝑗𝜖𝜎
+ min 𝑗𝜖𝜎 {  𝑡𝑗6 +  𝑡𝑗7}
Hasil Perhitungan secara lengkap dapat dilihat di tabel 3.
Tabel 3 Partial Sequence Iterasi 2
Batch q1 q2 q3 q4 q5 q6 q7 b1 b2 b3 b4 b5 b6 b7 B J1.1 92,4 169,2 169,2 169,2 169,2 374,7 654,7 4354,6 5618,3 7828,3 5644,1 5644,1 6124,3 8785,8 8785,8 J1.2 92,4 169,2 169,2 169,2 169,2 374,7 654,7 4354,6 5618,3 7828,3 5644,1 5644,1 6124,3 8785,8 8785,8 J1.3 92,4 169,2 169,2 169,2 169,2 374,7 654,7 4354,6 5618,3 7828,3 5644,1 5644,1 6124,3 8785,8 8785,8 J1.4 92,4 169,2 169,2 169,2 169,2 374,7 654,7 4354,6 5618,3 7828,3 5644,1 5644,1 6124,3 8785,8 8785,8 J1.5 92,4 169,2 169,2 169,2 169,2 374,7 654,7 4354,6 5618,3 7828,3 5644,1 5644,1 6124,3 8785,8 8785,8 J1.6 92,4 169,2 169,2 169,2 169,2 374,7 654,7 4354,6 5618,3 7828,3 5644,1 5644,1 6124,3 8785,8 8785,8 J1.7 92,4 169,2 169,2 169,2 169,2 374,7 654,7 4354,6 5618,3 7828,3 5644,1 5644,1 6124,3 8785,8 8785,8 *J1.8 90,3 166,2 166,2 166,2 166,2 363,5 632,3 4354,6 5618,3 7921,4 5737,3 5641,1 6121,3  8774,6 8774,6 J2.1 114,1 213,1 213,1 213,1 213,1 415,1 705,1 4354,6 5638,9 7968,3 5784,2 5688,0 6168,2 8826,2 8826,2 J2.2 114,1 213,1 213,1 213,1 213,1 415,1 705,1 4354,6 5638,9 7968,3 5784,2 5688,0 6168,2 8826,2 8826,2 J2.3 114,1 213,1 213,1 213,1 213,1 415,1 705,1 4354,6 5638,9 7968,3 5784,2 5688,0 6168,2 8826,2 8826,2 J2.4 114,1 213,1 213,1 213,1 213,1 415,1 705,1 4354,6 5638,9 7968,3 5784,2 5688,0 6168,2 8826,2 8826,2 J2.5 114,1 213,1 213,1 213,1 213,1 415,1 705,1 4354,6 5638,9 7968,3 5784,2 5688,0 6168,2 8826,2 8826,2 J2.6 114,1 213,1 213,1 213,1 213,1 415,1 705,1 4354,6 5638,9 7968,3 5784,2 5688,0 6168,2 8826,2 8826,2 J2.7 114,1 213,1 213,1 213,1 213,1 415,1 705,1 4354,6 5638,9 7968,3 5784,2 5688,0 6168,2 8826,2 8826,2 J2.8 J3.1 140,6 265,9 265,9 265,9 265,9 467,4 762,4 4354,6 5665,4 8021,1 5836,9 5740,8 6221,0 8878,5 8878,5 J3.2 140,6 265,9 265,9 265,9 265,9 467,4 762,4 4354,6 5665,4 8021,1 5836,9 5740,8 6221,0 8878,5 8878,5 J3.3 140,6 265,9 265,9 265,9 265,9 467,4 762,4 4354,6 5665,4 8021,1 5836,9 5740,8 6221,0 8878,5 8878,5 J3.4 140,6 265,9 265,9 265,9 265,9 467,4 762,4 4354,6 5665,4 8021,1 5836,9 5740,8 6221,0 8878,5 8878,5 J3.5 140,6 265,9 265,9 265,9 265,9 467,4 762,4 4354,6 5665,4 8021,1 5836,9 5740,8 6221,0 8878,5 8878,5 J3.6 140,6 265,9 265,9 265,9 265,9 467,4 762,4 4354,6 5665,4 8021,1 5836,9 5740,8 6221,0 8878,5 8878,5 J3.7 126,5 234,2 234,2 234,2 234,2 407,5 661,2 4354,6 5651,3 7989,5 5805,3 5709,2 6189,4 8818,6 8818,6 J4.1 114,1 211,6 545,1 798,1 1051,1 1051,1 1051,1 4354,6 5638,9 7966,8 6116,2 6273,0 7006,2 9462,2 9462,2 J4.2 114,1 211,6 545,1 798,1 1051,1 1051,1 1051,1 4354,6 5638,9 7966,8 6116,2 6273,0 7006,2 9462,2 9462,2 J4.3 114,1 211,6 545,1 798,1 1051,1 1051,1 1051,1 4354,6 5638,9 7966,8 6116,2 6273,0 7006,2 9462,2 9462,2 J4.4 114,1 211,6 545,1 798,1 1051,1 1051,1 1051,1 4354,6 5638,9 7966,8 6116,2 6273,0 7006,2 9462,2 9462,2 J4.5 114,1 211,6 545,1 798,1 1051,1 1051,1 1051,1 4354,6 5638,9 7966,8 6116,2 6273,0 7006,2 9462,2 9462,2 J4.6 114,1 211,6 545,1 798,1 1051,1 1051,1 1051,1 4354,6 5638,9 7966,8 6116,2 6273,0 7006,2 9462,2 9462,2 J4.7 114,1 211,6 545,1 798,1 1051,1 1051,1 1051,1 4354,6 5638,9 7966,8 6116,2 6273,0 7006,2 9462,2 9462,2 J4.8 68,2 130,5 257,3 353,4 449,5 449,5 449,5 4537,3 5765,3 8159,5 5964,9 5828,3 6404,7 8860,6 8860,6 J5.1 140,6 265,9 649,4 902,4 1155,4 1155,4 1155,4 4354,6 5665,4 8021,1 6220,4 6377,3 7110,5 9566,5 9566,5 J5.2 140,6 265,9 649,4 902,4 1155,4 1155,4 1155,4 4354,6 5665,4 8021,1 6220,4 6377,3 7110,5 9566,5 9566,5 J5.3 140,6 265,9 649,4 902,4 1155,4 1155,4 1155,4 4354,6 5665,4 8021,1 6220,4 6377,3 7110,5 9566,5 9566,5 J5.4 140,6 265,9 649,4 902,4 1155,4 1155,4 1155,4 4354,6 5665,4 8021,1 6220,4 6377,3 7110,5 9566,5 9566,5 J5.5 140,6 265,9 649,4 902,4 1155,4 1155,4 1155,4 4354,6 5665,4 8021,1 6220,4 6377,3 7110,5 9566,5 9566,5 J5.6 140,6 265,9 649,4 902,4 1155,4 1155,4 1155,4 4354,6 5665,4 8021,1 6220,4 6377,3 7110,5 9566,5 9566,5 J5.7 132,6 247,8 600,6 833,4 1066,1 1066,1 1066,1 4354,6 5657,4 8003,0 6171,7 6308,3 7021,3 9477,2 9477,2 J6.1 188,5 388,0 721,5 974,5 1227,5 1435,0 1725,0 4354,6 5713,3 8143,2 6292,6 6449,4 7182,6 9846,1 9846,1 J6.2 188,5 388,0 721,5 974,5 1227,5 1435,0 1725,0 4354,6 5713,3 8143,2 6292,6 6449,4 7182,6 9846,1 9846,1 J6.3 188,5 388,0 721,5 974,5 1227,5 1435,0 1725,0 4354,6 5713,3 8143,2 6292,6 6449,4 7182,6 9846,1 9846,1

## ISSN 1978-1431 print / ISSN 2527-4112 online
J6.4 188,5 388,0 721,5 974,5 1227,5 1435,0 1725,0 4354,6 5713,3 8143,2 6292,6 6449,4 7182,6 9846,1 9846,1 J6.5 188,5 388,0 721,5 974,5 1227,5 1435,0 1725,0 4354,6 5713,3 8143,2 6292,6 6449,4 7182,6 9846,1 9846,1 J6.6 188,5 388,0 721,5 974,5 1227,5 1435,0 1725,0 4354,6 5713,3 8143,2 6292,6 6449,4 7182,6 9846,1 9846,1 J6.7 188,5 388,0 721,5 974,5 1227,5 1435,0 1725,0 4354,6 5713,3 8143,2 6292,6 6449,4 7182,6 9846,1 9846,1 J6.8 90,5 161,3 274,7 360,7 446,7 517,3 615,9 4354,6 5618,3 7916,5 5845,8 5835,6 6401,9 8928,4 8928,4
*J1.8 Job yang terpilih pada iterasi 2
Pada tabel 4 dapat diketahui job yang terpilih adalah job 1.8 maka job 1.8 akan dikerjakan setelah job 2.8, perhitungan dilakukan terus sampai pada iterasi ke 44.
Tabel 4 Hasil Rekapan Partial Sequence Sampaim Iterasi ke-44

## 4. Simpulan
Urutan pengerjaan yang dihasilkan  dengan metode Branch and Bound adalah Job 2.8, Job 1.8, Job 2.1, Job 2.2, Job 2.3, Job 6.8, Job 3.7, Job 2.4, Job 2.5, Job 1.1, Job 1.2, Job 1.3, Job 1.4, Job 4.1, Job 5.7, Job 2.6, Job 2.7, Job 1.5, Job 1.6, Job 1.7, Job 3.1, Job 3.2, Job 4.2, Job 3.3, Job 3.4, Job 4.3, Job 3.5, Job 3.6, Job 4.4, Job 4.5, Job 4.6, Job 4.7, Job 5.1, Job 5.2, Job 5.3, Job 5.4, Job 5.5, Job 5.6, Job 6.1, Job 6.2, Job 6.3, Job 6.4, Job 6.5,  Job 6.6,  Job  6.7,  dan  Job 4.8. Hasil  perhitungan  dengan  metode usulan  dapat dibandingkan  dengan  metode  perusahaan.  Penjadwalan  dengan  metode  perusahaan memiliki nilai makespan sebesar 10584,385 menit, sedangkan jika menggunakan metode Branch and Bound memiliki nilai makespan sebesar 9794,719 menit. Metode Branch and Bound lebih  baik  jika  dibanding  dengan  metode  perusahaan,  dengan  selisih  waktu sebesar 789,66 menit atau 1,8 hari lebih cepat dari pada metode perusahaan. Atau dengan kata lain 7,46 % lebih cepat dibanding metode perusahaan. Oleh karena itu, metode yang diusulkan  untuk  perusahaan  guna  meminimalkan  waktu makespan- nya  yaitu  dengan menggunakan metode Branch and Bound.
Iterasi
Job
q1 q2 q3 q4 q5 q6 q7 b1 b2 b3 b4 b5 b6 b7 B Job Terpilih J1.1 52,35 128,1 128,1 128,1 128,1 333,6 613,6 4317,68 5577,29 7883,32 5699,16 5603,02 6192,3 8901,3 8901,3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . J2.8 40,014 93,474 93,474 93,474 93,474 202,554 359,154 4354,6 5618,28 7848,69 5664,53 5568,39 6157,67 8770,25 8770,3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . J6.8 50,49 118,32 231,71 317,73 403,75 474,3 572,9 4317,68 5575,43 7873,54 5802,77 5792,65 6467,95 9042 9042 J2.8 J1.1 92,364 169,224 169,224 169,224 169,224 374,724 654,724 4354,6 5618,28 7828,3 5644,14 5644,14 6124,34 8785,82 8785,8 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . J1.8 90,27 166,194 166,194 166,194 166,194 363,474 632,274 4354,6 5618,28 7921,41 5737,25 5641,11 6121,31 8774,57 8774,6 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . J6.8 90,504 161,304 274,694 360,714 446,734 517,284 615,884 4354,6 5618,28 7916,52 5845,75 5835,63 6401,85 8928,38 8928,4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . J2.8-J1.8-J2.1-J2.2-J2.3-J6.8-J3.7-J2.4-
J2.5-J1.1-J1.2-J1.3-J1.4-J4.1-J5.7-J2.6-
J2.7-J1.5-J1.6-J1.7-J3.1-J3.2-J4.2-J3.3- J3.4-J4.3-J3.5-J3.6-J4.4-J4.5-J4.6-J4.7- J5.1-J5.2-J5.3-J5.4-J5.5-J5.6-J6.1-J6.2- J6.3-J6.4-J6.5-J6.6-J6.7-J4.8 9020,55 5607,39
J1.8 9504,72 9297,22 9044,22 8791,22 J6.8 9794,7 9794,72 9600,86 9393,36 9267,09 1 2 J2.8 44 3965,38 5260,22
4321,44 9794,72

## Referensi
[1] V.  A.  Sari,  D.  D.  Damayanti,  and  W.  Juliani,  "Penjadwalan  Produksi  Dengan Mempertimbangkan  Ukuran  Lot  Transfer  Batch  Untuk  Minimasi  Makespan Komponen  Isolating  Cock  Di  Pt  Pindad," Jurnal  Rekayasa  Sistem  &  Industri (JRSI), vol. 2, pp. 74-81, 2015.
[2] M. Haming and M. Nurnajamuddin, Manajemen Produksi Modern . Jakarta: Bumi Aksara, 2007.
[3] K. R. Baker and D. Trietsch, Principles of sequencing and scheduling : John Wiley & Sons, 2013.
[4] I. Masudin, D. M. Utama, and F. Susastro, "Penjadwalan Flowshop Menggunakan Algoritma Nawaz Enscore HaM," Jurnal Ilmiah Teknik Industri, vol. 13, pp. 54- 59, 2014.
[5] M.  Firdaus,  I.  Masudin,  and  D.  M.  Utama,  "Penjadwalan  Flowshop  Dengan Menggunakan Simulated Annealing," Spektrum Industri, vol. 13, 2015.
[6] Ł. Kruk, J. Lehoczky, and S. Shreve, "Second order approximation for the customer time  in  queue  distribution  under  the  FIFO  service  discipline," Annales Universitatis  Mariae  Curie-Sklodowska,  sectio  AI – Informatica, vol.  1,  pp.  1-12, 2015.
[7] M. Husen, I. Masudin, and D. M. Utama, "Penjadwalan Job Shop Statik Dengan Metode  Simulated  Annealing  Untuk  Meminimasi  Waktu  Makespan," Spektrum Industri, vol. 13, 2015.
[8] Yusrofi,  A.  K.  Garside,  and  D.  Marsetiya  U,  "Penjadwalan Job  Shop dengan Menggunakan Algoritma Penjadwalan Non Delay untuk Meminimasi Makespan Studi  Kasus  di  Mebel  Rieki,"  Teknik  Industri,  Universitas  Muhammadiyah Malang, Malang, 2015.
[9] S. Harto, A. K. Garside, and D. M. Utama, "penjadwalan produksi menggunakan algoritma  jadwal  non  delay  untuk  meminimalkan  makespan  studi  kasus  di  cv. Bima mebel," Spektrum Industri, vol. 14, 2016.
[10] S.  Altmeyer,  S.  M.  Sundharam,  and  N.  Navet,  "The  case  for  FIFO  real-time scheduling," University of Luxembourg2016.
[11] R. Ginting, Penjadwalan Mesin . Medan: Graha Ilmu, 2009.
[12] K. R. Baker, Introduction to sequencing and scheduling : John Wiley & Sons, 1974.