Bandara Halim Perdanakusuma adalah salah satu bandar udara yang terletak di DKI Jakarta. Permasalahan yang sering muncul yaitu banyaknya aktivitas dan semakin meningkat setiap hari, menyebabkan arus kedatangan kendaraan menjadi naik dan khususnya pada saat kendaraan keluar keluar bandara untuk pembayaran parkir yang menyebabkan jumlah antrian menjadi menaik yang menyebabkan dampak secara tidak langsung seperti menghabiskan banyak waktu dan juga kenyamanan. Berdasarkan masalah tersebut, dilakukan analisis terhadap kinerja antrian yang diterapkan di perusahaan ini, guna mengatasi masalah yang ada saat ini. Pada penelitian menggunakan metode Antrian Multi Channel Single Phase(M/M/s) atau model antrian jalur berganda dan pengujian distribusi data menggunakan software Input Analyzer. Pengumpulan data yang dilakukan dengan observasi berupa waktu antar kedatangan, waktu pelayanan dan data sekunder yaitu database perusahaan yaitu data tingkat kedatangan kendaraan. Berdasarkan hasil data observasi dan data sekunder pada pengelola pelayanan di Bandara Halim Perdanakusuma yang dikelola oleh PT Securindo Packatama Indonesia mempunyai 4 loket tahap pelayanan pembayaran parkir di gerbang utama dengan rata-rata tingkat kedatangan 833 kendaraan per jam dan rata-rata waktu pelayanan 209 kendaran per jam pada jam-jam sibuk. Dalam proses pelayanan, menggunakan sistem antrian FIFO (First In First Out). Hasil analisis data yang telah diolah diketahui pada kondisi awal dengan tingkat 99 %. Setelah dilakukan perhitungan parameter antrian dengan cara penambahan 2 server didapatkan hasil 66 %. Analisis kinerja antrian ini menunjukkan bahwa antrian kendaraan akan optimal jika tingkat utilitas menurun maka antrian dapat berkurang. Oleh sebab itu tingkat utilitas harus diperkecil melalui penambahan server atau kemampuan individual setiap server.Kata Kunci: Teori Antrian, Utilitas