This paper proposes a flexible uplink scheduling algorithm that can perfectly support Variable Multi-Rate Wide-Band (VMR-WB) VoIP services with multi-mode codec, solving the problems of uplink resources wastes, additional access delay and overwhelmingly large overhead. In our proposed algorithm, the BS adapts uplink resources assignment according to the reserved bit in the generic MAC header of IEEE802.16e, which is utilized to indicate the mode transition of each SS. Hence an efficient scheme is proposed to implement the uplink resource request and allocation procedure. The performance analysis of the conventional algorithms (UGS, rtPS and ertPS) as well as the one proposed in this paper is also provided. Through the numerical validations, proposed algorithm performs efficiently than the conventional algorithms over enhancement of resource utilization, total throughput, and reduction of packet transmission delay. Also, it is proved that our algorithm can support more voice users than the conventional algorithms.