PT. Makmur Grafika merupakan sebuah perusahaan yang memproduksi buku dan Al-Quran yang berlokasi di Lingkungan Industri Kecil, Semarang. Dalam melakukan proses produksi menggunakan penjadwalan yang berdasarkan order yang masuk pada setiap produk yang akan diproduksi sehingga seringkali perusahaan dalam menyelesaikan job melampaui target waktu yang ada. Berdasarkan data pada bulan Mei 2018 terdapat 3job yang mengalami keterlambatan. Penelitian ini bertujuan memberikan solusi perbaikan penjadwalan produksi agar dapat meminimalkan makespan. Dalam penelitian ini, untuk menyelesaikan masalah penjadwalan maka digunakan metode branch and bound. Metode Branch and Bound adalah suatu alat pencaian solusi optimal pada permasalahan optimasi seperti penjadwalan dengan mencari batas bawah dari tiap-tiap job yang dikerjakan. Berdasarkan pengolahan data, hasil penjadwalan produksi menggunakan metode yang diterapkan perusahaan mendapat hasil nilai makespan sebesar 278.401 menit dengan urutan job 1-2-3-4-5-6-7-8-9, sedangkan dengan perhitungan metode Branch and Bound mendapatkan nilai makespan sebesar 266.627 menit dengan urutan job 3-7-8-9-1-6-5-2-4. Penjadwalan produksi dengan metode Branch and Bound dapat meminimalkan makespan sebesar 11.774 menit atau sebesar 4,35%. Sehingga dengan menggunakan metode branch and bound dapat menjadi solusi penyelesaian masalah penjadwalan untuk meminimasi makespan.

Kata kunci : branch and bound, makespan, penjadwalan produksi