Sistem antrean adalah suatu sistem yang menyatakan kondisi pada sekelompok orang atau barang yang berkumpul dalam barisan, menunggu untuk mendapatkan produk ataupun jasa dalam hal pelayanan. Sistem antrean sering ditemukan pada suatu fasilitas pelayanan publik, di antaranya pada sistem pelayanan pembayaran pajak kendaraan bermotor. Pelayanan yang dibutuhkan masyarakat adalah pelayanan yang cepat dan efisien. Penelitian ini bertujuan untuk memperoleh lama waktu maksimum yang dibutuhkan sistem dalam melayani wajib pajak dengan memodelkan sistem antrean pelayanan pembayaran pajak kendaraan bermotor menggunakan model Petri Net dan Aljabar Max-Plus. Model Petri Net digunakan untuk membentuk coverability tree yang kemudian dikonstruksi ke dalam model Aljabar Max-Plus. Model Aljabar Max-Plus merupakan suatu model matematika yang efektif untuk menganalisis sistem dinamis, khususnya dalam konteks waktu dan nilai maksimum suatu variabel sebagai solusi optimal waktu pelayanan dalam
sistem antrean pembayaran pajak kendaraan bermotor. Data penelitian diperoleh melalui observasi secara langsung di Samsat MT Haryono Samarinda. Selanjutnya, dilakukan simulasi model dengan menggunakan data waktu kedatangan wajib pajak ke-k. Hasil yang diperoleh pada penelitian ini adalah lamanya waktu maksimum pelayanan wajib pajak tahunan yaitu selama 26 menit 54 detik setelah waktu kedatangan, sedangkan lamanya waktu maksimum pelayanan wajib pajak 5 tahunan yaitu selama 27 menit 42 detik setelah waktu kedatangan.