Efisiensi waktu produksi berperan penting dalam industri makanan, termasuk di pabrik tempe Asli HB Samarinda. Proses pembuatan tempe melibatkan beberapa tahap yang cukup lama, seperti persiapan bahan baku, fermentasi, dan pengasaman. Untuk mengoptimasi jadwal produksi sehingga waktu produksi dapat digunakan secara efektif dan efisien dapat menggunakan aljabar Max-Plus. Penelitian ini bertujuan untuk memodelkan sistem produksi tempe dengan menggunakan petri net dan menyelesaikan masalah waktu produksi tempe dengan mengoptimalkan waktu produksi menggunakan aljabar Max-Plus. Data penelitian diperoleh melalui hasil wawancara dengan kepala cabang pabrik tempe Asli HB Samarinda. Penggunaan petri net untuk membentuk coverability tree yang selanjutnya dikonstruksi ke dalam model aljabar Max-Plus. Kemudian dilakukan simulasi model menggunakan data waktu produksi dimulai pada periode ke-t. Hasil yang diperoleh pada penelitian ini menunjukkan bahwa waktu optimal atau waktu minimum untuk produksi tempe adalah 3 hari 6 jam 57 menit setelah waktu produksi dimulai.