A new algorithm is proposed for wireless voice over IP(VoIP) codecs that allocates radio resources in consideration of the variations in packet size and packet-generation period. This algorithm allows resources to be utilized more efficiently in Mobile-WiMAX systems. The outstanding performance of our proposed algorithm with respect to average throughput and average packet dropping probability is demonstrated through intensive numerical analysis and simulations. VoIP capacity is compared with respect to the application of different VoIP codecs (G.729B, adaptive multirate (AMR)) and VoIP header compression schemes (payload header suppression (PHS) and robust header compression (ROHC)).