P T. Kaloka Binangun adalah perusahaan yang bergerak dalam industri manufaktur. Perusahan ini memproduksi barang berupa kardus packaging, yang dikenal dengan paper palette. Produk paper palette yang diproduksi memiliki varian yang beragam sesuai dengan jenis dan spesifikasi pesanan dari para pelanggan. Dalam hal ini perusahaan dituntut untuk dapat memproduksi seluruh paper palette tanpa keterlambatan penyelesaian pengerjaan. Namun di lain sisi perusahaan mengalami kendala terhadap lamanya waktu penyelesaian pengerjaan seluruh job (makespan) dan waktu total keterlambatan yang ada (total tardiness) selama penjadwalan produksi. Ini disebabkan karena belum adanya teknik penjadwalan tetap atau tertentu oleh perusahaan. Lamanya waktu penyelesaian pengerjaan job juga disebabkan oleh adanya dependent setup time antar job untuk setiap stage permesinan. Untuk meminimasi waktu makespan dan total tardiness maka digunakan metode Random Sampling, Genetic Algorithm dan BOGAW yang dapat menghasilkan urutan penjadwalan pengerjaan job dengan waktu makespan dan total tardiness minimum. Melalui penggunaan metode Random Sampling diperoleh urutan job 3-8-1-2-4-5-9-10-6-7 menghasilkan makespan 6.649 menit dan dan total tardiness 142.011 menit. Melalui penggunaan metode Genetic Algorithm diperoleh urutan job 3-5-2-1-9-8-6-7-10-4 menghasilkan makespan 6.615 menit dan total tardiness 116.209 menit. Penggunaan metode BOGAW diterapkan dengan mengkombinasikan urutan — urutan penjadwalan produksi yang memiliki nilai makespan dan total tardiness hingga didapatkan urutan penjadwalan produksi terbaik. Hasil penelitian menunjukkan urutan penjadwalan terbaik didapat dengan menggunakan urutan job 8-5-6-2-7-4-9-1-10-3 yang memiliki nilai tnakespan sebesar 6.775 menit dan total tardiness sebesar 107.343 menit. Urutan job tersebut juga dapat meminimasi makespan sebesar 1,26% dan total tardiness sebesar 4,56% jika dibandingkan dengan kondisi perusahaan scat ini untuk pengerjaan job.