This letter proposes an efficient uplink scheduling algorithm for the voice over Internet protocol (VoIP) service with variable frame-duration according to the voice activity in IEEE 802.16e/m systems. The proposed algorithm dynamically changes the grant-interval to save the uplink bandwidth, and it uses the random access scheme when the voice activity changes from silent-period to talk-spurt. Numerical results show that the proposed algorithm can increase the VoIP capacity by 26 percent compared to the conventional extended real-time polling service (ertPS).