Abstrak PR. Adi Bungsu (PR. AB) adalah perusahaan rokok yang memproduksi rokok Filter 16 yang telah tersebar di beberapa daerah di Indonesia. Pentingnya kepuasan konsumen bagi perusahaan mengharuskan PR. AB menyelesaikan order konsumen tepat waktu. Selama ini, PR. Adi Bungsu menerapkan aturan jadwal produksi First Come First Served (FCFS), dimana PR. AB beberapa kali mengalami keterlambatan penyelesaian order Filter 16 hingga melewati batas due date seperti yang terjadi pada bulan April hingga Juni 2014.. Oleh karena itu, perlu dilakukan penjadwalan produksi dengan pendekatan yang berbeda untuk menyelesaikan masalah keterlambatan penyelesain order. Dalam penelitian ini, metode pendekatan yang digunakan dalam penjadwalan produksi rokok adalah algoritma Simulated Annealing (SA) yang menggunakan hasil penjadwalan aturan Earliest Due Date (EDD) sebagai jadwal inisiasi dalam meminimasi nilai Max. Tardiness. Berdasarkan hasil perhitungan yang dilakukan dapat diketahui efisiensi hasil jadwal algoritma SA terhadap jadwal aktual pada bulan April sebesar 79%, pada bulan Mei sebesar 52% dan pada bulan Juni sebesar 100%. Hal tersebut menunjukkan bahwa jadwal yang dihasilkan dari algoritma SA lebih baik dari jadwal aktual PR. AB yang menggunakan aturan FCFS dalam fungsinya untuk meminimalkan Max. Tardiness. Kata kunci: penjadwalan produksi, minimasi max. tardiness, algoritma simulated annealing