Penelitian ini bertujuan untuk mendapatkan urutan dan pembebanan job pada masing-masing mesin yang digunakan sehingga didapatkan makespan yang paling minimum dengan menggunakan metode branch and bound yang dilakukan pada produk Kapal Navigasi DM.30/MI/08/015 di PT PINDAD (Persero). Data yang digunakan pada penelitian ini adalah jumlah job yang akan diproses, jumlah dan jenis mesin yang digunakan, aliran proses masing-masing job, data waktu proses job dan data waktu setup job masing-masing mesin.
Pencapaian tujuan diawali dengan membuat algoritma branch and bound. Data digunakan untuk menghasilkan alternatif sehingga didapatkan lower bound pada masing-masing alternatif dan dipilih alternatif yang memiliki lower bound terkecil untuk dijadwalkan. Perhitungan dilakukan secara berulang hingga semua job telah terjadwalkan.
Hasil dari metode branch and bound adalah urutan pengerjaan dan pembebanan job pada masing-masing mesin yang disesuaikan dengan kriteria yang ingin dicapai yaitu minimasi makespan. Berdasarkan perulangan perhitungan pada alternatif yang dipilih menghasilkan makespan sebesar 92,5 jam, sedangkan makespan pada penjadwalan kondisi awal sebesar 96 jam. Angka ini menunjukkan bahwa penjadwalan menggunakan metode branch and bound dapat meminimasi makespan sebesar 3,64%.
penjadwalan, makespan, branch and bound, lower bound